Stuff I find slightly meaningful and close to achievable

Block gaussian elimination

This post mirrors the background section of the schur complement wikipedia entry.
It re-creates the block-LDU of a square matrix in terms of block matrices.

Assume we have a square matrix \({M}\) of size \((m+n)\times (m+n)\) with blocks \(A, B, C, D\). Assume \(A\) is square \(n \times n\) and invertible, and \(D\) is square \(m \times m\). Our matrix is:

$$
{M} =
\begin{bmatrix}
A& B\\
C& D
\end{bmatrix}
$$

and we wish to perform block gaussian elimination to remove the lower-left block \(C\).

Finding the correct transformation

We proceed by left-multiplying by a lower-block-triangular matrix \(L\):

$$
LM =
\begin{bmatrix}
L_{11} & 0 \\
L_{21} & L_{22}
\end{bmatrix}
\begin{bmatrix}
A& B\\
C& D
\end{bmatrix}
=
\begin{bmatrix}
A'& B'\\
0 & D'
\end{bmatrix}
$$

The most important equation is the equality implied by the lower-left block: we must pick \(L\) so that \(L_{21}A + L_{22}C = 0\). We do not need to find every possible solution, just one is enough. Let's pick \(L_{22} = \mathrm{I}_m\) the identity and \(L_{21} = -CA^{-1}\). To simplify things we also set \(L_{11} = \mathrm{I}_n\).

We finally have that

$$
LM =
\begin{bmatrix}
\mathrm{I}_{n} & 0 \\
-CA^{-1} & \mathrm{I}_{m}
\end{bmatrix}
\begin{bmatrix}
A& B\\
C& D
\end{bmatrix}
=
\begin{bmatrix}
A& B\\
0 & D -CA^{-1}B
\end{bmatrix}
$$

The matrix \(D -CA^{-1}B\) is called the Schur complement of \(D\) in \(M\). One can find the right order(\(D\) minus \(C, A, B\)) visually by using the following rule:

schur rule

Block diagonalization

Can we further simplify our matrix \(LM\) ? It turns out we can transform \(LM\) into a simpler matrix, a product of a triangular and diagonal matrix. To find the correct transformation, we repeat the process to find \(U\) so that

$$
LMU = \begin{bmatrix}
A& B\\
0 & D -CA^{-1}B
\end{bmatrix}
\begin{bmatrix}
U_{11} & U_{12} \\
0 & U_{22}
\end{bmatrix}
=
\begin{bmatrix}
D_{11} & 0 \\
0 & D_{22}
\end{bmatrix}
$$

Again, we only need to find one solution, and it's easy to identify the critical equation, which is the one involving the \(B\) and \(U_{12}\) blocks: \( A U_{12} + BU_{22} = 0\).
We pick (as we did before \( U_{22} = \mathrm{I}_m\) and \(U_{12} =\, – A^{-1}B\). The rest is not important, so we pick the simplest solution \(U_{11} = \mathrm{I}_n\).

Finally, the decomposition is

$$
LMU =
\begin{bmatrix}
\mathrm{I}_{n} & 0 \\
-CA^{-1} & \mathrm{I}_{m}
\end{bmatrix}
\begin{bmatrix}
A& B\\
C & D
\end{bmatrix}
\begin{bmatrix}
\mathrm{I}_{n} & \, – A^{-1}B\\
0 & \mathrm{I}_{m}
\end{bmatrix}
=
\begin{bmatrix}
A & 0 \\
0 & D – CA^{-1}B
\end{bmatrix}
$$

The LDU decomposition

The above equality can be modified by multiplying by the inverses \(\tilde{L}, \tilde{U}\) of \(L,U\). These matrices are also lower and upper triangular, so that

$$ M = \tilde{L}D\tilde{U}$$

This decomposition into simple block-matrices (block-triangular and block-diagonal) is called the block-LDU decomposition. Its final form is

$$
\begin{bmatrix}
A& B\\
C & D
\end{bmatrix}
=
\begin{bmatrix}
\mathrm{I}_{n} & 0 \\
CA^{-1} & \mathrm{I}_{m}
\end{bmatrix}
\begin{bmatrix}
A & 0 \\
0 & D – CA^{-1}B
\end{bmatrix}
\begin{bmatrix}
\mathrm{I}_{n} & \, A^{-1}B\\
0 & \mathrm{I}_{m}
\end{bmatrix}
$$

A good way of recalling quickly the decomposition is (assuming one knows the expression for the schur complement):

block ldu memo