Elimination Algorithm

Input: An $n\times k$ matrix ($M\in M_{n\times k}(\mathbb{F})$) Output: A matrix $M^{\prime }$ in Echelon Form equivalent to $M$

Process

1. Check for zero rows. If the rows $R_r$ for $i\le r\le n$ are all zeroes, then we’re done
2. Otherwise, find the first non-zero coeff. find the $a_{rj}\ne 0$ with the smallest $j$ and $r\ge i$
   1. Divide out $a_{rj}$ by applying the operation $M\stackrel{\frac{1}{a_{rk}}{R}_r}{\to }{M}_{next}$
   2. Exchange $R_i$ and $R_r$ by applying operation $M\stackrel{R_r\leftrightarrow R_i}{\to }{M}_{next}$
   3. Clear the column $j$th column using operation $M\stackrel{-a_{rj}{R}_i+R_j}{\to }{M}_{next}$
3. Run the elimination algorithm on $M_{next}$

This process is based off the Every Linear System Has A Row-Echelon Form Theorem