Page 165 - 35Linear Algebra

7.7 LU Redux 165

Reading homework: problem 7

For matrices that are not square, LU decomposition still makes sense.
Given an m × n matrix M, for example we could write M = LU with L
a square lower unit triangular matrix, and U a rectangular matrix. Then
L will be an m × m matrix, and U will be an m × n matrix (of the same
shape as M). From here, the process is exactly the same as for a square
matrix. We create a sequence of matrices L i and U i that is eventually the
LU decomposition. Again, we start with L 0 = I and U 0 = M.

−2 1 3
Example 99 Let’s find the LU decomposition of M = U 0 = . Since M
−4 4 1
is a 2 × 3 matrix, our decomposition will consist of a 2 × 2 matrix and a 2 × 3 matrix.

1 0
Then we start with L 0 = I 2 = .
0 1
The next step is to zero-out the first column of M below the diagonal. There is
only one row to cancel, then, and it can be removed by subtracting 2 times the first
row of M to the second row of M. Then:

1 0 −2 1 3
L 1 = , U 1 =
2 1 0 2 −5
Since U 1 is upper triangular, we’re done. With a larger matrix, we would just continue
the process.

7.7.3 Block LDU Decomposition

Let M be a square block matrix with square blocks X, Y, Z, W such that X −1
exists. Then M can be decomposed as a block LDU decomposition, where
D is block diagonal, as follows:

X Y
M =
Z W
Then:

I 0 X 0 I X Y
−1
M = .
ZX −1 I 0 W − ZX −1 Y 0 I

165