Gauss-Jordan Elimination

RREF

Definition

Example

$RREF(2,3,6,8)$ The white squares are 0, the empty grey squares are arbitrary numbers

Read the solution

General algorithm

Input: $A\mathbf{x}=b_j,j\in [m]$ Output: $R\mathbf{x}={\mathbf{c}}_j,j\in [m]$

Runtime: $O(m^2(m+n))$

Relation to CR-decomposition

CR decomposition

• Proof