Schur Complement Lemma

Lemma: Schur Complement

Let S be a symmetric matrix partitioned into blocks:

  S = left( begin{array}{cc} A & B  B^T & C end{array} right) ,

where both A,C are symmetric and square. Assume that C is positive definite. Then the following properties are equivalent:

  • S is positive semi-definite.

  • The Schur complement of C in S, defined as the matrix A-BC^{-1}B^T, is positive semi-definite.

Proof: Recall that the matrix S is positive semi-definite if and only if x^TSx ge0 for any vector x. Partitioning the vector x similarly to S, as x=(y,z), we obtain that S is positive semi-definite if and only if

  forall :  (z,y) ~:~     g(y,z) := left( begin{array}{c} y  z end{array} right)^T  left( begin{array}{cc} A & B  B^T & C end{array} right) left( begin{array}{c} y  z end{array} right)  ge 0.

This is equivalent to: for every y,

  0 ge f(y) := min_{z} : g(y,z) .

Since S is positive semi-definite, the corresponding quadratic function g is convex, jointly in its two arguments. Due to the partial minimization result, we obtain that the partial minimum f(y) is convex as well.

It is easy to obtain a closed-form expression for f. We simply have to minimize the convex quadratic function g with respect to its second argument. Since the problem of minimizing g is not constrained, we just set the gradient of g with respect to z to zero (see here):

  nabla_z g (y,z) = 2(Cz+B^Ty) = 0,

which leads to the (unique) optimizer z^ast(y) := -C^{-1}B^Ty. Plugging this value we obtain:

 f(y) = g(y,z^ast(y)) = y^T(A-BC^{-1}B^T)y.

Since f is convex, its Hessian must be positive semi-definite. Hence A-BC^{-1}B^T succeq 0, as claimed.