The Schur complement of a block matrix, encountered in linear algebra and the theory of matrices, is defined as follows.

Suppose p, q are nonnegative integers such that p + q > 0, and suppose A, B, C, D are respectively p × p, p × q, q × p, and q × q matrices of complex numbers. Let so that M is a (p + q) × (p + q) matrix.

If D is invertible, then the Schur complement of the block D of the matrix M is the p × p matrix defined by If A is invertible, the Schur complement of the block A of the matrix M is the q × q matrix defined by In the case that A or D is singular, substituting a generalized inverse for the inverses on M/A and M/D yields the generalized Schur complement.

The Schur complement is named after Issai Schur[1] who used it to prove Schur's lemma, although it had been used previously.[2] Emilie Virginia Haynsworth was the first to call it the Schur complement.[3] The Schur complement is a key tool in the fields of numerical analysis, statistics, and matrix analysis. The Schur complement is sometimes referred to as the Feshbach map after a physicist Herman Feshbach.[4]

Background

edit

The Schur complement arises when performing a block Gaussian elimination on the matrix M. In order to eliminate the elements below the block diagonal, one multiplies the matrix M by a block lower triangular matrix on the right as follows:   where Ip denotes a p×p identity matrix. As a result, the Schur complement   appears in the upper-left p×p block.

Continuing the elimination process beyond this point (i.e., performing a block Gauss–Jordan elimination),   leads to an LDU decomposition of M, which reads   Thus, the inverse of M may be expressed involving D−1 and the inverse of Schur's complement, assuming it exists, as   The above relationship comes from the elimination operations that involve D−1 and M/D. An equivalent derivation can be done with the roles of A and D interchanged. By equating the expressions for M−1 obtained in these two different ways, one can establish the matrix inversion lemma, which relates the two Schur complements of M: M/D and M/A (see "Derivation from LDU decomposition" in Woodbury matrix identity § Alternative proofs).

Properties

edit
  • If p and q are both 1 (i.e., A, B, C and D are all scalars), we get the familiar formula for the inverse of a 2-by-2 matrix:
 
provided that AD − BC is non-zero.
  • In general, if A is invertible, then
 
whenever this inverse exists.
  • (Schur's formula) When A, respectively D, is invertible, the determinant of M is also clearly seen to be given by
 , respectively
 ,
which generalizes the determinant formula for 2 × 2 matrices.
  • (Guttman rank additivity formula) If D is invertible, then the rank of M is given by
 
  • (Haynsworth inertia additivity formula) If A is invertible, then the inertia of the block matrix M is equal to the inertia of A plus the inertia of M/A.
  • (Quotient identity)  .[5]
  • The Schur complement of a Laplacian matrix is also a Laplacian matrix.[6]

Application to solving linear equations

edit

The Schur complement arises naturally in solving a system of linear equations such as[7]

 .

Assuming that the submatrix   is invertible, we can eliminate   from the equations, as follows.

 

Substituting this expression into the second equation yields

 

We refer to this as the reduced equation obtained by eliminating   from the original equation. The matrix appearing in the reduced equation is called the Schur complement of the first block   in  :

 .

Solving the reduced equation, we obtain

 

Substituting this into the first equation yields

 

We can express the above two equation as:

 

Therefore, a formulation for the inverse of a block matrix is:

 

In particular, we see that the Schur complement is the inverse of the   block entry of the inverse of  .

In practice, one needs   to be well-conditioned in order for this algorithm to be numerically accurate.

This method is useful in electrical engineering to reduce the dimension of a network's equations. It is especially useful when element(s) of the output vector are zero. For example, when   or   is zero, we can eliminate the associated rows of the coefficient matrix without any changes to the rest of the output vector. If   is null then the above equation for   reduces to  , thus reducing the dimension of the coefficient matrix while leaving   unmodified. This is used to advantage in electrical engineering where it is referred to as node elimination or Kron reduction.

Applications to probability theory and statistics

edit

Suppose the random column vectors X, Y live in Rn and Rm respectively, and the vector (X, Y) in Rn + m has a multivariate normal distribution whose covariance is the symmetric positive-definite matrix

 

where   is the covariance matrix of X,   is the covariance matrix of Y and   is the covariance matrix between X and Y.

Then the conditional covariance of X given Y is the Schur complement of C in  :[8]

 

If we take the matrix   above to be, not a covariance of a random vector, but a sample covariance, then it may have a Wishart distribution. In that case, the Schur complement of C in   also has a Wishart distribution.[citation needed]

Conditions for positive definiteness and semi-definiteness

edit

Let X be a symmetric matrix of real numbers given by   Then

  • If A is invertible, then X is positive definite if and only if A and its complement X/A are both positive definite:[2]: 34 
 
  • If C is invertible, then X is positive definite if and only if C and its complement X/C are both positive definite:
 
  • If A is positive definite, then X is positive semi-definite if and only if the complement X/A is positive semi-definite:[2]: 34 
 
  • If C is positive definite, then X is positive semi-definite if and only if the complement X/C is positive semi-definite:
 

The first and third statements can be derived[7] by considering the minimizer of the quantity   as a function of v (for fixed u).

Furthermore, since   and similarly for positive semi-definite matrices, the second (respectively fourth) statement is immediate from the first (resp. third) statement.

There is also a sufficient and necessary condition for the positive semi-definiteness of X in terms of a generalized Schur complement.[2] Precisely,

  •   and
  •  

where   denotes a generalized inverse of  .

See also

edit

References

edit
  1. ^ Schur, J. (1917). "Über Potenzreihen die im Inneren des Einheitskreises beschränkt sind". J. reine u. angewandte Mathematik. 147: 205–232. doi:10.1515/crll.1917.147.205.
  2. ^ a b c d Zhang, Fuzhen (2005). Zhang, Fuzhen (ed.). The Schur Complement and Its Applications. Numerical Methods and Algorithms. Vol. 4. Springer. doi:10.1007/b105056. ISBN 0-387-24271-6.
  3. ^ Haynsworth, E. V., "On the Schur Complement", Basel Mathematical Notes, #BNB 20, 17 pages, June 1968.
  4. ^ Feshbach, Herman (1958). "Unified theory of nuclear reactions". Annals of Physics. 5 (4): 357–390. doi:10.1016/0003-4916(58)90007-1.
  5. ^ Crabtree, Douglas E.; Haynsworth, Emilie V. (1969). "An identity for the Schur complement of a matrix". Proceedings of the American Mathematical Society. 22 (2): 364–366. doi:10.1090/S0002-9939-1969-0255573-1. ISSN 0002-9939. S2CID 122868483.
  6. ^ Devriendt, Karel (2022). "Effective resistance is more than distance: Laplacians, Simplices and the Schur complement". Linear Algebra and Its Applications. 639: 24–49. arXiv:2010.04521. doi:10.1016/j.laa.2022.01.002. S2CID 222272289.
  7. ^ a b Boyd, S. and Vandenberghe, L. (2004), "Convex Optimization", Cambridge University Press (Appendix A.5.5)
  8. ^ von Mises, Richard (1964). "Chapter VIII.9.3". Mathematical theory of probability and statistics. Academic Press. ISBN 978-1483255385.