Shaka

Schur Complement

#math

Schur complement is an important concept in block Gaussian elimination in matrix theory whereby a matrix with larger dimension can be reduced to another matrix with smaller dimension by elimination. To be strict, Schur complement is the residual after eliminating the coupling between the component blocks of the matrix with larger dimension.

Definition

Given a matrix M∈C(m+n)×(m+n)\mathbf{M} \in \mathbb{C}^{(m + n) \times (m + n)} is comprised of 4 component block matrices, denoted by A∈Cm×m\mathbf{A} \in \mathbb{C}^{m\times m}, B∈Cm×n\mathbf{B} \in \mathbb{C}^{m\times n}, C∈Cn×m\mathbf{C} \in \mathbb{C}^{n\times m}, and D∈Cn×n\mathbf{D} \in \mathbb{C}^{n\times n} respectively, i.e.,

M=[ABCD](1)\begin{aligned}\mathbf{M} = \begin{bmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{C} & \mathbf{D} \end{bmatrix} &\text{(1)}\end{aligned}
  • If A\mathbf{A} is invertible, the Schur complement of A\mathbf{A} in M\mathbf{M} is defined as SA≜D−CA−1B∈Cm×m\mathbf{S}_{\mathbf{A}} \triangleq \mathbf{D} - \mathbf{C} \mathbf{A}^{-1} \mathbf{B} \in \mathbb{C}^{m\times m};
  • If D\mathbf{D} is invertible, the Schur complement of D\mathbf{D} in M\mathbf{M} is defined as SD≜A−BD−1C∈Cn×n\mathbf{S}_{\mathbf{D}} \triangleq \mathbf{A} - \mathbf{B} \mathbf{D}^{-1} \mathbf{C} \in \mathbb{C}^{n\times n}.

Principle

For a linear system represented by

[ABCD][x1x2]=[y1y2]\begin{aligned}\begin{bmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{C} & \mathbf{D} \end{bmatrix} \begin{bmatrix} \mathbf{x}_1 \\ \mathbf{x} _2 \end{bmatrix} = \begin{bmatrix} \mathbf{y}_1 \\ \mathbf{y} _2 \end{bmatrix}\end{aligned}

or equivalently the equation set

Ax1+Bx2=y1(2)Cx1+Dx2=y2(3)\begin{aligned}\mathbf{A} \mathbf{x}_1 + \mathbf{B} \mathbf{x}_{2} &= \mathbf{y}_1 &\text{(2)}\\\mathbf{C} \mathbf{x}_1 + \mathbf{D} \mathbf{x}_{2} &= \mathbf{y}_2 &\text{(3)}\end{aligned}

from (2) we get x1=A−1(y1−Bx2)\mathbf{x}_1 = \mathbf{A}^{-1}(\mathbf{y}_1 - \mathbf{B}\mathbf{x}_2) and substitutes it into (3) we obtain

(D−CA−1B)⏟SAx2=y2−CA−1y1.\begin{aligned}\underbrace{\left(\mathbf{D} - \mathbf{C} \mathbf{A}^{-1} \mathbf{B}\right)}_{\mathbf{S}_{\mathbf{A}}}\mathbf{x}_2 = \mathbf{y}_2 - \mathbf{C}\mathbf{A}^{-1}\mathbf{y}_1.\end{aligned}

In this way, the Schur complement reduces a (m+n)(m+n)-dimensional problem to a nn-dimensional one.

Schur complement is usually used for dimension reduction in the computation of matrix inversion.

The block matrix M\mathbf{M} in (1) can be LDU decomposed as

M=[ABCD]=[ImCA−1In]⏟L[ASA]⏟D[ImA−1BIn]⏟U\begin{aligned}\mathbf{M} &= \begin{bmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{C} & \mathbf{D} \end{bmatrix}\\&= \underbrace{\begin{bmatrix} \mathbf{I}_m & \\ \mathbf{C}\mathbf{A}^{-1} & \mathbf{I}_n \end{bmatrix}}_L \underbrace{\begin{bmatrix} \mathbf{A} & \\ & \mathbf{S}_{\mathbf{A}} \end{bmatrix}}_D \underbrace{\begin{bmatrix} \mathbf{I}_m & \mathbf{A}^{-1}\mathbf{B} \\ & \mathbf{I}_n \end{bmatrix}}_U\end{aligned}

Then, its inverse can be obtained as

M−1=[ABCD]−1=[ImA−1BIn]−1[ASA]−1[ImCA−1In]−1=[Im−A−1BIn][A−1SA−1][Im−CA−1In]=[A−1+A−1BSA−1CA−1−A−1BSA−1−SA−1CA−1SA−1]\begin{aligned}\mathbf{M}^{-1} &= \begin{bmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{C} & \mathbf{D} \end{bmatrix}^{-1}\\&= \begin{bmatrix} \mathbf{I}_m & \mathbf{A}^{-1}\mathbf{B} \\ & \mathbf{I}_n \end{bmatrix}^{-1} \begin{bmatrix} \mathbf{A} & \\ & \mathbf{S}_{\mathbf{A}} \end{bmatrix}^{-1} \begin{bmatrix} \mathbf{I}_m & \\ \mathbf{C}\mathbf{A}^{-1} & \mathbf{I}_n \end{bmatrix}^{-1}\\&= \begin{bmatrix} \mathbf{I}_m & -\mathbf{A}^{-1}\mathbf{B} \\ & \mathbf{I}_n \end{bmatrix} \begin{bmatrix} \mathbf{A}^{-1} & \\ & \mathbf{S}_{\mathbf{A}}^{-1} \end{bmatrix} \begin{bmatrix} \mathbf{I}_m & \\ -\mathbf{C}\mathbf{A}^{-1} & \mathbf{I}_n \end{bmatrix}\\&= \begin{bmatrix} \mathbf{A}^{-1} + \mathbf{A}^{-1}\mathbf{B} \mathbf{S}_{\mathbf{A}}^{-1} \mathbf{C} \mathbf{A}^{-1} & -\mathbf{A}^{-1} \mathbf{B} \mathbf{S}_{\mathbf{A}}^{-1} \\ -\mathbf{S}_{\mathbf{A}}^{-1} \mathbf{C} \mathbf{A}^{-1} & \mathbf{S}_{\mathbf{A}}^{-1} \end{bmatrix}\end{aligned}

Properties

  • det⁡(M)=det⁡(A)⋅det⁡(SA)=det⁡(D)⋅det⁡(SD)\det(\mathbf{M}) = \det(\mathbf{A}) \cdot \det(\mathbf{S}_{\mathbf{A}}) = \det(\mathbf{D}) \cdot \det(\mathbf{S}_{\mathbf{D}})
  • M−1=[ABCD]−1=[A−1+A−1BSA−1CA−1−A−1BSA−1−SA−1CA−1SA−1]\mathbf{M}^{-1} = \begin{bmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{C} & \mathbf{D} \end{bmatrix}^{-1} = \begin{bmatrix} \mathbf{A}^{-1} + \mathbf{A}^{-1}\mathbf{B} \mathbf{S}_{\mathbf{A}}^{-1} \mathbf{C} \mathbf{A}^{-1} & -\mathbf{A}^{-1} \mathbf{B} \mathbf{S}_{\mathbf{A}}^{-1} \\ -\mathbf{S}_{\mathbf{A}}^{-1} \mathbf{C} \mathbf{A}^{-1} & \mathbf{S}_{\mathbf{A}}^{-1} \end{bmatrix}
  • M\mathbf{M} is invertible   ⟺  \iff A\mathbf{A} and SA\mathbf{S}_{\mathbf{A}} are both invertible   ⟺  \iff D\mathbf{D} and SD\mathbf{S}_{\mathbf{D}} are both invertible.