Schur Complements and the Matrix Inversion Lemma

Contents

• Preliminaries
• Summary
• Schur Complements
  • Definition
  • Key Properties
  • Matrix Inversion Lemma
  • Characterizing Symmetric Positive Definite Matrices
• Generalized Schur Complements
  • SVD and Pseudoinverses
  • Definition and Factorization
  • Characterizing Symmetric Positive Semidefinite Matrices
• References

Preliminaries

The post assumes standard linear algebra knowledge at the level presented in S. Axler’s Linear Algebra Done Right, 3e (LADR). All results in this post apply to both real and complex-valued matrices, unless otherwise specified.

• \(\F\) stands for either \(\R\) or \(\C\).
• \(I_n\) denotes the \(n \times n\) identity matrix.
• \(\Sym^n\) denotes the vector space of symmetric \(n \times n\) real matrices.
• \(\zero\) denotes an all-zero vector or matrix, whereas 0 denotes scalar zero.

Summary

I summarize the key results here. Consider a square matrix with block partition

Let \(M/A = D - C A^{-1} B\) and \(M/D = A - B D^{-1} C\) denote the Schur complements.

If \(A\) is invertible, then \(M\) is invertible \(\iff \ M/A\) is invertible, and either implies that

Similarly, if \(D\) is invertible, then \(M\) is invertible \(\iff \ M/D\) is invertible, and either implies that

These two results combine to give the matrix inversion lemma, which states that if \(A, D\) are invertible and any of (\(M, M/D, M/A\)) are invertible, then:

• all of \(M\), \(M/A\), and \(M/D\) are invertible;
• \((M/A)^{-1} = D^{-1} + D^{-1} C (M/D)^{-1} B D^{-1}\);
• \((M/D)^{-1} = A^{-1} + A^{-1} B (M/A)^{-1} C A^{-1}\).

Finally, the positive (semi-)definiteness of \(M \in \Sym^n\) is related to the positive (semi-)definiteness of its Schur complements by the following properties:

1. \(M \succ 0 \ \iff \ A, (M/A) \succ 0 \ \iff \ D, (M/D) \succ 0\).
2. If \(A \succ 0\), then \(M \succeq 0 \ \iff \ (M/A) \succeq 0\).
3. If \(D \succ 0\), then \(M \succeq 0 \ \iff \ (M/D) \succeq 0\).

If we consider generalized Schur complements (replacing \(A^{-1}\) and \(D^{-1}\) with their Moore-Penrose pseudoinverses), then the following conditions are equivalent for \(M \in \Sym^n\):

1. \(M \succeq 0\).
2. \(A \succeq 0\), \((I - A A^\dagger) B = \zero\), \(D - B^\top A^\dagger B \succeq 0\).
3. \(D \succeq 0\), \((I - D D^\dagger) B^\top = \zero\), \(A - B D^\dagger B^\top \succeq 0\).

Schur Complements

Definition

Consider a square matrix \(M\) of size \((n+m) \times (n+m)\), partitioned as

where \(A \in \F^{n \times n}\), \(B \in \F^{n \times m}\), \(C \in \F^{m \times n}\), and \(D \in \F^{m \times m}\).

If \(A\) is invertible, the Schur complement of the block \(A\) of the matrix \(M\) is defined as the \(m \times m\) matrix

Similarly, if \(D\) is invertible, the Schur complement of the block \(D\) of the matrix \(M\) is defined as the \(n \times n\) matrix

Key Properties

All of the properties of Schur complements have analogous results when considering block \(A\) and block \(D\).

Lemma (Factorization using Schur complements): If \(A\) is invertible, then \(M\) can be factorized as

If \(D\) is invertible, then \(M\) can be factorized as

Both of the equalities can be seen by directly multiplying the matrix factors.

Lemma (Determinant of Block Matrix): If \(A\) is invertible, then \(\det(M) = \det(A) \det(M/A)\). Similarly, if \(D\) is invertible, then \(\det(M) = \det(D) \det(M/D)\).

Theorem (Invertibility of Schur complement): If \(A\) is invertible, then

and either implies that

Similarly, if \(D\) is invertible, then

and either implies that

Matrix Inversion Lemma

The matrix inversion lemma is a corollary of the previous theorem.

In fact, since there are 2 valid ways to write out each block of \(M^{-1}\), this provides \(2^4 = 16\) valid expressions for \(M^{-1}\).

Note that the identities in the matrix inversion lemma do not actually require constructing the full block matrix \(M\). Thus, the lemma is often stated without explicitly constructing \(M\), and instead directly considers arbitrary matrices \(A \in \F^{n \times n}\), \(B \in \F^{n \times m}\), \(C \in \F^{m \times n}\), and \(D \in \F^{m \times m}\).

If we substitute \(\bar{C} = -C\) and \(\bar{D} = D^{-1}\) into the matrix inversion lemma, then we arrive at the Woodbury matrix identity.

Some texts such as Boyd’s Convex Optimization book (Appendix C.4.3) substitute \(D = -I_m\) (which is invertible) into the matrix inversion lemma.

Finally, the special case of the matrix inversion lemma where \(A \in \R^{n \times n}\), \(B = u \in \R^n\), \(C = v^\top \in \R^{1 \times n}\), and \(D = D^{-1} = -1\) is known as the Sherman-Morrison formula.

Discussion

The matrix inversion lemma naturally leads to the following question: if \(A\) and \(D\) are invertible, do we actually need the condition that one of (\(M\), \(M/A\), or \(M/D\)) is invertible in order for the lemma to hold? The answer is yes, as shown by the following counterexample.

Consider the all-ones matrix \(M = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}.\) Clearly \(A = D = 1\) is invertible, but \(M\) is not invertible because it is not full-rank.

On the other hand, there also exist invertible matrices such as

where neither \(A\) nor \(D\) are invertible (and therefore \(M/A\) and \(M/D\) are undefined). In other words, the matrix inversion lemma may be useful in many settings, but it does not apply to all invertible matrices.

Characterizing Symmetric Positive Definite Matrices

This section considers the special case where \(M\) is real and symmetric (i.e., \(C = B^\top\)):

Then by the factorization lemma above, if \(A\) is invertible, then

If \(D\) is invertible, then

The following function \(f: \R^n \times \R^m \to \R\) is useful for our analysis of \(M\):

Note that this implies

Lemma (Positive definite diagonal blocks): If \(M \succ 0\), then \(A, D \succ 0\). If \(M \succeq 0\), then \(A, D \succeq 0\).

Theorem (Conditions for Positive Definiteness):

1. \(M \succ 0 \ \iff \ A, (M/A) \succ 0 \ \iff \ D, (M/D) \succ 0\).
2. If \(A \succ 0\), then \(M \succeq 0 \ \iff \ (M/A) \succeq 0\).
3. If \(D \succ 0\), then \(M \succeq 0 \ \iff \ (M/D) \succeq 0\).

Generalized Schur Complements

This section explores generalized Schur complements when \(A\) and \(D\) are not invertible. To do so, we rely on their pseudoinverses, which we define in terms of their singular value decomposition (SVD).

SVD and Pseudoinverses

Every matrix \(P \in \F^{n \times m}\) with \(\rank P = r\) has a compact SVD \(P = U \Sigma V^*\) where

• \(U \in \F^{n \times r}\) and \(V \in \F^{m \times r}\) have orthonormal columns;
• \(\Sigma = \diag(\sigma_1, \dotsc, \sigma_r) \in \Sym^r\) is a positive definite diagonal matrix with \(\sigma_1 \geq \dotsb \geq \sigma_r > 0\).

This compact SVD can be extended to a full SVD

where \(\bar{U}\), \(\bar{V}\) are unitary matrices.

The Moore-Penrose pseudoinverse (Wikipedia) of \(P\) is defined as

Using the compact SVD of \(\bar{\Sigma}\), we can derive its pseudoinverse

Thus, the pseudoinverse of \(P\) can also be expressed in terms of its full SVD:

The pseudoinverse satisfies

Furthermore, if \(P\) is Hermitian, then \(P^\dagger\) is also Hermitian:

Lemma (Range of \(P\) and \(P P^\dagger\)): For any \(P \in \F^{n \times m}\) and \(y \in \F^n\),

It is sometimes convenient to write this as \((I - P P^\dagger) y = \zero\). A corollary is that \(\range P = \range P P^\dagger\).

Definition and Factorization

Now, we can formally define the generalized Schur complement of the block \(A\) of the matrix \(M\) as the \(m \times m\) matrix

The generalized Schur complement of the block \(D\) of the matrix \(M\) is defined as the \(n \times n\) matrix

Lemma (Factorization using Generalized Schur complements): If \((I - A A^\dagger) B = \zero\) and \((I - A^* A^\dagger) C^* = \zero\), then

If \((I - D^* D^\dagger) B^* = \zero\) and \((I - D D^\dagger) C = \zero\), then

These identities can be checked by straightforward matrix multiplication, using the properties of the pseudoinverse, and observing that for any \(P \in \F^{n \times n}\) and \(N \in \F^{n \times m}\),

Characterizing Symmetric Positive Semidefinite Matrices

This section again considers the special case where \(M\) is real and symmetric (i.e., \(C = B^\top\)).

Lemma (Minimization of a Convex Quadratic Function): For all \(P \in \Sym^n\), the function \(f: \R^n \to \R\)

has a minimum value if and only if \(P \succeq 0\) and \((I - P P^\dagger) b = \zero\) (or equivalently, \(b \in \range P\)), in which case the minimum value is

Furthermore, if \(r = \rank P\) and \(P = Q D Q^\top\) is an eigendecomposition (equivalently, a full SVD) of \(P\), then the optimal value is achieved by all \(x_* \in \R^n\) of the following form for all \(z \in \R^{n-r}\):

Corollary (Minimization of a Strictly Convex Quadratic Function): If \(P \in \Sym^n\) is invertible, then

has a minimum value if and only if \(P \succ 0\), in which case the minimum value is uniquely attained by \(x_* = -P^{-1} b\) with \(f(x_*) = -b^\top P^{-1} b\).

Theorem (Conditions for Positive Semi-Definiteness): For any symmetric matrix \(M = \begin{bmatrix} A & B \\ B^\top & D \end{bmatrix}\), the following conditions are equivalent:

1. \(M \succeq 0\).
2. \(A \succeq 0\), \((I_n - A A^\dagger) B = \zero_{n \times m}\), \(D - B^\top A^\dagger B \succeq 0\).
3. \(D \succeq 0\), \((I_m - D D^\dagger) B^\top = \zero_{m \times n}\), \(A - B D^\dagger B^\top \succeq 0\).

If \(M \succeq 0\), then it has the following factorizations:

References

• Jean Gallier. Geometric Methods and Applications, 2e, 2011. https://doi.org/10.1007/978-1-4419-9961-0.
  • Gallier’s textbook covers most of the material from this post, including the generalized Schur complement using pseudoinverses. CH 16.1 proves the matrix inversion lemma (without using determinants), CH 16.2 considers Schur complements in symmetric matrices, and CH 16.3 considers generalized Schur complements in symmetric matrices.
  • CH 15.1 and 15.2 provide the lemmas used for the generalized Schur complements.
• Jean Gallier. “The Schur Complement and Symmetric Positive Semidefinite (and Definite) Matrices,” 2019. https://www.cis.upenn.edu/~jean/schur-comp.pdf.
  • Gallier’s notes mostly mirror his textbook (Section 1 = CH 16.1, Section 2 = CH 16.2, Section 4 = CH 15.1/15.2/16.3), combining the relevant chapters into a succinct exposition on Schur Complements. While my post borrows many results from Gallier, I provided new or more detailed proofs in several places, most notably the lemma on Minimization of a Convex Quadratic Function.
• S. Boyd and L. Vandenberghe. Convex Optimization, 2004. https://web.stanford.edu/~boyd/cvxbook/.
  • Appendix A.5.5 discusses Schur complements when \(M\) is symmetric, including a derivation of \(M^{-1}\) as well as the conditions for positive definiteness and semidefiniteness.
  • Appendix C.4.1 essentially derives the form of \(M^{-1}\) when \(A\) and \(M/A\) are invertible.
  • Appendix C.4.3 derives the simpler form of the Woodbury matrix identity.
• C.E. Rasmussen and C.K.I. Williams. Gaussian Processes for Machine Learning, 2006. http://www.gaussianprocess.org/gpml/.
  • Appendix A.3 describes the Woodbury matrix identity and the matrix inversion lemma, without proof.
• T. Lienart. “Matrix inversion lemmas.” https://tlienart.github.io/pub/csml/mtheory/matinvlem.html.
  • As of May 9, 2021, Lienart’s notes provides a concise derivation of the matrix inversion lemma, albeit with some additional unwritten assumptions.
  • Shows the relation between the matrix inversion lemma and the Sherman-Morrison formula.
• Relevant Wikipedia pages:
  • Schur_complement: defines the Schur complement and gives conditions for positive (semi-)definiteness in symmetric matrices, but misses details on the matrix inversion lemma.
  • Invertible matrix: Blockwise inversion: shows the correspondence between the two inverses of \(M\) used in the matrix inversion lemma, but misses proof details.
  • Woodbury matrix identity: gives a direct proof of the Woodbury matrix identity without discussing Schur complements.
• S. Axler. Linear Algebra Done Right, 3e, 2015. https://linear.axler.net/.
  • General linear algebra reference, abbreviated as LADR in this post.
• Another interesting matrix inversion lemma which considers \(M^\top M\) is provided on StackExchange here, although I haven’t taken the time to verify it completely.