Gaussian Elimination

Gaussian elimination is the systematic method for solving any system of linear equations. You’ll learn the three row operations, how to reduce a matrix to echelon form, and how to read off the solution.

Gaussian elimination turns a system of equations into an augmented matrix and then uses row operations to simplify it into row echelon form (or reduced row echelon form).

These are the only moves you’re allowed to make on an augmented matrix (they don’t change the solution):

1. Swap two rows
2. Multiply a row by a nonzero scalar
3. Add a multiple of one row to another row

Transform the augmented matrix into this staircase pattern:

$$\begin{bmatrix} 1 & * & * & \vert & * \\ 0 & 1 & * & \vert & * \\ 0 & 0 & 1 & \vert & * \end{bmatrix}$$

From here, you can read off the solution by back-substitution. Going further to reduced row echelon form (RREF) means each pivot is 1 and all entries above and below each pivot are zero, so the solution reads directly off the matrix.

• Unique solution: one value for each variable
• No solution: a row like $[0 \; 0 \; 0 \; \vert \; 5]$ (means $0 = 5$, impossible)
• Infinitely many solutions: a row of zeros with free variables

In the diagram: the augmented matrix is reduced step by step. Each arrow shows which row operation was applied. The final RREF form gives the solution directly: $x = 2$, $y = 1$.

Example 1: Full Row Reduction

Solve:

$$\begin{cases} 2x + 4y = 8 \\ 3x + 5y = 11 \end{cases}$$

Start with the augmented matrix:

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

Step 1: Divide $R_1$ by 2:

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

Step 2: $R_2 \leftarrow R_2 - 3R_1$:

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

Step 3: $R_2 \leftarrow -R_2$:

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

Step 4: $R_1 \leftarrow R_1 - 2R_2$:

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

Solution: $x = 2$, $y = 1$.

Example 2: No Solution

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

$R_2 \leftarrow R_2 - R_1$:

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

The bottom row says $0 = 2$, which is impossible. No solution.

Example 3: A 3x3 System

$$\begin{cases} x + y + z = 6 \\ 2x + 3y + z = 14 \\ x - y + 2z = 2 \end{cases}$$

Augmented matrix:

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

$R_2 \leftarrow R_2 - 2R_1$, $R_3 \leftarrow R_3 - R_1$:

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

$R_3 \leftarrow R_3 + 2R_2$:

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

Back-substitute: $-z = 0$ so $z = 0$. Then $y - 0 = 2$ so $y = 2$. Then $x + 2 + 0 = 6$ so $x = 4$.

Solution: $x = 4$, $y = 2$, $z = 0$.

Gaussian elimination (and its computer-optimized versions) is used constantly in:

• Game engines: solving for bone positions in inverse kinematics, balancing physics constraints, lighting calculations
• Computer graphics: solving large systems for realistic rendering
• Machine learning: least squares regression
• Engineering: circuit analysis, structural engineering

Example: When a game character grabs an object, inverse kinematics uses Gaussian elimination to figure out the exact joint angles needed to reach the target position. The engine sets up a system of equations and row-reduces it every frame.