Linear Algebra · Book or PDF

A First Course in Linear Algebra

A.G. Hamilton · Study material generated by AI from this edition. Not affiliated with the publisher.

Chapter 1 · pp. 10–19

Gaussian Elimination

This chapter introduces a standard, repeatable method for solving sets of simultaneous linear equations, however many there are. The method is called Gaussian elimination (the "GE process"). It is first done with full equations, then shortened by writing only the coefficients in an array and using row operations. The chapter also shows what can go wrong, and why some systems have no solution or many.

Linear equations and the idea of elimination

A linear equation has unknowns that appear only to the first power, and no two unknowns are multiplied together. So $2x + 3y = 5$ is linear, but $x^2 + y = 1$ and $xy = 4$ are not. To solve a set of simultaneous equations means to find every set of values for the unknowns that makes all the equations true at the same time (p. 10).

For two equations, you combine them so that one unknown disappears. For example, with $x + y = 3$ and $x - y = 1$ , adding gives $2x = 4$ , so $x = 2$ , and then $y = 1$ (p. 10).

For $n$ equations in $n$ unknowns the plan is the same:

Eliminate one unknown. This leaves $n-1$ equations in $n-1$ unknowns.
Repeat. Next you have $n-2$ equations in $n-2$ unknowns, and so on, until one equation in one unknown is left.
Substitute back to find the other unknowns.

With three equations, you get two equations in two unknowns, solve those, then put the answers into an original equation to find the first unknown. Only a few simple operations are used, again and again (pp. 10–12).

Why a fixed routine is needed

Doing elimination "by feel" gets harder as the number of unknowns grows, because there are many possible ways to proceed. Some systems also break the simple method. A system may be inconsistent (no solution at all) or may have many solutions. A computer needs an automatic procedure that copes with every case. Gaussian elimination is that procedure, and it works for small and large systems alike (p. 12). Later work shows that the only possible outcomes are one solution, no solution, or infinitely many solutions (pp. 12, 14).

The five stages for three equations

Gaussian elimination turns the system into a new system with the same solutions that is easy to read from the bottom up. For three equations in $x_1, x_2, x_3$ the stages are (pp. 11–12):

Divide equation 1 by the coefficient of $x_1$ . If that coefficient is zero, put a different equation first.
Subtract multiples of equation 1 from equations 2 and 3 to remove $x_1$ from them.
Divide equation 2 by the coefficient of $x_2$ . If it is zero, swap with equation 3.
Subtract a multiple of equation 2 from equation 3 to remove $x_2$ .
Divide equation 3 by the coefficient of $x_3$ .

Then back-substitute. The book's Example 1.3 ends with $x_3 = 2$ , then $x_2 = 1$ , then $x_1 = -2$ (p. 11).

A small example of my own:

$x_1 + x_2 + x_3 = 6$ , $\;2x_1 + x_2 - x_3 = 1$ , $\;x_1 - x_2 + 2x_3 = 5$ .

Stage 1: the coefficient of $x_1$ is already 1.
Stage 2: equation 2 minus 2 times equation 1 gives $-x_2 - 3x_3 = -11$ . Equation 3 minus equation 1 gives $-2x_2 + x_3 = -1$ .
Stage 3: divide equation 2 by $-1$ to get $x_2 + 3x_3 = 11$ .
Stage 4: add 2 times the new equation 2 to equation 3 to get $7x_3 = 21$ .
Stage 5: $x_3 = 3$ .

Back-substitution gives $x_2 = 11 - 9 = 2$ and $x_1 = 6 - 2 - 3 = 1$ .

Notice that after stage 1 the first equation never changes again, and after stage 3 the second equation is also fixed. The process works downward, and each equation reaches its final form in turn (pp. 12, 14).

Shortening the work with arrays

Writing every equation each time is wasteful. Instead, write an array of the coefficients and right-hand sides, leaving out the unknowns and equals signs. The system $x+y-z=4$ , $2x-y+3z=7$ , $4x+y+z=15$ becomes a 3-by-4 array (p. 14):

$\begin{array}{ccc|c} 1 & 1 & -1 & 4 \\ 2 & -1 & 3 & 7 \\ 4 & 1 & 1 & 15 \end{array}$

Operations on equations become elementary row operations on rows (p. 14):

interchange two rows;
multiply or divide a row by a number;
add or subtract a multiple of one row to or from another.

For example, "row 2 minus 2 times row 1" copies the step used in ordinary elimination. Because these operations do not change the solutions, the final array describes the same system.

Row-echelon form

The goal of the process is row-echelon form. In this form, the first non-zero entry of each row is 1, and that 1 lies to the right of the leading 1 in the row above. Any all-zero rows sit at the bottom. In a well-behaved square system, this gives 1s down the diagonal and a triangle of zeros in the lower left (pp. 14, 16). Example 1.7 reaches this shape for four equations in four unknowns (p. 16).

When the pivot is zero

At stage 3, the coefficient of $x_2$ may be zero. There are two cases.

A lower row has a non-zero entry there. Swap with it. By hand, choose the row that makes the arithmetic easiest, such as one whose entry is 1, as in Example 1.5 (pp. 14, 16).
No lower row has a non-zero entry there. Do nothing and move on to $x_3$ , as in Example 1.6. These systems are analysed in the next chapter (p. 16).

Partial pivoting is the fixed rule computers use. When a swap is needed, choose the row whose entry in that column is numerically largest, ignoring signs. For entries $0$ , $2$ , $-5$ , you would pick the row with $-5$ . The rule tells a computer exactly what to do, and it also gives more accurate answers when rounding errors occur, as they always do on computers. Small hand examples usually skip it (pp. 14, 16).

When the last unknown has a zero coefficient

In stage 5, the coefficient of $x_3$ in the last row may be zero. Then the system has either no solutions or infinitely many (pp. 14, 16).

No solutions. The last row reads $0\ 0\ 0\ |\ c$ with $c \neq 0$ . This says $0 = c$ , which is impossible, so the equations are inconsistent. Example 1.6 is of this kind. A simple case is $x + y = 1$ together with $x + y = 2$ .
Infinitely many solutions. The last row is all zeros, so one equation gave no new information. Fewer equations remain than unknowns, so you set one unknown equal to a parameter $t$ . In Example 2.1, the equations reduce to the single equation $x + 2y = 1$ . Setting $y = t$ gives $x = 1 - 2t$ , so every pair $(1-2t,\ t)$ works (p. 19).

In Example 1.4, if the last row has a zero coefficient but a non-zero right-hand side, you divide that row by the right-hand number, as stage 5 would otherwise fail (p. 14).

Check yourself

Which of these is not a linear equation, and why: $3x - y = 2$ , $x^2 + y = 1$ , $xy = 4$ ?
In the five-stage process for three equations, which stages involve dividing, and which involve subtracting a multiple of an equation?
Use elimination to solve $x + y = 5$ and $2x - y = 4$ .
A system reduces to the array rows $1\ 2\ |\ 3$ and $0\ 0\ |\ 4$ . What does this tell you about its solutions?
Why might a computer swap a zero pivot with the row whose entry is numerically largest, instead of any row with a non-zero entry?