Editing Invertible matrix (section)

=== Blockwise inversion ===
Let 

<math> \mathbf M = \begin{bmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{C} & \mathbf{D} \end{bmatrix}</math>

where {{math|'''A'''}}, {{math|'''B'''}}, {{math|'''C'''}} and {{math|'''D'''}} are [[block matrix|matrix sub-blocks]] of arbitrary size and <math>\mathbf M / \mathbf A := \mathbf D - \mathbf C \mathbf A^{-1} \mathbf B </math> is the [[Schur complement]] of {{math|'''A'''}}. ({{math|'''A'''}} must be square, so that it can be inverted. Furthermore, {{math|'''A'''}} and {{math|'''D''' − '''CA'''{{sup|−1}}'''B'''}} must be nonsingular.<ref>
{{cite book |last=Bernstein |first=Dennis |title=Matrix Mathematics |publisher=Princeton University Press |year=2005 |isbn=978-0-691-11802-4 |pages=44}}</ref>)

Matrices can also be ''inverted blockwise'' by using the analytic inversion formula:<ref>{{cite journal |last1=Tzon-Tzer |first1=Lu |last2=Sheng-Hua |first2=Shiou |title=Inverses of 2 × 2 block matrices |journal=Computers & Mathematics with Applications |date=2002 |volume=43 |issue=1–2 |pages=119–129 |doi=10.1016/S0898-1221(01)00278-4}}</ref>

{{NumBlk
|: | <math>\begin{bmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{C} & \mathbf{D} \end{bmatrix}^{-1} =
  \begin{bmatrix}
     \mathbf{A}^{-1} + \mathbf{A}^{-1}\mathbf{B}\ (\mathbf M / \mathbf A)^{-1}\mathbf{CA}^{-1} &
    -\mathbf{A}^{-1}\mathbf{B}\left(\mathbf M / \mathbf A \right)^{-1} \\
    -\left(\mathbf M / \mathbf A \right)^{-1}\mathbf{CA}^{-1} &
     \left(\mathbf M / \mathbf A \right)^{-1}
  \end{bmatrix},
</math>
| {{EquationRef|1}}
}}

The strategy is particularly advantageous if {{math|'''A'''}} is diagonal and {{math|'''M''' / '''A'''}} is a small matrix, since they are the only matrices requiring inversion.

The [[nullity theorem]] says that the nullity of {{math|'''A'''}} equals the nullity of the sub-block in the lower right of the inverse matrix, and that the nullity of {{math|'''B'''}} equals the nullity of the sub-block in the upper right of the inverse matrix.

The inversion procedure that led to Equation ({{EquationNote|1}}) performed matrix block operations that operated on {{math|'''C'''}} and {{math|'''D'''}} first. Instead, if {{math|'''A'''}} and {{math|'''B'''}} are operated on first, and provided {{math|'''D'''}} and {{math|1='''M''' / '''D''' := '''A''' − '''BD'''{{sup|−1}}'''C'''}} are nonsingular,<ref>
{{cite book
  | last = Bernstein
  | first = Dennis
  | title = Matrix Mathematics
  | publisher = Princeton University Press
  | year = 2005
  | pages = 45
  | isbn = 978-0-691-11802-4 }}
</ref> the result is

{{NumBlk
|: | <math>
\begin{bmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{C} & \mathbf{D} \end{bmatrix}^{-1} = \begin{bmatrix}
     \left( \mathbf M / \mathbf D \right)^{-1} &
    -\left( \mathbf M / \mathbf D \right)^{-1}\mathbf{BD}^{-1} \\
    -\mathbf{D}^{-1}\mathbf{C}\left(\mathbf M / \mathbf D\right)^{-1} &
     \quad \mathbf{D}^{-1} + \mathbf{D}^{-1}\mathbf{C}\left(\mathbf M / \mathbf D\right)^{-1}\mathbf{BD}^{-1}
  \end{bmatrix}.
</math>
| {{EquationRef|2}}
}}

Equating the upper-left sub-matrices of Equations ({{EquationNote|1}}) and ({{EquationNote|2}}) leads to
{{NumBlk
|: | <math>\begin{align}
  \left(\mathbf{A} - \mathbf{BD}^{-1}\mathbf{C}\right)^{-1}
    &= \mathbf{A}^{-1} + \mathbf{A}^{-1}\mathbf{B}\left(\mathbf{D} - \mathbf{CA}^{-1}\mathbf{B}\right)^{-1}\mathbf{CA}^{-1} \\
  \left(\mathbf{A} - \mathbf{BD}^{-1}\mathbf{C}\right)^{-1}\mathbf{BD}^{-1}
    &= \mathbf{A}^{-1}\mathbf{B}\left(\mathbf{D} - \mathbf{CA}^{-1}\mathbf{B}\right)^{-1} \\
  \mathbf{D}^{-1}\mathbf{C}\left(\mathbf{A} - \mathbf{BD}^{-1}\mathbf{C}\right)^{-1}
    &= \left(\mathbf{D} - \mathbf{CA}^{-1}\mathbf{B}\right)^{-1}\mathbf{CA}^{-1} \\
  \mathbf{D}^{-1} + \mathbf{D}^{-1}\mathbf{C}\left(\mathbf{A} - \mathbf{BD}^{-1}\mathbf{C}\right)^{-1}\mathbf{BD}^{-1}
    &= \left(\mathbf{D} - \mathbf{CA}^{-1}\mathbf{B}\right)^{-1}
\end{align}</math>
| {{EquationRef|3}}
}}

where Equation ({{EquationNote|3}}) is the [[Woodbury matrix identity]], which is equivalent to the [[binomial inverse theorem]].

If {{math|'''A'''}} and {{math|'''D'''}} are both invertible, then the above two block matrix inverses can be combined to provide the simple factorization
{{NumBlk
|: | <math>\begin{bmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{C} & \mathbf{D} \end{bmatrix}^{-1} =
  \begin{bmatrix}
    \left(\mathbf{A} - \mathbf{B} \mathbf{D}^{-1} \mathbf{C}\right)^{-1} & \mathbf{0} \\
    \mathbf{0} & \left(\mathbf{D} - \mathbf{C} \mathbf{A}^{-1} \mathbf{B}\right)^{-1}
  \end{bmatrix} \begin{bmatrix}
     \mathbf{I} & -\mathbf{B} \mathbf{D}^{-1} \\
    -\mathbf{C} \mathbf{A}^{-1} & \mathbf{I}
  \end{bmatrix}.
</math>
| {{EquationRef|2}}
}}

By the [[Weinstein–Aronszajn identity]], one of the two matrices in the block-diagonal matrix is invertible exactly when the other is.

This formula simplifies significantly when the upper right block matrix {{math|'''B'''}} is the [[zero matrix]]. This formulation is useful when the matrices {{math|'''A'''}} and {{math|'''D'''}} have relatively simple inverse formulas (or [[Moore–Penrose inverse|pseudo inverses]] in the case where the blocks are not all square. In this special case, the block matrix inversion formula stated in full generality above becomes 

:<math>\begin{bmatrix} \mathbf{A} & \mathbf{0} \\ \mathbf{C} & \mathbf{D} \end{bmatrix}^{-1} =
  \begin{bmatrix} \mathbf{A}^{-1} & \mathbf{0} \\ -\mathbf{D}^{-1}\mathbf{CA}^{-1} & \mathbf{D}^{-1} \end{bmatrix}.</math>

If the given invertible matrix is a symmetric matrix with invertible block {{math|'''A'''}} the following block inverse formula holds<ref name="Cormen"/>
{{NumBlk
|: | <math>\begin{bmatrix} \mathbf{A} & \mathbf{C}^T \\ \mathbf{C} & \mathbf{D} \end{bmatrix}^{-1} =
  \begin{bmatrix}
    \mathbf{A}^{-1} + \mathbf{A}^{-1}\mathbf{C}^T \mathbf{S}^{-1}\mathbf{C}\mathbf{A}^{-1} & -\mathbf{A}^{-1}\mathbf{C}^T\mathbf{S}^{-1} \\
    -\mathbf{S}^{-1}\mathbf{C}\mathbf{A}^{-1} & \mathbf{S}^{-1}
  \end{bmatrix},
</math>
| {{EquationRef|4}}
}}
where <math>\mathbf{S} = \mathbf{D} - \mathbf{C}\mathbf{A}^{-1}\mathbf{C}^T</math>. This requires 2 inversions of the half-sized matrices {{math|'''A'''}} and {{math|'''S'''}} and only 4 multiplications of half-sized matrices, if organized properly
<math display=block>\begin{align}
\mathbf{W}_1 &= \mathbf{C}\mathbf{A}^{-1}, \\[3mu]
\mathbf{W}_2 &= \mathbf{W}_1\mathbf{C}^{T}=\mathbf{C}\mathbf{A}^{-1}\mathbf{C}^T, \\[3mu]
\mathbf{W}_3 &= \mathbf{S}^{-1}\mathbf{W}_1=\mathbf{S}^{-1}\mathbf{C}\mathbf{A}^{-1}, \\[3mu]
\mathbf{W}_4 &= \mathbf{W}_1^T\mathbf{W}_3=\mathbf{A}^{-1}\mathbf{C}^T \mathbf{S}^{-1}\mathbf{C}\mathbf{A}^{-1},
\end{align}</math> together with some additions, subtractions, negations and transpositions of negligible complexity. Any matrix  <math>\mathbf{M}</math> has an associated positive semidefinite, symmetric matrix <math>\mathbf{M}^T\mathbf{M}</math>, which is exactly invertible (and positive definite), if and only if <math>\mathbf{M}</math> is invertible. By writing <math>\mathbf{M}^{-1}=\left(\mathbf{M}^T\mathbf{M}\right)^{-1}\mathbf{M}^T</math> matrix inversion can be reduced to inverting symmetric matrices and 2 additional matrix multiplications, because the [[Definite_matrix#Decomposition|positive definite matrix]] <math>\mathbf{M}^T\mathbf{M}</math> satisfies the invertibility condition for its left upper block {{math|'''A'''}}.

Those formulas together allow to construct a [[divide and conquer algorithm]] that uses blockwise inversion of associated symmetric matrices to invert a matrix with the same time complexity as the [[matrix multiplication algorithm]] that is used internally.<ref name="Cormen">T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, ''Introduction to Algorithms'', 3rd ed., MIT Press, Cambridge, MA, 2009, §28.2.</ref> [[Computational complexity of matrix multiplication|Research into matrix multiplication complexity]] shows that there exist matrix multiplication algorithms with a complexity of {{math|''O''(''n''<sup>2.371552</sup>)}} operations, while the best proven lower bound is {{math|[[Big O notation#Family of Bachmann–Landau notations|Ω]](''n''{{sup|2}} log ''n'')}}.<ref>[[Ran Raz]]. On the complexity of matrix product. In Proceedings of the thirty-fourth annual ACM symposium on Theory of computing. ACM Press, 2002. {{doi|10.1145/509907.509932}}.</ref>