3.3.1 Linear systems and Gaussian elimination

What a linear system is

A linear equation in the unknowns $x_1, \ldots, x_n$ multiplies each unknown by a number, adds the results and sets the sum equal to a number. There are no powers, roots or products of unknowns: $2x_1 - x_2 = 3$ is linear, $x_1 x_2 = 3$ is not.

A linear system is a set of linear equations that must all hold at once. A solution is a list of values for the unknowns that satisfies every equation.

Lesson 1.2.1 solved one already. The lines $y = -x + 7$ and $y = 2x + 1$ meet at $(2, 5)$ . Rename $x$ and $y$ as $x_1$ and $x_2$ , and bring the unknowns to the left:

\begin{aligned} x_1 + x_2 &= 7 \\ -2x_1 + x_2 &= 1 \end{aligned}

Lesson 3.2.1 multiplied a matrix by a vector: entry $i$ of $A\mathbf{x}$ is row $i$ of $A$ times $\mathbf{x}$ . So the whole system is one matrix equation:

\begin{pmatrix} 1 & 1 \\ -2 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 7 \\ 1 \end{pmatrix}

Rule: A linear system

A\mathbf{x} = \mathbf{b}

$A$ is the coefficient matrix, with one row per equation and one column per unknown. $\mathbf{x}$ is the vector of unknowns and $\mathbf{b}$ the right-hand side. Row $i$ of $A\mathbf{x} = \mathbf{b}$ is equation $i$ .

Two pictures of one system

The row picture. Each equation is a line in the plane of $x_1$ and $x_2$ . A solution lies on both lines, so it is the point where they meet: $(2, 5)$ .

The column picture. Lesson 3.2.1 also read $A\mathbf{x}$ as a linear combination of the columns of $A$ (lesson 3.1.1). The columns of $A$ are $\mathbf{a}_1 = (1, -2)$ and $\mathbf{a}_2 = (1, 1)$ , each a column vector. The system asks: how much of each column adds up to $\mathbf{b}$ ?

2\begin{pmatrix} 1 \\ -2 \end{pmatrix} + 5\begin{pmatrix} 1 \\ 1 \end{pmatrix} = \begin{pmatrix} 7 \\ 1 \end{pmatrix}

Rule: The column picture

x_1\mathbf{a}_1 + x_2\mathbf{a}_2 + \cdots + x_n\mathbf{a}_n = \mathbf{b}

Solving $A\mathbf{x} = \mathbf{b}$ means finding the combination of the columns $\mathbf{a}_1, \ldots, \mathbf{a}_n$ of $A$ that gives $\mathbf{b}$ . The solution's entries are the amounts of each column.

The same system twice. As rows, two lines meet at $(2, 5)$ ; elimination swaps the second line for $x_2 = 5$ , dashed, through the same point. As columns, 2 of $\mathbf{a}_1$ and then 5 of $\mathbf{a}_2$ reach $\mathbf{b}$ .

With three unknowns, each equation is a flat plane in space and the row picture looks for the point on all three. The column picture combines three columns in $\mathbb{R}^3$ , the space of lists of three numbers. Lesson 3.3.2 shows what happens when the lines or planes do not meet in one point.

A

import numpy as np A = np.array([[1, 1], [-2, 1]]) b = np.array([7, 1]) x = np.array([2, 5]) print(A @ x) print(2 * A[:, 0] + 5 * A[:, 1]) print(np.linalg.solve(A, b))

⌘/Ctrl + Enter runs the cell

The augmented matrix and three row operations

Elimination works on the numbers alone. Write $\mathbf{b}$ as an extra column beside $A$ , behind a bar: this is the augmented matrix $[A \mid \mathbf{b}]$ . Each row is one equation.

\left(\begin{array}{cc|c} 1 & 1 & 7 \\ -2 & 1 & 1 \end{array}\right)

Write $R_1, R_2, \ldots$ for the rows. Three row operations change the equations without changing the solutions.

Rule: Row operations

\begin{gathered} R_i \leftrightarrow R_j \\[4pt] R_i \to c\,R_i,\ c \neq 0 \\[4pt] R_i \to R_i - m\,R_j \end{gathered}

Swap two rows; multiply a row by a number that is not 0; subtract a multiple of one row from another. Each can be undone, by the same kind of operation, so no solution is lost or gained.

To eliminate $x_1$ from the second equation, add 2 times row 1 to row 2. That is $R_2 \to R_2 - (-2)R_1$ . The new row 2 is $(-2 + 2, 1 + 2 \mid 1 + 14) = (0, 3 \mid 15)$ , which says $3x_2 = 15$ .

In the row picture, the second line has become the flat line $x_2 = 5$ . It still passes through $(2, 5)$ , because a row operation keeps the solutions: the dashed line in the figure.

Now solve from the bottom up. Row 2 gives $x_2 = 15 \div 3 = 5$ . Row 1 then gives $x_1 = 7 - x_2 = 2$ .

Try itM is the augmented matrix, made of decimals (dtype=float) so that its rows can hold fractions. M[1] is row 2: Python counts from 0.The row operation is one line. The last two lines solve from the bottom up.

import numpy as np M = np.array([[1, 1, 7], [-2, 1, 1]], dtype=float) M[1] = M[1] + 2 * M[0] print(M) x2 = M[1, 2] / M[1, 1] x1 = (M[0, 2] - M[0, 1] * x2) / M[0, 0] print(x1, x2)

⌘/Ctrl + Enter runs the cell

Elimination, pivots and back substitution

Elimination aims for row echelon form: a staircase of zeros below the diagonal. The first nonzero entry of each row is its pivot, and each pivot sits to the right of the pivot in the row above. Rows of zeros, if any, go at the bottom.

Work one column at a time, from left to right. Use the pivot to clear every entry below it.

Rule: One elimination step

\begin{gathered} m = \frac{\text{entry to clear}}{\text{pivot}} \\[4pt] R_i \to R_i - m\,R_{\text{pivot}} \end{gathered}

The multiplier $m$ is the entry below the pivot divided by the pivot. Subtracting $m$ times the pivot row puts a 0 in that place. Then back substitution solves the last equation first and works upwards.

A 3 × 3 example by hand

Solve this system:

\begin{aligned} x_1 + 2x_2 + x_3 &= 3 \\ 2x_1 + 5x_2 + 3x_3 &= 8 \\ 3x_1 + 4x_2 + 4x_3 &= 14 \end{aligned}

Its augmented matrix is

\left(\begin{array}{ccc|c} 1 & 2 & 1 & 3 \\ 2 & 5 & 3 & 8 \\ 3 & 4 & 4 & 14 \end{array}\right)

The first pivot is the 1 in the top left. Two steps clear column 1, and one more clears column 2 below the new pivot.

step	operation	multiplier	new row of $A$	new entry of $\mathbf{b}$
1	$R_2 - 2R_1$	$2 \div 1 = 2$	$0,\ 1,\ 1$	2
2	$R_3 - 3R_1$	$3 \div 1 = 3$	$0,\ -2,\ 1$	5
3	$R_3 - (-2)R_2$	$-2 \div 1 = -2$	$0,\ 0,\ 3$	9

The result is in row echelon form, with pivots 1, 1 and 3 on the diagonal:

\left(\begin{array}{ccc|c} 1 & 2 & 1 & 3 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & 3 & 9 \end{array}\right)

Back substitution reads it from the bottom:

\begin{aligned} x_3 &= 9 \div 3 = 3 \\ x_2 &= 2 - x_3 = -1 \\ x_1 &= 3 - 2x_2 - x_3 = 2 \end{aligned}

So $\mathbf{x} = (2, -1, 3)$ . Check it in the third original equation: $3(2) + 4(-1) + 4(3) = 14$ .

A

import numpy as np A = np.array([[1, 2, 1], [2, 5, 3], [3, 4, 4]]) b = np.array([3, 8, 14]) M = np.column_stack([A, b]).astype(float) M[1] -= 2 * M[0] M[2] -= 3 * M[0] M[2] -= -2 * M[1] print(M) x3 = M[2, 3] / M[2, 2] x2 = (M[1, 3] - M[1, 2] * x3) / M[1, 1] x1 = (M[0, 3] - M[0, 1] * x2 - M[0, 2] * x3) / M[0, 0] print(x1, x2, x3) print(A @ np.array([x1, x2, x3]))

⌘/Ctrl + Enter runs the cell

A zero pivot: swap rows

Sometimes the pivot place holds a 0, and dividing by it is impossible. Then swap in a row from below that has a nonzero entry in that column: the first row operation.

Take this system:

\left(\begin{array}{ccc|c} 1 & 2 & 1 & 3 \\ 2 & 4 & 3 & 8 \\ 1 & 3 & 2 & 4 \end{array}\right)

Clearing column 1 with $R_2 - 2R_1$ and $R_3 - R_1$ leaves a 0 where the second pivot should be:

\left(\begin{array}{ccc|c} 1 & 2 & 1 & 3 \\ 0 & 0 & 1 & 2 \\ 0 & 1 & 1 & 1 \end{array}\right)

Row 3 has a 1 in column 2, so swap rows 2 and 3. The matrix is then already in row echelon form. Back substitution gives $x_3 = 2$ , $x_2 = 1 - x_3 = -1$ and $x_1 = 3 - 2x_2 - x_3 = 3$ .

If every entry at and below the pivot place is 0, no swap helps: that column has no pivot. Lesson 3.3.2 shows that the system then has no solution or infinitely many.

(3, -1, 2)

import numpy as np M = np.array([[1, 2, 1, 3], [2, 4, 3, 8], [1, 3, 2, 4]], dtype=float) M[1] -= 2 * M[0] M[2] -= 1 * M[0] print(M[1, 1]) M[[1, 2]] = M[[2, 1]] print(M) print(np.linalg.solve(M[:, :3], M[:, 3]))

⌘/Ctrl + Enter runs the cell

A tiny pivot needs a swap too

A pivot that is not 0 but very small causes a different problem: rounding. A computer keeps about 16 significant digits (lesson 2.8.1), and a tiny pivot makes a huge multiplier.

Solve $10^{-20}x_1 + x_2 = 1$ and $x_1 + x_2 = 2$ . The answer is very close to $(1, 1)$ . With the pivot $10^{-20}$ , the multiplier is $10^{20}$ , and row 2 becomes $(0,\ 1 - 10^{20} \mid 2 - 10^{20})$ .

To 16 digits, both $1 - 10^{20}$ and $2 - 10^{20}$ round to $-10^{20}$ . So $x_2 = 1$ , and then row 1 gives $x_1 = (1 - 1) \div 10^{-20} = 0$ : wrong.

Swap the rows first and the multiplier is $10^{-20}$ instead. Nothing important is lost, and the answer is $(1, 1)$ .

Rule: Partial pivoting

\begin{gathered} \text{pivot} = \text{the largest } |a_{ic}| \\[4pt] \text{over the rows } i \ge c \end{gathered}

Before clearing column $c$ , swap up the row, at or below row $c$ , whose entry $a_{ic}$ in that column is largest in size. Every multiplier is then at most 1 in size, which keeps rounding errors small. It also takes care of zero pivots.

x_1 = 0

import numpy as np def two_by_two(M): M = M.astype(float) M[1] -= (M[1, 0] / M[0, 0]) * M[0] x2 = M[1, 2] / M[1, 1] x1 = (M[0, 2] - M[0, 1] * x2) / M[0, 0] return x1, x2 M = np.array([[1e-20, 1, 1], [1, 1, 2]]) print(*two_by_two(M)) print(*two_by_two(M[[1, 0]])) print(np.linalg.solve(M[:, :2], M[:, 2]))

⌘/Ctrl + Enter runs the cell

Solving with NumPy

np.linalg.solve(A, b) returns the solution of $A\mathbf{x} = \mathbf{b}$ for a square $A$ . NumPy passes the work to LAPACK, a library of compiled linear-algebra routines. Its routine runs this lesson's method: elimination with partial pivoting, then back substitution.

Lesson 3.2.3 could also solve the system as $A^{-1}\mathbf{b}$ , with np.linalg.inv. Computing the whole inverse takes more arithmetic than one elimination and adds rounding, so solve is the better choice.

When elimination finds a column with no pivot, solve stops with LinAlgError: Singular matrix, though rounding can hide a missing pivot (lesson 3.3.2). A matrix that is not square is refused too. Lesson 3.3.2 deals with both kinds of system, and case study 3.3.4 uses solve to copy one asset's payoff with others.

A\mathbf{x} - \mathbf{b}

import numpy as np A = np.array([[1, 2, 1], [2, 5, 3], [3, 4, 4]]) b = np.array([3, 8, 14]) x = np.linalg.solve(A, b) print(x) print(A @ x - b) try: np.linalg.solve(np.array([[1, 2], [2, 4]]), np.array([3, 5])) except np.linalg.LinAlgError as err: print("LinAlgError:", err)

⌘/Ctrl + Enter runs the cell

Common mistakes

Apply a row operation to the whole row, right-hand side included. Changing $A$ and not $\mathbf{b}$ solves a different system.
Watch the sign of the multiplier. To clear a $-2$ below a pivot of 1, $m = -2$ , so the step is $R_2 - (-2)R_1 = R_2 + 2R_1$ .
Never divide by a zero pivot. Swap in a row from below. If every entry below is 0 too, the column has no pivot (lesson 3.3.2).
Multiplying a row by 0 is not a row operation. It throws an equation away and can add false solutions.
Back-substitute from the bottom. The last row has one unknown; each row above adds one more.
A tiny pivot is a trap in code. Swap up the largest entry in size, as np.linalg.solve does.
Prefer solve(A, b) to inv(A) @ b, and check the answer by computing $A\mathbf{x} - \mathbf{b}$ .

Linear systems and elimination

0 of 11 correct

1.
Write $3x_1 - x_2 = 4$ , $x_1 + 2x_2 = 6$ as $A\mathbf{x} = \mathbf{b}$ . What is $a_{12}$ , the entry in row 1, column 2?
2.
Find $x_1$ in $x_1\begin{pmatrix} 1 \\ 2 \end{pmatrix} + x_2\begin{pmatrix} 1 \\ -1 \end{pmatrix} = \begin{pmatrix} 5 \\ 1 \end{pmatrix}$
3.
To clear the 6 below the pivot 2 in $\begin{pmatrix} 2 & 1 \\ 6 & 5 \end{pmatrix}$ , you subtract $m$ times row 1 from row 2. What is $m$ ?
4.
After that step, $R_2 - 3R_1$ , what is the new entry in row 2, column 2?
5.
Solve $2x_1 + x_2 = 4$ , $6x_1 + 5x_2 = 18$ by elimination. What is $x_2$ ?
6.
In the same system, $2x_1 + x_2 = 4$ with $x_2 = 3$ . What is $x_1$ ?
7.
Back-substitute: $x_1 + x_2 - x_3 = 2$ , $2x_2 + x_3 = 7$ , $4x_3 = 12$ . What is $x_1$ ?
8.
Solve $x_1 + x_2 + x_3 = 6$ , $x_2 + x_3 = 5$ , $x_1 + x_3 = 4$ . What is $x_2$ ?
9.
Which number may a row never be multiplied by?
10.
Partial pivoting on $\begin{pmatrix} 0 & 1 & 2 \\ 3 & 1 & 0 \\ -4 & 0 & 1 \end{pmatrix}$ : which row is swapped up to give the first pivot? Give its number
11.
Without a swap, eliminating below the pivot 0.001 in $\begin{pmatrix} 0.001 & 1 \\ 1 & 1 \end{pmatrix}$ uses which multiplier?

How to type answers

Powers with ^: x^7, 2^(1/3), a^-2.
Multiply with * or by writing side by side: 3x^2, 2(x+1).
ln(x) is the natural log, log(x, 2) is log base 2, e is Euler's number, sqrt(x) is a square root.
sin(x), cos(x) and tan(x) take radians; write pi for π and sin(x)^2 for sin²x.
Your first answer to each question is saved: it counts towards your score and brings the question back for review.
Exact answers like ln(20)/ln(3) are best. Decimals need about 4 significant figures.

A\mathbf{x} = \mathbf{b}

Linear systems and Gaussian elimination

What a linear system is

Rule: A linear system

Two pictures of one system

Rule: The column picture

The augmented matrix and three row operations

Rule: Row operations

Elimination, pivots and back substitution

Rule: One elimination step

A 3 × 3 example by hand

A zero pivot: swap rows

A tiny pivot needs a swap too

Rule: Partial pivoting

Solving with NumPy

Common mistakes

Linear systems and elimination

Summary card

Free further reading