11 Gauss-Jordan, REF, RREF, Properties of REF

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}^{m,n}$ be an $m\times n$ matrix. $R$ is in row echelon form (REF) if the following holds: There exist $r\le m$ column indices $1\le j_1<j_2<\cdots <j_r\le n$ such that:

1. For $i=1,2,\dots ,r$, we have $r_{i{j}_i}=1$ (1’s in gray).
2. 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,\dots ,j_r$)
• RREF($j_1,j_2,\dots ,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,\dots j_r$) has a rank of $r$, since the columns $j_1,j_2,\dots ,j_r$ are independent.

Direct Solution of Linear Systems in REF

Direct solution: If $A$ is in REF($j_1,j_2,\dots ,j_r$) (rows $i>r$ are zero)

• If $b_i\ne 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=\{\begin{array}{ll}{b}_i,& \text{if }j=j_i\\ 0,& \text{otherwise}.\end{array}$$

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:

1. 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.
2. 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:

1. Forward Elimination:
   • Subtract 2 times row 1 from row 2: $$\left[\begin{array}{ccc}1& 2& 3\\ 0& 0& 1\\ 3& 6& 10\end{array}\right]$$
   • Subtract 3 times row 1 from row 3: $$\left[\begin{array}{ccc}1& 2& 3\\ 0& 0& 1\\ 0& 0& 1\end{array}\right]$$
   • Subtract row 2 from row 3: $$\left[\begin{array}{ccc}1& 2& 3\\ 0& 0& 1\\ 0& 0& 0\end{array}\right]$$
   This is now in REF.
2. Backward Elimination:
   • Subtract 3 times row 2 from row 1: $$\left[\begin{array}{ccc}1& 2& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}\right]$$

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\times n$ matrix. There exists an invertible $m\times 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\times n$ matrix, $M$ an invertible $m\times m$ matrix, and $R=MA$ in REF($j_1,j_2,\dots ,j_r$). Then $A$ has independent columns $j_1,j_2,\dots ,j_r$.

Proof:

• Column $j$ of $A$ is dependent $⟺$ there is $x$ in ${\mathbb{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,\dots ,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\text{ in }REF(1,2,\dots m)$ and $R_0=I$ and $⟹M=A^{-1}$.

CR decomposition

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

• $A$ is in REF($j_1,j_2,\dots ,j_r$). Then:
  • $R$ = the first $r$ rows of $R_0$ (the nonzero rows of $R_0$).
  • $C$ = columns $j_1,j_2,\dots ,j_r$ of $A$ (the independent columns of $A$)

Proof: $R_0=MCR$.

1. $M$ is the product of elementary row operation matrices that transform $A$ into $R_0$.
2. $C$ has columns $j_1,j_2,\dots ,j_r$ of $A$ (the independent ones by Lemma 3.22).
3. $MC$ has columns $j_1,j_2,\dots ,j_r$ of $R_0=MA$: the unit vectors $e_1,e_2,\dots ,e_r$.

Visualization:

• $MC$: an $m\times r$ matrix consisting of the identity matrix ($I$) in the top $r$ rows and zeros below.
• $R_0$: an $(m-r)\times 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