Corrected exercises: homogeneous systems, linear combinations and the rank theorem (MATH 133)

The theorem needs exactly one thing: the number of unknowns $n$ strictly larger than the number of equations $m$. $A_1$ is $2 \times 4$, so $n = 4 > 2 = m$ and a nontrivial solution is GUARANTEED before any row operation. $A_2$ and $A_4$ are $3 \times 3$, and $A_3$ is $4 \times 3$: for all three the hypothesis fails, and the correct answer is not no, it is the theorem is silent. A student who writes that $A_3$ has only the trivial solution because it has more equations than unknowns has turned a one-way statement into a two-way one, and part c) shows what that costs.

$R_2 \to R_2 - 2R_1$ gives $(0, 3, -4, -7)$, so the system reads $x_1 - x_2 + 2x_3 + 3x_4 = 0$ and $3x_2 - 4x_3 - 7x_4 = 0$. Two pivots, in columns $1$ and $2$, so $x_3$ and $x_4$ are free. Choosing $x_3 = 3$ and $x_4 = 0$ avoids fractions: $x_2 = 4$, then $x_1 = x_2 - 2x_3 = 4 - 6 = -2$. The solution $(-2, 4, 3, 0)$ checks in both rows: $-2 - 4 + 6 + 0 = 0$ and $-4 + 4 + 0 - 0 = 0$. The choice $x_3 = 0$, $x_4 = 3$ gives another one, $(-2, 7, 0, 3)$, and there are infinitely many.

For $A_2$: $R_2 \to R_2 - 2R_1$ and $R_3 \to R_3 - 3R_1$ give two copies of $(0, 1, 3)$, then $R_3 \to R_3 - R_2$ kills the third row and $R_1 \to R_1 - 2R_2$ gives $(1, 0, -7)$. Rank $2$, $x_3 = t$ free, $x = t(7, -3, 1)$: a SQUARE system with nontrivial solutions. For $A_3$: $R_2 - 2R_1$, $R_3 - R_1$ and $R_4 - 3R_1$ all give $(0, 3, -3)$, so after $R_2 \to \frac{1}{3}R_2$ and clearing, only two pivots survive: $x = t(-1, 1, 1)$. Four equations, and still a whole line of solutions. For $A_4$: $R_3 \to R_3 - R_1$ gives $(0, -1, 1)$, then $R_3 \to R_3 + R_2$ gives $(0, 0, 2)$: three pivots for three unknowns, no free variable, only $x = 0$.

In P the three lines are distinct and meet only at the origin: the only common point is the trivial solution, and the rank is $2$ (the first two rows already give two pivots). In Q the three equations are multiples of $x - 2y = 0$, so they draw the SAME line three times; every point of it, such as $(2, 1)$, solves all three. The rank is $1$ and one variable is free. The figure is the whole lesson: adding equations can only remove solutions if the new equations carry new information, that is if they add a pivot.

Theorem (Nicholson, Section 1.3): if a homogeneous system has more variables than equations, it has a nontrivial solution. Converse: if a homogeneous system has a nontrivial solution, then it has more variables than equations. The converse is FALSE, and this exercise gives two counterexamples: $A_2$ has $3$ equations and $3$ unknowns, $A_3$ has $4$ equations and $3$ unknowns, and both have nontrivial solutions. What decides in every case is the rank: a nontrivial solution exists exactly when the rank is smaller than the number of unknowns, so that at least one column has no pivot.

$R_2 \to R_2 - 2R_1$ gives $(0, 0, 1, 2, -1)$ and $R_3 \to R_3 + R_1$ gives $(0, 0, 2, 4, -2)$. Then $R_3 \to R_3 - 2R_2$ turns the third row into zeros. Finally $R_1 \to R_1 - R_2$ clears the entry above the second pivot: $(1, -2, 0, -2, 3)$. The reduced form is $\begin{pmatrix} 1 & -2 & 0 & -2 & 3 \\ 0 & 0 & 1 & 2 & -1 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}$. No right-hand column is written, and none is needed: for a homogeneous system it stays zero through every operation.

Two pivots, in columns $1$ and $3$: the rank is $2$, the leading variables are $x_1$ and $x_3$, and the free ones are $x_2 = s$, $x_4 = t$, $x_5 = u$. The two rows read $x_1 = 2s + 2t - 3u$ and $x_3 = -2t + u$. Setting one parameter to $1$ and the others to $0$ in turn gives the three basic solutions $X_1 = (2, 1, 0, 0, 0)$, $X_2 = (2, 0, -2, 1, 0)$ and $X_3 = (-3, 0, 1, 0, 1)$, and the general solution is $x = sX_1 + tX_2 + uX_3$. Check one before moving on: $A X_2$ gives $2 - 0 - 2 + 0 + 0 = 0$, $4 - 0 - 6 + 2 + 0 = 0$ and $-2 + 0 - 2 + 4 + 0 = 0$.

The count is $n - r$, the number of columns without a pivot, and has nothing to do with the number of equations. Here $5 - 2 = 3$. The trap is to compute $5 - 3 = 2$ with the three equations. The reduction itself shows why that is wrong: it proved $R_3 + R_1 = 2(R_2 - 2R_1)$, that is $R_3 = 2R_2 - 5R_1$, and indeed $2(2, -4, 3, 2, 3) - 5(1, -2, 1, 0, 2) = (-1, 2, 1, 4, -4)$. The third equation is a consequence of the first two, so it contributed a zero row, not a pivot. An equation that adds no pivot removes no parameter, and a marker who sees $5 - 3$ on the page knows the student counted rows.

Both are solutions: $(4, 1, -2, 1, 0) = X_1 + X_2$ and $(-6, 0, 2, 0, 2) = 2X_3$, and any linear combination of solutions of $Ax = 0$ is again a solution. But they are not on the same footing. A nonzero multiple of a basic solution is still accepted as a basic solution, and Nicholson does exactly this to clear fractions, so $2X_3$ is fine. The sum $X_1 + X_2$ is not a basic solution: it has two parameters switched on at once, and a list that contains it together with $X_1$ or $X_2$ would no longer describe each parameter once. What never changes, whatever scaling is used, is the NUMBER of basic solutions: three.

Impose $x_1 = 2s + 2t - 3u = 0$ and $x_3 = -2t + u = 0$. The second gives $u = 2t$, then the first gives $2s + 2t - 6t = 0$, so $s = 2t$. With $t = 1$: $s = 2$, $u = 2$, and $x = 2X_1 + X_2 + 2X_3 = (0, 2, 0, 1, 2)$. It checks in all three rows: $0 - 4 + 0 + 0 + 4 = 0$, $0 - 8 + 0 + 2 + 6 = 0$ and $0 + 4 + 0 + 4 - 8 = 0$. Writing the general solution as a combination first is what made this a two-line computation.

Count the blue pivots: two, in columns $1$ and $3$. The rank is $2$, so the solutions involve $5 - 2 = 3$ parameters, $x_2$, $x_4$ and $x_5$, and the system has $3$ basic solutions. The subtraction $5 - 3$ uses the number of EQUATIONS, and it silently assumes that every equation contributed a pivot. The third row of the figure is entirely zero: that equation was a consequence of the other two, it produced no pivot, and it removed no parameter. The rank theorem subtracts pivots, and the number of pivots can be anything from $0$ up to the smaller of $m$ and $n$.

Two pivots again, in columns $1$ and $2$, so the rank is $2$ and the solutions involve $3 - 2 = 1$ parameter, $x_3$: a whole line of solutions, although there are more equations than unknowns. The three zero rows are three equations that, after elimination, read $0 = 0$ (they must, since the system is consistent: a nonzero number on the right would have made it inconsistent). They were combinations of the first two and added nothing. A tall system is not overdetermined because of its shape; it is overdetermined only if its rows carry more information than its columns can absorb.

$R_2 \to R_2 - 2R_1$, $R_3 \to R_3 - 3R_1$ and $R_4 \to R_4 - R_1$ give three copies of $(0, 0, 1, 3)$. Then $R_3 \to R_3 - R_2$ and $R_4 \to R_4 - R_2$ leave two zero rows. The reduced form has rows $(1, 2, 0, -1)$ and $(0, 0, 1, 3)$: rank $2$. A SQUARE $4 \times 4$ matrix, and yet $4 - 2 = 2$ parameters. With $x_2 = s$ and $x_4 = t$: $x_1 = -2s + t$ and $x_3 = -3t$. The basic solutions are $(-2, 1, 0, 0)$ and $(1, 0, -3, 1)$. Check the second in the last row of $B$: $1 + 0 - 3 + 2 = 0$. Square does not mean one solution; only rank equal to $n$ does.

(i) NO. The rank is at most $3$, the number of rows, so there are at least $5 - 3 = 2$ basic solutions, never one. This is where the count of equations is legitimately used: as a BOUND on the rank, never as its value. (ii) YES, provided the rank is $1$: for instance six equations that are all multiples of $x_1 + x_2 + x_3 + x_4 = 1$. Then $4 - 1 = 3$ parameters. (iii) NO. If such a system is consistent, its rank is at most $2$, so at least $4 - 2 = 2$ parameters: infinitely many solutions. If it is inconsistent, it has none. Exactly one is impossible either way.

$R_2 \to R_2 - R_1$ gives $0x + 0y + 0z = 2$, that is $0 = 2$: the system has NO solution. The two equations describe two parallel planes that never meet. The rank theorem starts with the word consistent, and here that hypothesis fails, so $n - r = 2$ counts nothing. The correct habit is to settle consistency first, by looking for a row of the form $0 = c$ with $c \neq 0$, and only then to count parameters. Two parameters for an empty set is the kind of line that costs the whole question.

$Ax = 1 \cdot \begin{pmatrix} 3 \\ 1 \end{pmatrix} + 2 \cdot \begin{pmatrix} -1 \\ 2 \end{pmatrix} = \begin{pmatrix} 1 \\ 5 \end{pmatrix}$. On the figure the first arrow ends at $(3, 1)$, the first grey copy of $a_2$ takes it to $(2, 3)$, the second to $(1, 5)$, and the orange arrow from the origin lands exactly there. The picture is the definition: the entries of $x$ are not coordinates in the usual sense, they are the numbers of steps taken along each COLUMN.

By the columns: $1 \cdot \begin{pmatrix} 1 \\ 3 \\ 0 \end{pmatrix} - 2 \cdot \begin{pmatrix} 0 \\ -1 \\ 4 \end{pmatrix} + 3 \cdot \begin{pmatrix} 2 \\ 1 \\ -2 \end{pmatrix} = \begin{pmatrix} 7 \\ 8 \\ -14 \end{pmatrix}$. By the rows: $1 + 0 + 6 = 7$, then $3 + 2 + 3 = 8$, then $0 - 8 - 6 = -14$. Same vector, as it must be. The column reading is the one that answers questions (what can $Ax$ reach?); the row reading is the fast way to compute one product. A standard slip in the column version is to multiply the columns by the entries of $x$ in the wrong order: $x_1$ goes with column $1$, whatever the rows look like.

$C$ has $3$ columns, so $x$ must have $3$ entries: only $(1, 0, 2)$ works. $(1, 1)$ has too few entries and $(1, 0, 2, 1)$ too many, and for both the product is simply UNDEFINED, not zero. $C(1, 0, 2) = 1 \cdot \begin{pmatrix} 1 \\ 0 \end{pmatrix} + 0 \cdot \begin{pmatrix} 2 \\ 3 \end{pmatrix} + 2 \cdot \begin{pmatrix} -1 \\ 4 \end{pmatrix} = \begin{pmatrix} -1 \\ 8 \end{pmatrix}$, a vector with $2$ entries, one per ROW of $C$. The trap is to expect a result of the same size as $x$: a $2 \times 3$ matrix takes vectors with $3$ entries and returns vectors with $2$.

Each unknown multiplies the column of its coefficients: $x_1 \begin{pmatrix} 2 \\ 1 \end{pmatrix} + x_2 \begin{pmatrix} -1 \\ 0 \end{pmatrix} + x_3 \begin{pmatrix} 3 \\ 5 \end{pmatrix} = \begin{pmatrix} 4 \\ -1 \end{pmatrix}$. The missing $x_2$ in the second equation is a $0$ in the second column, and forgetting it shifts every later entry. In matrix form, $A = \begin{pmatrix} 2 & -1 & 3 \\ 1 & 0 & 5 \end{pmatrix}$, $x = (x_1, x_2, x_3)$ and $b = (4, -1)$. The three forms, system, vector equation and $Ax = b$, carry exactly the same information, and solving any of them means row reducing $(A \mid b)$.

The coefficients of the combination are the entries of $x$, one per column, including a $0$ for the column that does not appear: $3a_1 + 0a_2 - a_3 = A(3, 0, -1) = \begin{pmatrix} 1 \\ 8 \\ 2 \end{pmatrix}$. Row check: $3 + 0 - 2 = 1$, $9 + 0 - 1 = 8$, $0 + 0 + 2 = 2$. And $Ae_2 = 0a_1 + 1a_2 + 0a_3 = a_2 = (0, -1, 4)$: multiplying by $e_j$ picks out column $j$. That remark is small and it is used constantly, for instance to show in the next exercise that every column of $A$ is a right-hand side for which $Ax = b$ is consistent.

$a_2 = -2a_1$: both columns lie on the dashed line $y = x/2$, so EVERY combination $x_1a_1 + x_2a_2$ stays on that line. The point $(4, 2)$ is on it, $(4, 3)$ is not. Row reduction confirms. For $(4, 2)$: $R_1 \leftrightarrow R_2$ gives $(1, -2 \mid 2)$ and $(2, -4 \mid 4)$, then $R_2 \to R_2 - 2R_1$ gives $(0, 0 \mid 0)$: consistent, with $x_2$ free, $x_1 = 2 + 2x_2$. So $x = (2, 0)$ works, and so does $x = (0, -1)$, which is $-a_2 = (4, 2)$. For $(4, 3)$ the same operations end with $(0, 0 \mid 4 - 6) = (0, 0 \mid -2)$, the equation $0 = -2$: no solution. Two columns in the plane do not guarantee that the whole plane is reached.