Gaussian Elimination

Augmented matrices: the x's and y's are overhead

A system of equations like $2x + 3y = 5$ $4x - y = 1$

carries around the variables $x$, $y$ as pure decoration. All the mathematical content is in the coefficients and constants — the $x$ and $y$ are just labels dressed up as variables. Strip them off and you get the augmented matrix $[A|\vec{b}]$:

$\left[\begin{array}{cc|c} 2 & 3 & 5 \\ 4 & -1 & 1 \end{array}\right]$

Column 1 holds the coefficients of $x$, column 2 holds the coefficients of $y$, and the column after the bar holds the right-hand sides. The variables are implied by position. Everything that follows is pure matrix surgery.

The three legal row operations

The soul of the algorithm is this: each operation rewrites the system into an equivalent one — same solution set, different appearance. There are exactly three legal operations:

1. Swap two rows: $R_i \leftrightarrow R_j$
2. Scale a row by a nonzero constant: $R_i \leftarrow c R_i$ (with $c \ne 0$)
3. Add a multiple of one row to another: $R_i \leftarrow R_i + c R_j$

Why are these legal? Each corresponds to a valid equation manipulation:

• Swapping equations: the ORDER of equations in a system is irrelevant.
• Scaling an equation: multiplying both sides by the same nonzero constant.
• Row-combining: adding the same thing (a multiple of another equation) to both sides.

Any sequence of these three operations preserves the solution set. This is the formal justification of everything you did informally in the Algebra stratum — you were doing row operations, and now they have names. The operations are sacred. Don't invent a fourth one; I will find out.

Forward elimination: building the staircase

Row Echelon Form (REF) is the target of forward elimination. A matrix is in REF when:

• All zero rows are at the bottom.
• Each nonzero row's pivot (leftmost nonzero entry) is strictly to the right of the pivot in the row above.

The picture is a staircase: each row's leading entry steps to the right compared to the previous one. Here's the forward-elimination procedure:

1. Find the leftmost nonzero column. Its first nonzero entry becomes the pivot.
2. If needed, swap rows to bring a nonzero entry to the pivot position.
3. Use Row Operation 3 to zero out everything BELOW the pivot.
4. Move to the submatrix below and to the right of the pivot; repeat.

Example: Solve $2x+y-z=1$, $4x-y+z=5$, $-2x+2y+z=3$.

$\left[\begin{array}{ccc|c} 2 & 1 & -1 & 1 \\ 4 & -1 & 1 & 5 \\ -2 & 2 & 1 & 3 \end{array}\right]$

$R_2 \leftarrow R_2 - 2R_1$: $[4-4, -1-2, 1-(-2), 5-2] = [0,-3,3,3]$.

$R_3 \leftarrow R_3 + R_1$: $[-2+2, 2+1, 1+(-1), 3+1] = [0,3,0,4]$.

$\left[\begin{array}{ccc|c} 2 & 1 & -1 & 1 \\ 0 & -3 & 3 & 3 \\ 0 & 3 & 0 & 4 \end{array}\right]$

$R_3 \leftarrow R_3 + R_2$: $[0+0, 3+(-3), 0+3, 4+3] = [0,0,3,7]$.

$\left[\begin{array}{ccc|c} 2 & 1 & -1 & 1 \\ 0 & -3 & 3 & 3 \\ 0 & 0 & 3 & 7 \end{array}\right]$

This is REF. Three pivots visible.

Back-substitution and RREF

From REF, back-substitution solves the system bottom-up. The bottom row says $3z = 7 \Rightarrow z = 7/3$. Middle row: $-3y + 3(7/3) = 3 \Rightarrow -3y + 7 = 3 \Rightarrow y = 4/3$. Top row: $2x + (4/3) - (7/3) = 1 \Rightarrow 2x - 1 = 1 \Rightarrow x = 1$.

Reduced Row Echelon Form (RREF) is the fully digested form: each pivot is $1$, and every entry above AND below each pivot is $0$. RREF requires additionally zeroing out above each pivot (more row operations), but gives you the solution directly without back-substitution.

Reading the verdict: three possible outcomes

After elimination, one of three things happens:

1. Unique solution: The matrix has $n$ pivots for $n$ unknowns. No free variables. One solution.

2. No solution: A row of the form $\left[\begin{array}{ccc|c}0&0&\cdots&k\end{array}\right]$ with $k \ne 0$ appears. This says "$0 = k$," which is false. Inconsistent system.

3. Infinitely many solutions: Pivots are present, but fewer than the number of unknowns. The "free variables" (columns without pivots) can take any value, and the pivot variables are expressed in terms of them. Parametrized solution set.

The pivot count is the first sighting of what the Vector Spaces stratum will call rank. In the next stratum, rank + nullity = $n$ is the fundamental conservation law of linear algebra — and pivot counting is exactly how you compute rank from elimination. File that away: it's going to blow the lid off everything.

Finding $A^{-1}$ by row-reducing $[A|I]$

Here's a beautiful consequence of the same algorithm. Form the augmented matrix $[A|I]$ — the matrix $A$ side-by-side with the identity matrix. Run elimination on the whole thing until the left side becomes $I$. Whatever the right side becomes is $A^{-1}$.

Why does this work? Every row operation is multiplication by an elementary matrix on the left. So the sequence of operations that transforms $A \to I$ is multiplication by $E_k \cdots E_1$, and $E_k \cdots E_1 A = I$ means $E_k \cdots E_1 = A^{-1}$. Since we apply the same operations to $I$, the right side becomes $A^{-1} I = A^{-1}$. It's beautiful and it should make you a little furious that nobody explains it this way the first time.

Example: Find the inverse of $A = \begin{pmatrix}2&1\\5&3\end{pmatrix}$.

$\left[\begin{array}{cc|cc}2&1&1&0\\5&3&0&1\end{array}\right]$

$R_2 \leftarrow R_2 - \frac{5}{2}R_1$: $[5-5, 3-5/2, 0-5/2, 1-0] = [0, 1/2, -5/2, 1]$.

$\left[\begin{array}{cc|cc}2&1&1&0\\0&1/2&-5/2&1\end{array}\right]$

$R_2 \leftarrow 2R_2$: $[0,1,-5,2]$.

$R_1 \leftarrow R_1 - R_2$: $[2,0,6,-2]$.

$R_1 \leftarrow \frac{1}{2}R_1$: $[1,0,3,-1]$.

$\left[\begin{array}{cc|cc}1&0&3&-1\\0&1&-5&2\end{array}\right]$

So $A^{-1} = \begin{pmatrix}3&-1\\-5&2\end{pmatrix}$. Check: $\det(A) = (2)(3)-(1)(5)=1$, and the formula gives $A^{-1} = \begin{pmatrix}3&-1\\-5&2\end{pmatrix}$. Agreement. Elimination eats the inverse problem too.