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

**skeptopotamus** · October 7th 2012, 02:54 AM

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?

**skeptopotamus** · October 7th 2012, 06:08 PM

Sorry; I should say that it is pretty obvious, but the "obvious proof" is extremely ugly and inelegant. Does anyone have a nicer one?

**skeptopotamus** · October 8th 2012, 09:42 PM

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.

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

LinkBack

Thread Tools

Display

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

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

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

Similar Math Help Forum Discussions

spectral theory

Inverse of a Spectral Matrix

Spectral Decomposition of a Matrix

Schur Complement problem

Set Theory-Finding the Relative Complement of Two Functions

Search Tags