## 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:

## 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):