Guides / Linear algebra

Gaussian elimination and matrix inverses: whole-row operations, and [A | I] to [I | A⁻¹]

Gaussian elimination solves a system of linear equations by writing it as a grid of numbers and simplifying the rows until the answer can be read off from the bottom up. The same steps find an inverse, a determinant and a rank, and they are what a linear algebra library does underneath. The method itself is short. It goes wrong when an operation is applied to only part of a row, when a zero pivot is divided by, and when the last row is misread.

Why it works

Each row operation turns the system into one with exactly the same solutions. Adding a multiple of one equation to another can't create or destroy a solution, because it can be undone by subtracting the same multiple. Swapping two equations changes nothing, and multiplying one by a nonzero number can be undone by dividing. So the system you end with, in echelon form, has the same solutions as the one you started with, and in echelon form each equation has one fewer unknown than the one above it.

Row reducing [A | I] works because every row operation is a multiplication on the left by some invertible matrix E. If a sequence of them turns A into I, their product E satisfies EA = I, so E = A⁻¹. Doing the same operations to I builds that product: EI = A⁻¹.

Example 1: a 3×3 system

Solve x + y + 2z = 9, 2x + 4y − 3z = 1, 3x + 6y − 5z = 0.

1. 112924−3136−50The augmented matrix: coefficients on the left, right-hand sides after the bar.
2. R₂ − 2R₁, R₃ − 3R₁: 112902−7−1703−11−27The multipliers are the entries to clear divided by the pivot 1. The right side changes too: 1 − 2·9 = −17 and 0 − 3·9 = −27.
3. R₃ − 32R₂: 112902−7−1700−1/2−3/2The second pivot is 2 and the entry below it is 3, so the multiplier is 3/2. Check: −11 + 21/2 = −1/2 and −27 + 51/2 = −3/2.
4. z = 3, y = 2, x = 1Back substitution, from the bottom row up: −½z = −3/2, then 2y − 21 = −17, then x + 2 + 6 = 9.
5. (x, y, z) = (1, 2, 3)Check all three: 1 + 2 + 6 = 9, 2 + 8 − 9 = 1, 3 + 12 − 15 = 0.

Example 2: a zero pivot

Solve y + z = 3, x + 2y = 4, 2x + 3y + z = 9.

1. 011312042319The first equation has no x, so the top-left entry is 0. You can't clear a column with a 0 pivot.
2. R₁ ↔ R₂: 120401132319Swap in a row with a nonzero first entry. Reordering equations doesn't change the solutions.
3. R₃ − 2R₁, then R₃ + R₂: 120401130024R₃ − 2R₁ = (0, −1, 1 | 1); adding R₂ clears the −1.
4. z = 2, y = 1, x = 2y = 3 − 2 and x = 4 − 2·1. Check the last equation: 4 + 3 + 2 = 9.

Example 3: a free variable, and a system with no solution

Solve x + y − z = 2, 2x + 3y + z = 7, 3x + 4y = 9. Then change the 9 to 10.

1. R₂ − 2R₁, R₃ − 3R₁: 11−1201330133The last two rows came out the same.
2. R₃ − R₂: 11−1201330000The last row says 0 = 0: true, and no information. The third equation was the sum of the first two.
3. z = t, y = 3 − 3t, x = −1 + 4tThere is no pivot in the z column, so z is free. Solve for the pivot variables in terms of it: x = 2 − y + z.
4. (−1 + 4t, 3 − 3t, t), any tCheck t = 1: (3, 0, 1) gives 3 + 0 − 1 = 2, 6 + 0 + 1 = 7 and 9 + 0 = 9.
5. with 10: last row [0 0 0 | 1]The same steps end in 10 − 6 − 3 = 1 on the right. That row says 0 = 1, so there is no solution: the third equation now contradicts the other two.

Example 4: a 2×2 inverse

Invert A = 2314 and solve Ax = (7, 6).

1. det A = 2·4 − 3·1 = 5Not 0, so A is invertible.
2. A⁻¹ = 154−3−12Swap the diagonal entries, change the signs of the other two, divide by the determinant.
3. x = A⁻¹76 = 1528 − 18−7 + 12 = 21Check: 2·2 + 3·1 = 7 and 2 + 4 = 6.

Example 5: a 3×3 inverse from [A | I]

Invert A = 121011122.

1. R₃ − R₁: 121100011010001−101Every operation acts on all six columns. A is now upper triangular with 1s on the diagonal.
2. R₂ − R₃, R₁ − R₃: 12020−101011−1001−101Now clear upward, starting from the last pivot.
3. R₁ − 2R₂: 1000−2101011−1001−1012 − 2 = 0, 0 − 2 = −2, −1 + 2 = 1.
4. A⁻¹ = 0−2111−1−101Check one row of AA⁻¹: (1, 2, 1) times the columns gives 0 + 2 − 1 = 1, −2 + 2 + 0 = 0 and 1 − 2 + 1 = 0.

Common mistakes, and the exact line they happen on

1. Leaving the right side behind

The system x + 2y = 4, 3x − y = 5.

1. 1243−15Right so far.
2. R₂ − 3R₁: 1240−75This is the mistake. The operation stopped at the bar. The right side must become 5 − 3·4 = −7. As written it gives y = −5/7 and x = 38/7, and 3·38/7 + 5/7 = 17, not 5. Done properly, −7y = −7, so y = 1 and x = 2.

2. Forgetting to divide by the determinant

The matrix from Example 4.

1. 2314 → swap and negate: 4−3−12Right so far.
2. A⁻¹ = 4−3−12, x = 105This is the mistake. This matrix is 5A⁻¹: multiplying it by A gives 5I, not I. The answer it gives fails the check, since A(10, 5) = (35, 30), five times (7, 6). Divide by det A = 5 to get x = (2, 1).

3. Reading a row of zeros as "no solution"

The system from Example 3.

1. last row [0 0 0 | 0]Right so far.
2. so the system has no solutionThis is the mistake. A row of zeros on both sides says 0 = 0, which is always true. No solution needs a nonzero number after the bar, as in [0 0 0 | 1]. Here z is free, and (−1, 3, 0), (3, 0, 1) and every other point on that line are solutions.

Practice

1. Solve x + y = 5, 2x − y = 1 by row reduction.

   Show answer

   R₂ − 2R₁ gives [0 −3 | −9], so y = 3 and x = 2.

2. Solve x + y + z = 2, x − y + 2z = 6, 2x + y − z = −1.

   Show answer

   (x, y, z) = (1, −1, 2). Check: 1 − 1 + 2 = 2, 1 + 1 + 4 = 6, 2 − 1 − 2 = −1.

3. Find the inverse of 5273.

   Show answer

   The determinant is 15 − 14 = 1, so the inverse is 3−2−75.

4. For which k does x + 2y = 3, 2x + ky = 6 fail to have exactly one solution, and what happens then?

   Show answer

   R₂ − 2R₁ gives [0 k − 4 | 0]. For k = 4 that row is all zeros, so y is free: x = 3 − 2t, y = t, infinitely many solutions. (With a right side other than 6 it would be no solution.)

5. Is 123456789 invertible?

   Show answer

   No. R₂ − 4R₁ = (0, −3, −6) and R₃ − 7R₁ = (0, −6, −12), which is twice the row above, so elimination leaves a row of zeros and only two pivots. The determinant is 0, and (1, −2, 1) is sent to 0.