Lecture from 23.10.2024 | Video: Videos ETHZ

## Gauss-Jordan Elimination

Gauss-Jordan elimination is an extension of Gaussian elimination that reduces a matrix to **reduced row echelon form (RREF)**. This form simplifies solving linear systems and determining properties like rank and linear independence. First let us define **REF** and **RREF**.

### REF and RREF

Let $R=[r_{ij}]_{i=1,j=1}$ be an $m×n$ matrix. $R$ is in **row echelon form (REF)** if the following holds: There exist $r≤m$ column indices $1≤j_{1}<j_{2}<⋯<j_{r}≤n$ such that:

- For $i=1,2,…,r$, we have $r_{ij_{i}}=1$ (1’s in gray).
- For all $i,j$, we have $r_{ij}=0$ whenever:
- $i>r$ (completely white rows) or
- $j<j_{i}$ (partially white rows) or
- $j=j_{k}$ (0’s in gray) for all $k>i$.

If $r=m$, $R$ is in **reduced row echelon form (RREF)** (no completely white rows).

You can denote these matrices by:

- REF($j_{1},j_{2},…,j_{r}$)
- RREF($j_{1},j_{2},…,j_{m}$).

Note that naturally you can’t convert a tall and skinny matrix into RREF, since you have more columns than matrices.

Another thing you can observe immediately is: REF($j_{1},j_{2},j_{3},…j_{r}$) has a rank of $r$, since the columns $j_{1},j_{2},…,j_{r}$ are independent.

### Direct Solution of Linear Systems in REF

**Direct solution:** If $A$ is in REF($j_{1},j_{2},…,j_{r}$) (rows $i>r$ are zero)

- If $b_{i}=0$ for some $i>m$:
**no solution!**(since any linear combination of the column vectors of $A$ will return a $0$ in those columns) - Otherwise: $x_{j}={b_{i},0, ifj=j_{i}otherwise. $

Our trivial solution, called canonical solution is when we simply put in $b_{i}$ in the right spot. Note that there might be other solutions too. You could technically put any number into x at all the spots where $x_{i}=0$.

### Solution Set

When we have a matrix in REF, it’s easy to see the solution (or lack thereof).

**Unique Solution:**If $R$ is the identity matrix, $x=c$.**Infinite Solutions:**If $R$ has a row of zeros, and the corresponding entry in $c$ is also zero, there are infinitely many solutions (free variables).**No Solution:**If $R$ has a row of zeros, but the corresponding entry in $c$ is non-zero, the system is inconsistent and has no solution.

### Gauss-Jordan Elimination Algorithm

The Gauss-Jordan algorithm extends Gaussian elimination by performing the following steps:

**Forward Elimination (Gaussian Elimination):**Transform the matrix into row echelon form (REF) using the same steps as Gaussian elimination. This involves creating pivots (leading**1s**) and using them to eliminate entries below.**Backward Elimination:**Starting from the last pivot, eliminate entries*above*the pivot using row operations. This step transforms the matrix from REF to RREF.

#### Example

Let’s use Gauss-Jordan elimination to transform the following matrix $A$ into RREF:

$A= 123 246 3710 $**Forward Elimination:**- Subtract 2 times row 1 from row 2: $ 103 206 3110 $
- Subtract 3 times row 1 from row 3: $ 100 200 311 $
- Subtract row 2 from row 3: $ 100 200 310 $

**Backward Elimination:**- Subtract 3 times row 2 from row 1: $ 100 200 010 $

This is now in RREF.

### Properties and Applications

**Rank:**The rank of a matrix is equal to the number of non-zero rows (or pivots) in its RREF.**Linear Independence:**The columns of a matrix are linearly independent if and only if the RREF has a pivot in every column.**Inverse Calculation:**Gauss-Jordan elimination can be used to calculate the inverse of a matrix (see Calculating the Inverse).

## Properties of REF

### Invertibility and REF

**Theorem 3.21:** Let $A$ be an $m×n$ matrix. There exists an invertible $m×m$ matrix $M$ such that $MA=R_{0}$ is in REF.

**Proof:** Every elementary row operation is equivalent to multiplying by an invertible elementary matrix. Since REF can be reached through a sequence of elementary row operations, $MA$ can be obtained by multiplying $A$ by the product of those invertible matrices.

**Important Note:** The theorem doesn’t guarantee $MA$ to be in RREF, only in REF.

**Connection to Solving Linear Systems:**
The matrix $M$ represents the sequence of row operations used to transform $A$ into REF. If we apply the same sequence of row operations to the augmented matrix $[A∣b]$, we get $[MA∣Mb]$. Since $R_{0}=MA$ is in REF, we can now directly solve the system $MAx=R_{0}x=Mb=c$ using the method described above. This gives us the same solution as the original system $Ax=b$.

*It’s quite similar to the usefulness of LU decomposition. See: [[10 Calculating the Inverse, LU and LUP Decomposition#solving-ax—b-with-lu|Solving $Ax=b$ with LU]]*

### Independence and REF

**Theorem 3.22:** Let $A$ be an $m×n$ matrix, $M$ an invertible $m×m$ matrix, and $R=MA$ in REF($j_{1},j_{2},…,j_{r}$). Then $A$ has independent columns $j_{1},j_{2},…,j_{r}$.

**Proof:**

**Column $j$ of $A$ is dependent $⟺$ there is $x$ in $R_{n}$: $Ax=0$ and $x_{j}=−1,x_{k}=0$ for $k>j$.**This means that column $j$ can be written as a linear combination of previous columns.**The same condition is true for $R=MA$: $Rx=M(Ax)=0$.****Since $Ax=0$ and $Mx=0$ have the same solutions, $A$ and $R_{0}$ have the same (in)dependent columns.**$R_{0}$ has independent columns $j_{1},j_{2},…,j_{r}$ because they are leading columns in REF.

**Important Note:** This theorem applies to REF, not RREF.

An interesting consequence of this theorem is that if $A$ is invertible, then by the Inverse Theorem (Inverse Theorem (Theorem 3.11)), we know all columns are independent $⟹R_{0}inREF(1,2,…m)$ and $R_{0}=I$ and $⟹M=A_{−1}$.

### CR decomposition

**Theorem 3.24:** Let $A$ be an $m×n$ matrix; how to combine the independent columns; $R$ how to get all columns.

- $A$ is in REF($j_{1},j_{2},…,j_{r}$). Then:
- $R$ = the first $r$ rows of $R_{0}$ (the nonzero rows of $R_{0}$).
- $C$ = columns $j_{1},j_{2},…,j_{r}$ of $A$ (the independent columns of $A$)

**Proof:** $R_{0}=MCR$.

**$M$**is the product of elementary row operation matrices that transform $A$ into $R_{0}$.- $C$ has columns $j_{1},j_{2},…,j_{r}$ of $A$ (the independent ones by Lemma 3.22).
- $MC$ has columns $j_{1},j_{2},…,j_{r}$ of $R_{0}=MA$: the unit vectors $e_{1},e_{2},…,e_{r}$.

**Visualization:**

**$MC$**: an $m×r$ matrix consisting of the identity matrix ($I$) in the top $r$ rows and zeros below.**$R_{0}$**: an $(m−r)×n$ matrix with the remaining rows of $R_{0}$.

**Key Points:**

- The CR decomposition provides a way to express an arbitrary matrix $A$ in terms of its independent columns and the corresponding unit vectors.
- It allows us to understand the relationship between the columns of $A$ and its REF.

**Continue here:** 12 Vector Spaces, Subspaces