LU Decomposition

LU Decomposition

Every square matrix $A$ (with non-zero pivots) can be factored as $A = LU$ where:

• $L$ is lower triangular with 1s on the diagonal
• $U$ is upper triangular

This is Gaussian elimination written as a matrix product.

Algorithm

For each pivot column $k$, eliminate below the diagonal by subtracting scaled rows:

$\text{factor} = \frac{U_{ik}}{U_{kk}}, \quad L_{ik} = \text{factor}, \quad U_{i} \leftarrow U_{i} - \text{factor} \cdot U_{k}$

The multipliers become the entries of $L$.

Example

$A = \begin{pmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 8 & 7 & 9 \end{pmatrix} = \underbrace{\begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 4 & 3 & 1 \end{pmatrix}}_{L} \underbrace{\begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 2 \end{pmatrix}}_{U}$

Why LU?

Once $A = LU$, solving $Ax = b$ costs $O(n^2)$ — just two triangular solves — instead of rerunning Gaussian elimination for each new $b$.

Your Task

Implement lu_decompose(A) returning (L, U). Modify a copy of A in-place for U while recording multipliers in L.