Results 1 to 3 of 3

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

  1. #1
    Newbie
    Joined
    Nov 2011
    Posts
    24

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Nov 2011
    Posts
    24

    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2011
    Posts
    24

    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.
    Last edited by skeptopotamus; October 8th 2012 at 10:46 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. spectral theory
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 8th 2011, 08:01 PM
  2. Inverse of a Spectral Matrix
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: October 27th 2010, 07:34 AM
  3. Spectral Decomposition of a Matrix
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: April 17th 2010, 12:03 PM
  4. Schur Complement problem
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 9th 2010, 07:18 AM
  5. Replies: 2
    Last Post: May 19th 2008, 10:48 PM

Search Tags


/mathhelpforum @mathhelpforum