Schur complement

In linear algebra , the Schur complement describes a matrix that is calculated from the individual blocks of a larger matrix. The Schur complement is named after Issai Schur .

definition

Let M be a matrix that is composed of four sub-blocks: ${\displaystyle (n+m)\times (n+m)}$

${\displaystyle M=\left({\begin{matrix}A&B\\C&D\end{matrix}}\right)}$.

It should be A a - B a -, C a - and D is a matrix. Furthermore it is assumed that A is invertible . ${\displaystyle n\times n}$ ${\displaystyle n\times m}$ ${\displaystyle m\times n}$ ${\displaystyle m\times m}$

The matrix

${\displaystyle S=D-CA^{-1}B\,}$

called Schur complement of A in M .

Interpretation as the result of Gaussian elimination

The Schur complement can be as a result of a step of Gaussian elimination on the plane of the array blocks interpret: The formal application of the Gaussian elimination on the - block matrix corresponding to the multiplication from the left with the matrix ${\displaystyle (2\times 2)}$ ${\displaystyle M}$

${\displaystyle L=\left({\begin{matrix}I_{n}&0\\-CA^{-1}&I_{m}\end{matrix}}\right),}$

wherein and the - or - identity matrices call. The Schur complement then appears in the lower, right-hand block of the matrix product : ${\displaystyle I_{n}}$ ${\displaystyle I_{m}}$ ${\displaystyle (n\times n)}$ ${\displaystyle (m\times m)}$

${\displaystyle LM=\left({\begin{matrix}A&B\\0&D-CA^{-1}B\end{matrix}}\right).}$

Hence the inverse of can be calculated from the inverse of and from its Schur complement : ${\displaystyle M}$ ${\displaystyle A}$ ${\displaystyle S}$

${\displaystyle \left({\begin{matrix}A&B\\C&D\end{matrix}}\right)^{-1}=\left({\begin{matrix}A^{-1}+A^{-1}BS^{-1}CA^{-1}&-A^{-1}BS^{-1}\\-S^{-1}CA^{-1}&S^{-1}\end{matrix}}\right)}$

or

${\displaystyle \left({\begin{matrix}A&B\\C&D\end{matrix}}\right)^{-1}=\left({\begin{matrix}I_{n}&-A^{-1}B\\0&I_{m}\end{matrix}}\right)\left({\begin{matrix}A^{-1}&0\\0&S^{-1}\end{matrix}}\right)\left({\begin{matrix}I_{n}&0\\-CA^{-1}&I_{m}\end{matrix}}\right).}$

properties

Assuming that M is symmetric , M is positive definite if and only if A and the Schur complement S are positive definite.

Analogous to the definition given above, the Schur complement to block D can also be formed.

For two invertible matrices of the same size and with the partial matrices or be and the corresponding Schur complements of in , or in . With the definition of the following matrix product ${\displaystyle M_{1}}$ ${\displaystyle M_{2}}$ ${\displaystyle A_{1},B_{1},C_{1},D_{1}}$ ${\displaystyle A_{2},B_{2},C_{2},D_{2}}$ ${\displaystyle S_{1}}$ ${\displaystyle S_{2}}$ ${\displaystyle A_{1}}$ ${\displaystyle M_{1}}$ ${\displaystyle A_{2}}$ ${\displaystyle M_{2}}$

${\displaystyle A*B=A(A+B)^{-1}B}$and if the Schur complement of denotes, which is formed in a corresponding manner as for , then the Schur complement of the product is equal to the product of the Schur complements: ${\displaystyle S_{*}}$ ${\displaystyle M_{1}*M_{2}}$ ${\displaystyle M_{1},M_{2}}$ ${\displaystyle S_{*}=S_{1}*S_{2}}$

Use in solving systems of linear equations

Schur's complement can be used to solve systems of linear equations of the form

${\displaystyle \left({\begin{matrix}A&B\\C&D\end{matrix}}\right)\left({\begin{matrix}x\\y\end{matrix}}\right)=\left({\begin{matrix}f\\g\end{matrix}}\right)}$

can be used. Here x and f denote vectors of length n and y and g denote vectors of length m . This system of equations is written out:

${\displaystyle Ax+By=f\,}$

${\displaystyle Cx+Dy=g\,}$

Multiplying the first equation from the left by and adding to the second equation yields ${\displaystyle -CA^{-1}}$

${\displaystyle (D-CA^{-1}B)y=g-CA^{-1}f.\,}$

So if you can invert A and S , then you can solve this equation for y and then

${\displaystyle Ax=f-By\,}$

calculate to get the solution to the original problem. ${\displaystyle (x,y)}$

The solution of one system is reduced to the solution of one and one system. ${\displaystyle (n+m)\times (n+m)}$ ${\displaystyle n\times n}$ ${\displaystyle m\times m}$

An important remark in this context is the fact that the inverse matrix does not have to be explicitly formed in some iterative numerical algorithms such as Krylov subspace methods . As a closer examination of the equation systems to be solved shows, only the effect of on the vectors and, in the course of the iterative solution of , on the previous solution is required, so that the formation of the inverse can be understood as the solution of a linear system of equations. A very efficient solution is possible, especially with thinly populated matrices . ${\displaystyle A^{-1}}$ ${\displaystyle A^{-1}}$ ${\displaystyle f}$ ${\displaystyle (D-CA^{-1}B)y=g-CA^{-1}f}$ ${\displaystyle y_{\text{alt}}}$

See also

• Saddle point problem

literature

• Edgar Brunner, Ullrich Munzel: Nonparametric data analysis. Springer, Berlin 2002, ISBN 3-540-43375-9 , pp. 268f ( limited preview in the Google book search).