LUP Decomposition

The LUP decomposition of an $n \times n$ matrix $A$ is the triple $(L, U, P)$ satisfying

Here:

• $L$: unit lower triangular, $n \times n$ with all diagonal entries $1$
• $U$: upper triangular, $n \times n$
• $P$: permutation matrix, $n \times n$

Properties

• $P$ permutes the rows of $A$, placing large entries in the pivot position to avoid dividing by a small or zero element. Same reordering as partial pivoting.
• LUP decomposition exists for any nonsingular matrix $A$.
• LUP decomposition of $A$ is not unique.
• LUP decomposition solves $A\vec{x} = \vec{b}$ more robustly than LU decomposition without pivoting, at approximately the same cost.

Solving $A\vec{x} = \vec{b}$

Multiplying $A\vec{x} = \vec{b}$ by $P$ and substituting $PA = LU$ gives

• Solve $L\vec{y} = P\vec{b}$ for $\vec{y}$ by forward substitution.
• Solve $U\vec{x} = \vec{y}$ for $\vec{x}$ by back substitution.

Recursive Leading-Row-Column Algorithm

Recursively constructs $L$, $U$, $P$ so that $PA = LU$.

Block Matrix Notation

An $n \times n$ matrix can be partitioned into a $2 \times 2$ grid of smaller matrices, called blocks. Each block is itself a matrix, vector, or scalar, sized so the blocks line up into an $n \times n$ whole.

Here:

• $\bar{a}_{11}$: $1 \times 1$, a scalar
• $\bar{a}_{12}^T$: $1 \times (n-1)$, a row vector
• $\bar{a}_{21}$: $(n-1) \times 1$, a column vector
• $\bar{A}_{22}$: $(n-1) \times (n-1)$, a matrix

Block matrices multiply like ordinary matrices, treating each block as if it were a single entry, provided block dimensions are compatible for each product and sum.

The Schur complement of $\bar{a}_{11}$ in the block matrix above is

The block $\bar{A}_{22}$ with the effect of $\bar{a}_{11}$‘s row and column subtracted out.

Base Case

$n = 1$: $A = (a)$, so $L = (1)$, $U = (a)$, $P = (1)$.

Recursive Step

• Choose row $i$ so that $|a_{i1}| \geq |a_{j1}|$ for all $j = 1, 2, \ldots, n$.
• Let $P_1$ be the permutation matrix that moves row $i$ to row $1$, leaving the other rows in order.
• Let $\bar{A} = P_1 A$, partitioned in block form

• Eliminate the first column below $\bar{a}_{11}$

$A'$ is the Schur complement of $\bar{a}_{11}$ in $\bar{A}$, as defined above.

• Recurse on $A'$ to find $P_2, L_2, U_2$ with $P_2 A' = L_2 U_2$.
• Combine

Meaning of Each Part

• $\bar{a}_{11}$
  Scalar. The pivot, already the largest entry of column $1$ after the swap.
• $\bar{a}_{12}^T$
  $1 \times (n-1)$ row vector. The rest of pivot row $1$, to the right of $\bar{a}_{11}$.
• $\bar{a}_{21}$
  $(n-1) \times 1$ column vector. The rest of column $1$, below $\bar{a}_{11}$. This is what elimination must zero out.
• $\bar{A}_{22}$
  $(n-1) \times (n-1)$ block. Everything else, untouched by the swap.
• $\bar{a}_{21}/\bar{a}_{11}$
  Column of multipliers, 1 per row below the pivot. Same role as $m_{ji}$ in ordinary LU: the amount of the pivot row subtracted from each row below to clear column $1$.
• $A'$
  $(n-1) \times (n-1)$ block left over after elimination. Algebraically identical to what remains of $\bar{A}_{22}$ once each row has had a multiple of $\bar{a}_{12}^T$ subtracted from it.

The recursion is elimination applied to 1 column at a time, exactly as in Gaussian elimination, but written so each step reduces the problem to a strictly smaller matrix $A'$ instead of looping over rows.

• $A'$ depends on $\bar{a}_{21}$, $\bar{a}_{12}^T$, $\bar{a}_{11}$, all fixed only after $P_1$ is chosen and the first elimination is done.
• The pivot row for $A'$ is therefore chosen from $A'$‘s own first column, not from $A$‘s. This is why $P$ cannot be computed in 1 pass: $P_2$ requires $A'$, and $A'$ requires $P_1$.
• The recursion bottoms out at $n = 1$, where there is nothing left to pivot or eliminate.

Building $L$, $U$, $P$ From the Base Case

The recursion computes $A'$ going down, then builds $L$, $U$, $P$ going back up, 1 level at a time, using the combine formulas.

At each level, the level below has already returned a smaller $L_2$, $U_2$, $P_2$ solving $P_2 A' = L_2 U_2$. That triple is embedded whole into the bottom-right $(n-1) \times (n-1)$ block of the current level’s $L$, $U$, $P$. The current level contributes only its own pivot row and pivot column, in the first row and column.

• $U$
  Top row is $\bar{a}_{11}$ and $\bar{a}_{12}^T$, unchanged from this level. Bottom-right block is $U_2$, unchanged from below. No mixing between levels, since elimination already zeroed out the rest of column $1$.
• $L$
  Top row is $1$ then zeros, since row $1$ of $\bar{A}$ was never used to eliminate anything. First column below the diagonal is the multiplier column $\bar{a}_{21}/\bar{a}_{11}$, but permuted by $P_2$ first, so its entries land in the same row order as $L_2$. Bottom-right block is $L_2$, unchanged from below.
• $P$
  $P_2$ is embedded into the bottom-right block of an $n \times n$ identity, giving a matrix that reorders rows $2, \ldots, n$ and leaves row $1$ fixed. This is multiplied by $P_1$, so $P_1$‘s swap is applied first, then $P_2$‘s reordering.

Unwinding starts at the base case, $L = (1)$, $U = (a)$, $P = (1)$, and combines 1 level at a time until level $1$ returns the full $n \times n$ $L$, $U$, $P$.

Worked Example

Level 1, $n = 3$:

• Column $1$ is $(0 \enspace 2 \enspace 6)^T$. Largest magnitude is $6$, row $3$. $i = 3$.
• $P_1$ swaps row $1$ and row $3$.

• $\bar{a}_{11} = 6$, $\bar{a}_{12}^T = (8 \enspace 8)$, $\bar{a}_{21} = (2 \enspace 0)^T$, $\bar{A}_{22} = \begin{pmatrix} 9 & 0 \\ 5 & 5 \end{pmatrix}$.
• Multipliers: $\bar{a}_{21}/\bar{a}_{11} = (1/3 \enspace 0)^T$.
• Schur complement:

Level 2, recurse on $A'$, $n = 2$:

• Column $1$ is $(19/3 \enspace 5)^T \approx (6.33 \enspace 5)^T$. Largest is row $1$. $i = 1$, so $P_2 = I_2$, no swap.
• $\bar{a}_{11} = 19/3$, $\bar{a}_{12}^T = (-8/3)$, $\bar{a}_{21} = (5)$, $\bar{A}_{22} = (5)$.
• Multiplier: $5 / (19/3) = 15/19$.
• Schur complement:

Level 3, base case, $n = 1$: $L = (1)$, $U = (135/19)$, $P = (1)$.

Combine level 2 with the base case: $P_2 = I_2$, so

Combine level 1 with level 2: $P_2 = I_2$, so $P$ reduces to $P_1$

$PA$ places row $3$ of $A$ first, row $2$ second, row $1$ last, matching the row swap chosen at level $1$. $L$ and $U$ multiply back to this reordered matrix.