LU Factorization and Pivoting, linear algebra I lesson

Two measurements lead to the equations $2x + y = 5$ and $4x + 3y = 11$ . Elimination subtracts twice the first equation from the second, which leaves $y = 1$ and then $x = 2$ . When new measurements arrive, say $1$ and $1$ , only the right side is new, so every elimination step on the coefficients stays the same. This lesson stores the elimination in two triangular matrices so that each new right side costs only two quick substitutions, and it shows how to keep track of row swaps along the way. Tuples such as $(5, 11)$ stand for column vectors.

Key terms

Lower and upper triangular matrices

Definition A square $n \times n$ matrix $L = [\ell_{ij}]$ is lower triangular if $\ell_{ij} = 0$ whenever $i < j$ , so every entry above the main diagonal is zero. It is unit lower triangular if, in addition, every diagonal entry equals $1$ . A square matrix $U = [u_{ij}]$ is upper triangular if $u_{ij} = 0$ whenever $i > j$ , so every entry below the main diagonal is zero. A triangular matrix is invertible exactly when all of its diagonal entries are nonzero. A product of lower triangular matrices of the same size is lower triangular, and the same holds for upper triangular and for unit lower triangular matrices.

In plain words A triangular matrix keeps all of its nonzero entries on the diagonal or on one side of it. A system whose coefficient matrix is triangular with nonzero diagonal entries can be solved one unknown at a time.

Example The matrices

L = \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix}, \qquad U = \begin{bmatrix} 2 & 1 \\ 0 & 1 \end{bmatrix}

are unit lower triangular and upper triangular. Every echelon form of a square matrix is upper triangular, because the leading entry of row $i$ lies in column $i$ or further right.

LU factorization

Definition Let $A$ be an $n \times n$ matrix, and suppose Gaussian elimination reduces $A$ to an upper triangular matrix $U$ without swapping rows. It works through the columns from left to right, and in column $j$ it applies $R_i \to R_i - \ell_{ij}R_j$ to each row $i > j$ . The numbers $\ell_{ij}$ are the elimination multipliers. Each one is the entry being cleared divided by the pivot in position $(j, j)$ , so every pivot used as a divisor must be nonzero. Then

A = LU,

where $L$ is the unit lower triangular matrix whose entry in position $(i, j)$ below the diagonal is $\ell_{ij}$ . This is an LU factorization of $A$ . The reason is that elimination multiplies $A$ on the left by elementary matrices, giving $EA = U$ , and $L = E^{-1}$ adds back every row multiple that elimination subtracted. That is why the multipliers enter $L$ with a plus sign.

In plain words Elimination subtracts multiples of higher rows from lower rows. The matrix $L$ remembers those multiples, and multiplying by $L$ adds them back, which rebuilds $A$ from $U$ .

Example For

A = \begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix}

the multiplier is $\ell_{21} = 4/2 = 2$ , and $R_2 \to R_2 - 2R_1$ leaves the matrix $U$ from the previous example. Then

\begin{aligned} LU &= \begin{bmatrix} 1 & 0 \\ 2 & 1 \end{bmatrix} \begin{bmatrix} 2 & 1 \\ 0 & 1 \end{bmatrix} \\[0.4em] &= \begin{bmatrix} 2 & 1 \\ 4 & 3 \end{bmatrix} = A. \end{aligned}

The second row of $LU$ is twice the first row of $U$ plus the second row of $U$ ,

2\begin{bmatrix} 2 & 1 \end{bmatrix} + \begin{bmatrix} 0 & 1 \end{bmatrix} = \begin{bmatrix} 4 & 3 \end{bmatrix}.

Storing $-2$ instead, copied from the sign of the row operation, would give the second row $\begin{bmatrix} -4 & -1 \end{bmatrix}$ , which does not rebuild $A$ .

Forward substitution

Definition Let $L$ be an $n \times n$ lower triangular matrix with nonzero diagonal entries. Forward substitution solves $L\mathbf{w} = \mathbf{b}$ from the top down, computing for $i = 1, 2, \dots, n$ in turn

w_i = \frac{1}{\ell_{ii}}\Bigl(b_i - \sum_{j=1}^{i-1} \ell_{ij} w_j\Bigr).

Each row finds one new unknown from the ones above it, and for a unit lower triangular $L$ there is no division at all. Back-substitution solves $U\mathbf{x} = \mathbf{w}$ for an upper triangular $U$ with nonzero diagonal entries in the same way from the bottom up. If $A = LU$ , the system $A\mathbf{x} = \mathbf{b}$ reads $L(U\mathbf{x}) = \mathbf{b}$ , so it is solved in two triangular steps,

L\mathbf{w} = \mathbf{b}, \qquad U\mathbf{x} = \mathbf{w}.

The back-substitution needs every diagonal entry of $U$ to be nonzero, which holds exactly when $A$ is invertible.

In plain words Forward substitution replays the stored elimination on a new right side. Back-substitution then solves the triangular system from the bottom. The vector $\mathbf{w}$ in the middle is the right side after elimination, not the answer.

Example With $L$ and $U$ from above and $\mathbf{b} = (5, 11)$ , forward substitution gives $w_1 = 5$ and $2 \cdot 5 + w_2 = 11$ , so $\mathbf{w} = (5, 1)$ . Back-substitution in $2x + y = 5$ , $y = 1$ gives $y = 1$ and $x = 2$ . For the new data $\mathbf{b} = (1, 1)$ the same factors give $w_1 = 1$ and $2 + w_2 = 1$ , so $\mathbf{w} = (1, -1)$ . Then $y = -1$ and $2x - 1 = 1$ , so $x = 1$ . The original equations check, since $2 - 1 = 1$ and $4 - 3 = 1$ .

Permutation matrix

Definition An $n \times n$ permutation matrix is a matrix obtained by reordering the rows of $I_n$ . Each of its rows and each of its columns contains exactly one entry $1$ , and all other entries are $0$ . If row $i$ of $P$ is row $k$ of $I_n$ , then row $i$ of $PA$ is row $k$ of $A$ . So multiplying on the left by $P$ reorders the rows of $A$ , and $P\mathbf{b}$ reorders the entries of $\mathbf{b}$ in the same way. Every permutation matrix is invertible, with $P^{-1} = P^{\top}$ .

In plain words A permutation matrix is the identity with its rows shuffled. Multiplying by it shuffles the rows of whatever comes next in the same way.

Example The matrix

P = \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}

consists of rows 3, 1 and 2 of $I_3$ . So $PA$ lists the rows of $A$ in the order 3, 1, 2, and $P(7, 3, 20) = (20, 7, 3)$ . Its transpose puts everything back, since $P^{\top}P = I_3$ .

Pivoted LU factorization

Definition A pivoted LU factorization of an $n \times n$ matrix $A$ is

PA = LU,

where $P$ is an $n \times n$ permutation matrix, $L$ is unit lower triangular and $U$ is upper triangular. Every square matrix has one, produced by elimination with row swaps, and $P$ records the final order of the rows. Since $P$ is invertible, $A\mathbf{x} = \mathbf{b}$ is equivalent to $PA\mathbf{x} = P\mathbf{b}$ , that is, to $LU\mathbf{x} = P\mathbf{b}$ . When $A$ is invertible, so is $U$ , and its diagonal entries are nonzero. Then solve $L\mathbf{w} = P\mathbf{b}$ by forward substitution and $U\mathbf{x} = \mathbf{w}$ by back-substitution. The permutation reorders the equations, never the unknowns, so $\mathbf{x}$ needs no reordering at the end.

In plain words When a pivot position holds a zero, swap in a lower row with a nonzero entry there, if there is one. Factor the reordered matrix, and reorder the right side in the same way before solving.

Example The matrix

K = \begin{bmatrix} 0 & 2 \\ 1 & 3 \end{bmatrix}

has a zero in its first pivot position, yet it is invertible. Swapping its rows with the permutation matrix $P$ that has rows $\mathbf{e}_2^{\top}$ and $\mathbf{e}_1^{\top}$ gives

PK = \begin{bmatrix} 1 & 3 \\ 0 & 2 \end{bmatrix},

which is already upper triangular, so $L = I_2$ and $U = PK$ . For $\mathbf{b} = (4, 7)$ the permuted right side is $P\mathbf{b} = (7, 4)$ . The second row gives $2y = 4$ , so $y = 2$ , and the first gives $x + 3y = 7$ , so $x = 1$ . In the original order the equations are $2y = 4$ and $x + 3y = 7$ , and both hold.

Partial pivoting

Definition Partial pivoting is a rule for choosing row swaps during elimination. At step $j$ , look at the entries in column $j$ in rows $j$ through $n$ of the current matrix, choose one of largest absolute value, and swap its row with row $j$ . If all of these entries are zero, position $(j, j)$ of $U$ stays zero, so $A$ is singular, and elimination moves on to the next column. Each swap exchanges three things, the two whole rows of the current matrix, the multipliers already stored in columns $1$ through $j - 1$ of $L$ for those two rows, and the two positions in the record of row order that builds $P$ . Every multiplier then has absolute value at most $1$ . In floating point arithmetic this tends to limit the growth of rounding errors, though it cannot remove the sensitivity of a badly conditioned system.

In plain words Before clearing a column, bring up the row whose entry there is largest in absolute value. When rows move, the multipliers already written in $L$ move with them, because each multiplier belongs to its row.

Example Factor

M = \begin{bmatrix} 0 & 2 & 1 \\ 1 & 1 & 0 \\ 2 & 3 & 4 \end{bmatrix}.

In column 1 the candidates are $0$ , $1$ and $2$ , so swap rows 1 and 3, and the row order becomes 3, 2, 1. The multipliers are $\ell_{21} = \tfrac{1}{2}$ and $\ell_{31} = 0$ , and $R_2 \to R_2 - \tfrac{1}{2}R_1$ gives

\begin{bmatrix} 2 & 3 & 4 \\ 0 & -\tfrac{1}{2} & -2 \\ 0 & 2 & 1 \end{bmatrix}.

In column 2 the candidates are $-\tfrac{1}{2}$ and $2$ , so swap rows 2 and 3, and the row order becomes 3, 1, 2. The stored multipliers in column 1 of $L$ swap as well, so now $\ell_{21} = 0$ and $\ell_{31} = \tfrac{1}{2}$ . The new multiplier is $\ell_{32} = -\tfrac{1}{2} \div 2 = -\tfrac{1}{4}$ , and $R_3 \to R_3 + \tfrac{1}{4}R_2$ finishes the elimination. The factors are

\begin{aligned} P &= \begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}, \\[0.8em] L &= \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ \tfrac{1}{2} & -\tfrac{1}{4} & 1 \end{bmatrix}, \\[0.8em] U &= \begin{bmatrix} 2 & 3 & 4 \\ 0 & 2 & 1 \\ 0 & 0 & -\tfrac{7}{4} \end{bmatrix}. \end{aligned}

The first two rows of $LU$ are the first two rows of $U$ , which are rows 3 and 1 of $M$ . The third row of $LU$ is

\begin{aligned} &\tfrac{1}{2}\begin{bmatrix} 2 & 3 & 4 \end{bmatrix} - \tfrac{1}{4}\begin{bmatrix} 0 & 2 & 1 \end{bmatrix} \\[0.4em] &\quad + \begin{bmatrix} 0 & 0 & -\tfrac{7}{4} \end{bmatrix} \\[0.4em] &\quad = \begin{bmatrix} 1 & 1 & 0 \end{bmatrix}, \end{aligned}

which is row 2 of $M$ , so $PM = LU$ . Had the multiplier $\tfrac{1}{2}$ stayed in row 2 of $L$ , this check would fail. For $\mathbf{b} = (7, 3, 20)$ we get $P\mathbf{b} = (20, 7, 3)$ , forward substitution gives $\mathbf{w} = (20, 7, -\tfrac{21}{4})$ , and back-substitution gives $\mathbf{x} = (1, 2, 3)$ . In the original order, $M\mathbf{x} = (4 + 3, 1 + 2, 2 + 6 + 12) = (7, 3, 20)$ .

Check yourself

Find the LU factorization of the matrix below and use it to solve $A\mathbf{x} = (4, 14)$ .

A = \begin{bmatrix} 1 & 2 \\ 3 & 8 \end{bmatrix}

Show the answer

The multiplier is $\ell_{21} = 3/1 = 3$ , and $R_2 \to R_2 - 3R_1$ leaves the upper triangular matrix, so

L = \begin{bmatrix} 1 & 0 \\ 3 & 1 \end{bmatrix}, \qquad U = \begin{bmatrix} 1 & 2 \\ 0 & 2 \end{bmatrix}.

Forward substitution gives $w_1 = 4$ and $3 \cdot 4 + w_2 = 14$ , so $\mathbf{w} = (4, 2)$ . Back-substitution gives $2y = 2$ , so $y = 1$ , and $x + 2 = 4$ , so $x = 2$ . The original equations check, since $2 + 2 = 4$ and $6 + 8 = 14$ .

Show that the matrix below has no LU factorization without row swaps, even though it is invertible. Then find $PA = LU$ and solve $A\mathbf{x} = (3, 5)$ .

A = \begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}

Show the answer

Suppose $A = LU$ with $L$ unit lower triangular and $U$ upper triangular. The top left entries give $0 = u_{11}$ , and the bottom left entries give $1 = \ell_{21}u_{11} = 0$ , which is impossible. Swapping the rows gives

PA = \begin{bmatrix} 1 & 1 \\ 0 & 1 \end{bmatrix},

which is upper triangular, so $L = I_2$ and $U = PA$ . It has two pivots, so $A$ is invertible. The right side $\mathbf{b} = (3, 5)$ becomes $P\mathbf{b} = (5, 3)$ . Back-substitution gives $y = 3$ and $x + 3 = 5$ , so $x = 2$ . In the original order, $0 \cdot 2 + 3 = 3$ and $2 + 3 = 5$ .

Use partial pivoting to factor the matrix below as $PA = LU$ , then solve $A\mathbf{x} = (5, 11)$ . What goes wrong if you forget to permute the right side?

A = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}

Show the answer

In column 1 the candidates are $1$ and $3$ , so swap the rows. The multiplier is $\ell_{21} = \tfrac{1}{3}$ , and $R_2 \to R_2 - \tfrac{1}{3}R_1$ turns the second row into $\begin{bmatrix} 0 & \tfrac{2}{3} \end{bmatrix}$ . So

\begin{gathered} P = \begin{bmatrix} 0 & 1 \\ 1 & 0 \end{bmatrix}, \qquad L = \begin{bmatrix} 1 & 0 \\ \tfrac{1}{3} & 1 \end{bmatrix}, \\[0.4em] U = \begin{bmatrix} 3 & 4 \\ 0 & \tfrac{2}{3} \end{bmatrix}. \end{gathered}

The right side $\mathbf{b} = (5, 11)$ becomes $P\mathbf{b} = (11, 5)$ . Forward substitution gives $w_1 = 11$ and $w_2 = 5 - \tfrac{11}{3} = \tfrac{4}{3}$ . Back-substitution gives $\tfrac{2}{3}y = \tfrac{4}{3}$ , so $y = 2$ , and $3x + 8 = 11$ , so $x = 1$ . The original equations check, since $1 + 4 = 5$ and $3 + 8 = 11$ .

Forgetting the permutation means solving $LU\mathbf{x} = (5, 11)$ , which gives $\mathbf{x} = (-17, 14)$ . That vector solves $PA\mathbf{x} = (5, 11)$ , so it satisfies $A\mathbf{x} = (11, 5)$ , the system with its two right sides exchanged.

LU Factorization and Pivoting

Key terms

Lower and upper triangular matrices

LU factorization

Forward substitution

Permutation matrix

Pivoted LU factorization

Partial pivoting

Check yourself

How this lesson connects

Builds on

Used later in

Where this leads in Linear Algebra II