Exercise 0.1: Solve by Gaussian elimination: eight direct calculations

For each system, write the augmented matrix, reduce it to row echelon form by Gaussian elimination, then conclude: give the unknowns asked for, or the nature of the solution set when there is no unique solution.

Only three operations on the rows: interchange two rows, multiply a row by a nonzero number, add a multiple of another row to a row. Clear the first column below the first pivot, then the second column below the second pivot, and read the last row: a pivot everywhere gives a unique solution by back substitution, a row $0=c$ with $c\neq 0$ gives none, a row $0=0$ leaves a free unknown, which you take as a parameter. The rank is the number of pivots.

a) $\begin{cases} 3x-2y=11 \\ 5x+4y=-11 \end{cases}$ : give $x$ and $y$ .
b) $\begin{cases} 2x-y+3z=9 \\ 4y-z=-6 \\ 3z=6 \end{cases}$ , already triangular: solve by back substitution, then give $y$ and $x$ .
c) $\begin{cases} x-y+2z=5 \\ 2x+y-z=3 \\ x+2y+z=6 \end{cases}$ : give $x$ and $z$ .
d) $\begin{cases} 3y+z=5 \\ x+2y-z=-1 \\ 2x+y+3z=5 \end{cases}$ : give $x$ and $z$ .
e) $\begin{cases} x-2y+z=3 \\ 2x+y-3z=1 \\ 4x-3y-z=9 \end{cases}$ : state the nature of the solution set and give the rank of the coefficient matrix.
f) $\begin{cases} x+y-z=2 \\ 2x+3y+z=9 \\ 3x+4y=11 \end{cases}$ : state the nature of the solution set, then give the value of $x$ when $z=2$ .
g) $\begin{cases} x+2y+3z=4 \\ 2x+5y+4z=3 \end{cases}$ : solve with $z=t$ as the parameter, then give $x$ for $t=0$ and the coefficient of $t$ in $y$ .
h) Give the rank of the matrix $\begin{pmatrix} 1 & -1 & 2 & 3 \\ 2 & 1 & 1 & 0 \\ 4 & -1 & 5 & 6 \end{pmatrix}$ .

Type your answers, the page tells you right or wrong 0/15

a)

x

y

b)

y

x

c)

x

z

d)

x

z

e)

The system has

Rank of the coefficient matrix

f)

The system has

x

when

z=2

g)

x

for

t=0

Coefficient of

t

in

y

h)

Rank

Show the solution

Answers

a) $x=1$ , $y=-4$
b) $z=2$ , $y=-1$ , $x=1$
c) $(2, 1, 2)$
d) interchange $R_{1}\leftrightarrow R_{2}$ ; $(-1, 1, 2)$
e) row $0=2$ : no solution; rank $2$
f) infinitely many solutions, $(-3+4t, 5-3t, t)$ ; $x=5$
g) $(14-7t, -5+2t, t)$ ; $14$ and $2$
h) $R_{3}=2R_{1}+R_{2}$ ; rank $2$

The move that decides everything: read the LAST row of the echelon form before concluding. A nonzero pivot, a row $0=c$ with $c\neq 0$ , a row $0=0$ : these three readings alone tell you whether there is one solution, none or infinitely many, whatever the number of equations.

a)

Augmented matrix $\left[\begin{array}{cc|c} 3 & -2 & 11 \\ 5 & 4 & -11 \end{array}\right]$ . $R_{2}\to 3R_{2}-5R_{1}$ gives $(0\ \ 22\,|\,-33-55)=(0\ \ 22\,|\,-88)$ , so $y=-4$ ; then $3x-2\times(-4)=11$ , $3x=3$ and $x=1$ . Pitfall: $3\times(-11)-5\times 11=-88$ , two signs to carry.

b)

Back substitute from the last row: $z=\frac{6}{3}=2$ ; $4y-2=-6$ , so $y=-1$ ; $2x-(-1)+3\times 2=9$ , so $2x=2$ and $x=1$ . Pitfall: $-y$ with $y=-1$ is $+1$ .

c)

$R_{2}\to R_{2}-2R_{1}$ : $(0\ \ 3\ \ -5\,|\,-7)$ ; $R_{3}\to R_{3}-R_{1}$ : $(0\ \ 3\ \ -1\,|\,1)$ ; $R_{3}\to R_{3}-R_{2}$ : $(0\ \ 0\ \ 4\,|\,8)$ . Back substitution: $z=2$ , then $3y-10=-7$ and $y=1$ , then $x=5+y-2z=5+1-4=2$ .

d)

The first pivot is zero: interchange $R_{1}$ and $R_{2}$ , which gives the rows $(1\ \ 2\ \ -1\,|\,-1)$ , $(0\ \ 3\ \ 1\,|\,5)$ and $(2\ \ 1\ \ 3\,|\,5)$ . $R_{3}\to R_{3}-2R_{1}$ : $(0\ \ -3\ \ 5\,|\,7)$ ; $R_{3}\to R_{3}+R_{2}$ : $(0\ \ 0\ \ 6\,|\,12)$ . Back substitution: $z=2$ , $3y+2=5$ so $y=1$ , $x=-1-2y+z=-1-2+2=-1$ . Pitfall: interchanging COLUMNS instead of rows, which permutes the unknowns.

e)

$R_{2}\to R_{2}-2R_{1}$ : $(0\ \ 5\ \ -5\,|\,-5)$ ; $R_{3}\to R_{3}-4R_{1}$ : $(0\ \ 5\ \ -5\,|\,-3)$ ; $R_{3}\to R_{3}-R_{2}$ : $(0\ \ 0\ \ 0\,|\,2)$ . The last row says $0=2$ : no solution. The coefficient matrix has two pivots, so rank $2$ , and the augmented matrix has rank $3$ . Pitfall: concluding that there are infinitely many solutions because the coefficients of the last row vanish; it is the nonzero right-hand side that decides.

f)

$R_{2}\to R_{2}-2R_{1}$ : $(0\ \ 1\ \ 3\,|\,5)$ ; $R_{3}\to R_{3}-3R_{1}$ : $(0\ \ 1\ \ 3\,|\,5)$ ; $R_{3}\to R_{3}-R_{2}$ : $(0\ \ 0\ \ 0\,|\,0)$ . A row $0=0$ : rank $2$ for three unknowns, infinitely many solutions with one parameter. With $z=t$ : $y=5-3t$ and $x=2-y+z=2-5+3t+t=-3+4t$ . For $z=2$ : $y=-1$ and $x=5$ . Pitfall: writing $x=2-y-z$ , when $-z$ moves to the other side with a plus sign.

g)

Two equations for three unknowns: at least one parameter remains. $R_{2}\to R_{2}-2R_{1}$ : $(0\ \ 1\ \ -2\,|\,-5)$ . With $z=t$ : $y=-5+2t$ , then $x=4-2y-3z=4+10-4t-3t=14-7t$ . For $t=0$ : $x=14$ ; the coefficient of $t$ in $y$ is $2$ . Check with $t=0$ , $(14, -5, 0)$ : $14-10=4$ and $28-25=3$ .

h)

$R_{2}\to R_{2}-2R_{1}$ : $(0\ \ 3\ \ -3\ \ -6)$ ; $R_{3}\to R_{3}-4R_{1}$ : $(0\ \ 3\ \ -3\ \ -6)$ ; $R_{3}\to R_{3}-R_{2}$ : a zero row. Two pivots, so rank $2$ : the third row was $2R_{1}+R_{2}$ . Pitfall: answering $3$ because there are three rows; the rank counts the INDEPENDENT rows.

Check: a solution you find goes back into ALL the original equations, not only into the echelon form. For infinitely many solutions, check the parametric form for two values of the parameter; for no solution, find the combination of rows that contradicts the right-hand side, here $R_{3}=2R_{1}+R_{2}$ on the left but $9\neq 2\times 3+1$ on the right.

Tick the exercises you have done or want to review: a free account, no password, keeps your ticks and your right answers from one visit to the next, tells you which chapter to tackle next and lets you ask for the exercise you are missing. Create your space, an email is enough.

Exercise 1: Augmented matrix, elementary row operations and Gaussian elimination

Consider the system $\begin{cases} x+2y-z=2 \\ 2x+5y+z=15 \\ 3x+4y-7z=-10 \end{cases}$ .

a) Write the augmented matrix $[A\,|\,B]$ of this system.
b) Perform the operations $R_{2}\to R_{2}-2R_{1}$ and $R_{3}\to R_{3}-3R_{1}$ , and write the resulting matrix.
c) Finish the reduction to obtain a row echelon form, stating the operation used.
d) Solve the system by back substitution, then check your solution in the three original equations.

Show the solution

Answers

a) Augmented matrix $3\times 4$
b) $(0, 1, 3\,|\,11)$ and $(0, -2, -4\,|\,-16)$
c) $R_3\to R_3+2R_2$ : $(0, 0, 2\,|\,6)$
d) $(1, 2, 3)$

a)

$[A\,|\,B]=\left[\begin{array}{ccc|c} 1 & 2 & -1 & 2 \\ 2 & 5 & 1 & 15 \\ 3 & 4 & -7 & -10 \end{array}\right]$ . The top-left entry is $1$ , which makes it an ideal pivot: no fraction will be introduced at the first step.

b)

$R_{2}\to R_{2}-2R_{1}$ gives $(2-2, 5-4, 1+2\,|\,15-4)=(0, 1, 3\,|\,11)$ . Then $R_{3}\to R_{3}-3R_{1}$ gives $(3-3, 4-6, -7+3\,|\,-10-6)=(0, -2, -4\,|\,-16)$ .

The matrix becomes $\left[\begin{array}{ccc|c} 1 & 2 & -1 & 2 \\ 0 & 1 & 3 & 11 \\ 0 & -2 & -4 & -16 \end{array}\right]$ . Watch the sign in the third column of $R_{2}$ : $1-2(-1)=1+2=3$ . Subtracting a multiple of a negative entry produces an addition, and that is where most row reduction errors creep in.

c)

The pivot of the second row is $1$ ; use it to clear the $-2$ below it: $R_{3}\to R_{3}+2R_{2}$ gives $(0, -2+2, -4+6\,|\,-16+22)=(0, 0, 2\,|\,6)$ .

The row echelon form is $\left[\begin{array}{ccc|c} 1 & 2 & -1 & 2 \\ 0 & 1 & 3 & 11 \\ 0 & 0 & 2 & 6 \end{array}\right]$ . The three pivots are $1$ , $1$ and $2$ , each strictly to the right of the one above: the form is indeed echelon. Three pivots for three unknowns already announce a unique solution, before it is even computed.

d)

Work from the last row up to the first. Third row: $2z=6$ , so $z=3$ . Second row: $y+3z=11$ , that is $y+9=11$ , so $y=2$ . First row: $x+2y-z=2$ , that is $x+4-3=2$ , so $x=1$ .

Check in the three original equations, not in the echelon rows, which could carry a propagated error. Equation 1: $1+2(2)-3=1+4-3=2$ , correct. Equation 2: $2(1)+5(2)+3=2+10+3=15$ , correct. Equation 3: $3(1)+4(2)-7(3)=3+8-21=-10$ , correct. The solution is $(x, y, z)=(1, 2, 3)$ .

Exercise 2: From Gauss to Gauss-Jordan: the reduced row echelon form

Take the row echelon form obtained in the previous exercise: $\left[\begin{array}{ccc|c} 1 & 2 & -1 & 2 \\ 0 & 1 & 3 & 11 \\ 0 & 0 & 2 & 6 \end{array}\right]$ .

a) State the two extra conditions that a REDUCED row echelon form must satisfy, and say which ones are missing here.
b) Continue the elimination up to the reduced row echelon form, stating each operation.
c) Read the solution of the system off the matrix you obtain.
d) When is Gaussian elimination enough, and when is Gauss-Jordan clearly better? Justify by the work actually saved.

Show the solution

Answers

a) Pivots equal to 1 and zeros above
b) $[I\,|\,(1, 2, 3)]$
c) $x=1$ , $y=2$ , $z=3$
d) Gauss for one system; Gauss-Jordan to invert or to parametrize

a)

A reduced row echelon form requires two more conditions: every pivot must be exactly $1$ , and every pivot must be the ONLY nonzero entry of its column, so there must also be zeros above the pivots.

Here both conditions are missing. The pivot of the third row is $2$ , not $1$ . And nonzero entries remain above the pivots: the $2$ in position $(1, 2)$ above the pivot of the second column, and the $-1$ and the $3$ above the pivot of the third column.

b)

First normalize the last pivot: $R_{3}\to\dfrac{1}{2}R_{3}$ gives $(0, 0, 1\,|\,3)$ .

Then work upward, column by column. $R_{2}\to R_{2}-3R_{3}$ gives $(0, 1, 3-3\,|\,11-9)=(0, 1, 0\,|\,2)$ . Then $R_{1}\to R_{1}+R_{3}$ gives $(1, 2, -1+1\,|\,2+3)=(1, 2, 0\,|\,5)$ .

It remains to clear the second column: $R_{1}\to R_{1}-2R_{2}$ gives $(1, 2-2, 0\,|\,5-4)=(1, 0, 0\,|\,1)$ .

The reduced row echelon form is $\left[\begin{array}{ccc|c} 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 2 \\ 0 & 0 & 1 & 3 \end{array}\right]$ . The order of work to remember: clear the columns from RIGHT to LEFT, starting from the last pivot. Each row you use to clear upward then has zeros everywhere except its pivot and its right-hand side, so each operation changes a single entry of the left block and the numbers stay small. Working from left to right also reaches the reduced form, but it carries larger intermediate entries along the way.

c)

The reading is immediate: the first row says $x=1$ , the second $y=2$ , the third $z=3$ . No back substitution is needed, the matrix IS the solution. We do get $(1, 2, 3)$ again, which confirms the previous exercise by a different route.

d)

Gauss is plenty when you want the solution of a single system with a unique solution: back substitution is quick, and pushing on to the reduced form adds work for no gain. It is in fact the most efficient method under exam time pressure on an ordinary $3\times 3$ system.

Gauss-Jordan becomes clearly better in three situations. First, when a matrix has to be inverted, since the procedure $[A\,|\,I]\to[I\,|\,A^{-1}]$ requires the reduced form. Next, when the system has infinitely many solutions: the reduced form directly gives each leading unknown in terms of the free parameters, where back substitution forces a tedious substitution that invites sign errors. Finally, when the same system must be solved for several right-hand sides, which can be handled at once by attaching several columns.

In other words, the extra cost of Gauss-Jordan is an investment: it only pays off when you need the full structure of the solution, not just a triple of numbers.

Exercise 3: The three cases: unique solution, no solution, infinitely many

A linear system only ever has three possible outcomes. This exercise brings out all three, and each time asks you to recognize them ON the row echelon form.

a) Solve $\begin{cases} x+2y+z=3 \\ 2x+4y+2z=7 \end{cases}$ and conclude.
b) Solve $\begin{cases} x+y+z=6 \\ x+2y+3z=14 \\ 2x+3y+4z=20 \end{cases}$ and give the solution set in parametric form.
c) In case b), check your parametric form for two different values of the parameter.
d) Interpret geometrically the three possible cases for a system of three equations in three unknowns.

Show the solution

Answers

a) $0=1$ : no solution
b) $(t-2, 8-2t, t)$
c) $t=3$ : $(1, 2, 3)$ ; $t=0$ : $(-2, 8, 0)$
d) A point, nothing, a line or a plane

a)

Augmented matrix $\left[\begin{array}{ccc|c} 1 & 2 & 1 & 3 \\ 2 & 4 & 2 & 7 \end{array}\right]$ . Apply $R_{2}\to R_{2}-2R_{1}$ : $(2-2, 4-4, 2-2\,|\,7-6)=(0, 0, 0\,|\,1)$ .

The second row reads $0x+0y+0z=1$ , that is $0=1$ , which is impossible. The system is INCONSISTENT: it has NO solution.

The signal to recognize: a row whose left part is entirely zero but whose right-hand side is not. Note that the left side of the second equation is exactly twice that of the first, while $7\neq 2\times 3$ : the two equations contradict each other.

b)

Augmented matrix $\left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 1 & 2 & 3 & 14 \\ 2 & 3 & 4 & 20 \end{array}\right]$ . Apply $R_{2}\to R_{2}-R_{1}$ , which gives $(0, 1, 2\,|\,8)$ , then $R_{3}\to R_{3}-2R_{1}$ , which gives $(0, 1, 2\,|\,8)$ .

The two new rows are identical, so $R_{3}\to R_{3}-R_{2}$ gives $(0, 0, 0\,|\,0)$ . The row echelon form is $\left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & 2 & 8 \\ 0 & 0 & 0 & 0 \end{array}\right]$ .

Here the zero row has a ZERO right-hand side, which expresses no contradiction at all: it is the equation $0=0$ , always true, which simply signals a redundant equation. The system is consistent. It has two pivots (columns of $x$ and $y$ ) for three unknowns, so $3-2=1$ free parameter. The unknown $z$ , whose column carries no pivot, becomes the parameter.

Set $z=t$ . The second row gives $y+2t=8$ , so $y=8-2t$ . The first gives $x+(8-2t)+t=6$ , that is $x=6-8+2t-t=t-2$ .

The solution set is $\{(t-2, 8-2t, t)\ :\ t\in\mathbb{R}\}$ , INFINITELY many solutions. The whole set must be given: answering with a single particular solution, even a correct one, does not earn the marks.

c)

For $t=3$ : $(1, 2, 3)$ . Check: $1+2+3=6$ , correct; $1+4+9=14$ , correct; $2+6+12=20$ , correct.

For $t=0$ : $(-2, 8, 0)$ . Check: $-2+8+0=6$ , correct; $-2+16+0=14$ , correct; $-4+24+0=20$ , correct. Two different values of the parameter give two different solutions, both valid: the parametric form is right.

d)

Each linear equation in three unknowns represents a PLANE in space, and solving the system amounts to finding the intersection of the three planes.

Unique solution: the three planes meet in a single POINT, like two walls and a ceiling in the corner of a room. No solution: the planes have no point common to all three, either because two of them are distinct parallel planes, or because they form a prism, each pair meeting along a line but the three lines staying distinct. That is case a), where the two planes are parallel and distinct. Infinitely many solutions: the three planes meet along a common LINE, which is case b), the solution parametrized by $t$ being precisely a parametric equation of that line. Infinitely many can also occur if the three planes coincide, in which case the solution set is a whole plane, with two parameters.

This bridge with geometry is not decoration: recognizing that the solution of b) is a line with direction vector $(1, -2, 1)$ , read directly off the coefficients of $t$ , ties this chapter to the one on lines and planes in space.

Exercise 4: Inverting a matrix by Gauss-Jordan elimination

Consider the matrix $A=\begin{pmatrix} 1 & 1 & 1 \\ 0 & 1 & 2 \\ 1 & 2 & 4 \end{pmatrix}$ .

Recall the principle: form $[A\,|\,I]$ and apply elementary row operations until the left block becomes $I$ ; the right block is then $A^{-1}$ .

a) Write the matrix $[A\,|\,I]$ .
b) Apply Gauss-Jordan elimination to obtain $[I\,|\,A^{-1}]$ .
c) Check your result by computing $A\,A^{-1}$ .
d) Use $A^{-1}$ to solve the system $AX=B$ with $B=\begin{pmatrix} 6 \\ 8 \\ 17 \end{pmatrix}$ .

Show the solution

Answers

a) $[A\,|\,I]$
b) $A^{-1}=\begin{pmatrix}0&-2&1\\2&3&-2\\-1&-1&1\end{pmatrix}$
c) $AA^{-1}=I_3$
d) $X=(1, 2, 3)$

a)

$[A\,|\,I]=\left[\begin{array}{ccc|ccc} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 2 & 0 & 1 & 0 \\ 1 & 2 & 4 & 0 & 0 & 1 \end{array}\right]$ . Every operation that follows acts on WHOLE rows, right block included: forgetting to apply an operation on the right is the error that ruins the computation.

b)

Clear below the first pivot. $R_{3}\to R_{3}-R_{1}$ gives $(0, 1, 3\,|\,-1, 0, 1)$ , which produces $\left[\begin{array}{ccc|ccc} 1 & 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 2 & 0 & 1 & 0 \\ 0 & 1 & 3 & -1 & 0 & 1 \end{array}\right]$ .

Clear below the second pivot: $R_{3}\to R_{3}-R_{2}$ gives $(0, 0, 1\,|\,-1, -1, 1)$ . The left block is now in echelon form with three pivots, which already guarantees that $A$ is invertible.

Work upward. $R_{2}\to R_{2}-2R_{3}$ gives $(0, 1, 0\,|\,0+2, 1+2, 0-2)=(0, 1, 0\,|\,2, 3, -2)$ . Then $R_{1}\to R_{1}-R_{3}$ gives $(1, 1, 0\,|\,1+1, 0+1, 0-1)=(1, 1, 0\,|\,2, 1, -1)$ .

Finally $R_{1}\to R_{1}-R_{2}$ gives $(1, 0, 0\,|\,2-2, 1-3, -1+2)=(1, 0, 0\,|\,0, -2, 1)$ .

The final array is $\left[\begin{array}{ccc|ccc} 1 & 0 & 0 & 0 & -2 & 1 \\ 0 & 1 & 0 & 2 & 3 & -2 \\ 0 & 0 & 1 & -1 & -1 & 1 \end{array}\right]$ , so $A^{-1}=\begin{pmatrix} 0 & -2 & 1 \\ 2 & 3 & -2 \\ -1 & -1 & 1 \end{pmatrix}$ .

c)

First row of $A\,A^{-1}$ : $(1, 1, 1)$ against the first column $(0, 2, -1)$ gives $0+2-1=1$ ; against the second column $(-2, 3, -1)$ gives $-2+3-1=0$ ; against the third $(1, -2, 1)$ gives $1-2+1=0$ . We get $(1, 0, 0)$ .

Second row $(0, 1, 2)$ : $0+2-2=0$ , then $0+3-2=1$ , then $0-2+2=0$ , that is $(0, 1, 0)$ . Third row $(1, 2, 4)$ : $0+4-4=0$ , then $-2+6-4=0$ , then $1-4+4=1$ , that is $(0, 0, 1)$ . The product is $I_{3}$ : the inverse is confirmed.

d)

The solution is $X=A^{-1}B$ , not $BA^{-1}$ : the order of the factors is not free, and the product $BA^{-1}$ is not even defined for sizes $3\times 1$ and $3\times 3$ .

$X=\begin{pmatrix} 0 & -2 & 1 \\ 2 & 3 & -2 \\ -1 & -1 & 1 \end{pmatrix}\begin{pmatrix} 6 \\ 8 \\ 17 \end{pmatrix}$ . First component: $0(6)-2(8)+1(17)=-16+17=1$ . Second: $2(6)+3(8)-2(17)=12+24-34=2$ . Third: $-1(6)-1(8)+1(17)=-6-8+17=3$ . So $X=\begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix}$ .

Direct check in the system: $1+2+3=6$ , correct; $0+2+6=8$ , correct; $1+4+12=17$ , correct.

A remark on method: to solve ONE system, computing the inverse is a costly detour, and Gauss remains faster. The inverse pays off when several right-hand sides $B$ must be handled with the same matrix $A$ , since each one then takes a single matrix product.

Exercise 5: Rank and the consistency theorem

The RANK of a matrix is the number of pivots in its row echelon form, that is, the number of truly independent equations. This single quantity decides on its own how many solutions a system has, and a theorem sums it up.

a) Find the rank of the coefficient matrix of the system $\begin{cases} x+2y-z=2 \\ 2x+5y+z=15 \\ 3x+4y-7z=-10 \end{cases}$ , and conclude on the number of solutions without computing them.
b) State the consistency theorem (Rouché-Capelli): a system $AX=B$ is consistent if and only if $\operatorname{rank}(A)=\operatorname{rank}([A\,|\,B])$ . Illustrate the inconsistent case on $\begin{cases} x+2y+z=3 \\ 2x+4y+2z=7 \end{cases}$ by comparing the two ranks.
c) For a consistent system in $n$ unknowns, express the number of free parameters in terms of the rank, and deduce the criterion for a unique solution.
d) Can a system of $5$ equations in $3$ unknowns have a unique solution? Infinitely many? None? Discuss each case using the rank, stressing that it is the rank, not the number of equations, that decides.

Show the solution

Answers

a) Rank 3: unique solution
b) Ranks 1 and 2: inconsistent
c) $n-\operatorname{rank}(A)$ parameters
d) All three cases are possible

a)

Row reduce the coefficient matrix. With $R_{2}\to R_{2}-2R_{1}$ and $R_{3}\to R_{3}-3R_{1}$ , then $R_{3}\to R_{3}+2R_{2}$ , we obtain the row echelon form $\left[\begin{array}{ccc} 1 & 2 & -1 \\ 0 & 1 & 3 \\ 0 & 0 & 2 \end{array}\right]$ (the computation is that of exercise 1). It has three pivots, so $\operatorname{rank}(A)=3$ . Since the rank equals the number of unknowns, the system has a UNIQUE SOLUTION, and this is known before it is even computed. The determinant confirms it: $\det(A)=2\neq 0$ , in agreement with the rank, since a nonzero determinant always signals full rank.

b)

The consistency theorem states that a system $AX=B$ has at least one solution if and only if the rank of the coefficient matrix $A$ equals the rank of the augmented matrix $[A\,|\,B]$ . In other words, attaching the column of constants must not create an extra pivot. For the given system, the augmented matrix is $\left[\begin{array}{ccc|c} 1 & 2 & 1 & 3 \\ 2 & 4 & 2 & 7 \end{array}\right]$ . The operation $R_{2}\to R_{2}-2R_{1}$ gives $[0\ 0\ 0\,|\,1]$ . The left part then has a single pivot, so $\operatorname{rank}(A)=1$ , while the augmented matrix has a pivot in the column of constants, so $\operatorname{rank}([A\,|\,B])=2$ . The two ranks differ, so the system is INCONSISTENT: this is the impossible row $0=1$ , stated in terms of rank. The theorem formalizes exactly the signal you spot during row reduction.

c)

For a consistent system in $n$ unknowns, the number of free parameters is $n-\operatorname{rank}(A)$ : each pivot fixes a leading unknown, and the remaining unknowns, $n-\operatorname{rank}(A)$ of them, become free. The criterion for a unique solution follows at once: the solution is unique when there is NO free parameter, that is, when $\operatorname{rank}(A)=n$ . In short, a consistent system has a unique solution if $\operatorname{rank}(A)=n$ , and infinitely many if $\operatorname{rank}(A)<n$ , the infinite family having dimension $n-\operatorname{rank}(A)$ .

d)

All three cases are possible, and the rank is what separates them, never the number of equations. The rank of a $5\times 3$ matrix cannot exceed $3$ , the smaller of the numbers of rows and columns. Unique solution: if $\operatorname{rank}(A)=\operatorname{rank}([A\,|\,B])=3$ , the five equations reduce to three independent equations that determine the three unknowns; the two extra equations are consequences of the others, so redundant but consistent. Infinitely many: if the two ranks are equal but less than $3$ , say $2$ , then $3-2=1$ free parameter remains. No solution: if $\operatorname{rank}(A)<\operatorname{rank}([A\,|\,B])$ , which happens as soon as one equation contradicts the others, the system is inconsistent, the most common situation when five constraints are imposed on only three unknowns. That is the moral of the chapter: having more equations than unknowns guarantees nothing, and having fewer equations does not rule out inconsistency; only the rank settles it.

Exercise 6: Homogeneous systems and nontrivial solutions

A homogeneous system is a system $AX=0$ , in which every constant term is zero. This exercise establishes its properties, then applies them.

a) Prove that a homogeneous system is never inconsistent, and state what is called its trivial solution.
b) State and justify the condition on $\det(A)$ that guarantees the existence of NONTRIVIAL solutions.
c) Find all the values of $k$ for which the system $\begin{cases} kx+y+z=0 \\ x+ky+z=0 \\ x+y+kz=0 \end{cases}$ has nontrivial solutions.
d) For each of the values found in c), give the solution set in parametric form.
e) Prove that if a system $AX=B$ has two distinct solutions, then it has infinitely many.

Show the solution

Answers

a) $X=0$ is always a solution
b) Nontrivial if $\det A=0$
c) $k=1$ or $k=-2$
d) $k=1$ : plane; $k=-2$ : line $t(1, 1, 1)$
e) $X_1+\lambda(X_2-X_1)$ : infinitely many

a)

Whatever $A$ is, the zero vector satisfies $A\cdot 0=0$ . A homogeneous system therefore always has at least the solution $X=0$ , that is $x=y=z=0$ , called the TRIVIAL solution. A homogeneous system can thus never be inconsistent: the three general cases shrink to two here, either the trivial solution is the only one, or there are infinitely many.

Reading it on the row reduction: the column of constants is zero at the start, and it stays zero through every elementary operation, since any combination of zeros is zero. A row of the form $[0\ 0\ 0\,|\,c]$ with $c\neq 0$ can therefore never appear.

b)

The homogeneous system has nontrivial solutions if and only if $\det(A)=0$ .

Justification. If $\det(A)\neq 0$ , then $A$ is invertible, and $AX=0$ can be multiplied by $A^{-1}$ : $X=A^{-1}\cdot 0=0$ . The trivial solution is then the ONLY one. Conversely, if $\det(A)=0$ , the matrix is not invertible, row reduction produces fewer pivots than unknowns, so at least one free parameter appears; giving this parameter a nonzero value yields a nontrivial solution.

An equivalent reading in terms of sets of vectors: $\det(A)=0$ means that the columns of $A$ are linearly dependent, and a dependence relation among the columns is exactly a nontrivial solution of $AX=0$ . The two chapters say the same thing.

c)

Compute the determinant by cofactor expansion along the first row: $\det=k(k^{2}-1)-1(k-1)+1(1-k)=k^{3}-k-k+1+1-k=k^{3}-3k+2$ .

Look for an obvious root: for $k=1$ , $1-3+2=0$ . So factor out $k-1$ : $k^{3}-3k+2=(k-1)(k^{2}+k-2)=(k-1)(k-1)(k+2)=(k-1)^{2}(k+2)$ .

The determinant vanishes for $k=1$ (double root) and $k=-2$ . These are the only two values that give nontrivial solutions.

d)

For $k=1$ , the three equations become identical and reduce to $x+y+z=0$ . A single pivot remains for three unknowns, so $3-1=2$ free parameters. Setting $y=s$ and $z=t$ gives $x=-s-t$ , and the solution set is $\{(-s-t, s, t)\ :\ s,t\in\mathbb{R}\}$ . Geometrically, it is a PLANE through the origin. The double root of the determinant shows up here as the loss of two pivots instead of one.

For $k=-2$ , the system reads $\begin{cases} -2x+y+z=0 \\ x-2y+z=0 \\ x+y-2z=0 \end{cases}$ . Subtracting the second equation from the first: $-3x+3y=0$ , so $x=y$ . Subtracting the third from the second: $-3y+3z=0$ , so $y=z$ . Hence $x=y=z$ , and setting $z=t$ gives $\{(t, t, t)\ :\ t\in\mathbb{R}\}$ , with a single parameter. Check on the first equation: $-2t+t+t=0$ , correct. Geometrically, it is a LINE through the origin, with direction vector $(1, 1, 1)$ .

A point to remember: in both cases, the solution set contains the origin. That is a feature of homogeneous systems, and it sets them apart from general systems, whose solution set is a line or a plane that does not necessarily pass through the origin.

e)

Let $X_{1}$ and $X_{2}$ be two distinct solutions, so $AX_{1}=B$ and $AX_{2}=B$ with $X_{1}\neq X_{2}$ . For any real number $\lambda$ , set $X_{\lambda}=X_{1}+\lambda(X_{2}-X_{1})$ .

Compute: $AX_{\lambda}=AX_{1}+\lambda\big(AX_{2}-AX_{1}\big)=B+\lambda(B-B)=B+\lambda\cdot 0=B$ . So $X_{\lambda}$ is a solution for EVERY real number $\lambda$ .

Moreover, these solutions are pairwise distinct: if $X_{\lambda}=X_{\mu}$ , then $(\lambda-\mu)(X_{2}-X_{1})=0$ , and since $X_{2}-X_{1}\neq 0$ by hypothesis, we must have $\lambda=\mu$ . Each real number $\lambda$ therefore gives a different solution: the system has infinitely many.

Along the way, this result proves that there can never be exactly two, or exactly three, solutions. The number of solutions of a linear system is always $0$ , $1$ or infinite, and this proof explains why any case in between is impossible. Geometrically, the formula $X_{1}+\lambda(X_{2}-X_{1})$ is the parametric equation of the line through the two solutions: as soon as two solutions exist, the whole line joining them is made of solutions.

Exercise 7: Problem: full discussion of a system with two parameters

For real numbers $a$ and $b$ , consider the system $\begin{cases} x+2y+z=1 \\ 2x+5y+3z=4 \\ 3x+7y+az=b \end{cases}$ .

The goal is to determine, according to the values of $a$ and $b$ , the number of solutions of the system, then to compute them in each case. It is the most common exercise format at the end of the chapter, and the one where the most marks are lost by forgetting a case.

a) Write the augmented matrix and row reduce it in terms of $a$ and $b$ . Be careful never to divide by an expression that can be zero.
b) For which values of $a$ and $b$ does the system have a unique solution?
c) For which values does the system have no solution? Interpret geometrically.
d) For which values does it have infinitely many solutions? Give the solution set in parametric form.
e) Solve the system completely for $a=5$ and $b=7$ .
f) Compute the determinant of the coefficient matrix in terms of $a$ , and explain why it gives back exactly the condition found in b).

Show the solution

Answers

a) Last row $(0, 0, a-4\,|\,b-5)$
b) $a\neq 4$
c) $a=4$ , $b\neq 5$
d) $a=4$ , $b=5$ : $(t-3, 2-t, t)$
e) $(-1, 0, 2)$
f) $\det A=a-4$

a)

Augmented matrix: $\left[\begin{array}{ccc|c} 1 & 2 & 1 & 1 \\ 2 & 5 & 3 & 4 \\ 3 & 7 & a & b \end{array}\right]$ . The top-left pivot is $1$ and depends on no parameter, so it can be used without precaution.

$R_{2}\to R_{2}-2R_{1}$ gives $(0, 1, 1\,|\,2)$ . $R_{3}\to R_{3}-3R_{1}$ gives $(0, 1, a-3\,|\,b-3)$ .

The second pivot is $1$ , and it does not depend on the parameters either. $R_{3}\to R_{3}-R_{2}$ gives $(0, 0, a-3-1\,|\,b-3-2)=(0, 0, a-4\,|\,b-5)$ .

The row echelon form is $\left[\begin{array}{ccc|c} 1 & 2 & 1 & 1 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & a-4 & b-5 \end{array}\right]$ . The whole discussion now plays out on the last row, which reads $(a-4)z=b-5$ . A key point of method: we never divided by $a-4$ , we only subtracted. Dividing a row by a parametric expression without discussing whether it is zero is the error that costs the whole question, because it silently assumes $a\neq 4$ and skips the most interesting case.

b)

If $a-4\neq 0$ , that is $a\neq 4$ , we may divide and get $z=\dfrac{b-5}{a-4}$ . There are then three pivots for three unknowns, so a UNIQUE SOLUTION, whatever the value of $b$ .

Work upward to get it in general. The second row gives $y=2-z$ . The first gives $x=1-2y-z=1-2(2-z)-z=1-4+2z-z=z-3$ . The unique solution is therefore $\left(\dfrac{b-5}{a-4}-3, 2-\dfrac{b-5}{a-4}, \dfrac{b-5}{a-4}\right)$ .

c)

If $a=4$ , the last row becomes $0z=b-5$ . When $b\neq 5$ , this equation reads $0=b-5$ with $b-5\neq 0$ : it is impossible. The system has NO solution for $a=4$ and $b\neq 5$ .

Geometric interpretation: the three planes have no point common to all three. Here the first two planes do meet along a line, but the third plane is parallel to that line without containing it. The configuration is a prism: the planes meet pairwise along three distinct parallel lines, with no point common to all three.

d)

If $a=4$ AND $b=5$ , the last row becomes $0=0$ , an equation that is always true and carries no information. The system is consistent with two pivots for three unknowns, so $3-2=1$ free parameter: it has INFINITELY many solutions.

Set $z=t$ . The second row gives $y+t=2$ , so $y=2-t$ . The first gives $x+2(2-t)+t=1$ , that is $x+4-2t+t=1$ , so $x=t-3$ . The solution set is $\{(t-3, 2-t, t)\ :\ t\in\mathbb{R}\}$ .

Check for $t=0$ , that is $(-3, 2, 0)$ : equation 1, $-3+4+0=1$ , correct; equation 2, $-6+10+0=4$ , correct; equation 3 with $a=4$ , $-9+14+0=5=b$ , correct. Geometrically, the three planes meet along a line with direction vector $(1, -1, 1)$ , read off the coefficients of $t$ .

e)

For $a=5$ and $b=7$ , we are in the case $a\neq 4$ , so there is a unique solution. The last row gives $(5-4)z=7-5$ , that is $z=2$ . Then $y=2-z=0$ , and $x=z-3=-1$ .

Check in the original system: equation 1, $-1+0+2=1$ , correct; equation 2, $-2+0+6=4$ , correct; equation 3, $3(-1)+7(0)+5(2)=-3+10=7$ , correct. The solution is $(-1, 0, 2)$ .

f)

$\det(A)=\begin{vmatrix} 1 & 2 & 1 \\ 2 & 5 & 3 \\ 3 & 7 & a \end{vmatrix}=1(5a-21)-2(2a-9)+1(14-15)=5a-21-4a+18-1=a-4$ .

The determinant is exactly $a-4$ , which is precisely the last pivot obtained by row reduction. This is no coincidence: the elementary operations used here, which consist only of adding a multiple of one row to another, do NOT change the determinant. The determinant of the echelon matrix is therefore equal to that of $A$ , and for a triangular matrix it is the product of the diagonal entries, that is $1\times 1\times(a-4)=a-4$ .

The condition $\det(A)\neq 0$ , that is $a\neq 4$ , is therefore exactly the same as the unique-solution condition found in b). The two approaches, row reduction and determinant, necessarily agree.

What the determinant does NOT say, on the other hand, deserves emphasis. It settles the unique solution, but when it is zero it is silent about what comes next: it does not distinguish the case $b\neq 5$ (no solution) from the case $b=5$ (infinitely many), since it does not even depend on $b$ . Only row reduction of the AUGMENTED matrix, which carries the right-hand side, separates these two cases. That is why Cramer's rule becomes unusable as soon as the determinant is zero, and why a full discussion always goes through Gauss.

Exercise 8: The structure of the solution set

When a system $AX=B$ has infinitely many solutions, they are not scattered at random: they are organized around one particular solution. This exercise establishes the structure $X=X_{p}+X_{h}$ , where $X_{p}$ is a particular solution and $X_{h}$ runs through the solutions of the associated homogeneous system.

a) Prove that if $X_{p}$ is a solution of $AX=B$ and $X_{h}$ a solution of $AX=0$ , then $X_{p}+X_{h}$ is a solution of $AX=B$ . Prove the converse: every solution of $AX=B$ can be written $X_{p}+X_{h}$ for some $X_{h}$ that solves the homogeneous system.
b) Consider the system $\begin{cases} x+y+z=6 \\ x+2y+3z=14 \\ 2x+3y+4z=20 \end{cases}$ . Check that $X_{p}=(-2, 8, 0)$ is a solution, then solve the associated homogeneous system.
c) Write the general solution in the form $X_{p}+t\,X_{h}$ , and compare it with the parametric form $(t-2, 8-2t, t)$ obtained by direct row reduction.
d) Interpret geometrically: why does the solution set of the homogeneous system always pass through the origin, while that of the full system, in general, does not? What does $X_{p}$ represent in this picture?

Show the solution

Answers

a) $A(X_p+X_h)=B$ , and the converse
b) $X_h=t(1, -2, 1)$
c) $(-2, 8, 0)+t(1, -2, 1)$ : same set
d) Line translated by $X_p$

a)

Forward direction. Suppose $AX_{p}=B$ and $AX_{h}=0$ . Then, by linearity of the matrix product, $A(X_{p}+X_{h})=AX_{p}+AX_{h}=B+0=B$ . So $X_{p}+X_{h}$ is indeed a solution of $AX=B$ . Converse. Let $X$ be any solution of $AX=B$ . Set $X_{h}=X-X_{p}$ . Then $AX_{h}=A(X-X_{p})=AX-AX_{p}=B-B=0$ , so $X_{h}$ solves the homogeneous system. Writing $X=X_{p}+X_{h}$ expresses $X$ in the required form. Together, the two directions show that the solution set of $AX=B$ is EXACTLY the set of all $X_{p}+X_{h}$ as $X_{h}$ runs through the homogeneous solutions.

b)

Check of $X_{p}=(-2, 8, 0)$ : equation 1, $-2+8+0=6$ , correct; equation 2, $-2+16+0=14$ , correct; equation 3, $-4+24+0=20$ , correct. It is indeed a solution. Associated homogeneous system: $\begin{cases} x+y+z=0 \\ x+2y+3z=0 \\ 2x+3y+4z=0 \end{cases}$ . With $R_{2}\to R_{2}-R_{1}$ we get $y+2z=0$ , and $R_{3}\to R_{3}-2R_{1}$ gives $y+2z=0$ , the same row. Two pivots remain for three unknowns, so one free parameter. Setting $z=t$ , we get $y=-2t$ and $x=-y-z=2t-t=t$ . The set of homogeneous solutions is $\{t(1, -2, 1)\ :\ t\in\mathbb{R}\}$ .

c)

The general solution is therefore $X=X_{p}+t\,X_{h}=(-2, 8, 0)+t(1, -2, 1)=(-2+t, 8-2t, t)$ . The parametric form obtained by direct row reduction was $(t-2, 8-2t, t)$ : it is exactly the same set, since $-2+t=t-2$ . The two approaches agree, but the form $X_{p}+t\,X_{h}$ says more: it visibly separates the fixed part, a particular solution, from the moving part, which describes every direction along which you can move without leaving the solution set.

d)

The homogeneous system $AX=0$ always has the trivial solution $X=0$ : its solution set therefore contains the origin, and here it is a line through $O$ with direction vector $(1, -2, 1)$ . The solution set of the full system, for its part, is that same line TRANSLATED by the vector $X_{p}$ : it has the same direction $(1, -2, 1)$ , but it is shifted and no longer passes through the origin, except in the special case $B=0$ . That is the geometric meaning of the decomposition: $X_{h}$ gives the DIRECTION of the solution set, a subspace through the origin, and $X_{p}$ gives the TRANSLATION that puts it in the right place. We say that the solution set of a consistent system is an AFFINE subspace, that is, a shifted subspace. Choosing another particular solution does not change this set: it only amounts to locating the same object from another one of its points.

Exercise 9: Interpolation: the parabola through three points

Making a curve pass through prescribed points translates into a linear system whose unknowns are the coefficients of the curve. That is the principle of interpolation, which is everywhere in numerical computing. Here we look for the parabola $y=ax^{2}+bx+c$ .

a) Write the linear system in the unknowns $a$ , $b$ , $c$ expressing that the parabola passes through the points $(1, 2)$ , $(2, 3)$ and $(3, 6)$ .
b) Solve this system and give the equation of the parabola.
c) The determinant of the coefficient matrix is a Vandermonde determinant. Compute it and show that it is nonzero as soon as the three $x$ -coordinates are distinct. What does this guarantee about the existence and uniqueness of the parabola?
d) Now require the curve to pass through $(0, 1)$ , $(1, 3)$ and $(2, 5)$ , three COLLINEAR points. Solve and interpret the value found for $a$ . Does the system still have a unique solution?

Show the solution

Answers

a) $a+b+c=2$ , $4a+2b+c=3$ , $9a+3b+c=6$
b) $y=x^2-2x+3$
c) Determinant $-2$ : unique parabola
d) $y=2x+1$ : $a=0$ , unique solution

a)

Saying that the parabola $y=ax^{2}+bx+c$ passes through a point $(x_{0}, y_{0})$ means imposing $ax_{0}^{2}+bx_{0}+c=y_{0}$ . Substituting each $x$ -coordinate, the three points give $\begin{cases} a(1)^{2}+b(1)+c=2 \\ a(2)^{2}+b(2)+c=3 \\ a(3)^{2}+b(3)+c=6 \end{cases}$ , that is $\begin{cases} a+b+c=2 \\ 4a+2b+c=3 \\ 9a+3b+c=6 \end{cases}$ . The unknowns are the coefficients $a$ , $b$ , $c$ , not the points, which are data. Three points, three equations, three unknowns: interpolation IS a linear system, nothing more and nothing less.

b)

Eliminate $c$ by taking differences. The second equation minus the first: $3a+b=1$ . The third minus the second: $5a+b=3$ . Subtracting these two relations: $2a=2$ , so $a=1$ . Then $b=1-3a=1-3=-2$ , and $c=2-a-b=2-1+2=3$ . The parabola is $y=x^{2}-2x+3$ . Check on the three points: at $x=1$ , $1-2+3=2$ ; at $x=2$ , $4-4+3=3$ ; at $x=3$ , $9-6+3=6$ . All three points lie on it.

c)

The coefficient matrix is $\begin{pmatrix} 1 & 1 & 1 \\ 4 & 2 & 1 \\ 9 & 3 & 1 \end{pmatrix}$ , whose rows are built on the powers of the $x$ -coordinates $x_{1}=1$ , $x_{2}=2$ , $x_{3}=3$ : it is a Vandermonde matrix. Its determinant factors, up to sign, into the product of the differences of the $x$ -coordinates: with the columns ordered from $x^{2}$ down to $1$ , the reverse of the usual Vandermonde matrix, $\det=-(x_{2}-x_{1})(x_{3}-x_{1})(x_{3}-x_{2})=-(2-1)(3-1)(3-2)=-2$ . Direct check: $1(2-3)-1(4-9)+1(12-18)=-2$ . This product is nonzero as soon as the three $x$ -coordinates are DISTINCT, since each factor is then nonzero. A nonzero determinant guarantees that the system has a unique solution: there is therefore one parabola, and only one, through three points with distinct $x$ -coordinates. This is the fundamental result of polynomial interpolation: $n+1$ points with distinct $x$ -coordinates determine a unique polynomial of degree at most $n$ .

d)

The system becomes $\begin{cases} c=1 \\ a+b+c=3 \\ 4a+2b+c=5 \end{cases}$ . From the first, $c=1$ . The second gives $a+b=2$ , the third $4a+2b=4$ , that is $2a+b=2$ . Subtracting, $a=0$ , then $b=2$ . The solution is $a=0$ , $b=2$ , $c=1$ , which gives $y=2x+1$ : a LINE. The value $a=0$ shows that the parabola degenerates into a line, which was to be expected since the three points lie on the line of slope $2$ . The system still has a UNIQUE solution: the $x$ -coordinates $0$ , $1$ , $2$ are distinct, so the Vandermonde determinant $-(1-0)(2-0)(2-1)=-2$ is still nonzero, and uniqueness is guaranteed. Three points with distinct $x$ -coordinates always determine a unique polynomial of degree at most $2$ ; this polynomial is a true parabola if and only if the points are not collinear, otherwise the leading coefficient $a$ is zero.

Exercise 10: Problem: balancing a chemical equation with a homogeneous system

Balancing a chemical reaction means finding the coefficients that conserve each type of atom. The problem translates into a HOMOGENEOUS linear system, whose solution set shows why a reaction can always be balanced, and only up to a multiplicative constant. We balance the combustion of propane: $x_{1}\,\mathrm{C_{3}H_{8}}+x_{2}\,\mathrm{O_{2}}\rightarrow x_{3}\,\mathrm{CO_{2}}+x_{4}\,\mathrm{H_{2}O}$ .

a) By writing the conservation of carbon, hydrogen and oxygen, set up the homogeneous system of three equations satisfied by $x_{1}$ , $x_{2}$ , $x_{3}$ , $x_{4}$ .
b) Solve this system. How many free parameters does it have, and why was that predictable?
c) Find the smallest positive integer coefficients and write the balanced equation. Check the conservation of each atom.
d) Explain why the system necessarily has nontrivial solutions, and what physical meaning the free parameter carries.

Show the solution

Answers

a) $3x_1=x_3$ , $8x_1=2x_4$ , $2x_2=2x_3+x_4$
b) $t(1, 5, 3, 4)$ : one parameter
c) $C_3H_8+5\,O_2\to 3\,CO_2+4\,H_2O$
d) More unknowns than equations; scale

a)

Write the conservation atom by atom. Carbon: propane $\mathrm{C_{3}H_{8}}$ brings in $3x_{1}$ carbon atoms, the $\mathrm{CO_{2}}$ carries away $x_{3}$ , hence $3x_{1}=x_{3}$ . Hydrogen: $\mathrm{C_{3}H_{8}}$ brings in $8x_{1}$ atoms, the water $\mathrm{H_{2}O}$ carries away $2x_{4}$ , hence $8x_{1}=2x_{4}$ . Oxygen: the $\mathrm{O_{2}}$ brings in $2x_{2}$ atoms, shared between $2x_{3}$ in the $\mathrm{CO_{2}}$ and $x_{4}$ in the water, hence $2x_{2}=2x_{3}+x_{4}$ . The homogeneous system, with every term moved to the left, is $\begin{cases} 3x_{1}-x_{3}=0 \\ 8x_{1}-2x_{4}=0 \\ 2x_{2}-2x_{3}-x_{4}=0 \end{cases}$ .

b)

Express everything in terms of $x_{1}$ . The first equation gives $x_{3}=3x_{1}$ . The second gives $x_{4}=4x_{1}$ . The third gives $2x_{2}=2x_{3}+x_{4}=6x_{1}+4x_{1}=10x_{1}$ , so $x_{2}=5x_{1}$ . Setting $x_{1}=t$ , we get the family of solutions $(x_{1}, x_{2}, x_{3}, x_{4})=(t, 5t, 3t, 4t)=t(1, 5, 3, 4)$ . There is ONE free parameter. That was predictable: the system has four unknowns for only three equations, so at least $4-3=1$ unknown stays free. A homogeneous system with more unknowns than equations always has nontrivial solutions.

c)

The family $t(1, 5, 3, 4)$ gives positive integer coefficients for every positive integer $t$ ; the smallest correspond to $t=1$ , that is $(x_{1}, x_{2}, x_{3}, x_{4})=(1, 5, 3, 4)$ . The balanced equation is $\mathrm{C_{3}H_{8}}+5\,\mathrm{O_{2}}\rightarrow 3\,\mathrm{CO_{2}}+4\,\mathrm{H_{2}O}$ . Check atom by atom: carbon, $3$ on the left ( $3\times 1$ ) and $3$ on the right ( $3\times 1$ ); hydrogen, $8$ on the left ( $8\times 1$ ) and $8$ on the right ( $4\times 2$ ); oxygen, $10$ on the left ( $5\times 2$ ) and $10$ on the right ( $3\times 2+4\times 1$ ). Every type of atom is conserved: the equation is balanced.

d)

The system is homogeneous, so it always has the trivial solution $x_{1}=x_{2}=x_{3}=x_{4}=0$ , which obviously makes no chemical sense. But it ALSO has nontrivial solutions, and necessarily so, for a structural reason: with four unknowns and only three equations, the row echelon form can have at most three pivots, which leaves at least one unknown free; the rank is strictly less than the number of unknowns, which guarantees infinitely many solutions. In other words, a reaction involves more species than distinct elements, and this inequality ensures that a nontrivial balancing exists. The physical meaning of the free parameter is the SCALE of the reaction: multiplying every coefficient by the same factor describes the same reaction carried out in a larger or smaller quantity. Chemistry fixes the proportions, not the absolute quantities, and that is exactly what the line of solutions $t(1, 5, 3, 4)$ expresses. By convention we choose the smallest integers, but every point of this line describes the same transformation.

Exercise 11: A zero pivot and a row interchange

Consider the system $\begin{cases} y+2z=8 \\ x+y+z=6 \\ 2x+y-z=1 \end{cases}$ .

a) Write the augmented matrix. Why can't the elimination start with the top-left entry?
b) Interchange the first two rows, then reduce the matrix to row echelon form.
c) Solve the system and check the solution.
d) Compute the determinant of the coefficient matrix before and after the interchange. What does the interchange change, and what does it leave unchanged?
e) If the whole first column had been zero below the diagonal, with a zero at the top as well, what would you have had to conclude about the unknown $x$ ?

Show the solution

Answers

a) Zero pivot
b) $R_1\leftrightarrow R_2$ ; last row $(0, 0, -1\,|\,-3)$
c) $(1, 2, 3)$
d) $1$ then $-1$ : sign changed
e) $x$ is a free parameter

a)

$\left[\begin{array}{ccc|c} 0 & 1 & 2 & 8 \\ 1 & 1 & 1 & 6 \\ 2 & 1 & -1 & 1 \end{array}\right]$ . The top-left entry is zero: no multiple of the first row can clear the $1$ or the $2$ below it. A pivot must be NONZERO.

b)

$R_{1}\leftrightarrow R_{2}$ gives $\left[\begin{array}{ccc|c} 1 & 1 & 1 & 6 \\ 0 & 1 & 2 & 8 \\ 2 & 1 & -1 & 1 \end{array}\right]$ . Then $R_{3}\to R_{3}-2R_{1}$ gives $(0, -1, -3\,|\,-11)$ , and $R_{3}\to R_{3}+R_{2}$ gives $(0, 0, -1\,|\,-3)$ .

c)

$-z=-3$ , so $z=3$ ; $y+6=8$ , so $y=2$ ; $x+2+3=6$ , so $x=1$ . Check: $2+6=8$ , $1+2+3=6$ and $2+2-3=1$ .

d)

Before: $0(-1-1)-1(-1-2)+2(1-2)=3-2=1$ . After the interchange, the determinant is $-1$ : interchanging two rows changes its SIGN. The solution set, on the other hand, does not change, since we only rewrote the same equations in a different order.

e)

A column with no possible pivot at all means that the unknown $x$ appears in no equation: if the system is consistent, $x$ is a free parameter, and there is no unique solution.

The thread: a zero pivot is bypassed by a row interchange, which does not change the solutions but changes the sign of the determinant.

Exercise 12: A system of four equations by Gaussian elimination

Consider the system $\begin{cases} x+y+z+w=10 \\ x-y+z-w=-2 \\ 2x+y-z+w=5 \\ x+2y+3z-w=10 \end{cases}$ .

a) Eliminate $x$ from the last three equations using the first. Write the three rows you obtain.
b) Continue the reduction up to a triangular form.
c) Solve the system by back substitution.
d) Check the solution in the four original equations.
e) What is the rank of the coefficient matrix? How many solutions does the system have?

Show the solution

Answers

a) $(0, -2, 0, -2\,|\,-12)$ , $(0, -1, -3, -1\,|\,-15)$ , $(0, 1, 2, -2\,|\,0)$
b) Pivots $1$ , $1$ , $-3$ , $-9$
c) $(1, 2, 3, 4)$
d) All four equations satisfied
e) Rank 4: unique solution

a)

$R_{2}\to R_{2}-R_{1}$ : $(0, -2, 0, -2\,|\,-12)$ . $R_{3}\to R_{3}-2R_{1}$ : $(0, -1, -3, -1\,|\,-15)$ . $R_{4}\to R_{4}-R_{1}$ : $(0, 1, 2, -2\,|\,0)$ .

b)

Divide $R_{2}$ by $-2$ : $(0, 1, 0, 1\,|\,6)$ . Then $R_{3}\to R_{3}+R_{2}$ : $(0, 0, -3, 0\,|\,-9)$ and $R_{4}\to R_{4}-R_{2}$ : $(0, 0, 2, -3\,|\,-6)$ . Finally $R_{4}\to 3R_{4}+2R_{3}$ : $(0, 0, 0, -9\,|\,-36)$ .

c)

$-9w=-36$ , so $w=4$ . $-3z=-9$ , so $z=3$ . $y+w=6$ , so $y=2$ . $x+y+z+w=10$ , so $x=1$ . The solution is $(1, 2, 3, 4)$ .

d)

$1+2+3+4=10$ ; $1-2+3-4=-2$ ; $2+2-3+4=5$ ; $1+4+9-4=10$ . All four equations are satisfied.

e)

The row echelon form has four pivots, $1$ , $1$ , $-3$ and $-9$ : the rank is $4$ , equal to the number of unknowns, and the solution is unique. The method is the same as in dimension 3, with one more step; multiplying a row by $3$ to avoid fractions is allowed, provided you never multiply by zero.

The thread: whatever the size, Gaussian elimination clears one unknown per column, and the number of pivots decides the number of solutions.

Exercise 13: The LU decomposition

Consider $A=\begin{pmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 8 & 7 & 9 \end{pmatrix}$ . Reducing $A$ to row echelon form without row interchanges amounts to writing $A=LU$ , with $U$ upper triangular, the echelon form, and $L$ lower triangular, with $1$ s on its diagonal, which stores the multipliers used.

a) Reduce $A$ to row echelon form, recording each multiplier, and give $U$ .
b) Write $L$ by placing each multiplier in the position of the entry it cleared, then check that $LU=A$ on the last row.
c) Deduce $\det A$ .
d) Solve $AX=B$ with $B=\begin{pmatrix} 4 \\ 10 \\ 24 \end{pmatrix}$ in two stages: $LY=B$ by forward substitution, then $UX=Y$ by back substitution.
e) Why is this decomposition worthwhile when many systems must be solved with the same matrix $A$ ?

Show the solution

Answers

a) $U=\begin{pmatrix}2&1&1\\0&1&1\\0&0&2\end{pmatrix}$
b) $L=\begin{pmatrix}1&0&0\\2&1&0\\4&3&1\end{pmatrix}$
c) $\det A=4$
d) $Y=(4, 2, 2)$ , $X=(1, 1, 1)$
e) Row reduction done once

a)

$R_{2}\to R_{2}-2R_{1}$ gives $(0, 1, 1)$ , multiplier $2$ . $R_{3}\to R_{3}-4R_{1}$ gives $(0, 3, 5)$ , multiplier $4$ . $R_{3}\to R_{3}-3R_{2}$ gives $(0, 0, 2)$ , multiplier $3$ . So $U=\begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 2 \end{pmatrix}$ .

b)

$L=\begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 4 & 3 & 1 \end{pmatrix}$ . Last row of $LU$ : $(4\cdot 2, 4\cdot 1+3\cdot 1, 4\cdot 1+3\cdot 1+1\cdot 2)=(8, 7, 9)$ , which is indeed the last row of $A$ .

c)

$\det A=\det L\times\det U=1\times(2\times 1\times 2)=4$ : the determinant of a triangular matrix is read off its diagonal.

d)

$LY=B$ : $y_{1}=4$ , $2y_{1}+y_{2}=10$ so $y_{2}=2$ , $4y_{1}+3y_{2}+y_{3}=24$ so $y_{3}=2$ . $UX=Y$ : $2z=2$ so $z=1$ , $y+z=2$ so $y=1$ , $2x+y+z=4$ so $x=1$ . The solution is $(1, 1, 1)$ , and indeed $A\begin{pmatrix}1\\1\\1\end{pmatrix}=\begin{pmatrix}4\\10\\24\end{pmatrix}$ .

e)

The row reduction, the expensive part, is done only once. Each new right-hand side then needs only one forward and one back substitution, two very fast triangular computations: that is how software solves large systems, rather than by computing $A^{-1}$ .

The thread: the matrix $L$ keeps a record of the row reduction; solving $AX=B$ becomes two triangular systems.

Exercise 14: Problem: the equilibrium temperature of a plate

A square plate is held at $100\ ^{\circ}\mathrm{C}$ along its top edge, at $0\ ^{\circ}\mathrm{C}$ along its bottom edge and at $50\ ^{\circ}\mathrm{C}$ along its left and right edges. We study four interior points arranged in a square: $T_{1}$ top left, $T_{2}$ top right, $T_{3}$ bottom left and $T_{4}$ bottom right.

At equilibrium, the temperature at each interior point is the average of the temperatures of its four neighbours: the two nearest points on the edge and the two adjacent interior points.

a) Write the equation satisfied by $T_{1}$ , then the other three.
b) Put the system in the form $AT=B$ and row reduce it.
c) Find the four temperatures.
d) Recover the result using the left-right symmetry of the plate.
e) Compute the average of the four temperatures. Why was it predictable?

Show the solution

Answers

a) $4T_1=150+T_2+T_3$ , and so on
b) Four pivots: unique solution
c) $T_1=T_2=62.5$ °C, $T_3=T_4=37.5$ °C
d) $3a-b=150$ , $-a+3b=50$
e) 50 °C

a)

The neighbours of $T_{1}$ are the top edge, $100$ , the left edge, $50$ , then $T_{2}$ and $T_{3}$ : $4T_{1}=150+T_{2}+T_{3}$ . Likewise $4T_{2}=150+T_{1}+T_{4}$ , $4T_{3}=50+T_{1}+T_{4}$ and $4T_{4}=50+T_{2}+T_{3}$ .

b)

$\left[\begin{array}{cccc|c} 4 & -1 & -1 & 0 & 150 \\ -1 & 4 & 0 & -1 & 150 \\ -1 & 0 & 4 & -1 & 50 \\ 0 & -1 & -1 & 4 & 50 \end{array}\right]$ . Without fractions: $R_{2}\to 4R_{2}+R_{1}$ gives $(0, 15, -1, -4\,|\,750)$ and $R_{3}\to 4R_{3}+R_{1}$ gives $(0, -1, 15, -4\,|\,350)$ ; then $R_{3}\to 15R_{3}+R_{2}$ gives $(0, 0, 224, -64\,|\,6\,000)$ and $R_{4}\to 15R_{4}+R_{2}$ gives $(0, 0, -16, 56\,|\,1\,500)$ ; finally $R_{4}\to 14R_{4}+R_{3}$ gives $(0, 0, 0, 720\,|\,27\,000)$ . Four nonzero pivots: the solution is unique.

c)

Back substitution: $720T_{4}=27\,000$ , so $T_{4}=37.5$ ; $224T_{3}=6\,000+64\times 37.5=8\,400$ , so $T_{3}=37.5$ ; $15T_{2}=750+37.5+4\times 37.5=937.5$ , so $T_{2}=62.5$ ; $4T_{1}=150+62.5+37.5$ , so $T_{1}=62.5$ . Check: $4\times 62.5=250=150+62.5+37.5$ and $4\times 37.5=150=50+62.5+37.5$ .

d)

The plate and its edge conditions are symmetric about the vertical axis, and the solution is unique: it is therefore symmetric, $T_{1}=T_{2}=a$ and $T_{3}=T_{4}=b$ . The system reduces to $3a-b=150$ and $-a+3b=50$ . The first gives $b=3a-150$ , then $-a+9a-450=50$ , that is $a=62.5$ and $b=37.5$ .

e)

$\frac{62.5+62.5+37.5+37.5}{4}=50\ ^{\circ}\mathrm{C}$ , the average of the four edges, $\frac{100+0+50+50}{4}$ . This is no accident: adding the four equations gives $4\sum T_{i}=400+2\sum T_{i}$ , so $\sum T_{i}=200$ . The method, repeated on grids of thousands of points, is the one used by heat-transfer software.

The thread: a local law, the average of the neighbours, produces a linear system; symmetry and uniqueness let you reduce the number of unknowns.

Exercise 15: Problem: an ill-conditioned system

Consider the system $\begin{cases} x+y=2 \\ x+1.001\,y=2.001 \end{cases}$ , which models two almost redundant measurements.

a) Solve the system.
b) Compute the determinant of the coefficient matrix.
c) A measurement error changes the right-hand side $2.001$ into $2.002$ . Solve the new system.
d) By what percentage did the right-hand side change, rounded to two decimal places? Compare with the change in the solution.
e) Interpret geometrically, and say what happens if the coefficient $1.001$ is rounded to $1.00$ .

Show the solution

Answers

a) $(1, 1)$
b) $0.001$
c) $(0, 2)$
d) $0.05$ % versus a completely changed solution
e) Almost parallel lines; rounded: no solution

a)

Subtracting the first equation from the second: $0.001\,y=0.001$ , so $y=1$ and $x=1$ .

b)

$\det=1\times 1.001-1\times 1=0.001$ : nonzero, so the solution is unique, but the determinant is tiny.

c)

$0.001\,y=0.002$ , so $y=2$ and $x=0$ . The solution moves from $(1, 1)$ to $(0, 2)$ .

d)

$\frac{0.001}{2.001}\approx 0.0005$ , that is about $0.05\ \%$ . The solution, however, changed completely: $x$ goes from $1$ to $0$ , $y$ doubles. A tiny error in the data produces a huge error in the result: the system is ILL-CONDITIONED.

e)

The two equations represent two almost parallel lines: their slopes, $-1$ and $-\frac{1}{1.001}$ , barely differ. Moving one of them very slightly makes their intersection point slide a long way along the lines. With $1.00$ , the lines become parallel: $x+y=2$ and $x+y=2.001$ no longer have any solution, and the system changes nature because of a rounding.

The thread: a determinant close to zero, relative to the coefficients, signals a solution that is very sensitive to measurement errors.

Corrected exercises: linear systems, Gauss and Gauss-Jordan (201-SN4-RE)

Course recap

Calculations: systems to solve

Exercise 0.1: Solve by Gaussian elimination: eight direct calculations

Part A: the basics (/50)

Exercise 1: Augmented matrix, elementary row operations and Gaussian elimination

Exercise 2: From Gauss to Gauss-Jordan: the reduced row echelon form

Exercise 3: The three cases: unique solution, no solution, infinitely many

Exercise 4: Inverting a matrix by Gauss-Jordan elimination

Exercise 5: Rank and the consistency theorem

Part B: exam level (/50)

Exercise 6: Homogeneous systems and nontrivial solutions

Exercise 7: Problem: full discussion of a system with two parameters

Exercise 8: The structure of the solution set

Exercise 9: Interpolation: the parabola through three points

Exercise 10: Problem: balancing a chemical equation with a homogeneous system

Part C: the classics (/50)

Exercise 11: A zero pivot and a row interchange

Exercise 12: A system of four equations by Gaussian elimination

Exercise 13: The LU decomposition

Exercise 14: Problem: the equilibrium temperature of a plate

Exercise 15: Problem: an ill-conditioned system

See also

Looking for a linear algebra tutor in Montreal?