3.1 Gaussian Elimination & Row Echelon Forms

We have seen how to write systems of equations in the matrix form $A\mathbf{x} = \mathbf{b}$. But how do we actually find the values of $\mathbf{x}$ programmatically or systematically?

We use Gaussian Elimination. This is a step-by-step algorithm that uses simple row operations to simplify a matrix until the solution becomes obvious. Let's learn how it works.

1. The Augmented Matrix

To solve a system of equations, we stack the coefficient matrix $A$ and the target vector $\mathbf{b}$ together into a single grid called the augmented matrix, written as $[A \mid \mathbf{b}]$.

Let's look at this system: $2x + 4y = 8$ $x + y = 3$

We write it as: $\begin{bmatrix} 2 & 4 & \mid & 8 \\ 1 & 1 & \mid & 3 \end{bmatrix}$

2. Allowed Row Operations

During Gaussian elimination, we can perform three basic row operations. Crucially, these operations do not change the solution of the system:

1. Swap: Switch the position of two rows ($R_i \leftrightarrow R_j$).
2. Scale: Multiply or divide an entire row by a non-zero number ($R_i \leftarrow c \cdot R_i$).
3. Pivot Addition: Add or subtract a multiple of one row to another row ($R_i \leftarrow R_i + c \cdot R_j$).

Our goal is to use these operations to create zeros below the diagonal, making the equations easy to solve.

3. Step-by-Step Walkthrough

Let's solve our augmented matrix step-by-step: $\begin{bmatrix} 2 & 4 & \mid & 8 \\ 1 & 1 & \mid & 3 \end{bmatrix}$

Step 1: Create a Pivot of 1 in the top-left corner

We divide Row 1 by 2 ($R_1 \leftarrow R_1 / 2$): $\begin{bmatrix} 1 & 2 & \mid & 4 \\ 1 & 1 & \mid & 3 \end{bmatrix}$

Step 2: Create a 0 below our pivot

We subtract Row 1 from Row 2 ($R_2 \leftarrow R_2 - R_1$): $\begin{bmatrix} 1 & 2 & \mid & 4 \\ 0 & -1 & \mid & -1 \end{bmatrix}$

Step 3: Create a Pivot of 1 in the second row

We multiply Row 2 by -1 ($R_2 \leftarrow -1 \cdot R_2$): $\begin{bmatrix} 1 & 2 & \mid & 4 \\ 0 & 1 & \mid & 1 \end{bmatrix}$

We are now in Row Echelon Form (REF)!

A matrix is in Row Echelon Form (REF) if:

1. All rows of zeros (if any) are at the bottom.
2. The leading coefficient (the first non-zero number from the left, called the pivot) of a row is always to the right of the pivot above it.
3. All entries in a column below a pivot are zero.

From REF, we can read the second row as: $0x + 1y = 1 \implies y = 1$. We can plug $y = 1$ back into the first row to solve: $x + 2(1) = 4 \implies x = 2$. This process is called back-substitution.

Step 4: Go further to Reduced Row Echelon Form (RREF)

Instead of back-substitution, we can keep using row operations to clear the numbers above the pivots as well. This leads to Reduced Row Echelon Form (RREF).

Let's eliminate the $2$ above our second pivot. We subtract $2 \times \text{Row 2}$ from Row 1 ($R_1 \leftarrow R_1 - 2R_2$): $\begin{bmatrix} 1 & 0 & \mid & 2 \\ 0 & 1 & \mid & 1 \end{bmatrix}$

Now, we can read the solutions directly from the matrix:

• Row 1: $1x + 0y = 2 \implies x = 2$
• Row 2: $0x + 1y = 1 \implies y = 1$

The solution is $(2, 1)$!

4. REF vs. RREF: A Quick Comparison

          Row Echelon Form (REF)            Reduced Row Echelon Form (RREF)
        (Zeros below main diagonal)         (Main diagonal is 1, zeros elsewhere)
        
            ┌   1   2   3   │  6   ┐               ┌   1   0   0   │  1   ┐
            │   0   1   1   │  2   │               │   0   1   0   │  1   │
            └   0   0   1   │  1   ┘               └   0   0   1   │  1   ┘

5. Computing Systems in Machine Learning

While Gaussian elimination is the standard method we teach on paper, it is computationally expensive for computers.

• Gaussian elimination requires $O(n^3)$ operations. If you have a matrix with $10,000$ features, it would take trillions of calculations to solve.
• In machine learning libraries (like Python's numpy.linalg.solve or PyTorch), computers use more efficient matrix factorizations like LU Decomposition or QR Factorization to solve linear systems quickly and stable.

6. Check Your Understanding