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

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

Let $\displaystyle$A \in F^{n \times n}$$be written in block form \displaystyle A = \begin{pmatrix} A_{1,1} & A_{1,2} \\ A_{2,1} & A_{2,2} \end{pmatrix}$$

where $\displaystyle$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 \displaystyle S = A_{2,2}-A_{2,1}A_{1,1}^{-1}A_{1,2}$$. Assume that $\displaystyle$A_{1,1}$$has an \displaystyle LU$$ decomposition. After $\displaystyle$k$$steps of Gaussian elimination, we have \displaystyle 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 $\displaystyle$A_{2,2}^{(k+1)} = S$$. No idea where to start on a non-horrible-looking proof. Has anyone seen this theorem before? 2. ## 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? 3. ## 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 \displaystyle A^{(1)} =\begin{pmatrix} A_{11}^{(1)} & A_{12}^{(1)}\\ A_{21}^{(1)} & A_{22}^{(1)} \end{pmatrix}$$ such that $\displaystyle$A_{11}$$has an \displaystyle LU$$ decomposition. Perform Gaussian elimination on $\displaystyle$A$$up to the \displaystyle k$$th step. Then $\displaystyle$A^{(k+1)} =\begin{pmatrix} A_{11}^{(k+1)} & A_{12}^{(k+1)}\\ 0 & A_{22}^{(k+1)} \end{pmatrix}$$, \displaystyle A^{(k+1)} = G_kG_{k-1}\cdots G_1A^{(1)}$$. By $\displaystyle$G_k^{-1}=L_k$$, we have that \displaystyle A^{(1)} = L_1L_2\cdots L_kA^{(k+1)}$$.

We have that $\displaystyle$L_1L_2\cdots L_k= \begin{pmatrix}X_1 & 0\\ X_2 & I_{(n-k) \times (n-k)} \end{pmatrix}$$, where \displaystyle 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

$\displaystyle$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 \displaystyle X_1$$ is invertible by $\displaystyle$X_1$$triangular with non-zero entries on the main diagonal. Thus we have that \displaystyle 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

$\displaystyle$A_{11}^{(1)} = X_1A_{11}^{(k+1)}$$\displaystyle A_{12}^{(1)} = X_1A_{12}^{(k+1)}$$
$\displaystyle$A_{21}^{(1)} = X_2A_{11}^{(k+1)}$$\displaystyle 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 $\displaystyle$A_{22}^{(k+1)} = A_{22}^{(1)} - A_{21}^{(1)}A_{11}^{(1)*}A_{12}^{(1)}$$, hence we need to show that \displaystyle A_{22}^{(1)} - X_2A_{12}^{(k+1)} = A_{22}^{(1)} - A_{21}^{(1)}A_{11}^{(1)*}A_{12}^{(1)}$$,

i.e. $\displaystyle$X_2A_{12}^{(k+1)} = A_{21}^{(1)}A_{11}^{(1)*}A_{12}^{(1)}$$, where \displaystyle A_{11}^{(1)*}$$ is the inverse of $\displaystyle$A_{11}^{(1)}$.$

$\displaystyle$X_2A_{11}^{(k+1)} = X_2(X_1^{-1}X_1)A_{11}^{(k+1)} =\displaystyle X_2X_1^{-1}(X_1A_{11}^{(k+1)}) = X_2X_1^{-1}(A_{12}^{(1)})$$by \displaystyle A_{12}^{(1)} = X_1A_{12}^{(k+1)}. Thus \displaystyle 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)} = \displaystyle X_2A_{11}^{(k+1)}(A_{11}^{(k+1)*}X_1^{-1})A_{12}^{(1)}$$.

But $\displaystyle$A_{11}^{(k+1)*}X_1^{-1} = A_{11}^{(1)*}$$by \displaystyle A_{11}^{(1)} = X_1A_{11}^{(k+1)}$$.

Therefore, $\displaystyle$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)} =\displaystyle (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 \displaystyle A_{21}^{(1)} = X_2A_{11}^{(k+1)}$$. Thus the result is proven.