# Shae's Ramblings

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:

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