Practice / Linear algebra

Gaussian elimination, inverses and determinants by hand

Ten problems on solving linear systems by row reduction: a 2×2 and a 3×3 system on the augmented matrix, a zero pivot that needs a row swap, a free variable and an inconsistent row, the 2×2 inverse formula, a 3×3 inverse by Gauss–Jordan on [A | I], a determinant by row reduction, the rules for det(cA), det(AB) and det(A⁻¹), an LU factorization with forward and back substitution, and a singular matrix whose null space is a redundant feature, with worked solutions and the mistakes of updating only the left side, dropping 1/det and forgetting the sign of a swap.

Before you start

Almost every computation with matrices that is done by hand, and most of the ones a linear algebra library does for you, is Gaussian elimination underneath: solving $Ax = b$ inverting $A$ computing $\det A$ finding a rank or a null space. The method is three row operations used to clear the entries below each pivot, followed by back substitution. It goes wrong in a few predictable places: an operation applied to the coefficients but not to the right-hand side, a zero pivot divided by instead of swapped away, a row of zeros misread, the $\tfrac{1}{\det}$ dropped from the $2\times2$ inverse, and a row swap that silently flips the sign of a determinant. These ten problems cover each of them, and end with the singular matrix you meet in machine learning when one feature is the sum of two others.

The augmented matrix. The system $Ax = b$ is written $[A \mid b]$ the coefficients of each equation in a row, with its right-hand side after the bar. A row operation changes the whole row, right-hand side included.
Row operations. (1) Add a multiple of one row to another, written $R_2 \to R_2 - 3R_1$ (2) Swap two rows, $R_1 \leftrightarrow R_2$ (3) Multiply a row by a nonzero number. None of them changes the solutions of the system.
Pivots and echelon form. Working left to right, the first nonzero entry of each row is its pivot; elimination uses each pivot to clear the entries below it. A zero where a pivot should be is fixed by swapping with a lower row. In echelon form each pivot is to the right of the one above, and any rows of zeros are at the bottom.
Reading the result. A pivot in every column of $A$ one solution, found by back substitution from the last row up. A column without a pivot: its variable is free, and there are infinitely many solutions. A row $[0 \;\cdots\; 0 \mid c]$ with $c \ne 0$ says $0 = c$ no solution. A row of all zeros, $0 = 0$ says nothing.
Inverses. $A^{-1}$ satisfies $AA^{-1} = A^{-1}A = I$ and exists exactly when $\det A \ne 0$ For $2\times2$ $\begin{bmatrix}a&b\\c&d\end{bmatrix}^{-1} = \dfrac{1}{ad - bc}\begin{bmatrix}d&-b\\-c&a\end{bmatrix}$ In general, row reduce $[A \mid I]$ until the left half is $I$ the right half is then $A^{-1}$
Determinants. For $2\times2$ $ad - bc$ Adding a multiple of one row to another leaves $\det$ unchanged, a swap multiplies it by $-1$ and scaling a row by $c$ multiplies it by $c$ The determinant of a triangular matrix is the product of its diagonal entries. For $n\times n$ matrices, $\det(AB) = \det A\,\det B$ $\det(A^\top) = \det A$ and $\det(cA) = c^n\det A$
LU. $A = LU$ with $U$ the echelon form from elimination without swaps and $L$ lower triangular with $1$ s on its diagonal and the multipliers $\ell_{ij}$ below it, where $R_i \to R_i - \ell_{ij}R_j$ was the operation used.

Problems

·
Solve $x + 2y = 5$ $3x + 4y = 6$ by row reducing the augmented matrix.
·
Solve the system $x + y + z = 6$ $2x + y - z = 1$ $x - 2y + 3z = 6$
··
Solve $2y + z = 1$ $x + y + z = 4$ $2x + 3y + 2z = 7$
··
Solve $x + 2y + z = 4$ $2x + 4y + 3z = 11$ $x + 2y + 2z = 7$ Then say what happens if the last right-hand side is $8$ instead of $7$
·
Find the inverse of $A = \begin{bmatrix}4&7\\2&6\end{bmatrix}$ and use it to solve $Ax = (1, 2)^\top$
··
Find the inverse of $A = \begin{bmatrix}1&2&3\\0&1&4\\5&6&0\end{bmatrix}$ by row reducing $[A \mid I]$
··
Compute $\det A$ for $A = \begin{bmatrix}0&1&2\\1&0&3\\4&-3&8\end{bmatrix}$ by row reduction, and check it by cofactor expansion.
··
$A$ and $B$ are $3\times3$ matrices with $\det A = 3$ and $\det B = -2$ Find $\det(2A)$ $\det(-A)$ $\det(A^{-1})$ $\det(A^\top A)$ and $\det(A^2B)$ Can $\det(A + B)$ be found from this information?
···
Factor $A = \begin{bmatrix}2&1&1\\4&3&3\\8&7&9\end{bmatrix}$ as $A = LU$ use it to solve $Ax = (4, 10, 24)^\top$ and read off $\det A$
···
A design matrix has rows $(1, 1, 2)$ $(1, 2, k)$ and $(1, 3, 4)$ one row per example and one column per feature. For which $k$ is it singular? For that $k$ find its null space, solve $Ax = (2, 3, 4)^\top$ and show that $Ax = (1, 0, 0)^\top$ has no solution.

Answers

$x = -4$ $y = \tfrac92$
$(x, y, z) = (1, 2, 3)$
$(x, y, z) = (2, -1, 3)$
$(x, y, z) = (1 - 2t,\ t,\ 3)$ for every $t$ with $8$ the last row reads $0 = 1$ and there is no solution
$A^{-1} = \dfrac{1}{10}\begin{bmatrix}6&-7\\-2&4\end{bmatrix}$ $x = (-0.8, 0.6)^\top$
$A^{-1} = \begin{bmatrix}-24&18&5\\20&-15&-4\\-5&4&1\end{bmatrix}$
$\det A = -2$
$24$ $-3$ $\tfrac13$ $9$ $-18$ $\det(A + B)$ cannot be found
$L = \begin{bmatrix}1&0&0\\2&1&0\\4&3&1\end{bmatrix}$ $U = \begin{bmatrix}2&1&1\\0&1&1\\0&0&2\end{bmatrix}$ $x = (1, 1, 1)^\top$ $\det A = 2\cdot1\cdot2 = 4$
Singular for $k = 3$ null space $t(1, 1, -1)^\top$ $x = (t, t, 1 - t)^\top$ for $(2, 3, 4)^\top$ no solution for $(1, 0, 0)^\top$

Worked solutions

Problem 1

Solve $x + 2y = 5$ $3x + 4y = 6$ by row reducing the augmented matrix.

$\left[\begin{array}{cc|c}1&2&5\\3&4&6\end{array}\right]$ Each equation is a row; the right-hand sides go after the bar.
$R_2 \to R_2 - 3R_1$ $\left[\begin{array}{cc|c}1&2&5\\0&-2&-9\end{array}\right]$ The multiplier is $3 = \tfrac31$ the entry to clear over the pivot. The right side changes too: $6 - 3\cdot5 = -9$
$-2y = -9$ so $y = \tfrac92$ The last row is one equation in one unknown.
$x + 2\cdot\tfrac92 = 5$ so $x = -4$ Back substitution into the first row.
$x = -4$ $y = \tfrac92$ Check in the second equation: $3(-4) + 4\cdot\tfrac92 = -12 + 18 = 6$

Problem 2

Solve the system $x + y + z = 6$ $2x + y - z = 1$ $x - 2y + 3z = 6$

$\left[\begin{array}{ccc|c}1&1&1&6\\2&1&-1&1\\1&-2&3&6\end{array}\right]$ The augmented matrix.
$R_2 \to R_2 - 2R_1$ $R_3 \to R_3 - R_1$ $\left[\begin{array}{ccc|c}1&1&1&6\\0&-1&-3&-11\\0&-3&2&0\end{array}\right]$ Clear the first column below the pivot $1$
$R_3 \to R_3 - 3R_2$ $\left[\begin{array}{ccc|c}1&1&1&6\\0&-1&-3&-11\\0&0&11&33\end{array}\right]$ The second pivot is $-1$ and the multiplier is $\tfrac{-3}{-1} = 3$ Check the new row: $2 - 3(-3) = 11$ and $0 - 3(-11) = 33$
$11z = 33$ so $z = 3$ $-y - 9 = -11$ so $y = 2$ $x + 2 + 3 = 6$ so $x = 1$ Back substitution from the bottom row up.
$(x, y, z) = (1, 2, 3)$ Check all three: $1 + 2 + 3 = 6$ $2 + 2 - 3 = 1$ and $1 - 4 + 9 = 6$

Problem 3

Solve $2y + z = 1$ $x + y + z = 4$ $2x + 3y + 2z = 7$

$\left[\begin{array}{ccc|c}0&2&1&1\\1&1&1&4\\2&3&2&7\end{array}\right]$ The first equation has no $x$ so the top-left entry is $0$ and cannot be a pivot.
$R_1 \leftrightarrow R_2$ $\left[\begin{array}{ccc|c}1&1&1&4\\0&2&1&1\\2&3&2&7\end{array}\right]$ Swap in a row with a nonzero first entry. Swapping equations does not change the solutions.
$R_3 \to R_3 - 2R_1$ $\left[\begin{array}{ccc|c}1&1&1&4\\0&2&1&1\\0&1&0&-1\end{array}\right]$ Clear the first column.
$R_2 \leftrightarrow R_3$ then $R_3 \to R_3 - 2R_2$ $\left[\begin{array}{ccc|c}1&1&1&4\\0&1&0&-1\\0&0&1&3\end{array}\right]$ The swap is optional, but it makes the pivot $1$ and avoids fractions; $R_3 \to R_3 - \tfrac12R_2$ without it gives the same answer.
$(x, y, z) = (2, -1, 3)$ $z = 3$ $y = -1$ and $x = 4 - (-1) - 3 = 2$ Check: $2(-1) + 3 = 1$ $2 - 1 + 3 = 4$ and $4 - 3 + 6 = 7$

Problem 4

Solve $x + 2y + z = 4$ $2x + 4y + 3z = 11$ $x + 2y + 2z = 7$ Then say what happens if the last right-hand side is $8$ instead of $7$

$R_2 \to R_2 - 2R_1$ $R_3 \to R_3 - R_1$ $\left[\begin{array}{ccc|c}1&2&1&4\\0&0&1&3\\0&0&1&3\end{array}\right]$ Clearing the first column also clears the second: the $y$ coefficients are twice the $x$ coefficients in every row.
$R_3 \to R_3 - R_2$ $\left[\begin{array}{ccc|c}1&2&1&4\\0&0&1&3\\0&0&0&0\end{array}\right]$ The last row says $0 = 0$ which is always true and adds no information.
The pivots are in the $x$ and $z$ columns, so $y$ is free: $y = t$ No pivot in the $y$ column means nothing pins $y$ down.
$z = 3$ and $x = 4 - 2t - 3 = 1 - 2t$ Back substitution with $y = t$
With $8$ the same steps give the last row $[0\;0\;0 \mid 1]$ $R_3 - R_1$ now ends in $8 - 4 = 4$ and $R_3 - R_2$ in $4 - 3 = 1$
$(x, y, z) = (1 - 2t,\ t,\ 3)$ for every $t$ with $8$ the last row reads $0 = 1$ and there is no solutionCheck $t = 1$ $(-1, 1, 3)$ gives $-1 + 2 + 3 = 4$ $-2 + 4 + 9 = 11$ and $-1 + 2 + 6 = 7$

Problem 5

Find the inverse of $A = \begin{bmatrix}4&7\\2&6\end{bmatrix}$ and use it to solve $Ax = (1, 2)^\top$

$\det A = 4\cdot6 - 7\cdot2 = 10$ Not zero, so $A$ is invertible.
$A^{-1} = \dfrac{1}{10}\begin{bmatrix}6&-7\\-2&4\end{bmatrix}$ Swap the diagonal entries, negate the off-diagonal ones, divide by the determinant.
$AA^{-1} = \dfrac1{10}\begin{bmatrix}24 - 14&-28 + 28\\12 - 12&-14 + 24\end{bmatrix} = I$ Check before using it.
$x = A^{-1}b = \dfrac1{10}\begin{bmatrix}6 - 14\\-2 + 8\end{bmatrix} = \dfrac1{10}\begin{bmatrix}-8\\6\end{bmatrix}$ Multiply both sides of $Ax = b$ on the left by $A^{-1}$
$A^{-1} = \dfrac{1}{10}\begin{bmatrix}6&-7\\-2&4\end{bmatrix}$ $x = (-0.8, 0.6)^\top$ Check: $4(-0.8) + 7(0.6) = 1$ and $2(-0.8) + 6(0.6) = 2$

Problem 6

Find the inverse of $A = \begin{bmatrix}1&2&3\\0&1&4\\5&6&0\end{bmatrix}$ by row reducing $[A \mid I]$

$R_3 \to R_3 - 5R_1$ $\left[\begin{array}{ccc|ccc}1&2&3&1&0&0\\0&1&4&0&1&0\\0&-4&-15&-5&0&1\end{array}\right]$ Every operation acts on all six columns.
$R_3 \to R_3 + 4R_2$ third row $[0\;0\;1 \mid -5\;\;4\;\;1]$ $-15 + 16 = 1$ so the third pivot is already $1$
$R_2 \to R_2 - 4R_3$ and $R_1 \to R_1 - 3R_3$ rows $[0\;1\;0 \mid 20\;\;{-15}\;\;{-4}]$ and $[1\;2\;0 \mid 16\;\;{-12}\;\;{-3}]$ Now clear above the pivots, starting from the last column: $0 - 4(-5) = 20$ $1 - 16 = -15$ $1 + 15 = 16$
$R_1 \to R_1 - 2R_2$ first row $[1\;0\;0 \mid -24\;\;18\;\;5]$ $16 - 40 = -24$ $-12 + 30 = 18$ $-3 + 8 = 5$
$A^{-1} = \begin{bmatrix}-24&18&5\\20&-15&-4\\-5&4&1\end{bmatrix}$ Check one entry of $AA^{-1}$ per row: $(1, 2, 3)\cdot(-24, 20, -5) = -24 + 40 - 15 = 1$ $(0, 1, 4)\cdot(18, -15, 4) = 1$ $(5, 6, 0)\cdot(5, -4, 1) = 1$ No row was scaled and no rows were swapped, so $\det A$ is the product of the pivots, $1$ which is why the inverse has integer entries.

Problem 7

Compute $\det A$ for $A = \begin{bmatrix}0&1&2\\1&0&3\\4&-3&8\end{bmatrix}$ by row reduction, and check it by cofactor expansion.

$R_1 \leftrightarrow R_2$ $\begin{bmatrix}1&0&3\\0&1&2\\4&-3&8\end{bmatrix}$ and the determinant changes signThe top-left entry is $0$ so swap first. Keep a running factor of $-1$
$R_3 \to R_3 - 4R_1$ third row $(0, -3, -4)$ Adding a multiple of a row does not change the determinant.
$R_3 \to R_3 + 3R_2$ third row $(0, 0, 2)$ $-4 + 6 = 2$ again no change.
$\det A = -1\cdot(1\cdot1\cdot2) = -2$ The echelon form is triangular, so its determinant is the product of its diagonal; the one swap contributes the $-1$
$\det A = -2$ Cofactor expansion along the first row: $0 - 1\,(1\cdot8 - 3\cdot4) + 2\,(1\cdot(-3) - 0\cdot4) = 4 - 6 = -2$

Problem 8

$A$ and $B$ are $3\times3$ matrices with $\det A = 3$ and $\det B = -2$ Find $\det(2A)$ $\det(-A)$ $\det(A^{-1})$ $\det(A^\top A)$ and $\det(A^2B)$ Can $\det(A + B)$ be found from this information?

$\det(2A) = 2^3\det A = 24$ $2A$ doubles every one of the three rows, and each doubled row doubles the determinant.
$\det(-A) = (-1)^3\det A = -3$ The same rule with $c = -1$ for an even size the sign would not change.
$\det(A^{-1}) = \dfrac{1}{\det A} = \dfrac13$ $\det A\,\det(A^{-1}) = \det(AA^{-1}) = \det I = 1$
$\det(A^\top A) = \det A^\top\det A = 9$ and $\det(A^2B) = 3\cdot3\cdot(-2) = -18$ The product rule, with $\det A^\top = \det A$
$24$ $-3$ $\tfrac13$ $9$ $-18$ $\det(A + B)$ cannot be foundThe determinant is not additive. With $A = \operatorname{diag}(3, 1, 1)$ and $B = \operatorname{diag}(-2, 1, 1)$ $\det(A + B) = 1\cdot2\cdot2 = 4$ with $B = \operatorname{diag}(1, -2, 1)$ instead, $\det(A + B) = 4\cdot(-1)\cdot2 = -8$ Same determinants, different answers.

Problem 9

Factor $A = \begin{bmatrix}2&1&1\\4&3&3\\8&7&9\end{bmatrix}$ as $A = LU$ use it to solve $Ax = (4, 10, 24)^\top$ and read off $\det A$

$R_2 \to R_2 - 2R_1$ $R_3 \to R_3 - 4R_1$ rows $(0, 1, 1)$ and $(0, 3, 5)$ Multipliers $\ell_{21} = 2$ and $\ell_{31} = 4$
$R_3 \to R_3 - 3R_2$ row $(0, 0, 2)$ so $U = \begin{bmatrix}2&1&1\\0&1&1\\0&0&2\end{bmatrix}$ Multiplier $\ell_{32} = 3$
$L = \begin{bmatrix}1&0&0\\2&1&0\\4&3&1\end{bmatrix}$ The multipliers go below the diagonal, in the positions they cleared, with their signs as used in $R_i \to R_i - \ell R_j$
$Lc = b$ $c_1 = 4$ $c_2 = 10 - 2\cdot4 = 2$ $c_3 = 24 - 4\cdot4 - 3\cdot2 = 2$ Forward substitution, top row first. This repeats on $b$ what elimination did to $A$
$Ux = c$ $2x_3 = 2$ $x_2 + x_3 = 2$ $2x_1 + x_2 + x_3 = 4$ Back substitution: $x_3 = 1$ $x_2 = 1$ $x_1 = 1$
$L = \begin{bmatrix}1&0&0\\2&1&0\\4&3&1\end{bmatrix}$ $U = \begin{bmatrix}2&1&1\\0&1&1\\0&0&2\end{bmatrix}$ $x = (1, 1, 1)^\top$ $\det A = 2\cdot1\cdot2 = 4$ $\det A = \det L\det U$ and $\det L = 1$ Once $L$ and $U$ are known, each new right-hand side costs only the two triangular solves, which is why libraries factor once and reuse it.

Problem 10

A design matrix has rows $(1, 1, 2)$ $(1, 2, k)$ and $(1, 3, 4)$ one row per example and one column per feature. For which $k$ is it singular? For that $k$ find its null space, solve $Ax = (2, 3, 4)^\top$ and show that $Ax = (1, 0, 0)^\top$ has no solution.

$\det A = 1\,(8 - 3k) - 1\,(4 - k) + 2\,(3 - 2) = 6 - 2k$ Cofactor expansion along the first row of $A = \begin{bmatrix}1&1&2\\1&2&k\\1&3&4\end{bmatrix}$
$\det A = 0$ exactly when $k = 3$ Then the third column is $(2, 3, 4)^\top = (1, 1, 1)^\top + (1, 2, 3)^\top$ the third feature is the sum of the first two.
Row reduce with $k = 3$ $\begin{bmatrix}1&1&2\\0&1&1\\0&0&0\end{bmatrix}$ so $x_3 = t$ $x_2 = -t$ $x_1 = -t$ null space spanned by $(1, 1, -1)^\top$ $R_2 - R_1$ and $R_3 - R_1$ give $(0, 1, 1)$ and $(0, 2, 2)$ and $R_3 - 2R_2$ gives zeros. Check: $A(1, 1, -1)^\top = (0, 0, 0)^\top$
$(2, 3, 4)^\top$ is the third column, so $x = (0, 0, 1)^\top$ works, and every solution is $(0, 0, 1)^\top + t(1, 1, -1)^\top$ One solution plus anything in the null space.
For $(1, 0, 0)^\top$ the same operations end in the row $[0\;0\;0 \mid 1]$ The right side becomes $(1, -1, -1)$ after $R_2 - R_1$ and $R_3 - R_1$ and $R_3 - 2R_2$ turns its last entry into $-1 - 2(-1) = 1$ That row says $0 = 1$
Singular for $k = 3$ null space $t(1, 1, -1)^\top$ $x = (t, t, 1 - t)^\top$ for $(2, 3, 4)^\top$ no solution for $(1, 0, 0)^\top$ In regression terms: weights $w$ and $w + t(1, 1, -1)^\top$ give identical predictions, so $X^\top X$ is singular and the least-squares weights are not unique until a feature is dropped or a penalty such as ridge is added.

Where this goes wrong

1. Row operation applied to the coefficients only

The coefficients sit in a neat block, and the column after the bar is easy to leave behind.

$\left[\begin{array}{cc|c}1&2&5\\3&4&6\end{array}\right]$ Right so far: Problem 1.
“ $R_2 \to R_2 - 3R_1$ turns $(3, 4)$ into $(0, -2)$ ”The habit that causes the mistake: the operation is done on the coefficients and stops at the bar.
$\left[\begin{array}{cc|c}1&2&5\\0&-2&6\end{array}\right]$ so $y = -3$ and $x = 11$ The right side must become $6 - 3\cdot5 = -9$ The check exposes it: $3\cdot11 + 4(-3) = 21$ not $6$ The solution is $x = -4$ $y = \tfrac92$

2. Dropping the 1/det from the 2×2 inverse

The swap-and-negate pattern is the memorable part of the formula, and the scalar in front is not.

$A = \begin{bmatrix}4&7\\2&6\end{bmatrix}$ with $\begin{bmatrix}6&-7\\-2&4\end{bmatrix}$ from swapping and negatingRight so far: Problem 5.
“So $A^{-1} = \begin{bmatrix}6&-7\\-2&4\end{bmatrix}$ ”The step that causes the mistake: the division by $\det A = 10$ is skipped.
$x = \begin{bmatrix}6&-7\\-2&4\end{bmatrix}(1, 2)^\top = (-8, 6)^\top$ Then $Ax = (-32 + 42,\ -16 + 36)^\top = (10, 20)^\top$ ten times $b$ the matrix used is $10A^{-1}$ and $A$ times it is $10I$ not $I$ Divide by $\det A$ $x = (-0.8, 0.6)^\top$

3. A row of zeros read as no solution

A row with nothing left in it looks like a system that has broken down.

$\left[\begin{array}{ccc|c}1&2&1&4\\0&0&1&3\\0&0&0&0\end{array}\right]$ Right so far: Problem 4.
“The last row has no variables left.”True, and harmless: it says $0 = 0$
“So the system has no solution.”No solution needs a row $[0\;0\;0 \mid c]$ with $c \ne 0$ A row of zeros on both sides of the bar only says one equation was a combination of the others: here the third equation is the second minus the first. The $y$ column has no pivot, so there are infinitely many solutions, $(1 - 2t, t, 3)$ such as $(1, 0, 3)$ and $(-1, 1, 3)$

4. A row swap that keeps the determinant's sign

Row operations are thought of as harmless to the determinant, and for the most common one they are.

$A = \begin{bmatrix}0&1&2\\1&0&3\\4&-3&8\end{bmatrix}$ swap $R_1 \leftrightarrow R_2$ to get a nonzero pivotRight so far: Problem 7.
Eliminate to $\begin{bmatrix}1&0&3\\0&1&2\\0&0&2\end{bmatrix}$ Also right: the two row additions do not change the determinant.
$\det A = 1\cdot1\cdot2 = 2$ A swap multiplies the determinant by $-1$ so $\det A = -2$ as cofactor expansion confirms. Two swaps would cancel; an odd number leaves a minus sign.

5. det(2A) taken as 2 det A

Scalars come out of most things linearly, so the $2$ is pulled out once.

$\det A = 3$ for a $3\times3$ matrix $A$ Right so far: Problem 8.
“ $2A$ is $A$ times $2$ ”True; the question is what that does to the determinant.
$\det(2A) = 2\cdot3 = 6$ $2A$ multiplies each of the three rows by $2$ and the determinant is linear in each row separately, so the factor comes out three times: $\det(2A) = 2^3\cdot3 = 24$ A quick test: $\det(2I) = 8$ for the $3\times3$ identity, not $2$

Print this set: gaussian-elimination-inverses-and-determinants.pdf (problems, answers, and worked solutions on separate pages).

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