2.4-2.5 Partitioned Matrices & LU Factorization

Theory: Partitioned Matrices & LU Factorization

Partitioned (Block) Matrices (Lay §2.4)

A matrix can be partitioned into submatrices (called blocks) by horizontal and vertical lines:

A = \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix}

If the block sizes are conformable for matrix multiplication, partitioned matrices can be multiplied block by block as if their entries were scalars:

\begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix} \begin{bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{bmatrix} = \begin{bmatrix} A_{11}B_{11} + A_{12}B_{21} & A_{11}B_{12} + A_{12}B_{22} \\ A_{21}B_{11} + A_{22}B_{21} & A_{21}B_{12} + A_{22}B_{22} \end{bmatrix}

Block Diagonal Inverses

If $A$ is a block diagonal matrix where each diagonal block $A_{ii}$ is square and invertible:

A = \begin{bmatrix} A_1 & 0 \\ 0 & A_2 \end{bmatrix} \implies A^{-1} = \begin{bmatrix} A_1^{-1} & 0 \\ 0 & A_2^{-1} \end{bmatrix}

LU Factorization (Lay §2.5)

An LU factorization expresses an $m \times n$ matrix $A$ as the product:

A = LU

where:

$L$ is an $m \times m$ unit lower-triangular matrix (has $1$ s on the main diagonal and $0$ s above the main diagonal).
$U$ is an $m \times n$ upper-triangular / row echelon matrix.

    [ 1   0   0 ]   [ *   *   * ]
L = [ *   1   0 ]   [ 0   *   * ] = U
    [ *   *   1 ]   [ 0   0   * ]

[!NOTE] Why LU Factorization? When solving a series of equations $A\mathbf{x} = \mathbf{b}$ with different $\mathbf{b}$ vectors, solving two triangular systems takes only on the order of $n^2$ operations, compared to $\frac{2}{3}n^3$ for full row reduction of $A$ each time.

The Algorithm for $A = LU$

(When $A$ can be row-reduced to echelon form without row interchanges):

Reduce $A$ to an echelon form $U$ using only row replacement operations (adding multiples of a row to a row below it).
The entries in $L$ below its main diagonal record the multipliers used to clear entries: if operation $R_i \leftarrow R_i - c R_j$ was used, the entry in row $i$ , column $j$ of $L$ is $c$ .

Solving $A\mathbf{x} = \mathbf{b}$ Using $LU$

Since $A\mathbf{x} = L(U\mathbf{x}) = \mathbf{b}$ , set $\mathbf{y} = U\mathbf{x}$ :

Forward Substitution: Solve $L\mathbf{y} = \mathbf{b}$ for $\mathbf{y}$ .
Back Substitution: Solve $U\mathbf{x} = \mathbf{y}$ for $\mathbf{x}$ .

Solved Examples (Textbook Questions)

Exercise 1

(Adapted from Lay §2.4, Exercise 11)

Let $A = \begin{bmatrix} A_{11} & A_{12} \\ 0 & A_{22} \end{bmatrix}$ be a block upper-triangular matrix, where $A_{11}$ is $p \times p$ , $A_{22}$ is $q \times q$ , and both $A_{11}$ and $A_{22}$ are invertible.

Find a formula for $A^{-1}$ in block form.

Show solution ↓

Solution

We search for a block matrix $B = \begin{bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{bmatrix}$ such that:

A B = \begin{bmatrix} A_{11} & A_{12} \\ 0 & A_{22} \end{bmatrix} \begin{bmatrix} B_{11} & B_{12} \\ B_{21} & B_{22} \end{bmatrix} = \begin{bmatrix} I_p & 0 \\ 0 & I_q \end{bmatrix}

Multiply the blocks:

$A_{11} B_{11} + A_{12} B_{21} = I_p$
$A_{11} B_{12} + A_{12} B_{22} = 0$
$0 \cdot B_{11} + A_{22} B_{21} = 0 \implies A_{22} B_{21} = 0$
$0 \cdot B_{12} + A_{22} B_{22} = I_q \implies A_{22} B_{22} = I_q$

Solve for the blocks:

From (4): Since $A_{22}$ is invertible, $B_{22} = A_{22}^{-1}$ .
From (3): Multiply from the left by $A_{22}^{-1}$ : $B_{21} = A_{22}^{-1}(0) = 0$
From (1): Since $B_{21} = 0$ : $A_{11} B_{11} = I_p \implies B_{11} = A_{11}^{-1}$
From (2): $A_{11} B_{12} + A_{12} A_{22}^{-1} = 0 \implies A_{11} B_{12} = -A_{12} A_{22}^{-1}$ Multiply from the left by $A_{11}^{-1}$ : $B_{12} = -A_{11}^{-1} A_{12} A_{22}^{-1}$

Conclusion:

A^{-1} = \begin{bmatrix} A_{11}^{-1} & -A_{11}^{-1} A_{12} A_{22}^{-1} \\ 0 & A_{22}^{-1} \end{bmatrix}

Exercise 2

(Adapted from Lay §2.5, Exercise 7)

Find an LU factorization of the matrix:

A = \begin{bmatrix} 2 & 4 & -6 \\ 1 & 5 & 3 \\ 1 & 3 & -7 \end{bmatrix}

Explicitly state the row operations, the multipliers, and the matrices $L$ and $U$ .

Show solution ↓

Solution

We reduce $A$ to an upper-triangular echelon form $U$ using only row replacements:

Step 1: Clear column 1 below the pivot $a_{11} = 2$ .

Row 2: $R_2 \leftarrow R_2 - \left(\frac{1}{2}\right) R_1$
$[1, 5, 3] - \frac{1}{2}[2, 4, -6] = [0, 3, 6]$
Multiplier for position $(2, 1)$ : $\ell_{21} = \frac{1}{2}$ .
Row 3: $R_3 \leftarrow R_3 - \left(\frac{1}{2}\right) R_1$
$[1, 3, -7] - \frac{1}{2}[2, 4, -6] = [0, 1, -4]$
Multiplier for position $(3, 1)$ : $\ell_{31} = \frac{1}{2}$ .

The intermediate matrix is:

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

Step 2: Clear column 2 below the pivot in row 2 (which is $3$ ).

Row 3: $R_3 \leftarrow R_3 - \left(\frac{1}{3}\right) R_2$ $[0, 1, -4] - \frac{1}{3}[0, 3, 6] = [0, 0, -6]$ Multiplier for position $(3, 2)$ : $\ell_{32} = \frac{1}{3}$ .

This gives the upper-triangular matrix $U$ :

U = \begin{bmatrix} 2 & 4 & -6 \\ 0 & 3 & 6 \\ 0 & 0 & -6 \end{bmatrix}

Step 3: Construct $L$ . Place $1$ s on the diagonal and the recorded multipliers below:

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

Verification:

LU = \begin{bmatrix} 1 & 0 & 0 \\ 1/2 & 1 & 0 \\ 1/2 & 1/3 & 1 \end{bmatrix} \begin{bmatrix} 2 & 4 & -6 \\ 0 & 3 & 6 \\ 0 & 0 & -6 \end{bmatrix} = \begin{bmatrix} 2 & 4 & -6 \\ 1 + 0 & 2 + 3 & -3 + 6 \\ 1 + 0 + 0 & 2 + 1 + 0 & -3 + 2 - 6 \end{bmatrix} = \begin{bmatrix} 2 & 4 & -6 \\ 1 & 5 & 3 \\ 1 & 3 & -7 \end{bmatrix} = A \quad \checkmark

Exercise 3

(Adapted from Lay §2.5, Exercise 1 & 3)

Solve the system $A\mathbf{x} = \mathbf{b}$ using the given LU factorization:

L = \begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & -5 & 1 \end{bmatrix}, \quad U = \begin{bmatrix} 2 & -3 & 1 \\ 0 & 4 & 2 \\ 0 & 0 & 3 \end{bmatrix}, \quad \mathbf{b} = \begin{bmatrix} 1 \\ 0 \\ 11 \end{bmatrix}

Show solution ↓

Solution

The problem $A\mathbf{x} = \mathbf{b}$ is solved in two sequential steps:

Solve $L\mathbf{y} = \mathbf{b}$ for $\mathbf{y}$ (Forward Substitution).
Solve $U\mathbf{x} = \mathbf{y}$ for $\mathbf{x}$ (Back Substitution).

Step 1: Forward Substitution ( $L\mathbf{y} = \mathbf{b}$ )

\begin{bmatrix} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 2 & -5 & 1 \end{bmatrix} \begin{bmatrix} y_1 \\ y_2 \\ y_3 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 11 \end{bmatrix}

From row 1: $y_1 = 1$
From row 2: $-y_1 + y_2 = 0 \implies -1 + y_2 = 0 \implies y_2 = 1$
From row 3: $2y_1 - 5y_2 + y_3 = 11 \implies 2(1) - 5(1) + y_3 = 11 \implies -3 + y_3 = 11 \implies y_3 = 14$

So $\mathbf{y} = \begin{bmatrix} 1 \\ 1 \\ 14 \end{bmatrix}$ .

Step 2: Back Substitution ( $U\mathbf{x} = \mathbf{y}$ )

\begin{bmatrix} 2 & -3 & 1 \\ 0 & 4 & 2 \\ 0 & 0 & 3 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ 14 \end{bmatrix}

From row 3: $3x_3 = 14 \implies x_3 = \frac{14}{3}$
From row 2: $4x_2 + 2x_3 = 1 \implies 4x_2 + 2\left(\frac{14}{3}\right) = 1$ $4x_2 = 1 - \frac{28}{3} = -\frac{25}{3} \implies x_2 = -\frac{25}{12}$
From row 1: $2x_1 - 3x_2 + x_3 = 1 \implies 2x_1 - 3\left(-\frac{25}{12}\right) + \frac{14}{3} = 1$ $2x_1 + \frac{25}{4} + \frac{14}{3} = 1 \implies 2x_1 + \frac{75 + 56}{12} = 1 \implies 2x_1 + \frac{131}{12} = \frac{12}{12}$ $2x_1 = -\frac{119}{12} \implies x_1 = -\frac{119}{24}$

Conclusion: The solution is:

\mathbf{x} = \begin{bmatrix} -119/24 \\ -25/12 \\ 14/3 \end{bmatrix}

2.4-2.5 Partitioned Matrices & LU Factorization

Theory: Partitioned Matrices & LU Factorization

Partitioned (Block) Matrices (Lay §2.4)

Block Diagonal Inverses

LU Factorization (Lay §2.5)

The Algorithm for A=LUA = LUA=LU

Solving Ax=bA\mathbf{x} = \mathbf{b}Ax=b Using LULULU

Solved Examples (Textbook Questions)

The Algorithm for $A = LU$

Solving $A\mathbf{x} = \mathbf{b}$ Using $LU$