Chapter 76. PLU Decomposition

PLU decomposition is LU decomposition with row permutation. It factors a row-reordered matrix into a lower triangular matrix and an upper triangular matrix.

The standard form is

Here $A$ is the original matrix, $P$ is a permutation matrix, $L$ is lower triangular, and $U$ is upper triangular. The factor $P$ records row exchanges. The factors $L$ and $U$ record Gaussian elimination after those row exchanges. PLU is used because ordinary LU may fail when a pivot is zero, while row exchanges can move a usable pivot into position.

76.1 Motivation

LU decomposition without pivoting assumes that the required pivots are nonzero. This assumption is too strong.

Consider

The first pivot is $0$. Gaussian elimination cannot divide by this pivot. However, the matrix itself is not defective for solving linear systems. We can exchange the two rows:

This matrix is already upper triangular. The problem was the row order, not the matrix.

PLU decomposition separates these two issues. The permutation matrix $P$ chooses a workable row order. The triangular factors $L$ and $U$ then describe the elimination.

76.2 Permutation Matrices

A permutation matrix is obtained by rearranging the rows of the identity matrix. Each row contains exactly one $1$, and each column contains exactly one $1$. All other entries are $0$.

For example,

exchanges the first two rows of a matrix. If

then

Left multiplication by a permutation matrix permutes rows. Right multiplication by a permutation matrix permutes columns. In PLU decomposition, the usual purpose of $P$ is row permutation.

76.3 The Factorization

A PLU decomposition has the form

The factors have the following roles.

The matrix $P$ is orthogonal in the real case:

Therefore the equation

can also be written as

Some authors call this a PLU decomposition. Others reserve PLU for

The difference is only convention. The essential point is that a permutation factor is included with the triangular factors.

76.4 Why Pivoting Is Needed

Gaussian elimination proceeds by choosing a pivot, dividing by it, and using multiples of the pivot row to eliminate entries below it.

At step $k$, the pivot is the entry in position $(k,k)$ of the current matrix. If this entry is zero, elimination cannot proceed. If it is very small, elimination can proceed algebraically, but the computation may be unstable in floating point arithmetic.

Pivoting exchanges rows so that a better pivot appears in the pivot position.

In partial pivoting, the pivot row is chosen from the current column. The usual rule is to choose the row whose candidate pivot has largest absolute value. This is the most common version in practical LU factorization.

76.5 Partial Pivoting

Suppose the elimination is at column $k$. We examine the entries

Partial pivoting chooses an index $r$ such that

Then rows $k$ and $r$ are exchanged.

After the row exchange, the pivot is as large as possible within the remaining part of the current column. This does not guarantee perfect numerical behavior in every artificial example, but it is reliable in ordinary dense computations and widely used in numerical software.

76.6 A Simple Example

Let

Ordinary LU without pivoting fails because the first pivot is $0$.

Exchange the two rows. The permutation matrix is

Then

This matrix is already upper triangular, so we may take

Thus

This example shows the purpose of $P$. The permutation allows the triangular factorization to proceed.

76.7 A Three by Three Example

Let

The first pivot is $0$, so we exchange the first row with the second row. This gives

Now eliminate the entry below the first pivot in row $3$. The multiplier is

Subtract $\frac{1}{2}$ times row $1$ from row $3$:

At the second pivot position, the pivot is $2$. The entry below it is also $2$. No row exchange is necessary.

The multiplier is

Subtract row $2$ from row $3$:

The lower triangular factor is

The permutation matrix that exchanges the first two rows is

Therefore

Indeed,

76.8 Solving Systems with PLU

Suppose we want to solve

If

then multiply the equation $Ax=b$ by $P$:

Since $PA=LU$, this becomes

Introduce

Then solve the two triangular systems

and

Thus PLU solving has three stages:

The row permutation must be applied to the right-hand side as well as the coefficient matrix.

76.9 Example: Solving a System

Let

We have

First compute

Since $L$ is the identity matrix,

Now solve

That is,

The second equation gives

so

The first equation gives

Substituting $x_2=3$,

so

Therefore

76.10 Determinants from PLU

PLU decomposition also gives an efficient determinant formula.

If

then

If $L$ is unit lower triangular, then

Since $U$ is triangular,

Therefore

The determinant of a permutation matrix is either $1$ or $-1$. Each row exchange changes the sign. If the factorization uses $s$ row exchanges, then

Thus

This formula is commonly used in numerical computation, often through the logarithm of the absolute determinant when the matrix is large or ill-scaled.

76.11 Invertibility

A square matrix $A$ is invertible exactly when all pivots in a complete PLU factorization are nonzero.

If

and $P$, $L$, and $U$ are all invertible, then $A$ is invertible. The permutation matrix $P$ is always invertible. A unit lower triangular matrix $L$ is invertible. Therefore the decisive condition is whether $U$ has nonzero diagonal entries.

Since $U$ is triangular,

if and only if

Equivalently,

for every $i$.

76.12 Algorithm

The following algorithm computes a PLU decomposition using partial pivoting.

plu_decomposition(A):
    n = number of rows of A

    P = identity matrix of size n
    L = zero matrix of size n by n
    U = copy of A

    for k = 1 to n:
        pivot = k

        for i = k to n:
            if abs(U[i,k]) > abs(U[pivot,k]):
                pivot = i

        if U[pivot,k] == 0:
            stop: matrix is singular

        if pivot != k:
            swap rows k and pivot in U
            swap rows k and pivot in P
            swap entries L[k,1:k-1] and L[pivot,1:k-1]

        L[k,k] = 1

        for i = k+1 to n:
            L[i,k] = U[i,k] / U[k,k]
            U[i,k:n] = U[i,k:n] - L[i,k] * U[k,k:n]

    return P, L, U

The row swap in $L$ affects only columns already computed. This detail is important. Those entries store previous elimination multipliers, and their row order must remain consistent with the current row order.

76.13 Storage in Practice

Numerical libraries usually do not store $P$, $L$, and $U$ as three full dense matrices.

Instead, they commonly store:

The pivot vector records which rows were exchanged. The array that originally held $A$ is overwritten by the entries of $L$ and $U$.

This storage method avoids unnecessary memory use. It also reflects the fact that $L$ and $U$ occupy complementary triangular parts of the matrix, except for the diagonal of $L$, which is known to be all ones.

76.14 Operation Count

For a dense $n \times n$ matrix, PLU decomposition with partial pivoting has the same leading arithmetic cost as ordinary LU:

operations, ignoring lower-order terms.

Pivot search and row exchanges add lower-order work. The search for pivots costs on the order of $n^2$ comparisons. Row exchanges also cost on the order of $n^2$ data movement.

Thus pivoting improves robustness without changing the leading cubic cost of dense LU factorization.

76.15 Numerical Stability

Pivoting is not only a device for avoiding zero pivots. It also helps control numerical error.

If a pivot is very small, the multipliers

can become very large. Large multipliers can magnify rounding errors and produce unreliable results.

Partial pivoting chooses a large available pivot in the current column. This keeps the multipliers bounded in magnitude by $1$, since

after pivoting within the column.

This bound is one reason partial pivoting is effective in practice. It does not eliminate all possible instability, but it prevents the most immediate source of large elimination multipliers.

76.16 PLU and Row Echelon Form

PLU decomposition is closely related to row echelon form.

Gaussian elimination transforms a matrix into an upper triangular or row echelon matrix. PLU records the same process in factored form:

The matrix $U$ is the echelon-like result. The matrix $L$ stores the elimination multipliers. The matrix $P$ stores the row exchanges.

Thus PLU is not a different method from Gaussian elimination. It is Gaussian elimination with memory.

76.17 Comparison with LU

Ordinary LU is useful when the matrix is known to allow elimination without row exchanges. PLU is the standard default for general dense matrices.

76.18 Common Conventions

There are several equivalent ways to write the same idea.

When reading formulas, check which side of $A$ the permutation matrix appears on. The mathematical content is the same, but the stored permutation may represent either the performed row swaps or their inverse.

76.19 Summary

PLU decomposition extends LU decomposition by allowing row exchanges:

The permutation matrix $P$ records pivoting. The lower triangular matrix $L$ records elimination multipliers. The upper triangular matrix $U$ records the result of elimination.

PLU is the standard practical form of LU decomposition for general square matrices. It avoids zero pivots when possible, improves numerical stability, and provides an efficient way to solve systems:

It also gives direct access to determinant computation, invertibility tests, and reusable factorizations for multiple right-hand sides.