Gaussian Elimination

Chapter 1 • Section 1-2

"Why was the matrix sad? Because it had too many problems (equations)! 😂"

🪜 Row-Echelon Form (REF)

Before we solve systems, we need to tidy up our matrices. Think of this as organizing your room before you can find your lost socks.

Definition: Row-Echelon Matrix

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

  • All zero rows are at the bottom. 📉
  • The first nonzero entry in each nonzero row is a 1 (called the leading 1). 🥇
  • Each leading 1 is to the right of all leading 1's in the rows above it. ➡️

Definition: Reduced Row-Echelon Matrix

A matrix is in Reduced Row-Echelon Form (RREF) if:

  • It is in Row-Echelon Form.
  • Each leading 1 is the only nonzero entry in its column. 🦄

Visualizing RREF

$$ \left[\begin{array}{rrrr} 1 & 0 & 2 & 0 \\ 0 & 1 & 1 & 2 \\ 0 & 0 & 0 & 0 \end{array}\right] $$

Clean, organized, beautiful. ✨

🕵️ Spot the RREF Win $10

Which of these matrices is in Reduced Row-Echelon Form (RREF)?

🧹 Gaussian Elimination Algorithm

The ultimate algorithm to solve ANY linear system. It's like a recipe for success! 🍳

1

Transform to RREF

Use elementary row operations to turn your augmented matrix into a Reduced Row-Echelon Matrix.

2

Check for Inconsistency

If you see a row like $[0 \dots 0 \mid 1]$, STOP! 🛑 The system has no solution.

3

Solve for Variables

Assign parameters ($s, t, \dots$) to non-leading variables. Express leading variables in terms of these parameters.

Theorem: Existence of RREF

Every matrix can be reduced to at least one Reduced Row-Echelon Form matrix using elementary row operations.

Theorem: Uniqueness of RREF

Every matrix is row equivalent to a unique reduced row-echelon matrix.

This means no matter which row operations you use, you will always end up with the same RREF!

Let's Solve Some Problems! 🧠

Case 1: Unique Solution

System:

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

Resulting RREF:

$$ \left[\begin{array}{rrr|r} 1 & 0 & 0 & 5/3 \\ 0 & 1 & 0 & -4/3 \\ 0 & 0 & 1 & -2/3 \end{array}\right] $$

Solution: $x = 5/3, y = -4/3, z = -2/3$. Simple and clean! 😎

Advanced Problem: General Patterns

Find conditions on $a, b, c$ such that the system has (i) a unique solution, (ii) no solution, or (iii) infinitely many solutions.

$$ \begin{cases} 2x + 3y + az = b \\ -y + 2z = c \\ x + 3y - 2z = 1 \end{cases} $$

Solution Steps

  1. Augmented Matrix:
    $$ \left[\begin{array}{rrr|r} 2 & 3 & a & b \\ 0 & -1 & 2 & c \\ 1 & 3 & -2 & 1 \end{array}\right] $$
  2. Row Reduce: After several operations (swapping rows, eliminating), we get:
    $$ \left[\begin{array}{rrr|c} 1 & 0 & 4 & 1+3c \\ 0 & 1 & -2 & -c \\ 0 & 0 & a-2 & b-2-3c \end{array}\right] $$
  3. Analyze Cases:
    • Case 1 ($a-2 \neq 0$): If $a \neq 2$, we can divide by $(a-2)$ to get a leading 1 in the last row. $\implies$ Unique Solution.
    • Case 2 ($a=2$): The last row becomes $[0 \ 0 \ 0 \mid b-2-3c]$.
      • If $b-2-3c \neq 0$, we have $0 = \text{nonzero}$. $\implies$ No Solution.
      • If $b-2-3c = 0$, we have $0 = 0$. $\implies$ Infinitely Many Solutions.

🤔 Logic Check Win $15

If a system has a row $[0 \ 0 \ 0 \mid 0]$ in its RREF, what does it imply?

Rank of a Matrix 🎖️

The rank of a matrix $A$, denoted $\operatorname{rank} A$, is simply the number of leading 1's in its REF.

The Rank Theorem for $n$ variables:

  • If $\operatorname{rank} A < n$ (and consistent) $\rightarrow$ Infinitely many solutions (parameters = $n - \operatorname{rank} A$). ♾️
  • If $\operatorname{rank} A = n$ (and consistent) $\rightarrow$ Unique solution. 1️⃣

Example: Find the rank.

$$ A = \left[\begin{array}{rrr} 1 & -2 & 1 \\ 0 & 3 & 2 \end{array}\right] $$

There are 2 leading terms (the 1 and the 3). So, $\operatorname{rank} A = 2$.

Application: Sum of Powers ⚡

Ever wondered how to find the formula for $1^3 + 2^3 + \dots + n^3$? We can use linear algebra!

Assume it's a polynomial of degree 4: $S(n) = a_0 + a_1 n + a_2 n^2 + a_3 n^3 + a_4 n^4$.

Since $S(0) = 0$, we know $a_0 = 0$. We need to find $a_1, a_2, a_3, a_4$.

Plug in $n=1, 2, 3, 4$ to get a system of 4 equations!

$$ \left[\begin{array}{cccc|c} 1 & 1 & 1 & 1 & 1 \\ 2 & 4 & 8 & 16 & 9 \\ 3 & 9 & 27 & 81 & 36 \\ 4 & 16 & 64 & 256 & 100 \end{array}\right] $$

Solving this gives: $a_1=0, a_2=1/4, a_3=1/2, a_4=1/4$.

$$ \sum_{i=1}^n i^3 = \frac{n^2(n+1)^2}{4} $$

Mind = Blown 🤯

🏆 Final Boss Win $50

Does the Reduced Row-Echelon Form of a matrix depend on the sequence of operations used to get there?