Lecture 4. Factorization into $A = LU$

讲座摘要（lecture summary）

One goal of today’s lecture is to understand Gaussian elimination in terms of matrices; to find a matrix $L$ such that $A = LU$. We start with some useful facts about matrix multiplication.

Inverse of a product

The inverse of a matrix product $AB$ is $B^{−1}A^{−1}$.

数学语言表达如下

$$(AB)^{-1} = B^{-1}A^{-1}$$

Transpose of a product

We obtain the transpose of a matrix by exchanging its rows and columns. In other words, the entry in row $i$ column $j$ of $A$ is the entry in row $j$ column $i$ of $AT$.

The transpose of a matrix product $AB$ is $B^TA^T$. For any invertible matrix $A$, the inverse of $A^T$ is $(A^{−1})^T$.

$$A = LU$$

We’ve seen how to use elimination to convert a suitable matrix $A$ into an upper triangular matrix $U$. This leads to the factorization $A = LU$, which is very helpful in understanding the matrix $A$.

Recall that (when there are no row exchanges) we can describe the elimination of the entries of matrix $A$ in terms of multiplication by a succession of elimination matrices $E_{ij}$, so that $A \to E_{21}A \to E_{31}E_{21}A \to \dots \to U$. In the two by two case this looks like:

$$\begin{array}{cccc} E_{21} & A & &U \\ \begin{bmatrix*}[c] 1 & 0 \\ -4 & 1 \end{bmatrix*} & \begin{bmatrix*}[c] 2 & 1 \\ 8 & 7 \end{bmatrix*} & = & \begin{bmatrix*}[c] 2 & 1 \\ 0 & 3 \end{bmatrix*} \end{array}$$

We can convert this to a factorization $A = LU$ by “canceling” the matrix $E_{21}$; multiply by its inverse to get $E_{21}^{−1} E_{21}A = E_{21}^{−1}U$.

$$\begin{array}{cccc} A & L & &U \\ \begin{bmatrix*}[c] 2 & 1 \\ 8 & 7 \end{bmatrix*} & \begin{bmatrix*}[c] 1 & 0 \\ 4 & 1 \end{bmatrix*} & = & \begin{bmatrix*}[c] 2 & 1 \\ 0 & 3 \end{bmatrix*} \end{array}$$

The matrix $U$ is upper triangular with pivots on the diagonal. The matrix $L$ is lower triangular and has ones on the diagonal. Sometimes we will also want to factor out a diagonal matrix whose entries are the pivots:

$$\begin{array}{ccccc} A & & L & D & U^{'} \\ \begin{bmatrix*}[c] 2 & 1 \\ 8 & 7 \end{bmatrix*}& = & \begin{bmatrix*}[c] 1 & 0 \\ 4 & 1 \end{bmatrix*} & \begin{bmatrix*}[c] 2 & 0 \\ 0 & 3 \end{bmatrix*} & \begin{bmatrix*}[r] 1 & 1/2 \\ 0 & 1 \end{bmatrix*} \end{array}$$

In the three dimensional case, if $E_{32}E_{31}E_{21}A = U$ then $A = E_{21}^{−1}E{31}^{−1}E_{32}^{−1}U = LU$.

For example, suppose $E_{31}$ is the identity matrix and $E_{32}$ and $E_{21}$ are as shown below:

$$\begin{array}{cccc} E_{32} & E_{21} & & E \\ \begin{bmatrix*}[c] 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -5 & 1 \\ \end{bmatrix*} & \begin{bmatrix*}[c] 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix*} & = & \begin{bmatrix*}[c] 1 & 0 & 0 \\ -2 & 1 & 0 \\ 10 & -5 & 1 \end{bmatrix*} \end{array}$$

The $10$ in the lower left corner arises because we subtracted twice the first row from the second row, then subtracted five times the new second row from the third.

The factorization $A = LU$ is preferable to the statement $EA = U$ because the combination of row subtractions does not have the effect on $L$ that it did on $E$. Here $L = E^{−1} = E_{21}^{−1}E_{32}^{−1}$:

$$\begin{array}{cccc} E_{21}^{-1} & E_{32}^{-1} & & L \\ \begin{bmatrix*}[c] 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix*} & \begin{bmatrix*}[c] 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 5 & 1 \end{bmatrix*} & = & \begin{bmatrix*}[c] 1 & 0 & 0 \\ 2 & 1 & 0 \\ 0 & 5 & 1 \end{bmatrix*} \end{array}$$

Notice the $0$ in row three column one of $L = E^{−1}$, where $E$ had a $10$. If there are no row exchanges, the multipliers from the elimination matrices are copied directly into $L$.

How expensive is elimination?

Some applications require inverting very large matrices. This is done using a computer, of course. How hard will the computer have to work? How long will it take?

When using elimination to find the factorization $A = LU$ we just saw that we can build $L$ as we go by keeping track of row subtractions. We have to remember $L$ and (the matrix which will become) $U$; we don’t have to store $A$ or $E_{ij}$ in the computer’s memory.

How many operations does the computer perform during the elimination process for an $n × n$ matrix? A typical operation is to multiply one row and then subtract it from another, which requires on the order of $n$ operations. There are $n$ rows, so the total number of operations used in eliminating entries in the first column is about $n^2$. The second row and column are shorter; that product costs about $(n − 1)^2$ operations, and so on. The total number of operations needed to factor $A$ into $LU$ is on the order of $n^3$:

$$1^2 + 2^2 + \dots + (n-1)^2 + n^2 = \sum_{i = 1}^n i^2 \approx \int_{0}^{n}x^2dx = \frac{1}{3}n^3.$$

While we’re factoring A we’re also operating on $\bm{b}$. That costs about $n^2$ operations, which is hardly worth counting compared to $\displaystyle\frac{1}{3}n^3$.

Row exchanges

What if there are row exchanges? In other words, what happens if there’s a zero in a pivot position?

To swap two rows, we multiply on the left by a permutation matrix. For example,

$$P_{12} = \begin{bmatrix*}[c] 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix*}$$

swaps the first and second rows of a $3 × 3$ matrix. The inverse of any permutation matrix $P$ is $P^{−1} = P^{T}$.

There are $n!$ different ways to permute the rows of an $n × n$ matrix (including the permutation that leaves all rows fixed) so there are $n!$ permutation matrices. These matrices form a multiplicative group.

Problems and Solutions（习题及答案）

Exercises on factorization into $A = LU$

Problem 4.1: What matrix $E$ puts $A$ into triangular form $EA = U$? Multiply by $E^{−1} = L$ to factor $A$ into $LU$.

$$A = \begin{bmatrix*}[c] 1 & 3 & 0 \\ 2 & 4 & 0 \\ 2 & 0 & 1 \end{bmatrix*}$$

Solution

We will perform a series of row operations to transform the matrix $A$ into an upper triangular matrix. First, we multiply the first row by $2$ and then subtract it from the second row in order to make the first element of the second row $0$.:

$$\begin{bmatrix*}[r] 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix*} \begin{bmatrix*}[c] 1 & 3 & 0 \\ 2 & 4 & 0 \\ 2 & 0 & 1 \end{bmatrix*} = \begin{bmatrix*}[r] 1 & 3 & 0 \\ 0 & -2 & 0 \\ 2 & 0 & 1 \end{bmatrix*}$$

Next, we multiply the first row by $2$ (again) and subtract it from the third row in order to make the first element of the third row $0$:

$$\begin{bmatrix*}[r] 1 & 0 & 0 \\ 0 & 1 & 0 \\ -2 & 0 & 1 \\ \end{bmatrix*} \begin{bmatrix*}[r] 1 & 3 & 0 \\ 0 & -2 & 0 \\ 2 & 0 & 1 \end{bmatrix*} = \begin{bmatrix*}[r] 1 & 3 & 0 \\ 0 & -2 & 0 \\ 0 & -6 & 1 \end{bmatrix*}$$

Now, we multiply the second row by $3$ and subtract it from the third row in order to make the second element of the third row $0$:

$$\begin{bmatrix*}[r] 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -3 & 1 \\ \end{bmatrix*} \begin{bmatrix*}[r] 1 & 3 & 0 \\ 0 & -2 & 0 \\ 0 & -6 & 1 \end{bmatrix*} = \begin{bmatrix*}[r] 1 & 3 & 0 \\ 0 & -2 & 0 \\ 0 & 0 & 1 \end{bmatrix*} = U.$$

We take the three matrices we used to perform each operation and multiply them to get $E$:

$$\begin{array}{l} E = \begin{bmatrix*}[r] 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -3 & 1 \\ \end{bmatrix*} \begin{bmatrix*}[r] 1 & 0 & 0 \\ 0 & 1 & 0 \\ -2 & 0 & 1 \\ \end{bmatrix*} \begin{bmatrix*}[r] 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix*} \\ \\ =\begin{bmatrix*}[r] 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -3 & 1 \\ \end{bmatrix*} \begin{bmatrix*}[r] 1 & 0 & 0 \\ -2 & 1 & 0 \\ -2 & 0 & 1 \\ \end{bmatrix*}= \begin{bmatrix*}[r] 1 & 0 & 0 \\ -2 & 1 & 0 \\ 4 & -3 & 1 \\ \end{bmatrix*} = E. \end{array}$$

To check, we evaluate $EA$:

$$\begin{bmatrix*}[r] 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & -3 & 1 \\ \end{bmatrix*} \begin{bmatrix*}[r] 1 & 3 & 0 \\ 2 & 4 & 0 \\ 2 & 0 & 1 \\ \end{bmatrix*}= \begin{bmatrix*}[r] 1 & 3 & 0 \\ 0 & -2 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix*} = U.$$

To find $E^{−1}$, use the Gauss-Jordan elimination method (or just insert the multipliers $2, 2, 3$ into $E^{−1}$)

$$\begin{array}{c} \bigg[\begin{array}{rrr|rrr} 1 & 0 & 0 & 1 & 0 & 0 \\ -2 & 1 & 0 & 0 & 1 & 0 \\ 4 & -3 & 1 & 0 & 0 & 1 \end{array}\bigg] \to \bigg[\begin{array}{rrr|rrr} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 2 & 1 & 0 \\ 0 & -3 & 1 & -4 & 0 & 1 \end{array}\bigg] \to \\ \\ \bigg[\begin{array}{rrr|rrr} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 2 & 1 & 0 \\ 0 & 0 & 1 & 2 & 3 & 1 \end{array}\bigg] \to \begin{bmatrix*}[r] 1 & 0 & 0 \\ 2 & 1 & 0 \\ 2 & 3 & 1 \\ \end{bmatrix*} = E^{-1} \end{array}$$

We can check that this is in fact the inverse of E:

$$EE^{-1} = \begin{bmatrix*}[r] 1 & 0 & 0 \\ -2 & 1 & 0 \\ 4 & -3 & 1 \\ \end{bmatrix*} \begin{bmatrix*}[r] 1 & 0 & 0 \\ 2 & 1 & 0 \\ 2 & 3 & 1 \\ \end{bmatrix*} = \begin{bmatrix*}[r] 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix*} = I.$$

Finally, to factorize $A$ into $LU$ (where $L = E^{−1}$):

$$\begin{bmatrix*}[c] 1 & 3 & 0 \\ 2 & 4 & 0 \\ 2 & 0 & 1 \end{bmatrix*} = A = LU = \begin{bmatrix*}[r] 1 & 0 & 0 \\ 2 & 1 & 0 \\ 2 & 3 & 1 \\ \end{bmatrix*} \begin{bmatrix*}[r] 1 & 3 & 0 \\ 0 & -2 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix*}.$$

Problem 4.2: (2.6 #13. Introduction to Linear Algebra: Strang) Compute $L$ and $U$ for the symmetric matrix

$$A = \begin{bmatrix*}[r] a & a & a & a \\ a & b & b & b \\ a & b & c & c \\ a & b & c & d \end{bmatrix*}$$

Find four conditions on $a, b, c, d$ to get $A = LU$ with four pivots.

Solution

Elimination subtracts row $1$ from rows $2-4$, then row $2$ from rows $3-4$, and finally row $3$ from row $4$; the result is $U$. All the multipliers $\ell_{ij}$ are equal to $1$; so $L$ is the lower triangular matrix with $1$’s on the diagonal and below it.

$$\begin{array}{c} A \to \begin{bmatrix*}[c] a & a & a & a \\ 0 & b-a & b-a & b-a \\ 0 & b-a & c-a & c-a \\ 0 & b-a & c-a & d-a \end{bmatrix*} \to \begin{bmatrix*}[c] a & a & a & a \\ 0 & b-a & b-a & b-a \\ 0 & 0 & c-b & c-b \\ 0 & 0 & c-b & d-b \end{bmatrix*}\to \\ \\ \begin{bmatrix*}[c] a & a & a & a \\ 0 & b-a & b-a & b-a \\ 0 & 0 & c-b & c-b \\ 0 & 0 & 0 & d-c \end{bmatrix*} = U, L = \begin{bmatrix*}[r] 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{bmatrix*} \end{array}$$

The pivots are the nonzero entries on the diagonal of $U$. So there are four pivots when these four conditions are satisfied: $a \ne 0, b \ne a, c \ne b$,and $d \ne c$.