Linear Algebra · Solutions

Systems of Linear Equations

12 questions · about 106 minutes

Work this sheet on paper and show every step: write each row operation you perform in the form $R_{i} \leftarrow R_{i} + c R_{j}$ , say which entry is the pivot, and name every result you use (“by the existence and uniqueness criterion”, “by the rank theorem”, “by the structure theorem for solution sets”). No calculator is needed anywhere — every number is a small integer or a simple fraction, and a check in the original equations is expected wherever a solution is found. Full worked solutions are on a separate page; each question also has its own reveal, so you can check one answer without seeing the rest.

1.Sketch
For each pair of equations below, sketch both lines in the same $x y$ -plane, marking the intercepts you used to draw them. Classify the solution set as a single point, a whole line, or empty, and justify the classification algebraically — the picture alone does not settle it.
1. (a) $2 x - y = 1$ and $x + y = 5$ .
2. (b) $x - 2 y = 4$ and $- 3 x + 6 y = - 12$ .
3. (c) $x - 2 y = 4$ and $2 x - 4 y = 3$ .
4. (d)Using only the geometry of lines in the plane, explain why no system of two linear equations in two unknowns can have exactly two solutions.
Solution
(a) Two lines that cross once. The line $2 x - y = 1$ passes through $(0, - 1)$ and $(\frac{1}{2}, 0)$ and rises steeply (slope $2$ ); the line $x + y = 5$ passes through $(0, 5)$ and $(5, 0)$ and falls (slope $- 1$ ). The slopes differ, so the lines are not parallel and must cross exactly once. To find where, add the two equations: $3 x = 6$ , so $x = 2$ , and then $y = 5 - 2 = 3$ . The solution set is the single point $(2, 3)$ .
Check in both equations: $2 (2) - 3 = 1$ and $2 + 3 = 5$ . The sketch shows a steep rising line and a falling line meeting at $(2, 3)$ , with the four intercepts labelled.
(b) The same line twice. Multiplying $x - 2 y = 4$ through by $- 3$ gives $- 3 x + 6 y = - 12$ , which is exactly the second equation. So the two equations carry identical information and describe one line, through $(4, 0)$ and $(0, - 2)$ with slope $\frac{1}{2}$ . Draw a single line and label it with both equations. The solution set is the whole line: solving for $x$ , it is ${(4 + 2 t, t) : t \in R}$ .
Check at $t = 1$ : the point $(6, 1)$ gives $6 - 2 = 4$ and $- 18 + 6 = - 12$ .
(c) Parallel and distinct. Rewriting, $y = \frac{1}{2} x - 2$ and $y = \frac{1}{2} x - \frac{3}{4}$ : the same slope $\frac{1}{2}$ , different intercepts. The first line crosses the axes at $(4, 0)$ and $(0, - 2)$ ; the second at $(\frac{3}{2}, 0)$ and $(0, - \frac{3}{4})$ , so it lies strictly above the first everywhere. Algebraically: any solution of the first equation satisfies $2 x - 4 y = 8$ , and the second demands $2 x - 4 y = 3$ , so $8 = 3$ , which is false. The solution set is empty. The sketch shows two parallel lines that never meet.
(d) Suppose two lines had two distinct common points $P$ and $Q$ . Through two distinct points there passes exactly one line, so both lines are that line — they coincide, and then every point of the line is common to both, giving infinitely many solutions. So as soon as a pair of lines shares two points it shares all of them. The only possible counts are zero (parallel and distinct), one (crossing) and infinitely many (coincident): exactly the three pictures in (a), (b) and (c).
2.Computation
Consider the system
$3 x + 6 y = 12, 2 x + 5 y = 9.$
1. (a)Write the augmented matrix. Perform $R_{1} \leftarrow \frac{1}{3} R_{1}$ and then $R_{2} \leftarrow R_{2} - 2 R_{1}$ , writing the matrix after each step, and read off the solution. Check it in the original equations.
2. (b)For each of the two operations, write down the row operation that undoes it. Explain why the existence of these inverse operations is what guarantees that the solution you read off is a solution of the original system, and not merely of the reduced one.
3. (c)A student instead performs $R_{2} \leftarrow 0 \cdot R_{2}$ . Write the resulting system, exhibit a pair $(x, y)$ that solves it but does not solve the original, and say which requirement in the definition of the row operations has been violated.
Solution
(a) Reduce and read off. The augmented matrix is
$(3265129) .$
$R_{1} \leftarrow \frac{1}{3} R_{1}$ replaces the first row by $(1, 2 ∣ 4)$ :
$(122549) .$
$R_{2} \leftarrow R_{2} - 2 R_{1}$ replaces the second row by $(2 - 2, 5 - 4 ∣ 9 - 8) = (0, 1 ∣ 1)$ ; the first row is the source and does not change:
$(102141) .$
Row $2$ says $y = 1$ , and row $1$ then gives $x = 4 - 2 y = 2$ . Check in the original system: $3 (2) + 6 (1) = 12$ and $2 (2) + 5 (1) = 9$ . Both hold.
(b) Inverses and why they matter. The inverse of $R_{1} \leftarrow \frac{1}{3} R_{1}$ is $R_{1} \leftarrow 3 R_{1}$ ; the inverse of $R_{2} \leftarrow R_{2} - 2 R_{1}$ is $R_{2} \leftarrow R_{2} + 2 R_{1}$ .
The proof that row operations preserve the solution set has two halves. The direct half shows that any solution of the old system still satisfies the new equations (a scaled equation or a sum of true equations is still true). That half only says the original solutions survive; it does not say the reduced system has no extra solutions. The reverse inclusion comes from applying the same direct argument to the inverse operations, which carry the reduced system back to the original: any solution of the reduced system therefore satisfies the original equations. So $(2, 1)$ , read off the reduced system, is a solution of the original because $R_{1} \leftarrow 3 R_{1}$ and $R_{2} \leftarrow R_{2} + 2 R_{1}$ exist and are themselves row operations.
(c) Multiplying a row by zero. After $R_{2} \leftarrow 0 \cdot R_{2}$ the matrix is $(3060120)$ , the system $3 x + 6 y = 12$ , $0 = 0$ . The second equation has been erased, so the solution set is the whole line $x = 4 - 2 t$ , $y = t$ . The point $(4, 0)$ satisfies $3 (4) + 0 = 12$ , but in the original second equation $2 (4) + 5 (0) = 8 \neq = 9$ .
The violated requirement is that scaling (R2) uses a nonzero scalar. The operation $R_{2} \leftarrow 0 \cdot R_{2}$ has no inverse — nothing recovers $2 x + 5 y = 9$ from $0 = 0$ — so the reverse inclusion in (b) is unavailable, and the new system acquires solutions the original never had.
3.Computation
Consider the system
$x_{1} + x_{2} + x_{3} 2 x_{1} + 3 x_{2} + x_{3} + x_{4} x_{1} + 2 x_{2} + 2 x_{4} = 3 = 11 = 11.$
Write every row operation in the form $R_{i} \leftarrow R_{i} + c R_{j}$ and state the pivot you are working with at each stage.
1. (a)Write the augmented matrix and run the forward phase of Gaussian elimination to reach an echelon form.
2. (b)List the pivot columns, the basic variables and the free variables. Is the system consistent, and how many solutions does it have? Cite the criterion you are using.
3. (c)Run the backward phase to reach the reduced echelon form and write the general solution. Verify it against all three original equations for one nonzero value of the parameter.
Solution
(a) Forward phase. The augmented matrix is
$12113211001231111 .$
Column $1$ : the pivot is the $1$ in position $(1, 1)$ . $R_{2} \leftarrow R_{2} - 2 R_{1}$ gives $(0, 1, - 1, 1 ∣ 5)$ and $R_{3} \leftarrow R_{3} - R_{1}$ gives $(0, 1, - 1, 2 ∣ 8)$ :
$100111 1 - 1 - 1 012358 .$
Column $2$ : the pivot is the $1$ in position $(2, 2)$ . $R_{3} \leftarrow R_{3} - R_{2}$ gives $(0, 0, 0, 1 ∣ 3)$ :
$100110 1 - 1 0 011353 .$
Column $3$ of the remaining submatrix is zero, so the next pivot is the $1$ in position $(3, 4)$ , and there are no rows below it. This is an echelon form: the leading entries move strictly right down the rows.
(b) Reading the staircase. The pivot positions are $(1, 1)$ , $(2, 2)$ and $(3, 4)$ , so the pivot columns are $1$ , $2$ and $4$ . The basic variables are $x_{1}, x_{2}, x_{4}$ and the free variable is $x_{3}$ .
No row has the form $(0000 ∣ c)$ with $c \neq = 0$ , so by the existence and uniqueness criterion the system is consistent; and since there is a free variable, the same criterion says it has infinitely many solutions.
(c) Backward phase and the general solution. Start with the rightmost pivot, in column $4$ ; it is already $1$ . Clear above it with $R_{2} \leftarrow R_{2} - R_{3}$ , giving $(0, 1, - 1, 0 ∣ 2)$ ; row $1$ already has a $0$ in column $4$ . Next the pivot in column $2$ : $R_{1} \leftarrow R_{1} - R_{2}$ gives $(1, 0, 2, 0 ∣ 1)$ . The reduced echelon form is
$100010 2 - 1 0 001123 .$
Set $x_{3} = t$ . The rows say $x_{1} = 1 - 2 t$ , $x_{2} = 2 + t$ and $x_{4} = 3$ , so the general solution is
$(x_{1}, x_{2}, x_{3}, x_{4}) = (1 - 2 t, 2 + t, t, 3), t \in R .$
Check at $t = 1$ , the point $(- 1, 3, 1, 3)$ : $- 1 + 3 + 1 = 3$ ; $- 2 + 9 + 1 + 3 = 11$ ; $- 1 + 6 + 6 = 11$ . All three original equations hold.
4.Computation
Let $A = (1223)$ . Reducing $A$ to $I_{2}$ takes three operations, in this order: $R_{2} \leftarrow R_{2} - 2 R_{1}$ , then $R_{2} \leftarrow - R_{2}$ , then $R_{1} \leftarrow R_{1} - 2 R_{2}$ .
1. (a)Write the elementary matrices $E_{1}, E_{2}, E_{3}$ of the three operations, and for each write its inverse as a matrix together with the row operation that inverse represents.
2. (b)Compute $M = E_{3} E_{2} E_{1}$ and verify by multiplication that $M A = I_{2}$ . What is $M$ in terms of $A$ ?
3. (c)Write $A$ itself as a product of elementary matrices and check the product. Then compute $E_{1} E_{2} E_{3}$ and explain why it is not equal to $M$ .
Solution
(a) The three elementary matrices. Apply each operation to $I_{2}$ .
$R_{2} \leftarrow R_{2} - 2 R_{1}$ gives $E_{1} = (1 - 2 01)$ ; its inverse operation is $R_{2} \leftarrow R_{2} + 2 R_{1}$ , so $E_{1}^{- 1} = (1201)$ .
$R_{2} \leftarrow - R_{2}$ gives $E_{2} = (10 0 - 1)$ ; the inverse of scaling by $- 1$ is scaling by $\frac{1}{- 1} = - 1$ , the same operation, so $E_{2}^{- 1} = E_{2}$ .
$R_{1} \leftarrow R_{1} - 2 R_{2}$ gives $E_{3} = (10 - 2 1)$ ; its inverse operation is $R_{1} \leftarrow R_{1} + 2 R_{2}$ , so $E_{3}^{- 1} = (1021)$ .
(b) The product of the operations. Multiply right to left, since $E_{1}$ acts first:
$E_{2} E_{1} = (10 0 - 1) (1 - 2 01) = (12 0 - 1), M = E_{3} (E_{2} E_{1}) = (10 - 2 1) (12 0 - 1) = (- 3 2 2 - 1) .$
Verification:
$M A = (- 3 2 2 - 1) (1223) = (- 3 + 4 2 - 2 - 6 + 6 4 - 3) = (1001) .$
Since $A$ is square and $M A = I$ , $M = A^{- 1}$ . Sanity check with the $2 \times 2$ inverse formula: $det A = 3 - 4 = - 1$ , so $A^{- 1} = \frac{1}{- 1} (3 - 2 - 2 1) = (- 3 2 2 - 1)$ , which is $M$ .
(c) $A$ as a product, and the wrong order. From $M A = I$ we get $A = M^{- 1} = (E_{3} E_{2} E_{1})^{- 1} = E_{1}^{- 1} E_{2}^{- 1} E_{3}^{- 1}$ , using the rule that the inverse of a product reverses the order. So
$A = (1201) (10 0 - 1) (1021) .$
Check: the first two factors multiply to $(12 0 - 1)$ , and then $(12 0 - 1) (1021) = (12 2 4 - 1) = (1223) = A$ .
Now the other order: $E_{2} E_{3} = (10 0 - 1) (10 - 2 1) = (10 - 2 - 1)$ , and
$E_{1} E_{2} E_{3} = (1 - 2 01) (10 - 2 - 1) = (1 - 2 - 2 3) \neq = M .$
Matrix multiplication is not commutative, and the product records the operations in the reverse of the order they were performed: the last operation acts on the result of the earlier ones, so it sits furthest left. $E_{1} E_{2} E_{3}$ is the matrix of a different procedure — $R_{1} \leftarrow R_{1} - 2 R_{2}$ first, then $R_{2} \leftarrow - R_{2}$ , then $R_{2} \leftarrow R_{2} - 2 R_{1}$ — and indeed $(E_{1} E_{2} E_{3}) A = (1 - 4 - 2 + 6 2 - 6 - 4 + 9) = (- 3 4 - 4 5)$ , nowhere near $I_{2}$ .
5.Computation
Let $v_{1} = (1, - 1, 2)$ and $v_{2} = (3, 1, 4)$ in $R^{3}$ , and let $A$ be the $3 \times 2$ matrix whose columns are $v_{1}$ and $v_{2}$ .
1. (a)Decide whether $b = (4, 0, 6)$ and $c = (4, 0, 5)$ lie in $Span {v_{1}, v_{2}}$ . Where a vector is in the span, give the weights; where it is not, show why no weights can exist.
2. (b)Row-reduce $A$ augmented with a general right-hand side $(b_{1}, b_{2}, b_{3})$ to find a single linear equation in $b_{1}, b_{2}, b_{3}$ that describes the span. Verify it on $b$ and on $c$ , and say what geometric object the span is.
3. (c)State the question about $c$ in (a) in each of its three equivalent forms — as a system of scalar equations, as a vector equation, and as a matrix equation — and name the theorem that makes the three forms equivalent.
Solution
(a) Solve for weights. $b$ is in the span exactly when $x_{1} v_{1} + x_{2} v_{2} = b$ has a solution, that is, when
$x_{1} + 3 x_{2} = 4, - x_{1} + x_{2} = 0, 2 x_{1} + 4 x_{2} = 6.$
The second equation forces $x_{1} = x_{2}$ ; the first then gives $4 x_{2} = 4$ , so $x_{2} = 1$ and $x_{1} = 1$ . The third must be checked, not assumed: $2 (1) + 4 (1) = 6$ , which holds. So $b = v_{1} + v_{2}$ and $b$ is in the span.
For $c = (4, 0, 5)$ the first two coordinates are the same, so any weights would again have to be $x_{1} = x_{2} = 1$ , and then the third coordinate reads $2 + 4 = 6 \neq = 5$ . No weights exist and $c$ is not in the span.
(b) The span as one equation. Reduce with a symbolic right-hand side:
$1 - 1 2 314 b_{1} b_{2} b_{3} R_{2} \leftarrow R_{2} + R_{1}, R_{3} \leftarrow R_{3} - 2 R_{1} 100 34 - 2 b_{1} b_{1} + b_{2} b_{3} - 2 b_{1} .$
The pivot in column $2$ is the $4$ . $R_{3} \leftarrow R_{3} + \frac{1}{2} R_{2}$ makes the last row $(0, 0 ∣ b_{3} - 2 b_{1} + \frac{1}{2} (b_{1} + b_{2}))$ . The system is consistent exactly when that entry is $0$ ; multiplying by $2$ ,
$- 3 b_{1} + b_{2} + 2 b_{3} = 0.$
Check: $b = (4, 0, 6)$ gives $- 12 + 0 + 12 = 0$ , in the span; $c = (4, 0, 5)$ gives $- 12 + 0 + 10 = - 2 \neq = 0$ , not in the span — matching (a). The two spanning vectors are not multiples of one another ( $3/1 \neq = 1/ (- 1)$ ), so the span is a plane through the origin in $R^{3}$ , and $- 3 b_{1} + b_{2} + 2 b_{3} = 0$ is its equation. Sanity check that the generators satisfy it: $v_{1}$ gives $- 3 - 1 + 4 = 0$ and $v_{2}$ gives $- 9 + 1 + 8 = 0$ .
(c) The three views. As scalar equations: $x_{1} + 3 x_{2} = 4$ , $- x_{1} + x_{2} = 0$ , $2 x_{1} + 4 x_{2} = 5$ . As a vector equation: $x_{1} (1, - 1, 2) + x_{2} (3, 1, 4) = (4, 0, 5)$ . As a matrix equation: $A x = c$ with
$A = 1 - 1 2 314, x = (x_{1} x_{2}) .$
The theorem that the three views agree says these have exactly the same solution set, and in particular that $A x = c$ is consistent if and only if $c$ lies in the span of the columns of $A$ . Here all three are inconsistent, which is what (a) found.
6.Computation
The system below contains real parameters $h$ and $k$ :
$x + 2 y - z = 1, 2 x + 5 y + z = 4, x + 3 y + h z = k .$
1. (a)Reduce the augmented matrix to echelon form, keeping $h$ and $k$ symbolic, and determine for which pairs $(h, k)$ the system has no solution, exactly one solution, and infinitely many solutions. Name the criterion you use.
2. (b)In the case $h = 2$ , $k = 3$ , write the solution set in parametric form and check one of its points in the original equations.
3. (c)Take $h = 2$ and leave the right-hand side $(b_{1}, b_{2}, b_{3})$ unspecified. Explain, naming the theorem, why there must exist right-hand sides for which the system is inconsistent; state $rank (A)$ and the possible values of $rank ([A ∣ b])$ ; and find the condition on $b_{1}, b_{2}, b_{3}$ for consistency.
Solution
(a) Symbolic elimination. The augmented matrix and its reduction:
$121253 - 1 1 h 14 k R_{2} \leftarrow R_{2} - 2 R_{1}, R_{3} \leftarrow R_{3} - R_{1} 100211 - 1 3 h + 1 12 k - 1 .$
The pivot in column $2$ is the $1$ in row $2$ . $R_{3} \leftarrow R_{3} - R_{2}$ gives the last row $(0, 0, h - 2 ∣ k - 3)$ :
$100210 - 1 3 h - 2 12 k - 3 .$
Everything is decided by the last row, $(h - 2) z = k - 3$ , via the existence and uniqueness criterion.
If $h \neq = 2$ : three pivots in three columns, no impossible row, so exactly one solution for every $k$ . If $h = 2$ and $k \neq = 3$ : the last row reads $0 = k - 3 \neq = 0$ , an impossible row, so no solution. If $h = 2$ and $k = 3$ : the last row is $0 = 0$ , there are two pivots and $z$ is free, so infinitely many solutions.
Sanity check of the unique case at $h = 3$ , $k = 4$ : $z = 1$ , then $y = 2 - 3 z = - 1$ , then $x = 1 - 2 y + z = 4$ . In the original equations: $4 - 2 - 1 = 1$ , $8 - 5 + 1 = 4$ , $4 - 3 + 3 = 4$ . All hold.
(b) The free case. With $h = 2, k = 3$ the echelon form is rows $(1, 2, - 1 ∣ 1)$ , $(0, 1, 3 ∣ 2)$ , $(0, 0, 0 ∣ 0)$ . Set $z = t$ . Row $2$ gives $y = 2 - 3 t$ ; row $1$ gives $x = 1 - 2 y + z = 1 - 4 + 6 t + t = - 3 + 7 t$ . So
$x y z = - 3 20 + t 7 - 3 1, t \in R,$
a line in $R^{3}$ . Check at $t = 1$ , the point $(4, - 1, 1)$ : $4 - 2 - 1 = 1$ , $8 - 5 + 1 = 4$ , $4 - 3 + 2 = 3$ . All hold.
(c) Why some right-hand sides must fail. With $h = 2$ the coefficient matrix reduces to rows $(1, 2, - 1)$ , $(0, 1, 3)$ , $(0, 0, 0)$ : two pivots, so $rank (A) = 2$ , and the third row has no pivot. The solvability theorem says $A x = b$ is consistent for every $b$ if and only if $A$ has a pivot in every row; that fails, so some $b$ makes the system inconsistent. Appending a column adds at most one pivot, so $rank ([A ∣ b])$ is $2$ (consistent) or $3$ (inconsistent).
To find the condition, repeat the reduction with a general right-hand side: $R_{2} \leftarrow R_{2} - 2 R_{1}$ leaves $b_{2} - 2 b_{1}$ , $R_{3} \leftarrow R_{3} - R_{1}$ leaves $b_{3} - b_{1}$ , and $R_{3} \leftarrow R_{3} - R_{2}$ leaves $b_{3} - b_{1} - (b_{2} - 2 b_{1}) = b_{1} - b_{2} + b_{3}$ in the last row. The system is consistent exactly when
$b_{1} - b_{2} + b_{3} = 0.$
Sanity checks: $(1, 4, 3)$ from part (b) gives $1 - 4 + 3 = 0$ , consistent as found; $(0, 0, 1)$ gives $1 \neq = 0$ , so $A x = (0, 0, 1)$ is an explicit inconsistent instance.
7.Proof
Let $A$ be an $m \times n$ matrix. Quote by name each proposition or theorem you use.
1. (a)Suppose $A x = b$ is consistent. Prove that it has exactly one solution if and only if $Null (A) = {0}$ .
2. (b)Now suppose $A$ is square ( $m = n$ ) and $A x = 0$ has only the trivial solution. Prove that $A x = b$ is consistent for every $b \in R^{n}$ .
3. (c)Show by explicit examples that (b) fails without the hypothesis $m = n$ : give a non-square $A$ for which $A x = 0$ has only the trivial solution but $A x = b$ is inconsistent for some $b$ , and a non-square $A$ for which $A x = b$ is consistent for every $b$ but $Null (A) \neq = {0}$ . In each case point to the step of your proof in (b) that breaks.
Solution
(a) Uniqueness is a statement about the null space. Let $p$ be a solution of $A x = b$ , which exists by hypothesis.
( $\Rightarrow$ ) Suppose $p$ is the only solution, and let $h \in Null (A)$ . Then $A (p + h) = A p + A h = b + 0 = b$ , so $p + h$ is a solution. By uniqueness $p + h = p$ , hence $h = 0$ . So $Null (A) = {0}$ .
( $\Leftarrow$ ) Suppose $Null (A) = {0}$ and let $x_{1}, x_{2}$ be solutions. Then $A (x_{1} - x_{2}) = A x_{1} - A x_{2} = b - b = 0$ , so $x_{1} - x_{2} \in Null (A) = {0}$ and $x_{1} = x_{2}$ . There is exactly one solution. $■$
(Both directions are the structure theorem for solution sets in the special case where the null space is trivial: the solution set $p + Null (A)$ is a single point exactly when $Null (A)$ is.)
(b) Counting pivots in a square matrix. By the proposition on when nontrivial solutions exist, $A x = 0$ has only the trivial solution if and only if every column of $A$ is a pivot column. So $A$ has $n$ pivot positions.
Distinct pivot positions lie in distinct rows, so these $n$ pivots occupy $n$ distinct rows. But $A$ has exactly $m = n$ rows, so every row of $A$ contains a pivot position.
By the solvability theorem, a pivot in every row is equivalent to $A x = b$ being consistent for every $b \in R^{m} = R^{n}$ . $■$
(c) Two counterexamples. Tall: take $A = (10)$ , which is $2 \times 1$ . The equation $A x = 0$ reads $x = 0$ , $0 = 0$ , so only the trivial solution. But $A x = (0, 1)$ reads $x = 0$ , $0 = 1$ , which is inconsistent. The step that breaks is " $n$ pivots fill all $m$ rows": here $n = 1$ pivot cannot fill $m = 2$ rows, and the second row has none.
Wide: take $A = (100100)$ , which is $2 \times 3$ . It has a pivot in every row, so by the solvability theorem $A x = b$ is consistent for every $b \in R^{2}$ (indeed $x = (b_{1}, b_{2}, 0)$ works). But column $3$ has no pivot, so $x_{3}$ is free and $(0, 0, 1) \in Null (A)$ . Here the hypothesis of (b) itself fails — the null space is not trivial — which shows the converse direction "pivot in every row $\Rightarrow$ pivot in every column" is false when there are more columns than rows. The two conditions coincide only when $m = n$ .
8.Computation
Let $A$ be the coefficient matrix of the system
$x_{1} + 2 x_{2} + x_{3} + x_{4} 2 x_{1} + 4 x_{2} - x_{3} - 4 x_{4} x_{1} + 2 x_{2} + 3 x_{3} + 5 x_{4} = 2 = 7 = 0.$
1. (a)Reduce the augmented matrix to reduced echelon form and write the solution set in parametric vector form $x = p + s v_{1} + t v_{2}$ .
2. (b)Give a spanning set for $Null (A)$ , and verify directly that every row of $A$ sends each spanning vector to $0$ .
3. (c)Verify that $q = (2, 1, - 3, 1)$ is a solution, write $q - p$ as an explicit combination of $v_{1}$ and $v_{2}$ , and explain, quoting the structure theorem, why $q + s v_{1} + t v_{2}$ describes exactly the same set as your answer to (a).
Solution
(a) Reduce to RREF. Forward phase:
$121242 1 - 1 3 1 - 4 5 270 R_{2} \leftarrow R_{2} - 2 R_{1}, R_{3} \leftarrow R_{3} - R_{1} 100200 1 - 3 2 1 - 6 4 23 - 2 .$
Column $2$ of the remaining block is zero, so the next pivot is the $- 3$ in position $(2, 3)$ . $R_{3} \leftarrow R_{3} + \frac{2}{3} R_{2}$ gives $(0, 0, 0, 0 ∣ - 2 + 2) = (0, 0, 0, 0 ∣ 0)$ . Backward phase: $R_{2} \leftarrow - \frac{1}{3} R_{2}$ gives $(0, 0, 1, 2 ∣ - 1)$ , and $R_{1} \leftarrow R_{1} - R_{2}$ gives $(1, 2, 0, - 1 ∣ 3)$ :
$100200010 - 1 20 3 - 1 0 .$
Pivot columns $1$ and $3$ ; free variables $x_{2} = s$ and $x_{4} = t$ . The rows say $x_{1} = 3 - 2 s + t$ and $x_{3} = - 1 - 2 t$ , so
$x = 3 - 2 s + t s - 1 - 2 t t = p 30 - 1 0 + s v_{1} - 2 100 + t v_{2} 10 - 2 1 .$
Check $p$ in the original system: $3 - 1 = 2$ ; $6 + 1 = 7$ ; $3 - 3 = 0$ . All hold.
(b) The null space. By the structure theorem the parameter vectors span the null space: $Null (A) = Span {v_{1}, v_{2}}$ . Direct verification against the rows $(1, 2, 1, 1)$ , $(2, 4, - 1, - 4)$ , $(1, 2, 3, 5)$ of $A$ :
For $v_{1} = (- 2, 1, 0, 0)$ : $- 2 + 2 = 0$ ; $- 4 + 4 = 0$ ; $- 2 + 2 = 0$ .
For $v_{2} = (1, 0, - 2, 1)$ : $1 - 2 + 1 = 0$ ; $2 + 2 - 4 = 0$ ; $1 - 6 + 5 = 0$ .
Both are in the null space, as claimed.
(c) A different particular solution. Check $q = (2, 1, - 3, 1)$ : $2 + 2 - 3 + 1 = 2$ ; $4 + 4 + 3 - 4 = 7$ ; $2 + 2 - 9 + 5 = 0$ . So $q$ is a solution. Then
$q - p = (2 - 3, 1 - 0, - 3 + 1, 1 - 0) = (- 1, 1, - 2, 1) = v_{1} + v_{2},$
since $(- 2, 1, 0, 0) + (1, 0, - 2, 1) = (- 1, 1, - 2, 1)$ . That is, $q$ is the point of the family in (a) with $s = t = 1$ .
The structure theorem says the solution set is ${p^{'} + h : h \in Null (A)}$ for any one solution $p^{'}$ — the theorem's proof never used which solution was chosen. Taking $p^{'} = q$ gives the description $q + s v_{1} + t v_{2}$ . Concretely the two descriptions are reparametrisations of one another: $q + s v_{1} + t v_{2} = p + (s + 1) v_{1} + (t + 1) v_{2}$ , and as $(s, t)$ runs over $R^{2}$ so does $(s + 1, t + 1)$ . The particular solution is a choice; the set, and the null space directions, are not.
9.Critique
A student is asked whether $v_{1} = (1, 2, 1)$ , $v_{2} = (2, 4, 3)$ , $v_{3} = (3, 6, 4)$ are linearly independent, and submits the following.
Step 1. No vector in the list is a scalar multiple of another: $v_{2}$ is not a multiple of $v_{1}$ , because the first coordinates would need the factor $2$ while the third coordinates would need the factor $3$ , and the other two pairs fail the same way. So no vector is a linear combination of the others, and the list is linearly independent.
Step 2. This agrees with the corollary that a list of $p$ vectors in $R^{m}$ is dependent when $p > m$ : here $p = m = 3$ , so the corollary does not apply, and the list is independent.
Step 3. Confirmation by row reduction: the matrix with these columns reduces to $100210310$ , and every column has a nonzero entry, so every column is a pivot column.
1. (a)Each step contains an error. Identify all three, and for each say precisely which definition, proposition or corollary is being misstated or misapplied.
2. (b)Determine whether the list is independent. If it is dependent, give an explicit dependence relation and express one vector as a combination of the others.
Solution
(a) The three errors.
Step 1 tests pairs, but dependence is about combinations. The characterisation of dependence says a list is dependent if and only if some $v_{j}$ is a linear combination of the others — all of them together, not one at a time. For two vectors that reduces to "one is a multiple of the other", but for three it does not: $v_{3}$ may be a combination of $v_{1}$ and $v_{2}$ without being a multiple of either. The pairwise checks are correct as far as they go; the sentence "so no vector is a linear combination of the others" is a non sequitur.
Step 2 uses a one-way corollary backwards. The corollary " $p > m$ implies dependent" is an implication, not an equivalence. When $p \leq m$ it says nothing at all: lists with $p \leq m$ can be independent or dependent. (Any list containing $0$ is dependent, whatever $p$ is; so is $(1, 0, 0), (2, 0, 0), (0, 0, 1)$ in $R^{3}$ .) "The corollary does not apply" is not evidence of independence.
Step 3 confuses a nonzero column with a pivot column. The reduced matrix is correct, but a pivot column is a column containing a pivot position — the leading entry of some row — not a column with a nonzero entry in it. The leading entries are the $1$ in row $1$ (column $1$ ) and the $1$ in row $2$ (column $2$ ); the entries $3$ and $1$ in column $3$ are not leading entries of their rows. So the pivot columns are $1$ and $2$ only, and the proposition on independence in terms of pivots (independent if and only if every column is a pivot column) says the columns are dependent, the opposite of the student's conclusion.
(b) The correct determination. Row-reduce the matrix with the vectors as columns:
$121243364 R_{2} \leftarrow R_{2} - 2 R_{1}, R_{3} \leftarrow R_{3} - R_{1} 100201301 R_{2} \leftrightarrow R_{3} 100210310 .$
Two pivots for three columns, so column $3$ is free and the list is linearly dependent. To find a relation, solve $x_{1} v_{1} + x_{2} v_{2} + x_{3} v_{3} = 0$ with the free variable $x_{3} = 1$ : row $2$ gives $x_{2} + x_{3} = 0$ , so $x_{2} = - 1$ ; row $1$ gives $x_{1} + 2 x_{2} + 3 x_{3} = 0$ , so $x_{1} = 2 - 3 = - 1$ . Hence
$- v_{1} - v_{2} + v_{3} = 0, that is v_{3} = v_{1} + v_{2} .$
Check: $(1, 2, 1) + (2, 4, 3) = (3, 6, 4) = v_{3}$ . This is exactly the situation Step 1 could not see — $v_{3}$ is a combination of the other two while being a multiple of neither.
10.Proof
Let $A$ be an $m \times n$ matrix and $b \in R^{m}$ . In each part give a complete argument from the definitions of pivot position, rank and nullity, and from named results.
1. (a)Prove that $rank ([A ∣ b])$ equals either $rank (A)$ or $rank (A) + 1$ , and say which case is consistency.
2. (b)Prove: if $A x = b$ is consistent for every $b \in R^{m}$ and $A x = 0$ has only the trivial solution, then $A$ is square.
3. (c)Prove that $nullity (A) \geq n - m$ . Then, for $m = 2$ and $n = 4$ , give one matrix for which equality holds and one whose nullity is $4$ , verifying the rank of each.
Solution
(a) Appending a column adds at most one pivot. Run the forward phase of Gaussian elimination on $[A ∣ b]$ . The algorithm works through the columns from left to right, and every choice it makes while processing the first $n$ columns — which column is next, which rows to swap, which multiples to subtract — depends only on entries in those columns. So when the algorithm reaches column $n + 1$ , the left block has been carried to an echelon form $U$ of $A$ and the matrix reads $[U ∣ d]$ for some $d$ .
Every pivot of $U$ is a leading entry of its row in $[U ∣ d]$ too, because appending an entry to the right of a row does not change where its first nonzero entry is. That accounts for $rank (A)$ pivot positions of $[A ∣ b]$ . The remaining rows are zero to the left of the bar. If any of them has a nonzero entry in the last column, the algorithm swaps one such row to the top of the remaining block and clears the rest of the column below it, creating exactly one further pivot position, in column $n + 1$ ; if none does, no pivot is created. Since pivots move strictly rightward down the rows, a single column can contain at most one pivot position, so the last column contributes $0$ or $1$ pivots and never more. Hence
$rank ([A ∣ b]) \in {rank (A), rank (A) + 1} .$
(The counts are independent of the route taken, by the uniqueness of the reduced echelon form.) The extra pivot exists exactly when the last column is a pivot column, which by the existence and uniqueness criterion is exactly when the system is inconsistent. So $rank ([A ∣ b]) = rank (A)$ is the consistent case. $■$
(b) Full row rank and full column rank force $m = n$ . By the solvability theorem, $A x = b$ consistent for every $b \in R^{m}$ means $A$ has a pivot position in every row; distinct pivots lie in distinct rows, so the number of pivots is exactly $m$ , i.e. $rank (A) = m$ .
By the proposition on nontrivial solutions, $A x = 0$ having only the trivial solution means every column of $A$ is a pivot column; distinct pivots lie in distinct columns, so the number of pivots is exactly $n$ , i.e. $rank (A) = n$ .
The rank is a single well-defined number (uniqueness of the reduced echelon form), so $m = rank (A) = n$ and $A$ is square. $■$
(c) A lower bound on the nullity. By the rank bounds, $rank (A) \leq min (m, n) \leq m$ . By the rank theorem, $nullity (A) = n - rank (A)$ , and therefore
$nullity (A) = n - rank (A) \geq n - m . ■$
In words: a wide matrix cannot impose more independent constraints than it has rows, so at least $n - m$ degrees of freedom always survive.
Examples with $m = 2$ , $n = 4$ . Equality: $A = (10010000)$ is already in reduced echelon form with pivots in columns $1$ and $2$ , so $rank (A) = 2$ and $nullity (A) = 4 - 2 = 2 = n - m$ . Nullity $4$ : the zero matrix $A = (00000000)$ has no nonzero entry, hence no pivot, so $rank (A) = 0$ (by the rank bounds, the zero matrix is the only matrix of rank $0$ ) and $nullity (A) = 4$ : every vector of $R^{4}$ is in the null space. The intermediate value $3$ is also attainable, for instance by $(12243648)$ , whose second row is twice the first, leaving a single pivot.
11.Computation
Let
$A = 132286114 .$
Record every multiplier $ℓ_{ij}$ as you eliminate, with its sign.
1. (a)Find the $LU$ factorization of $A$ , and verify $LU = A$ by multiplying out rows $2$ and $3$ of the product.
2. (b)Using the factorization — not fresh elimination — solve $A x = b$ first for $b = (2, 4, 6)$ and then for $b = (3, 7, 12)$ . Show the forward and back substitutions and check each answer in $A$ .
3. (c)Let $B = 121243132$ . Prove that $B$ has no factorization $B = LU$ with $L$ unit lower triangular and $U$ upper triangular, then find a permutation matrix $P$ and an $LU$ factorization of $PB$ .
Solution
(a) Eliminate and record. Column $1$ : the pivot is $1$ . The multiplier for row $2$ is $ℓ_{21} = 3/1 = 3$ , and $R_{2} \leftarrow R_{2} - 3 R_{1}$ gives $(0, 2, - 2)$ . The multiplier for row $3$ is $ℓ_{31} = 2/1 = 2$ , and $R_{3} \leftarrow R_{3} - 2 R_{1}$ gives $(0, 2, 2)$ :
$100222 1 - 2 2 .$
Column $2$ : the pivot is $2$ . The multiplier for row $3$ is $ℓ_{32} = 2/2 = 1$ , and $R_{3} \leftarrow R_{3} - R_{2}$ gives $(0, 0, 4)$ . No interchange was needed, so by the theorem on multipliers
$U = 100220 1 - 2 4, L = 132011001 .$
Verification: row $2$ of $LU$ is $3 (1, 2, 1) + 1 (0, 2, - 2) = (3, 8, 1)$ ; row $3$ is $2 (1, 2, 1) + 1 (0, 2, - 2) + 1 (0, 0, 4) = (2, 4 + 2, 2 - 2 + 4) = (2, 6, 4)$ . Both match $A$ (row $1$ of $LU$ is row $1$ of $U$ , which is row $1$ of $A$ ).
(b) Two right-hand sides, one factorization. First, $b = (2, 4, 6)$ . Forward substitution on $L y = b$ , top down: $y_{1} = 2$ ; $3 y_{1} + y_{2} = 4$ gives $y_{2} = - 2$ ; $2 y_{1} + y_{2} + y_{3} = 6$ gives $y_{3} = 6 - 4 + 2 = 4$ . Back substitution on $U x = (2, - 2, 4)$ , bottom up: $4 x_{3} = 4$ gives $x_{3} = 1$ ; $2 x_{2} - 2 x_{3} = - 2$ gives $x_{2} = 0$ ; $x_{1} + 2 x_{2} + x_{3} = 2$ gives $x_{1} = 1$ . So $x = (1, 0, 1)$ . Check in $A$ : $1 + 0 + 1 = 2$ , $3 + 0 + 1 = 4$ , $2 + 0 + 4 = 6$ .
Second, $b = (3, 7, 12)$ . Forward: $y_{1} = 3$ ; $y_{2} = 7 - 3 (3) = - 2$ ; $y_{3} = 12 - 2 (3) - 1 (- 2) = 8$ . Back: $4 x_{3} = 8$ gives $x_{3} = 2$ ; $2 x_{2} - 2 (2) = - 2$ gives $x_{2} = 1$ ; $x_{1} + 2 (1) + 2 = 3$ gives $x_{1} = - 1$ . So $x = (- 1, 1, 2)$ . Check in $A$ : $- 1 + 2 + 2 = 3$ , $- 3 + 8 + 2 = 7$ , $- 2 + 6 + 8 = 12$ .
The elimination was paid for once; each further right-hand side costs only two triangular sweeps.
(c) A matrix that needs a permutation. Suppose $B = LU$ with $L$ unit lower triangular and $U$ upper triangular, and compare rows of the product. Row $1$ of $L$ is $(1, 0, 0)$ , so row $1$ of $U$ equals row $1$ of $B$ , namely $(1, 2, 1)$ . Row $2$ of $LU$ is $ℓ_{21} (1, 2, 1) + (0, u_{22}, u_{23}) = (ℓ_{21}, 2 ℓ_{21} + u_{22}, ℓ_{21} + u_{23})$ ; matching $(2, 4, 3)$ forces $ℓ_{21} = 2$ and then $u_{22} = 0$ . Row $3$ of $LU$ is $ℓ_{31} (1, 2, 1) + ℓ_{32} (0, 0, u_{23}) + (0, 0, u_{33})$ , whose first two entries are $(ℓ_{31}, 2 ℓ_{31})$ ; matching $(1, 3, 2)$ forces $ℓ_{31} = 1$ and $2 = 3$ , a contradiction. So no such factorization exists. (Elimination shows the same thing: after clearing column $1$ the $(2, 2)$ entry is $0$ while the $(3, 2)$ entry is $1$ , so a swap is unavoidable.)
Swap rows $2$ and $3$ in advance with $P = 100001010$ , so that
$PB = 112234123 .$
Now eliminate: $ℓ_{21} = 1$ , $R_{2} \leftarrow R_{2} - R_{1}$ gives $(0, 1, 1)$ ; $ℓ_{31} = 2$ , $R_{3} \leftarrow R_{3} - 2 R_{1}$ gives $(0, 0, 1)$ ; the $(3, 2)$ entry is already $0$ , so $ℓ_{32} = 0$ . Hence
$PB = LU with L = 112010001, U = 100210111 .$
Check: row $2$ of $LU$ is $(1, 2, 1) + (0, 1, 1) = (1, 3, 2)$ and row $3$ is $2 (1, 2, 1) + (0, 0, 1) = (2, 4, 3)$ , the second and third rows of $PB$ .
12.Computation
Four one-way intersections $A$ , $B$ , $C$ , $D$ are joined by five internal roads carrying, in cars per hour, $x_{1}$ from $A$ to $B$ , $x_{2}$ from $B$ to $C$ , $x_{3}$ from $C$ to $D$ , $x_{4}$ from $D$ to $A$ , and $x_{5}$ directly from $A$ to $C$ . External traffic per hour: $A$ takes in $200$ and releases $80$ ; $B$ takes in $30$ and releases $70$ ; $C$ takes in $60$ and releases $90$ ; $D$ takes in $50$ and releases $100$ . At every intersection, flow in equals flow out.
1. (a)Write the four conservation equations as a linear system, show that one of them is a consequence of the other three, and find the rank of the coefficient matrix.
2. (b)Solve the system and write all flows in parametric vector form. Interpret each null-space direction as a circulation in the network.
3. (c)The road from $D$ to $A$ is closed, so $x_{4} = 0$ , and no road may carry negative traffic. Find the set of all admissible flows and the smallest possible value of $x_{1}$ .
4. (d)Suppose instead that $D$ released $110$ cars per hour, everything else unchanged. Show that the system is inconsistent and say in one sentence what the impossible row means physically.
Solution
(a) The model. In equals out at each intersection:
$A$ : $x_{4} + 200 = x_{1} + x_{5} + 80$ , i.e. $x_{1} - x_{4} + x_{5} = 120$ .
$B$ : $x_{1} + 30 = x_{2} + 70$ , i.e. $x_{1} - x_{2} = 40$ .
$C$ : $x_{2} + x_{5} + 60 = x_{3} + 90$ , i.e. $x_{2} - x_{3} + x_{5} = 30$ .
$D$ : $x_{3} + 50 = x_{4} + 100$ , i.e. $x_{3} - x_{4} = 50$ .
Adding the $B$ , $C$ and $D$ equations gives $x_{1} - x_{2} + x_{2} - x_{3} + x_{5} + x_{3} - x_{4} = 40 + 30 + 50$ , that is $x_{1} - x_{4} + x_{5} = 120$ — exactly the $A$ equation. So $A$ is redundant: every internal road appears once as an inflow and once as an outflow, so summing all four left-hand sides gives $0$ , and the four right-hand sides $120 - 40 - 30 - 50$ also sum to $0$ because total external inflow ( $340$ ) equals total external outflow ( $340$ ).
For the rank, reduce the augmented matrix (rows in the order $A, B, C, D$ ):
$1100 0 - 1 10 00 - 1 1 - 1 00 - 1 1010120403050 R_{2} \leftarrow R_{2} - R_{1} 1000 0 - 1 10 00 - 1 1 - 1 10 - 1 1 - 1 10 120 - 80 3050 .$
Then $R_{3} \leftarrow R_{3} + R_{2}$ gives $(0, 0, - 1, 1, 0 ∣ - 50)$ and $R_{4} \leftarrow R_{4} + R_{3}$ gives $(0, 0, 0, 0, 0 ∣ 0)$ :
$1000 0 - 1 00 00 - 1 0 - 1 110 1 - 1 00 120 - 80 - 50 0 .$
Pivots in columns $1, 2, 3$ , so the coefficient matrix has rank $3$ ; by the rank theorem the nullity is $5 - 3 = 2$ .
(b) All flows. Free variables $x_{4} = t$ and $x_{5} = s$ . Row $3$ : $- x_{3} + t = - 50$ , so $x_{3} = 50 + t$ . Row $2$ : $- x_{2} + t - s = - 80$ , so $x_{2} = 80 + t - s$ . Row $1$ : $x_{1} = 120 + t - s$ . In parametric vector form
$x_{1} x_{2} x_{3} x_{4} x_{5} = 120805000 + t 11110 + s - 1 - 1 001 .$
Check the particular solution $(120, 80, 50, 0, 0)$ at every intersection: $A$ : $0 + 200 = 120 + 0 + 80$ ; $B$ : $120 + 30 = 80 + 70$ ; $C$ : $80 + 0 + 60 = 50 + 90$ ; $D$ : $50 + 50 = 0 + 100$ . All balance.
The direction $(1, 1, 1, 1, 0)$ adds one car per hour to each of $A \to B \to C \to D \to A$ : a circulation around the outer loop, which changes no external flow. The direction $(- 1, - 1, 0, 0, 1)$ reroutes one car per hour from the path $A \to B \to C$ onto the direct road $A \to C$ : the same car arrives at $C$ either way, so again nothing external changes. These are the two independent ways to move traffic around without anyone noticing at the boundary.
(c) Closing $D \to A$ . Setting $x_{4} = 0$ forces $t = 0$ , leaving the one-parameter family $(120 - s, 80 - s, 50, 0, s)$ . Nonnegativity requires $s \geq 0$ (road $A \to C$ ) and $80 - s \geq 0$ (road $B \to C$ ; the condition $120 - s \geq 0$ is then automatic). So the admissible flows are exactly
$(120 - s, 80 - s, 50, 0, s), 0 \leq s \leq 80.$
The smallest $x_{1}$ occurs at $s = 80$ : $x_{1} = 40$ , with $x_{2} = 0$ , $x_{3} = 50$ , $x_{5} = 80$ . Check at $A$ : $0 + 200 = 40 + 80 + 80$ ; at $B$ : $40 + 30 = 0 + 70$ ; at $C$ : $0 + 80 + 60 = 50 + 90$ ; at $D$ : $50 + 50 = 0 + 100$ . All balance, and no road is negative.
(d) Unbalanced totals. The $D$ equation becomes $x_{3} + 50 = x_{4} + 110$ , i.e. $x_{3} - x_{4} = 60$ ; the other three rows are unchanged. Repeating the reduction, the last step $R_{4} \leftarrow R_{4} + R_{3}$ now gives $(0, 0, 0, 0, 0 ∣ 60 - 50) = (0, 0, 0, 0, 0 ∣ 10)$ , an impossible row, so by the existence and uniqueness criterion the system is inconsistent. (Equivalently, $B + C + D$ now has left side equal to that of $A$ but right side $40 + 30 + 60 = 130 \neq = 120$ .) Physically: the network would have to release $350$ cars per hour while only $340$ enter, and a steady flow cannot create ten cars an hour out of nothing.

← Back to the question sheet