$\newcommand{\la}{\langle}$ $\newcommand{\ra}{\rangle}$ $\newcommand{\vu}{\mathbf{u}}$ $\newcommand{\vv}{\mathbf{v}}$ $\newcommand{\vw}{\mathbf{w}}$ $\newcommand{\vzz}{\mathbf{z}}$ $\newcommand{\nc}{\newcommand}$ $\nc{\Cc}{\mathbb{C}}$ $\nc{\Rr}{\mathbb{R}}$ $\nc{\Qq}{\mathbb{Q}}$ $\nc{\Nn}{\mathbb{N}}$ $\nc{\cB}{\mathcal{B}}$ $\nc{\cE}{\mathcal{E}}$ $\nc{\cC}{\mathcal{C}}$ $\nc{\cD}{\mathcal{D}}$ $\nc{\mi}{\mathbf{i}}$ $\nc{\span}[1]{\langle #1 \rangle}$ $\nc{\ol}[1]{\overline{#1} }$ $\nc{\norm}[1]{\left\| #1 \right\|}$ $\nc{\abs}[1]{\left| #1 \right|}$ $\nc{\vz}{\mathbf{0}}$ $\nc{\vo}{\mathbf{1}}$ $\nc{\DMO}{\DeclareMathOperator}$ $\DMO{\tr}{tr}$ $\DMO{\nullsp}{nullsp}$ $\nc{\va}{\mathbf{a}}$ $\nc{\vb}{\mathbf{b}}$ $\nc{\vx}{\mathbf{x}}$ $\nc{\ve}{\mathbf{e}}$ $\nc{\vd}{\mathbf{d}}$ $\nc{\vh}{\mathbf{h}}$ $\nc{\ds}{\displaystyle}$ $\nc{\bm}[1]{\begin{bmatrix} #1 \end{bmatrix}}$ $\nc{\gm}[2]{\bm{\mid & \cdots & \mid \\ #1 & \cdots & #2 \\ \mid & \cdots & \mid}}$ $\nc{\MN}{M_{m \times n}(K)}$ $\nc{\NM}{M_{n \times m}(K)}$ $\nc{\NP}{M_{n \times p}(K)}$ $\nc{\MP}{M_{m \times p}(K)}$ $\nc{\PN}{M_{p \times n}(K)}$ $\nc{\NN}{M_n(K)}$ $\nc{\im}{\mathrm{Im\ }}$ $\nc{\ev}{\mathrm{ev}}$ $\nc{\Hom}{\mathrm{Hom}}$ $\nc{\com}[1]{[\phantom{a}]^{#1}}$ $\nc{\rBD}[1]{ [#1]_{\cB}^{\cD}}$ $\DMO{\id}{id}$ $\DMO{\rk}{rk}$ $\DMO{\nullity}{nullity}$ $\DMO{\End}{End}$ $\DMO{\proj}{proj}$ $\nc{\GL}{\mathrm{GL}}$

Gauss-Jordan Elimination (Row Reduction)

The Gauss-Jordan Elimination (GJE) (something also called row reduction) is the key algorithm in Linear Algebra. It takes a matrix over a field as input and return the rref of its input.

GJE(M)
--------------------------
Input  : A matrix A over a field
Output : The rref of A
-------------------------
    FE = forward_eliminate(A)
    RA = back_substitute(FE)
    return RA
forward_eliminate(A):
    if A is the zero matrix: return A
    (m,n) = dimensions(A)
    (i,j) = index of the first non-zero entry of A # here (i,j) < (k,l) if (j <l) or (j=l and i < k)  
    R_1 <--> R_i  #swap R_i to the top row
    (1/a[1,j])R_1 --> R_1 #divide the first row by its pivot
    for 2 <= k <= m:
            -a_[k,j]R_1+R_k --> R_k #eliminate the other entries of that column. 
    D = A.delete(R1) # delete the first row from A
    F = forward_eliminate(D) # run forward_eliminate on the resulting matrix.
    return stack(R1,F) #stack R1 on top of the result from the previous step then return
back_substitution(A):
    for k in [m..2]: 
        j = the column index of the pivot of R_i
        for i in [k-1..1]:
            (-a_(i,j)R_k)+R_i ---> R_i # eliminate all entry above the pivot of R_k
    return A

Here is a more human readable form:

Input a matrix $A$.

Part I Forward Elimination: Start with the top row.

  1. If the current row and the rows below are all zero, then this Part is done. Otherwise, make the current row contains a left-most pivot among the remaining rows (the current one and those below) by ERO II (swapping) if necessary.
  2. Make the pivot 1 by ERO I (rescaling) if necessary.
  3. Eliminate all entries below the current pivot by ERO III (add a mulitple of row) if necessary.

If current row is the last row, then this part is finished otherwise move to the next row and repeat Step 1 through Step 3.

After Part I is done.

Part II. Backward Substitution:

Start with the last nonzero row.

  1. Elminate all entries above the current pivot by ERO III (add a multiple of row) if necessary.

If the current row is not the top row, move the row above and repeat Step 1.

As we have seen in the last lecture, a square matrix is invertible if and only if its rref is an identity matrix. Hence, GJE also can be used to find the inverse of an invertible matrix.

More generally, we can use GJE to find an invertible matrix $M$ so that $MA$ is the rref of $A$.

Instead of just applying GJE to $A \in M_n(K)$, we apply it to the block matrix $B = [A|I_n]$. Since $A$ is on the left and $I_n$ is in rref. It is easy to see that any sequence of EROs $\rho_1, \ldots, \rho_k$ that turns $A$ into $R_A$ turns $B$ into $R_B$.

Let $E_i$ be the elementary matrix corresponding to $\rho_i$ ($1 \le i \le k$), then $$R_B = (E_k \cdots E_1)B = (E_k\cdots E_1)[A|I_n] = [E_k\cdots E_1A | E_k\cdots E_1] = [MA|M] = [R_A|M]$$

So, the right side of $R_B$ is an invertible matrix $M$ so that $MA = R_A$. In particular, if $A$ is invertible, then $MA = I_n$ hence $M = A^{-1}$.

Checkpoint. Let $$ A = \left[\begin{array}{cccc} 2 & 1 & 1 & 7 \\ 1 & 0 & 1 & 2 \\ 1 & 2 & 0 & 7 \end{array}\right] $$ find the matrix $M$ by GJE so that $MA$ is the rref of $A$.

Checkpoint. Let $$ A = \left[\begin{array}{ccccc} -2 & -4 & 1 & 3 & -1 \\ 0 & 0 & -1 & 1 & 0 \\ 2 & 4 & -1 & -3 & -2 \\ 2 & 4 & -1 & -3 & -2 \end{array}\right] $$ find the matrix $M$ by GJE so that $MA$ is the rref of $A$.