Lecture Notes

A.1 Loewner Order

Part of the Series on Linear Algebra.

By Akshay Agrawal. Last updated Oct. 20, 2018.

Loewner Order

The Loewner order is a partial order on the set of positive semidefinite symmetric matrices. For two positive semidefinite matrices $A$ and $B$, we write $A \leq B$ to denote that $B - A$ is positive semidefinite (and symmetric) and $A < B$ to denote that $B - A$ is positive definite (and symmetric). The set of positive semidefinite symmetric matrices is denoted $S^n_{+}$, and the set of positive definite symmetric matrices is denoted $S^n_{++}$.

Below are some facts about this partial order.

For the following fact, let $A \in S^n$, with eigenvalues $\lambda_1 \geq \lambda_2 \geq ... \geq \lambda_n$.

(1): $\lambda_n I \leq A \leq \lambda_1 I$. This holds because $\lambda_n x^Tx \leq x^TAx \leq \lambda_1 x^Tx$.

(2): For $B \in S^n$ and $C \in S^n_{++}$, $CAC \leq CBC$ if and only if $A \leq B$. This is clear, for $x^TAx \leq x^TBx \iff z^TCACz \leq z^TCBCz$ for some $z$ such that $Cz = x$ (which is possible because C is full rank).

Let $A \in S^n$ and $B \in S^n_{++}$. Then

(3): $B^{-1/2}AB^{-1/2} \leq I$ if and only if $A \leq B$. Furthermore, if $A > 0$, $A \leq B$ if and only if $A^{-1/2}BA^{-1/2} \geq I$. We prove the former statement below; the latter is proved in an analogous fashion by starting with $B - A \geq 0$.

$$A - B \leq 0 \iff B^{1/2}(B^{-1/2}AB^{-1/2} - I)B^{1/2} \leq 0 \iff B^{-1/2}AB^{-1/2} \leq I,$$

where the last inequality follows because $B^{1/2}$ is full rank.

Let $A \in S^n_{++}$ and $B \in S^n_{++}$. Then

(4): $A \leq B$ if and only if $B^{-1} \leq A^{-1}$. One way to prove this is to use (2):

$$\begin{align*} B - A \geq 0 &\iff A^{-1/2}BA^{-1/2} \geq I \\ &\iff B^{1/2}A^{-1/2}A^{-1/2} B^{1/2} \geq I \\ &\iff B^{1/2}A^{-1}B^{1/2} \geq I \\ &\iff B^{-1} \leq A^{-1}, \end{align*}$$

where the second equivalence used the fact that for any two matrices $S$ and $T$, the eigenvalues of $ST$ equal those of $TS$.

Since for every $A \in S^n_{++}$ one can associate an ellipsoid $\mathcal{E}_A = \{x : x^TA^{-1}x \leq 1\}$, it follows from (4) that $A \leq B$ if and only if $\mathcal{E}_A \subseteq \mathcal{E}_B$.

Schur Complement and Definiteness

Let $X \in S^n$ be partitioned as

$$X = \begin{bmatrix} A & B \\ B^T & C, \end{bmatrix}$$

where $A \in S^k$. If $A$ is invertible, then the matrix

$$S = C - B^TA^{-1}B$$

is called the Schur complement of $A$ in $X$. The following facts are useful:

(5): $X > 0$ if and only if $A > 0$ and $S > 0$.

(6): If $A > 0$, then $X \geq 0$ if and only if $S \geq 0$.

These facts can be derived by considering the minimization of the following quadratic, with variable $u$:

$$z^T X z,$$

where

$$z = \begin{bmatrix} u \\ v \end{bmatrix}.$$

If $A > 0$, then the optimal point is $u = -A^{-1}Bv$ and the optimal value is $v^TSv$.

To see why (5) is true, first observe that $X > 0$ implies $A > 0$ by the definition of positive definite. So $X > 0$ implies $A > 0$, and $A > 0$ implies the optimal value of the quadratic minimization problem is $v^TSv$; since $X > 0$, the optimal value must be positive (no matter the value of the paremeter $v$). Hence $S > 0$. Conversely, if $A > 0$ and $S > 0$, then $z^TXz$ is strictly greater than $0$ for all $z$, that is, $X > 0$.

To see why (6) is true, first assume that $X \geq 0$. Because $A > 0$ and the minimum of the quadratic in question is $v^TSv$, it must be the case that $v^TSv \geq 0$, that is, $S \geq 0$. Conversely, if $S \geq 0$, then $z^TXz \geq 0$ for all $z$, that is, $X \geq 0$.

References

Boyd, S., & Vandenberghe, L. (2004). Convex optimization. Cambridge university press.