The magic factorization expresses a matrix as:

$ A = CW^{-1}R^* $

where:

• $C$ is an $m \times r$ matrix of linearly independent columns from $A$
• $R^*$ is an $r \times n$ matrix of linearly independent rows from $A$
• $W$ is the $r \times r$ invertible submatrix at the intersection
• $r = \text{rank}(A)$

Construction:

1. Identify pivot positions in RREF$(A)$
2. Extract pivot columns from $A$ to form $C$
3. Extract pivot rows from $A$ to form $R^*$
4. $W$ is the submatrix of $A$ at intersection of these rows/columns

Applications:

• Expresses $A$ in terms of its essential structure
• Generalizes LU factorization
• Useful in numerical linear algebra