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