Linear Algebra Basics Chapter 2: Elimination, Row Echelon Form, and Gaussian Elimination

In Chapter 1 we covered the concept of linear equation systems, matrix singularity, and determinants. This post focuses on actually solving those systems — starting from elimination, moving through row echelon forms, Gaussian elimination, and Rank.

This post is based on Week 1 of DeepLearning.AI's Mathematics for Machine Learning and Data Science.

What You'll Learn#

• Solving linear systems with Elimination
• Using Matrix Row Reduction to express the same process in matrix form
• Computing Row Echelon Form (REF) and Reduced Row Echelon Form (RREF)
• Finding Rank and using it to determine how many solutions a system has

---

Solving a Non-Singular System — Elimination#

Elimination works by combining equations to cancel out variables one at a time.

Example:

$\begin{cases} a + b = 11 \\ a - b = -5 \end{cases}$

If both equations are true, then any sum or difference of them is also true.

Step 1 — Add the two equations:

$(a + b) + (a - b) = 11 + (-5)$

$2a = 6 \quad \Rightarrow \quad a = 3$

Step 2 — Substitute $a = 3$:

$3 + b = 11 \quad \Rightarrow \quad b = 8$

Verify: $3 + 8 = 11$ ✓, $3 - 8 = -5$ ✓

Core principle: If an equation is true, then any linear combination of it — sums, differences, or scalar multiples — is also true. This is the mathematical foundation of elimination.

---

Solving Singular Systems#

1 Degree of Freedom — Infinitely Many Solutions#

$\begin{cases} a + b = 5 \\ 2a + 2b = 10 \end{cases}$

Subtracting twice equation 1 from equation 2:

$(2a + 2b) - 2(a + b) = 10 - 10$

$0 = 0$

This is an identity — always true. Both equations carry the same information, so $a$ can be any value and $b = 5 - a$ follows along.

This is called 1 degree of freedom — there is one variable we can freely choose.

No Solution — Inconsistent System#

$\begin{cases} a + b = 5 \\ 2a + 2b = 12 \end{cases}$

Subtracting twice equation 1 from equation 2:

$0 = 2$

This is a contradiction. The system has no solution.

---

Systems with More Variables#

The same principle applies to three-variable systems.

$\begin{cases} x + y + z = 6 \\ 2x + y + z = 8 \\ x + 2y + z = 9 \end{cases}$

Step 1 — Eliminate $x$ from rows 2 and 3 using row 1:

• $R_2 \leftarrow R_2 - 2R_1$: $\quad -y - z = -4$
• $R_3 \leftarrow R_3 - R_1$: $\quad y + 0z = 3$

Step 2 — Substitute $y = 3$:

$-3 - z = -4 \Rightarrow z = 1$

Step 3 — Back substitution:

$x + 3 + 1 = 6 \Rightarrow x = 2$

Solution: $x = 2,\ y = 3,\ z = 1$

---

Matrix Row Reduction#

The same process can be expressed using matrices instead of equations.

$\begin{cases} a + b = 11 \\ 2a - b = 2 \end{cases} \quad \Rightarrow \quad \begin{bmatrix} 1 & 1 \\ 2 & -1 \end{bmatrix}$

Apply row operation ($R_2 \leftarrow R_2 - 2R_1$):

$\begin{bmatrix} 1 & 1 \\ 0 & -3 \end{bmatrix}$

This form is Row Echelon Form (REF). From here, $-3b = -24 \Rightarrow b = 8$, then $a = 3$.

Reduced Row Echelon Form (RREF) goes one step further — each variable is fully isolated:

$\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \quad \Rightarrow \quad a = 3,\ b = 8$

Row Echelon Form of a Singular System#

For a singular system, elimination produces an all-zero row.

$\begin{bmatrix} 1 & 1 \\ 2 & 2 \end{bmatrix} \xrightarrow{R_2 - 2R_1} \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix}$

The second row is entirely zero, indicating infinitely many solutions (1 degree of freedom).

---

The 3 Rules of Row Echelon Form#

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

1. Each pivot (diagonal element) is 0 or 1
2. Everything below the diagonal is 0
3. Everything above the diagonal:
   • Can be any value if the pivot is 1
   • Must be 0 if the pivot is 0

---

Row Operations That Preserve Singularity#

The operations applied to equations can be applied equally to matrix rows. Crucially, these operations do not change the singularity of the matrix.

Note: Adding a fixed constant to every element of a row is not a valid row operation — it can change the singularity of the matrix.

---

Matrix Rank#

Rank represents the amount of independent information a matrix contains.

• After converting to REF, the number of non-zero rows equals the rank
• Equivalently: the maximum number of linearly independent rows

$\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \xrightarrow{\text{REF}} \begin{bmatrix} 1 & 2 \\ 0 & -2 \end{bmatrix} \quad \Rightarrow \quad \text{rank} = 2 \quad \text{(non-singular)}$

$\begin{bmatrix} 1 & 2 \\ 2 & 4 \end{bmatrix} \xrightarrow{\text{REF}} \begin{bmatrix} 1 & 2 \\ 0 & 0 \end{bmatrix} \quad \Rightarrow \quad \text{rank} = 1 \quad \text{(singular)}$

Rank and the Number of Solutions#

For an $n \times n$ matrix ($n$ variables, $n$ equations):

---

Gaussian Elimination#

Gaussian elimination is a systematic algorithm that applies row operations to an augmented matrix — the coefficient matrix combined with the constants column — to solve a system.

Step-by-Step Example#

$\begin{cases} x + 2y + z = 7 \\ 2x + y + z = 8 \\ x + y + 2z = 8 \end{cases}$

Augmented matrix:

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

Step 1 — $R_2 \leftarrow R_2 - 2R_1$, $R_3 \leftarrow R_3 - R_1$:

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

Step 2 — $R_3 \leftarrow R_3 - \frac{1}{3}R_2$:

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

Row Echelon Form (REF) is now complete.

Step 3 — Back Substitution:

$\frac{4}{3}z = 3 \Rightarrow z = \frac{9}{4}$

$-3y - \frac{9}{4} = -6 \Rightarrow y = \frac{5}{4}$

$x + 2 \cdot \frac{5}{4} + \frac{9}{4} = 7 \Rightarrow x = \frac{9}{4}$

Algorithm summary: Forward elimination builds the REF → Back substitution yields the solution.

---

Key Concepts Summary#

---

Quiz#

Q1. Solve the following system using elimination.

$\begin{cases} 3x + 2y = 1 \\ x - y = 3 \end{cases}$

Show answer

$R_1 \leftarrow R_1 - 3R_2$: $(3x + 2y) - 3(x - y) = 1 - 9$

$5y = -8 \Rightarrow y = -\frac{8}{5}$

$x = 3 + y = 3 - \frac{8}{5} = \frac{7}{5}$

Solution: $x = \dfrac{7}{5},\ y = -\dfrac{8}{5}$

---

Q2. Convert the following matrix to Row Echelon Form (REF) and find its rank.

$\begin{bmatrix} 1 & 2 & 3 \\ 2 & 4 & 6 \\ 0 & 1 & 1 \end{bmatrix}$

Show answer

$R_2 \leftarrow R_2 - 2R_1$:

$\begin{bmatrix} 1 & 2 & 3 \\ 0 & 0 & 0 \\ 0 & 1 & 1 \end{bmatrix}$

$R_2 \leftrightarrow R_3$ (swap rows):

$\begin{bmatrix} 1 & 2 & 3 \\ 0 & 1 & 1 \\ 0 & 0 & 0 \end{bmatrix}$

There are 2 non-zero rows, so rank = 2 (singular matrix).

---

Q3. Which of the following operations does NOT preserve the singularity of a matrix?

1. Swap two rows
2. Add one row to another
3. Add 5 to every element in a row
4. Multiply a row by 3

Show answer

Option 3 — Adding a fixed constant to all elements of a row is not a valid equation operation and can change the singularity of the matrix.

Options 1, 2, and 4 are all valid row operations that preserve singularity.

---

Q4. Determine the rank and solution type for the following system.

$\begin{cases} x + y = 3 \\ 2x + 2y = 6 \\ 3x + 3y = 9 \end{cases}$

Show answer

Augmented matrix:

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

After applying $R_2 \leftarrow R_2 - 2R_1$ and $R_3 \leftarrow R_3 - 3R_1$:

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

rank = 1, degrees of freedom = 1 → Infinitely many solutions (singular system)

All three equations carry the same information.

---

In the next post, we'll cover vector operations (addition, subtraction, dot product, norm), linear transformations, matrix multiplication, matrix inverses, and how all of this connects to neural networks (perceptrons).