Gaussian elimination and PALU decomposition

From elimination to PALU

At each pivot, eliminate entries below it by subtracting a multiple of the pivot row. The multiples are recorded in a unit lower-triangular matrix $L$; the resulting echelon matrix is $U$. If the pivot rows are reordered, that row permutation is the permutation matrix $P$.

$$PA=LU$$

Here $P$ reorders rows of the original matrix, $L$ stores the elimination multipliers, and $U$ is the row-echelon result. For a square nonsingular matrix, this is the familiar PALU factorization. The same identity also applies to the rectangular matrices in this demo.

Find the leftmost column with a nonzero entry among the rows not yet chosen.
Choose a pivot row there. Partial pivoting chooses the largest absolute entry in that column.
For each remaining row, record $\ell_{ik}=a_{i,j_k}/a_{k,j_k}$, where $j_k$ is the pivot column, then apply $R_i\leftarrow R_i-\ell_{ik}R_k$.
Place the pivot row next in the final row order; repeat. Rows with no pivot go at the bottom.

A pivot is the first nonzero entry of a row after earlier elimination steps. A row-echelon matrix has pivots moving strictly right as you go down, with zero rows at the bottom.

Explore the steps

Matrix shape

Matrix density

Pivot selection

Partial pivoting picks the largest-magnitude eligible pivot. Both choices may reorder rows; the difference is how the pivot is chosen.

Current matrix: × ; displayed to decimal places.

chosen (completed) row
not yet chosen
eliminated zero
pivot

Step of

The resulting factorization

The final row order defines $P$. In the displayed $L$, each entry below the diagonal is the multiplier used to eliminate that row; the diagonal entries are 1. $U$ is the echelon matrix after putting rows in that same order. Entries are rounded to the displayed precision.

The source matrix is random; choose a shape or density to generate another example.