# Schur Complement Problem (Spectral/Num. Lin./Matrix Theory)

• October 7th 2012, 02:54 AM
skeptopotamus
Schur Complement Problem (Spectral/Num. Lin./Matrix Theory)
Let $A \in F^{n \times n}$ be written in block form $A = \begin{pmatrix} A_{1,1} & A_{1,2} \\ A_{2,1} & A_{2,2} \end{pmatrix}$

where $A_{1,1} \in F^{k \times k}, A_{1,2} \in F^{n \times (n-k)}, A_{2,1} \in F^{(n-k) \times k}, A_{2,2} \in F^{(n-k) \times (n-k)}$. Let $S = A_{2,2}-A_{2,1}A_{1,1}^{-1}A_{1,2}$. Assume that $A_{1,1}$ has an $LU$ decomposition. After $k$ steps of Gaussian elimination, we have

$A^{(k+1)} = \begin{pmatrix} A_{1,1}^{(k+1)} & A_{1,2}^{(k+1)} \\ 0_{(n-k) \times k} & A_{2,2}^{(k+1)} \end{pmatrix}$.

Prove $A_{2,2}^{(k+1)} = S$.

No idea where to start on a non-horrible-looking proof. Has anyone seen this theorem before?
• October 7th 2012, 06:08 PM
skeptopotamus
Re: Schur Complement Problem (Spectral/Num. Lin./Matrix Theory)
Sorry; I should say that it is pretty obvious, but the "obvious proof" is extremely ugly and inelegant. Does anyone have a nicer one?
• October 8th 2012, 09:42 PM
skeptopotamus
Re: Schur Complement Problem (Spectral/Num. Lin./Matrix Theory)
Ok, I have solved the problem. Here is the proof, in case anybody was interested.

Let $A^{(1)} =\begin{pmatrix} A_{11}^{(1)} & A_{12}^{(1)}\\ A_{21}^{(1)} & A_{22}^{(1)} \end{pmatrix}$ such that $A_{11}$ has an $LU$ decomposition. Perform Gaussian elimination on $A$ up to the $k$th step. Then $A^{(k+1)} =\begin{pmatrix} A_{11}^{(k+1)} & A_{12}^{(k+1)}\\ 0 & A_{22}^{(k+1)} \end{pmatrix}$, $A^{(k+1)} = G_kG_{k-1}\cdots G_1A^{(1)}$. By $G_k^{-1}=L_k$, we have that $A^{(1)} = L_1L_2\cdots L_kA^{(k+1)}$.

We have that $L_1L_2\cdots L_k= \begin{pmatrix}X_1 & 0\\ X_2 & I_{(n-k) \times (n-k)} \end{pmatrix}$, where

$X_1 =\begin{pmatrix} 1 & 0 & 0 & \cdots & 0\\ m_{21} & 1 & 0 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ m_{k1} & m_{k2} & m_{k3} & \cdots & 1 \end{pmatrix}$, and

$X_2 = \begin{pmatrix} m_{k+1, 1} & m_{k+1, 2} & m_{k+1, 3} & \cdots & m_{k+1, k}\\ m_{k+2 ,1} & m_{k+2, 2} & m_{k+2, 3} & \cdots & m_{k+2, k}\\ \vdots & \vdots & \vdots & \ddots & \vdots \\ m_{n1} & m_{n2} & m_{n3} & \cdots & m_{nk} \end{pmatrix}$

Note that $X_1$ is invertible by $X_1$ triangular with non-zero entries on the main diagonal. Thus we have that

$A^{(1)} = \begin{pmatrix} X_1 & 0\\ X_2 & I_{(n-k) \times (n-k)} \end{pmatrix} \begin{pmatrix} A_{11}^{(k+1)} & A_{12}^{(k+1)}\\ 0 & A_{22}^{(k+1)} \end{pmatrix}$

By block multiplication, this implies that

$A_{11}^{(1)} = X_1A_{11}^{(k+1)}$
$A_{12}^{(1)} = X_1A_{12}^{(k+1)}$
$A_{21}^{(1)} = X_2A_{11}^{(k+1)}$
$A_{22}^{(1)} = X_2A_{12}^{(k+1)} + A_{22}^{(k+1)} \Rightarrow A_{22}^{(k+1)} = A_{22}^{(1)} - X_2A_{12}^{(k+1)}$.

But we wish to show that $A_{22}^{(k+1)} = A_{22}^{(1)} - A_{21}^{(1)}A_{11}^{(1)*}A_{12}^{(1)}$,

hence we need to show that $A_{22}^{(1)} - X_2A_{12}^{(k+1)} = A_{22}^{(1)} - A_{21}^{(1)}A_{11}^{(1)*}A_{12}^{(1)}$,

i.e. $X_2A_{12}^{(k+1)} = A_{21}^{(1)}A_{11}^{(1)*}A_{12}^{(1)}$,

where $A_{11}^{(1)*}$ is the inverse of $A_{11}^{(1)}.$

$X_2A_{11}^{(k+1)} = X_2(X_1^{-1}X_1)A_{11}^{(k+1)} =$

$X_2X_1^{-1}(X_1A_{11}^{(k+1)}) = X_2X_1^{-1}(A_{12}^{(1)})$

by $A_{12}^{(1)} = X_1A_{12}^{(k+1)}$.

Thus $X_2A_{11}^{(k+1)} = X_2X_1^{-1}A_{12}^{(1)} = X_2(A_{11}^{(k+1)}A_{11}^{(k+1)*})X_1^{-1}A_{12}^{(1)} =$

$X_2A_{11}^{(k+1)}(A_{11}^{(k+1)*}X_1^{-1})A_{12}^{(1)}$.

But $A_{11}^{(k+1)*}X_1^{-1} = A_{11}^{(1)*}$

by $A_{11}^{(1)} = X_1A_{11}^{(k+1)}$.

Therefore, $X_2A_{11}^{(k+1)} = X_2A_{11}^{(k+1)}(A_{11}^{(k+1)*}X_1^{-1})A_{12}^{(1)} = X_2A_{11}^{(k+1)}(A_{11}^{(1)*})A_{12}^{(1)} =$

$(X_2A_{11}^{(k+1)})A_{11}^{(1)*}A_{12}^{(1)} = (A_{21}^{(1)})A_{11}^{(1)*}A_{12}^{(1)} = A_{21}^{(1)}A_{11}^{(1)*}A_{12}^{(1)}$

by $A_{21}^{(1)} = X_2A_{11}^{(k+1)}$. Thus the result is proven.