Linear Algebra, Live
Strang §2.5 · Gauss-Jordan elimination

Gauss-Jordan: find A⁻¹ by elimination on [A | I]

Slide 2 gave a recipe for 2 by 2 inverses, and slide 3 showed that a chain of steps is undone by its own steps in reverse. Now we find the inverse of any square matrix, with the elimination from lesson 2. Picture a Rubik's cube. While you solve it, a friend writes down every move. The notes, read in order, take the scrambled cube back to solved. Gauss-Jordan elimination works the same way. Write A and the identity side by side as [A | I]. Do row steps until the left half becomes I, and do every step to the right half too. The right half keeps the record of all the steps, and that record is A⁻¹.

Lesson 3 · slide 4Gauss-Jordan
[ A  |  I ]  →  [ I  |  A⁻¹ ]
Key ideas
  1. Start with A and I written side by side: [A | I].
  2. Eliminate below the pivots, then above them, then divide each row by its pivot.
  3. When the left half becomes I, the right half is A⁻¹.
  4. If a zero row appears on the left, A has no inverse.
  5. To solve Ax = b, use elimination (A = LU), not A⁻¹: it is faster and more accurate.

Why the right half becomes A⁻¹

Each row step is a matrix E₁, E₂, and so on (lesson 2). Dividing a row by its pivot is a step matrix too: ½001 halves row 1 and keeps row 2. Multiply all the steps, last step on the left: E = ⋯E₃E₂E₁. The steps turn A into I, so EA = I, and that says E = A⁻¹. On the right, the same steps turn I into EI = E, which is A⁻¹. The right half is the friend's notebook.

The three stages

  • Forward: clear the entries below each pivot, as in lesson 2.
  • Backward: clear the entries above each pivot, from the bottom row up.
  • Scale: divide each row by its pivot, so the diagonal is all 1s.

Scaling doesn't disturb the zeros, so you can do it any time. Doing it last keeps the fractions away until the end. The finished left half, with pivots of 1 and zeros above and below them, is called the reduced row echelon form, rref for short. Lesson 4 uses it a lot. The lab's rref does all three stages.

A 2 by 2, step by step

Take slide 2's A = 2153. The pivot is 2 and the multiplier is ℓ = 5 ÷ 2 = 2.5. Each step below changes one row, and only the changed row is shown.

[A | I] = 21|1053|01
Forward: row 2 − 2.5·row 1 → 00.5|−2.51
Backward: row 2 now has 0.5 in column 2 and row 1 has 1 there, so the multiplier is 1 ÷ 0.5 = 2. Row 1 − 2·row 2 → 20|6−2
Scale: row 1 ÷ 2 → 10|3−1   row 2 ÷ 0.5 → 01|−52
A⁻¹ = 3−1−52, the same answer as slide 2's recipe ✓
Every step acts on the whole row, both halves. When the left half reads I, the right half is A⁻¹.

A bigger example: 3 × 3

Here every pivot is 1, so no fractions appear and the scale stage has nothing to do.

A = 110121012. Start from [A | I].
Forward: row 2 − row 1 → 011|−110
Forward: row 3 − row 2 → 001|1−11. The pivots are 1, 1, 1.
Backward: row 2 − row 3 → 010|−22−1
Backward: row 1 − row 2 → 100|3−21
A⁻¹ = 3−21−22−11−11
Two steps clear below the pivots, two clear above them. The left half turns into I and the right half into A⁻¹.

Check by multiplying: A times A⁻¹ must be I.

Row 2 of A times column 1 of A⁻¹: 1·3 + 2·(−2) + 1·1 = 0    times column 2: 1·(−2) + 2·2 + 1·(−1) = 1
All nine numbers of A times A⁻¹. Each one is a row of A dotted with a column of A⁻¹, and together they make I.

A computer does exactly these steps for a 1000 by 1000 matrix. It just has many more rows to clear.

The lab's matrix: a chain of springs

K = 2−10−12−10−12 appears in models of a chain of springs and masses. Its pivots are not 1, so fractions appear.
Start from [K | I]. As before, only the changed row is shown; the numbers after | are the right half.
Forward: row 2 + ½·row 1 → 03/2−1|½10
Forward: row 3 + ⅔·row 2 → 004/3|⅓⅔1. The pivots are 2, 3/2, 4/3.
Backward: row 2 + ¾·row 3 → 03/20|¾3/2¾
Backward: row 1 + ⅔·row 2 → 200|3/21½
Scale: row 1 ÷ 2 → 100|¾½¼
Scale: row 2 ÷ 3/2 → 010|½1½
Scale: row 3 ÷ 4/3 → 001|¼½¾
The left half is now I. Every entry of the right half is a multiple of ¼, so pull ¼ out front:
K⁻¹ = ¼ · 321242123
Check one column. The first column of K⁻¹ is ¼·321, and K times it must give the first column of I, 100. Because of the ¼ in front, K·321 itself should give 4·100 = 400:
K·321 = 6 − 2−3 + 4 − 1−2 + 2 = 400 ✓
The lab does all of these steps with rref.

When Gauss-Jordan gets stuck

Try slide 1's A = 1224, the matrix with no inverse:

row 2 − 2·row 1 → 12|1000|−21
Row 2 of the left half becomes all zeros. No row step can turn it into a row of I, so A has no inverse.

The second pivot is 0 and no lower row can help. The left half can never become I, so there is no A⁻¹. This is the same test as slide 1: a zero pivot means no inverse.

Think with the inverse, compute without it

Finding A⁻¹ takes about three times the work of factoring A = LU, and it adds more rounding error: tiny mistakes that creep in because a computer keeps only about 16 digits of each number. So to solve Ax = b, use elimination. The inverse is great for reasoning, as in x = A⁻¹b. It is rarely the best way to compute.

Next: Gauss-Jordan reads A row by row. Slide 5 turns the rows of a matrix into its columns, the transpose, and meets the matrices that stay the same when you do that.

Examples

Example 1 · A 2 by 2 by hand

Invert A = 2111.

Show solutionHide solution
[2 1 | 1 0; 1 1 | 0 1] → row 2 − ½·row 1 → [2 1 | 1 0; 0 ½ | −½ 1]
above: row 1 − 2·row 2 → [2 0 | 2 −2; 0 ½ | −½ 1]
divide: row 1 ÷ 2 and row 2 ÷ ½ → [1 0 | 1 −1; 0 1 | −1 2]
A⁻¹ = 1−1−12

Example 2 · A triangular matrix

Invert A = 120013001. Only upward steps are needed.

Show solutionHide solution
row 2 − 3·row 3, then row 1 − 2·row 2
A⁻¹ = 1−2601−3001

Where does the 6 come from? Follow the right half, which starts as I. Step 1 puts −3 in row 2, column 3, so row 2 becomes [0 1 −3]. Step 2 subtracts 2 times this new row 2 from row 1. Row 1 had 0 in column 3, so it gets 0 − 2·(−3) = 6. The second step uses the result of the first.

Example 3 · When Gauss-Jordan stops

Try A = 1224.

Show solutionHide solution
row 2 − 2·row 1 → [1 2 | 1 0; 0 0 | −2 1]

The left side has a zero row, so it can never become I. No inverse.

Example 4

Invert 3121.

Show solutionHide solution

det = 3 − 2 = 1. Inverse 1−1−23. Check: 3·1 + 1·(−2) = 1 ✓

Example 5

Invert the diagonal matrix with entries 1, 2, 4.

Show solutionHide solution

Divide each row by its pivot: the inverse is diagonal with entries 1, ½, ¼.

Exercise Show that 4·K⁻¹ has whole-number entries. In the last line, change ("K_inv", K_inv) to ("4 K_inv", 4 * K_inv). Edit the code and press Run.
slide_4.py Loading Python…
1
Output · Ctrl+Enter runs
Press Run to execute this slide's code. Ctrl+Enter works too.

Enjoying lesson 3? Get the full course: all 8 lessons through the SVD and PCA, your progress saved lesson by lesson, every solution and 5 extra problems per lesson. $20 once, yours for life.

4 / 7

Questions and comments

Stuck on something, or found a mistake? Ask here and I'll answer. You sign in with GitHub.

The full course

From Ax = b to PCA, by running it

Lessons 1 to 3 are free. Finish all eight and you will be able to:

You get: all 8 lessons with Python labs · every worked example and solution · 5 extra problems per lesson · your progress tracked · answers to your questions · every future update.

$20 once · lifetime access
Continue to checkout →

Already a member? Log in to the course