13.6 Positive Matrices in Blocks

Chapter 8 cut a matrix into blocks, ran one step of elimination, and gave a name to what was left in the far corner: the Schur complement. Section 1 of this chapter met that same quantity as a single number, in the induction that proved Sylvester’s criterion. This section puts the two together. For a Hermitian matrix split into blocks, positive definiteness can be decided one block at a time, and the deciding quantity is the Schur complement; two determinant inequalities, Fischer’s and Hadamard’s, then come almost for free.

Throughout, $F = \mathbb{R}$ or $F = \mathbb{C}$ , and $F^n$ carries the standard inner product.

13.6.1. What the blocks of a positive matrix must satisfy

A Hermitian matrix cut into blocks of sizes $k$ and $l$ has a shape forced on it. Suppose

$\mathbf{M} = \begin{pmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{D} & \mathbf{C} \end{pmatrix} \in M_{k+l}(F),$

with $\mathbf{A} \in M_k(F)$ , $\mathbf{B} \in M_{k\times l}(F)$ , $\mathbf{D} \in M_{l\times k}(F)$ and $\mathbf{C} \in M_l(F)$ . Starring a block matrix transposes the arrangement and stars each block, so $\mathbf{M}^{*} = \mathbf{M}$ says exactly three things: $\mathbf{A}^{*} = \mathbf{A}$ , $\mathbf{C}^{*} = \mathbf{C}$ , and $\mathbf{D} = \mathbf{B}^{*}$ . A Hermitian $\mathbf{M}$ is therefore always of the form

$\mathbf{M} = \begin{pmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{B}^{*} & \mathbf{C} \end{pmatrix}$

with $\mathbf{A}$ and $\mathbf{C}$ Hermitian and $\mathbf{B}$ unrestricted, and we write it this way from now on.

Two necessary conditions for positivity are immediate. The vectors of $F^{k+l}$ whose last $l$ coordinates vanish form a copy of $F^k$ , and on them the quadratic form of $\mathbf{M}$ is the quadratic form of $\mathbf{A}$ :

$\begin{pmatrix} \mathbf{x} \\ \mathbf{0} \end{pmatrix}^{*}\mathbf{M}\begin{pmatrix} \mathbf{x} \\ \mathbf{0} \end{pmatrix} = \mathbf{x}^{*}\mathbf{A}\mathbf{x} , \qquad \begin{pmatrix} \mathbf{0} \\ \mathbf{y} \end{pmatrix}^{*}\mathbf{M}\begin{pmatrix} \mathbf{0} \\ \mathbf{y} \end{pmatrix} = \mathbf{y}^{*}\mathbf{C}\mathbf{y} .$

So $\mathbf{M} \succeq 0$ forces $\mathbf{A} \succeq 0$ and $\mathbf{C} \succeq 0$ . This is the statement that a principal submatrix of a positive semidefinite matrix is positive semidefinite, used already in the proof of Theorem 13.1.4, here for the two index blocks $\{1, \dots, k\}$ and $\{k+1, \dots, k+l\}$ .

The two conditions are not sufficient, and the smallest counterexample has $k = l = 1$ :

$\mathbf{M} = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}, \qquad \mathbf{A} = (0) \succeq 0, \quad \mathbf{C} = (1) \succ 0 .$

Here $\det \mathbf{M} = -1 < 0$ , so $\mathbf{M} \not\succeq 0$ by Theorem 13.1.4 (e). Something must couple $\mathbf{B}$ to $\mathbf{A}$ and $\mathbf{C}$ , and the $2 \times 2$ case already says what. For $\mathbf{M} = \begin{psmallmatrix} a & b \\ \conj b & c\end{psmallmatrix}$ Hermitian, Example (The $2 \times 2$ Test) gives $\mathbf{M} \succ 0$ if and only if $a > 0$ and $ac - \lvert b\rvert^2 > 0$ . Divide the second condition by the positive number $a$ :

$c - \overline{b}\,a^{-1}b > 0 .$

Written with $\mathbf{B} = (b)$ , so that $\mathbf{B}^{*} = (\conj b)$ , the left-hand side is the Schur complement $\mathbf{M}/\mathbf{A}$ of Definition 8.3.1. The general statement now writes itself: replace the scalars by blocks.

13.6.2. Testing one block at a time

Theorem 13.6.1 (Positive Definiteness Block by Block)

Let $k, l \ge 1$ and let

$\mathbf{M} = \begin{pmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{B}^{*} & \mathbf{C} \end{pmatrix} \in M_{k+l}(F)$

be Hermitian, with $\mathbf{A} \in M_k(F)$ , $\mathbf{B} \in M_{k \times l}(F)$ and $\mathbf{C} \in M_l(F)$ .

(a) If $\mathbf{M} \succeq 0$ , then $\mathbf{A} \succeq 0$ and $\mathbf{C} \succeq 0$ . If $\mathbf{M} \succ 0$ , then $\mathbf{A} \succ 0$ and $\mathbf{C} \succ 0$ .
(b) Suppose $\mathbf{A} \succ 0$ . Then $\mathbf{A}$ is invertible, the Schur complement $\mathbf{M}/\mathbf{A} = \mathbf{C} - \mathbf{B}^{*}\mathbf{A}^{-1}\mathbf{B} \in M_l(F)$ is Hermitian, and $\mathbf{M} \succ 0 \iff \mathbf{M}/\mathbf{A} \succ 0 , \qquad\quad \mathbf{M} \succeq 0 \iff \mathbf{M}/\mathbf{A} \succeq 0 .$

Idea. Everything is one congruence. Chapter 8’s block elimination clears $\mathbf{B}$ and $\mathbf{B}^{*}$ at once and leaves $\mathbf{A}$ and $\mathbf{M}/\mathbf{A}$ on the diagonal; for a Hermitian $\mathbf{M}$ the two outer factors of that elimination are adjoint to each other, because the row operation and the column operation are the same operation seen twice. So the elimination is a congruence $\mathbf{S}^{*}\mathbf{M}\mathbf{S}$ , and Proposition 13.1.2 says that a congruence by an invertible matrix neither creates nor destroys positivity. All that remains is to read the verdict off a block diagonal matrix, where the quadratic form splits into two independent pieces. This is the step $(\ast)$ of Section 1’s proof of Sylvester’s criterion, with the last coordinate replaced by a block of $l$ coordinates.

Proof.

(a) Let $\mathbf{x} \in F^k$ and put $\mathbf{v} = (\mathbf{x}, \mathbf{0}) \in F^{k+l}$ . By Theorem 8.1.1, $\mathbf{M}\mathbf{v} = (\mathbf{A}\mathbf{x}, \mathbf{B}^{*}\mathbf{x})$ , and hence $\mathbf{v}^{*}\mathbf{M}\mathbf{v} = \mathbf{x}^{*}\mathbf{A}\mathbf{x}$ . If $\mathbf{M} \succeq 0$ , the left side is $\ge 0$ for every $\mathbf{x}$ , so $\mathbf{A} \succeq 0$ ; if $\mathbf{M} \succ 0$ , then $\mathbf{x} \ne \mathbf{0}$ forces $\mathbf{v} \ne \mathbf{0}$ and the left side is $> 0$ , so $\mathbf{A} \succ 0$ . The same argument with $\mathbf{v} = (\mathbf{0}, \mathbf{y})$ gives the statements for $\mathbf{C}$ .
(b) Since $\mathbf{A} \succ 0$ , every eigenvalue of $\mathbf{A}$ is positive (Theorem 13.1.5 (b)), so $0 \notin \operatorname{spec}(\mathbf{A})$ and $\mathbf{A}$ is invertible (Theorem 9.2.6). Also $(\mathbf{A}^{-1})^{*} = (\mathbf{A}^{*})^{-1} = \mathbf{A}^{-1}$ , so

$(\mathbf{M}/\mathbf{A})^{*} = \mathbf{C}^{*} - \mathbf{B}^{*}(\mathbf{A}^{-1})^{*}\mathbf{B} = \mathbf{C} - \mathbf{B}^{*}\mathbf{A}^{-1}\mathbf{B} = \mathbf{M}/\mathbf{A} ,$

and $\mathbf{M}/\mathbf{A}$ is Hermitian. Put

$\mathbf{S} = \begin{pmatrix} \mathbf{I}_k & -\mathbf{A}^{-1}\mathbf{B} \\ 0 & \mathbf{I}_l \end{pmatrix} , \qquad \mathbf{S}^{*} = \begin{pmatrix} \mathbf{I}_k & 0 \\ -\mathbf{B}^{*}\mathbf{A}^{-1} & \mathbf{I}_l \end{pmatrix} ,$

the second because $\mathbf{A}^{-1}$ is Hermitian. By Theorem 8.1.5, $\mathbf{S}$ is invertible. Two applications of Theorem 8.1.1 give

$\begin{aligned} \mathbf{M}\mathbf{S} &= \begin{pmatrix} \mathbf{A} & \mathbf{B} - \mathbf{A}\mathbf{A}^{-1}\mathbf{B} \\ \mathbf{B}^{*} & \mathbf{C} - \mathbf{B}^{*}\mathbf{A}^{-1}\mathbf{B} \end{pmatrix} = \begin{pmatrix} \mathbf{A} & 0 \\ \mathbf{B}^{*} & \mathbf{M}/\mathbf{A} \end{pmatrix} , \\[2pt] \mathbf{S}^{*}(\mathbf{M}\mathbf{S}) &= \begin{pmatrix} \mathbf{A} & 0 \\ \mathbf{B}^{*} - \mathbf{B}^{*}\mathbf{A}^{-1}\mathbf{A} & \mathbf{M}/\mathbf{A} \end{pmatrix} = \begin{pmatrix} \mathbf{A} & 0 \\ 0 & \mathbf{M}/\mathbf{A} \end{pmatrix} . \end{aligned} \tag{$\ast$}$

Write $\mathbf{N} = \mathbf{A} \oplus (\mathbf{M}/\mathbf{A})$ for that block diagonal matrix. For $\mathbf{y} = (\mathbf{y}_1, \mathbf{y}_2) \in F^k \times F^l$ ,

$\mathbf{y}^{*}\mathbf{N}\mathbf{y} = \mathbf{y}_1^{*}\mathbf{A}\mathbf{y}_1 + \mathbf{y}_2^{*}(\mathbf{M}/\mathbf{A})\mathbf{y}_2 . \tag{$\dagger$}$

Claim. Given $\mathbf{A} \succ 0$ : $\mathbf{N} \succ 0$ if and only if $\mathbf{M}/\mathbf{A} \succ 0$ , and $\mathbf{N} \succeq 0$ if and only if $\mathbf{M}/\mathbf{A} \succeq 0$ .

Proof. Taking $\mathbf{y}_1 = \mathbf{0}$ in $(\dagger)$ shows that positivity of $\mathbf{N}$ , weak or strict, passes to $\mathbf{M}/\mathbf{A}$ , since $\mathbf{y}_2 \ne \mathbf{0}$ forces $\mathbf{y} \ne \mathbf{0}$ . Conversely, suppose $\mathbf{M}/\mathbf{A} \succeq 0$ ; then both terms of $(\dagger)$ are $\ge 0$ , so $\mathbf{N} \succeq 0$ . If moreover $\mathbf{M}/\mathbf{A} \succ 0$ , then for $\mathbf{y} \ne \mathbf{0}$ at least one of $\mathbf{y}_1$ , $\mathbf{y}_2$ is non-zero, so at least one term of $(\dagger)$ is $> 0$ while the other is $\ge 0$ ; hence $\mathbf{N} \succ 0$ .

Finally $\mathbf{S}$ is invertible, so Proposition 13.1.2 (b) gives $\mathbf{M} \succ 0$ if and only if $\mathbf{S}^{*}\mathbf{M}\mathbf{S} = \mathbf{N} \succ 0$ . For the weak version, Proposition 13.1.2 (a) applied to $\mathbf{S}$ turns $\mathbf{M} \succeq 0$ into $\mathbf{N} \succeq 0$ , and applied to $\mathbf{S}^{-1}$ , together with $(\mathbf{S}^{-1})^{*}\mathbf{N}\mathbf{S}^{-1} = \mathbf{M}$ , turns $\mathbf{N} \succeq 0$ back into $\mathbf{M} \succeq 0$ . Combining with the claim proves (b).

The identity $(\ast)$ is Theorem 8.3.1 (a) in disguise. That theorem factors $\mathbf{M} = \mathbf{L}\,\mathbf{N}\,\mathbf{U}$ with $\mathbf{L}$ lower and $\mathbf{U}$ upper block triangular; here $\mathbf{L}$ and $\mathbf{U}$ are $(\mathbf{S}^{-1})^{*}$ and $\mathbf{S}^{-1}$ , so the two outer factors are adjoint to each other and the factorization is a congruence, not merely an equivalence. Taking determinants in $(\ast)$ recovers Theorem 8.3.2,

$\det \mathbf{M} = \det \mathbf{A} \cdot \det(\mathbf{M}/\mathbf{A}) ,$

which is the form in which we use it below.

Chapter 8 closed its treatment of Schur complements by observing that when $\mathbf{M}$ is real symmetric the complement $\mathbf{M}/\mathbf{A}$ is symmetric again, and promising that “Chapter 13 uses Schur complements to test whether $\mathbf{M}$ is positive definite one block at a time”. Theorem 13.6.1 is that test, and part (b) says exactly what the promise says: once the corner block $\mathbf{A}$ is known to be positive definite, the whole of $\mathbf{M}$ is positive definite precisely when the smaller matrix $\mathbf{M}/\mathbf{A}$ is. A question about $k + l$ coordinates has become a question about $l$ of them.

It also finishes what Section 1 started. There, in the induction proving Sylvester’s criterion, the matrix was split with $k = n-1$ and $l = 1$ ; the shear $\mathbf{S}$ was the matrix above with the column $\mathbf{b}$ in place of $\mathbf{B}$ ; and the congruence came out as $\mathbf{S}^{*}\mathbf{A}\mathbf{S} = \mathbf{A}' \oplus (s)$ with the single number $s = d - \mathbf{b}^{*}\mathbf{A}'^{-1}\mathbf{b}$ in the corner. That section promised that Section 6 would replace the scalar by a block. The scalar has become $\mathbf{M}/\mathbf{A}$ , and the argument is word for word the same one.

Example (A

4 \times 4

Tested in

2 \times 2

Blocks)

Decide whether each of

$\mathbf{M} = \left(\begin{array}{cc|cc} 2 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ \hline 1 & 1 & 3 & 2 \\ 0 & 1 & 2 & 4 \end{array}\right), \qquad \mathbf{M}' = \left(\begin{array}{cc|cc} 2 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ \hline 1 & 1 & 2 & 0 \\ 0 & 1 & 0 & 2 \end{array}\right)$

is positive definite, using the displayed partition. For the one that is not, exhibit a vector on which the quadratic form is negative.

Solution. Both matrices are real symmetric with the same corner and border,

$\mathbf{A} = \begin{pmatrix} 2 & 1 \\ 1 & 1\end{pmatrix}, \qquad \mathbf{B} = \begin{pmatrix} 1 & 0 \\ 1 & 1\end{pmatrix} .$

Step 1: the corner. The leading principal minors of $\mathbf{A}$ are $2$ and $2 - 1 = 1$ , both positive, so $\mathbf{A} \succ 0$ by Sylvester’s criterion (Theorem 13.1.5 (d)) and Theorem 13.6.1 (b) applies. Since $\det \mathbf{A} = 1$ , Theorem 0.9.8 gives $\mathbf{A}^{-1} = \begin{psmallmatrix} 1 & -1 \\ -1 & 2\end{psmallmatrix}$ .

Step 2: the coupling term. It is the same for both matrices:

$\mathbf{B}^{\top}\mathbf{A}^{-1} = \begin{pmatrix} 0 & 1 \\ -1 & 2\end{pmatrix}, \qquad \mathbf{B}^{\top}\mathbf{A}^{-1}\mathbf{B} = \begin{pmatrix} 1 & 1 \\ 1 & 2 \end{pmatrix} .$

Step 3: the complements. For $\mathbf{M}$ , with $\mathbf{C} = \begin{psmallmatrix} 3 & 2 \\ 2 & 4\end{psmallmatrix}$ ,

$\mathbf{M}/\mathbf{A} = \begin{pmatrix} 3 & 2 \\ 2 & 4\end{pmatrix} - \begin{pmatrix} 1 & 1 \\ 1 & 2\end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 1 & 2 \end{pmatrix} ,$

whose leading principal minors are $2$ and $3$ . So $\mathbf{M}/\mathbf{A} \succ 0$ , hence $\mathbf{M} \succ 0$ . As a by-product, $\det \mathbf{M} = \det \mathbf{A}\cdot\det(\mathbf{M}/\mathbf{A}) = 1 \cdot 3 = 3$ .

For $\mathbf{M}'$ , with $\mathbf{C}' = \begin{psmallmatrix} 2 & 0 \\ 0 & 2\end{psmallmatrix}$ ,

$\mathbf{M}'/\mathbf{A} = \begin{pmatrix} 2 & 0 \\ 0 & 2\end{pmatrix} - \begin{pmatrix} 1 & 1 \\ 1 & 2\end{pmatrix} = \begin{pmatrix} 1 & -1 \\ -1 & 0 \end{pmatrix} ,$

whose determinant is $-1$ . So $\mathbf{M}'/\mathbf{A}$ is not even positive semidefinite, and $\mathbf{M}'$ is not positive definite.

Step 4: the witness. The congruence $(\ast)$ turns a bad vector for $\mathbf{M}'/\mathbf{A}$ into a bad vector for $\mathbf{M}'$ . Here $\mathbf{y}_2 = (1, 1)$ gives $\mathbf{y}_2^{\top}(\mathbf{M}'/\mathbf{A})\mathbf{y}_2 = 1 - 1 - 1 + 0 = -1$ , so $\mathbf{y} = (0, 0, 1, 1)$ satisfies $\mathbf{y}^{\top}(\mathbf{S}^{\top}\mathbf{M}'\mathbf{S})\mathbf{y} = -1$ , and $\mathbf{x} = \mathbf{S}\mathbf{y}$ satisfies $\mathbf{x}^{\top}\mathbf{M}'\mathbf{x} = -1$ . Since $-\mathbf{A}^{-1}\mathbf{B} = \begin{psmallmatrix} 0 & 1 \\ -1 & -2\end{psmallmatrix}$ , we get $\mathbf{x} = (1, -3, 1, 1)$ . Checking directly, $\mathbf{M}'\mathbf{x} = (0, 0, 0, -1)$ and $\mathbf{x}^{\top}(\mathbf{M}'\mathbf{x}) = 0 + 0 + 0 - 1 = -1$ .

One $2 \times 2$ inverse and one $2 \times 2$ product replaced four leading principal minors of a $4 \times 4$ matrix. And when the answer is “no”, the congruence hands back an explicit vector, which a determinant test never does.

Quick check. Let $\mathbf{A} \succ 0$ . What is $\mathbf{M}/\mathbf{A}$ when $\mathbf{B} = 0$ , and what does Theorem 13.6.1 (b) say in that case?

Solution. When $\mathbf{B} = 0$ the Schur complement is $\mathbf{M}/\mathbf{A} = \mathbf{C} - 0 = \mathbf{C}$ , so the criterion reads: $\mathbf{M} \succ 0$ if and only if $\mathbf{C} \succ 0$ . That is the right answer, since $\mathbf{M} = \mathbf{A} \oplus \mathbf{C}$ is then block diagonal and $(\dagger)$ says its quadratic form is the sum of the two separate quadratic forms. The general case is this case after the change of variable $\mathbf{S}$ .

Warning. The corner must be definite, not merely semidefinite. If $\mathbf{A}$ is singular, then $\mathbf{A}^{-1}$ does not exist, $\mathbf{M}/\mathbf{A}$ is undefined, and Theorem 13.6.1 (b) says nothing whatsoever. This is a real obstruction, not a gap in the proof. The matrix $\begin{psmallmatrix} 0 & 1 \\ 1 & 1\end{psmallmatrix}$ above has $\mathbf{A} \succeq 0$ and $\mathbf{C} \succ 0$ and is not positive semidefinite, while $\begin{psmallmatrix} 0 & 0 \\ 0 & 1\end{psmallmatrix}$ , with the same $\mathbf{A}$ and the same $\mathbf{C}$ , is. The two differ only in $\mathbf{B}$ , so no criterion that ignores $\mathbf{B}$ can separate them.

Remark. There is a criterion for the semidefinite case with a singular corner, and it has three clauses instead of one: for Hermitian $\mathbf{M}$ , one has $\mathbf{M} \succeq 0$ exactly when $\mathbf{A} \succeq 0$ , every column of $\mathbf{B}$ lies in the column space of $\mathbf{A}$ , and $\mathbf{C} - \mathbf{B}^{*}\mathbf{A}^{+}\mathbf{B} \succeq 0$ . The middle clause is what the warning’s first matrix violates. The matrix $\mathbf{A}^{+}$ in the third clause is the Moore–Penrose pseudoinverse; it agrees with $\mathbf{A}^{-1}$ when $\mathbf{A}$ is invertible, and it is built from the singular values of $\mathbf{A}$ in Section 11 of this chapter. The statement and its proof belong there, with the tools they need. This section keeps the definite case, which is the one the rest of the chapter consumes.

13.6.3. Fischer’s inequality

The congruence $(\ast)$ computes $\det \mathbf{M}$ as $\det \mathbf{A} \cdot \det(\mathbf{M}/\mathbf{A})$ . If the Schur complement could be compared with $\mathbf{C}$ , that would bound $\det \mathbf{M}$ by $\det \mathbf{A}\det \mathbf{C}$ — and it can be, because $\mathbf{C}$ is the Schur complement plus something positive:

$\mathbf{C} = (\mathbf{M}/\mathbf{A}) + \mathbf{B}^{*}\mathbf{A}^{-1}\mathbf{B} .$

So what is needed is that adding a positive semidefinite matrix never decreases a determinant. That is the next lemma, and it is where the square root of Section 2 earns its keep.

Lemma 13.6.2 (Adding a positive matrix does not decrease the determinant)

Let $\mathbf{P}, \mathbf{Q} \in M_n(F)$ with $\mathbf{P} \succ 0$ and $\mathbf{Q} \succeq 0$ . Then

$\det(\mathbf{P} + \mathbf{Q}) \ge \det \mathbf{P} > 0 ,$

with equality if and only if $\mathbf{Q} = 0$ .

Idea. Whiten: divide the problem by $\mathbf{P}$ on both sides, using the inverse of $\mathbf{P}^{1/2}$ . The sum $\mathbf{P} + \mathbf{Q}$ becomes $\mathbf{I} + \mathbf{K}$ with $\mathbf{K} \succeq 0$ , and the determinant of $\mathbf{I} + \mathbf{K}$ is $\prod_i(1 + \mu_i)$ over the eigenvalues $\mu_i \ge 0$ of $\mathbf{K}$ . A product of numbers $\ge 1$ is $\ge 1$ , and it equals $1$ only when every factor does.

Proof. By Theorem 13.2.1 the matrix $\mathbf{P}^{1/2} \succeq 0$ exists, and it is invertible because $\mathbf{P}$ is (Theorem 13.2.1 (c)). Write $\mathbf{R} = (\mathbf{P}^{1/2})^{-1}$ , which is Hermitian, being the inverse of a Hermitian matrix. Since $\mathbf{P}^{1/2}\mathbf{R} = \mathbf{I}$ and $(\mathbf{P}^{1/2})^2 = \mathbf{P}$ ,

$\mathbf{P}^{1/2}\bigl(\mathbf{I} + \mathbf{R}\mathbf{Q}\mathbf{R}\bigr)\mathbf{P}^{1/2} = \mathbf{P} + \mathbf{Q} .$

Put $\mathbf{K} = \mathbf{R}^{*}\mathbf{Q}\mathbf{R} = \mathbf{R}\mathbf{Q}\mathbf{R}$ , so that $\mathbf{K} \succeq 0$ by Proposition 13.1.2 (a). Taking determinants with Theorem 7.5.4, and using $(\det \mathbf{P}^{1/2})^2 = \det \mathbf{P}$ ,

$\det(\mathbf{P} + \mathbf{Q}) = \det \mathbf{P} \cdot \det(\mathbf{I} + \mathbf{K}) .$

Now $\mathbf{K}$ is Hermitian, so $\mathbf{K} = \mathbf{U}\operatorname{diag}(\mu_1, \dots, \mu_n)\mathbf{U}^{*}$ with $\mathbf{U}$ unitary, by Corollary 12.4.3 over $\mathbb{C}$ and Corollary 12.5.2 over $\mathbb{R}$ ; and every $\mu_i \ge 0$ by Theorem 13.1.4 (b). Then $\mathbf{I} + \mathbf{K} = \mathbf{U}\operatorname{diag}(1 + \mu_1, \dots, 1 + \mu_n)\mathbf{U}^{*}$ , so

$\det(\mathbf{I} + \mathbf{K}) = \prod_{i=1}^{n}(1 + \mu_i) \ge 1 ,$

each factor being $\ge 1$ . Also $\det \mathbf{P} > 0$ , since the eigenvalues of $\mathbf{P}$ are positive (Theorem 13.1.5 (b)) and the determinant is their product. Hence $\det(\mathbf{P} + \mathbf{Q}) \ge \det \mathbf{P} > 0$ .

For the equality case, the product equals $1$ exactly when every $\mu_i = 0$ , that is when $\mathbf{K} = \mathbf{U}\,0\,\mathbf{U}^{*} = 0$ , and then $\mathbf{Q} = \mathbf{P}^{1/2}\mathbf{K}\mathbf{P}^{1/2} = 0$ . Conversely $\mathbf{Q} = 0$ gives equality. This proves the lemma.

Remark. Section 5 states this in its natural generality: the determinant is monotone for the Loewner order, so $\mathbf{A} \succeq \mathbf{B} \succeq 0$ implies $\det \mathbf{A} \ge \det \mathbf{B}$ . The special case proved here, in which the smaller of the two matrices is definite, is all this section and the next one need, and its proof is short enough to keep local.

Corollary 13.6.3 (Fischer’s Inequality)

Let $\mathbf{M} = \begin{psmallmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{B}^{*} & \mathbf{C}\end{psmallmatrix} \in M_{k+l}(F)$ with $\mathbf{M} \succeq 0$ , where $\mathbf{A} \in M_k(F)$ and $\mathbf{C} \in M_l(F)$ . Then

$\det \mathbf{M} \le \det \mathbf{A} \cdot \det \mathbf{C} .$

If $\mathbf{M} \succ 0$ , equality holds if and only if $\mathbf{B} = 0$ .

Idea. Do the definite case first and reach the general case by a limit. For $\mathbf{M} \succ 0$ the Schur complement exists, the determinant splits as $\det \mathbf{A}\det(\mathbf{M}/\mathbf{A})$ , and $\det \mathbf{C} \ge \det(\mathbf{M}/\mathbf{A})$ by Lemma 13.6.2 applied to $\mathbf{C} = (\mathbf{M}/\mathbf{A}) + \mathbf{B}^{*}\mathbf{A}^{-1}\mathbf{B}$ . For $\mathbf{M} \succeq 0$ , apply the definite case to $\mathbf{M} + t\mathbf{I}$ and let $t$ shrink to $0$ : both sides are polynomials in $t$ .

Proof. Case 1: $\mathbf{M} \succ 0$ . By Theorem 13.6.1 (a), $\mathbf{A} \succ 0$ , and by (b), $\mathbf{M}/\mathbf{A} \succ 0$ . By Theorem 8.3.2,

$\det \mathbf{M} = \det \mathbf{A} \cdot \det(\mathbf{M}/\mathbf{A}) .$

The matrix $\mathbf{A}^{-1}$ is positive definite. Indeed the eigenvalues of $\mathbf{A}$ are positive (Theorem 13.1.5 (b)), so $\mathbf{A}$ is invertible (Theorem 9.2.6); the identity $(\mathbf{A}^{-1})^{*} = (\mathbf{A}^{*})^{-1} = \mathbf{A}^{-1}$ makes $\mathbf{A}^{-1}$ Hermitian; and Proposition 13.1.2 (b) with the invertible $\mathbf{S} = \mathbf{A}^{-1}$ turns $\mathbf{S}^{*}\mathbf{A}\mathbf{S} = \mathbf{A}^{-1}\mathbf{A}\mathbf{A}^{-1} = \mathbf{A}^{-1}$ into $\mathbf{A}^{-1} \succ 0$ . (This is Exercise (B3: The inverse of a positive definite matrix).) So $\mathbf{Q} \mathrel{:=} \mathbf{B}^{*}\mathbf{A}^{-1}\mathbf{B} \succeq 0$ by Proposition 13.1.2 (a) with $\mathbf{S} = \mathbf{B}$ . Since $\mathbf{C} = (\mathbf{M}/\mathbf{A}) + \mathbf{Q}$ , Lemma 13.6.2 with $\mathbf{P} = \mathbf{M}/\mathbf{A}$ gives $\det \mathbf{C} \ge \det(\mathbf{M}/\mathbf{A})$ , with equality if and only if $\mathbf{Q} = 0$ . Multiplying by $\det \mathbf{A} > 0$ ,

$\det \mathbf{M} = \det \mathbf{A}\det(\mathbf{M}/\mathbf{A}) \le \det \mathbf{A}\det \mathbf{C} ,$

with equality if and only if $\mathbf{B}^{*}\mathbf{A}^{-1}\mathbf{B} = 0$ .

It remains to see that $\mathbf{B}^{*}\mathbf{A}^{-1}\mathbf{B} = 0$ holds only for $\mathbf{B} = 0$ . Let $\mathbf{R} = (\mathbf{A}^{1/2})^{-1}$ , a Hermitian matrix with $\mathbf{R}^2 = \mathbf{A}^{-1}$ , as in the proof of Lemma 13.6.2. Then $\mathbf{B}^{*}\mathbf{A}^{-1}\mathbf{B} = (\mathbf{R}\mathbf{B})^{*}(\mathbf{R}\mathbf{B})$ , whose $(j, j)$ entry is the squared norm of the $j$ -th column of $\mathbf{R}\mathbf{B}$ . If the whole matrix is $0$ , every column of $\mathbf{R}\mathbf{B}$ is $\mathbf{0}$ , so $\mathbf{R}\mathbf{B} = 0$ and $\mathbf{B} = \mathbf{A}^{1/2}(\mathbf{R}\mathbf{B}) = 0$ . The converse is clear.

Case 2: $\mathbf{M} \succeq 0$ . For real $t > 0$ the matrix $\mathbf{M} + t\mathbf{I}_{k+l}$ is Hermitian with $\mathbf{v}^{*}(\mathbf{M} + t\mathbf{I})\mathbf{v} = \mathbf{v}^{*}\mathbf{M}\mathbf{v} + t\left\| \mathbf{v} \right\|^2 > 0$ for $\mathbf{v} \ne \mathbf{0}$ , so $\mathbf{M} + t\mathbf{I} \succ 0$ . Its blocks are $\mathbf{A} + t\mathbf{I}_k$ , $\mathbf{B}$ and $\mathbf{C} + t\mathbf{I}_l$ , so Case 1 gives

$\det(\mathbf{M} + t\mathbf{I}) \le \det(\mathbf{A} + t\mathbf{I}_k)\cdot\det(\mathbf{C} + t\mathbf{I}_l)$

for every $t > 0$ . A determinant is a polynomial in the entries (Theorem 7.4.3), and the entries here are polynomials in $t$ , so both sides are polynomial, hence continuous, functions of $t$ . Letting $t$ decrease to $0$ preserves the inequality, and at $t = 0$ it reads $\det \mathbf{M} \le \det \mathbf{A}\det \mathbf{C}$ . This proves the corollary.

The inequality says that for a positive matrix the off-diagonal blocks are a liability: they can only shrink the determinant, and they cost nothing only when they are absent. Applying it repeatedly, to finer and finer partitions, gives the classical case in which every block is $1 \times 1$ . That is the next result.

13.6.4. Hadamard’s inequality

Theorem 13.6.4 (Hadamard’s Inequality)

(a) Let $\mathbf{A} \in M_n(F)$ with $\mathbf{A} \succeq 0$ . Then $\det \mathbf{A} \le a_{11}a_{22}\cdots a_{nn} ,$ with equality if and only if $\mathbf{A}$ is diagonal or some $a_{ii} = 0$ .
(b) Let $\mathbf{B} \in M_n(F)$ have columns $\mathbf{b}_1, \dots, \mathbf{b}_n$ . Then $\lvert\det \mathbf{B}\rvert \le \left\| \mathbf{b}_1 \right\|\,\left\| \mathbf{b}_2 \right\|\cdots\left\| \mathbf{b}_n \right\| ,$ with equality if and only if the columns are pairwise orthogonal or some column is $\mathbf{0}$ .

Idea. Part (a) is Fischer’s inequality with $k = 1$ , applied again and again: peel off the first row and column, bound $\det \mathbf{A}$ by $a_{11}\det \mathbf{A}'$ , and induct on the size. Part (b) is part (a) for the Gram matrix $\mathbf{A} = \mathbf{B}^{*}\mathbf{B}$ , whose diagonal entries are the squared lengths $\left\| \mathbf{b}_j \right\|^2$ and whose determinant is $\lvert\det \mathbf{B}\rvert^2$ . The equality conditions transfer along the same dictionary: $\mathbf{A}$ diagonal says the columns of $\mathbf{B}$ are orthogonal, and $a_{jj} = 0$ says $\mathbf{b}_j = \mathbf{0}$ .

Proof.

(a) Induct on $n$ . For $n = 1$ both sides are $a_{11}$ .
Let $n \ge 2$ and split $\mathbf{A}$ with $k = 1$ :

$\mathbf{A} = \begin{pmatrix} a_{11} & \mathbf{b}^{*} \\ \mathbf{b} & \mathbf{A}' \end{pmatrix}, \qquad \mathbf{b} \in F^{n-1},\quad \mathbf{A}' \in M_{n-1}(F) ,$

so that $\mathbf{A}'$ is the submatrix on rows and columns $2, \dots, n$ . By Theorem 13.6.1 (a), $\mathbf{A}' \succeq 0$ , and by Corollary 13.6.3,

$\det \mathbf{A} \le a_{11}\det \mathbf{A}' \le a_{11}\,(a_{22}\cdots a_{nn}) ,$

the second step being the inductive hypothesis applied to $\mathbf{A}'$ . This is the inequality.

For equality, suppose first that some $a_{ii} = 0$ . Fix $j \ne i$ and put $I = \{i, j\}$ . By Theorem 13.1.4 ((a) $\Rightarrow$ (e)) the principal minor on the rows and columns $I$ is $\ge 0$ , so $0 \le \det \mathbf{A}_{I,I} = a_{ii}a_{jj} - \lvert a_{ij}\rvert^2 = -\lvert a_{ij}\rvert^2 ,$ forcing $a_{ij} = 0$ ; and $a_{ji} = \overline{a_{ij}} = 0$ because $\mathbf{A}$ is Hermitian. As $j \ne i$ was arbitrary, row $i$ and column $i$ of $\mathbf{A}$ are zero (which is Exercise (C3: The largest entry sits on the diagonal) (b)) and $\det \mathbf{A} = 0$ ; the right-hand side is $0$ too, so equality holds. If $\mathbf{A}$ is diagonal, both sides are the product of the diagonal entries. Conversely, suppose equality holds and every $a_{ii} > 0$ . Then $\det \mathbf{A} = a_{11}\cdots a_{nn} > 0$ , so $\mathbf{A}$ is invertible, and a positive semidefinite matrix with no zero eigenvalue is positive definite (Theorem 13.1.5 (b)). Both inequalities in the display are therefore equalities. The first is the equality case of Corollary 13.6.3 for the positive definite $\mathbf{A}$ , so $\mathbf{b} = \mathbf{0}$ : the first row and column vanish off the diagonal. The second is the equality case of the inductive hypothesis for $\mathbf{A}'$ , whose diagonal entries are positive, so $\mathbf{A}'$ is diagonal. Hence $\mathbf{A}$ is diagonal, and the induction is complete.
(b) Put $\mathbf{A} = \mathbf{B}^{*}\mathbf{B}$ , which is positive semidefinite by Theorem 13.1.4 (c). Its $(j, j)$ entry is $\mathbf{b}_j^{*}\mathbf{b}_j = \left\| \mathbf{b}_j \right\|^2$ . By Theorem 7.5.4, and because $\det(\mathbf{B}^{*}) = \overline{\det \mathbf{B}}$ — the star transposes, which does not change the determinant (Theorem 7.4.5), and conjugates every entry, which conjugates the determinant —

$\det \mathbf{A} = \overline{\det \mathbf{B}}\,\det \mathbf{B} = \lvert\det \mathbf{B}\rvert^2 .$

Part (a) now reads $\lvert\det \mathbf{B}\rvert^2 \le \left\| \mathbf{b}_1 \right\|^2\cdots\left\| \mathbf{b}_n \right\|^2$ , and taking non-negative square roots gives the inequality.

For equality, note that $a_{jj} = 0$ says $\mathbf{b}_j = \mathbf{0}$ , and that $\mathbf{A}$ is diagonal exactly when $\langle \mathbf{b}_j, \mathbf{b}_i \rangle = a_{ij} = 0$ for all $i \ne j$ , that is, exactly when the columns are pairwise orthogonal. So the equality condition of (a) translates into the stated one. This proves the theorem.

Remark. Part (b) has a geometric reading, and it is the reason the inequality is remembered. Over $\mathbb{R}$ , $\lvert\det \mathbf{B}\rvert$ is the volume of the parallelepiped with edges $\mathbf{b}_1, \dots, \mathbf{b}_n$ (Definition 7.9.1), and the right-hand side is the volume of the box with the same edge lengths. So among all parallelepipeds with prescribed edge lengths, the rectangular one has the largest volume, and up to degenerate cases it is the only one. Tilting an edge costs volume.

$Diagram. Labels: b_1, b_2, area lvert det B rvert, area norm b_1\,norm b_2, the shaded parallelogram and the dashed rectangle\\ have the same two edge lengths$

Example (Two Determinant Bounds)

Bound $\lvert\det \mathbf{B}\rvert$ using Theorem 13.6.4 (b) for

$\mathbf{B}_1 = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}, \qquad \mathbf{B}_2 = \begin{pmatrix} 2 & 1 & 0 \\ 1 & 2 & 1 \\ 0 & 1 & 2 \end{pmatrix},$

and compare each bound with the exact value.

Solution. For $\mathbf{B}_1$ , both columns have norm $\sqrt2$ , so the bound is $2$ . The determinant is $-1 - 1 = -2$ , so $\lvert\det \mathbf{B}_1\rvert = 2$ and the bound is attained. The equality case predicts this: $\langle (1,-1), (1,1) \rangle = 1 - 1 = 0$ , so the columns are orthogonal.

For $\mathbf{B}_2$ , the columns have norms $\sqrt5$ , $\sqrt6$ and $\sqrt5$ , so the bound is $5\sqrt6 \approx 12.25$ . Expanding along the first row, $\det \mathbf{B}_2 = 2(4 - 1) - 1(2 - 0) = 4$ . The bound holds and is far from sharp, as it must be, since $\langle (1,2,1), (2,1,0) \rangle = 4 \ne 0$ means the columns are not orthogonal.

Warning. Part (a) needs positivity; without it the inequality can fail in either direction. The symmetric matrix

$\mathbf{A} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & -1 & 0 \\ 1 & 0 & -1 \end{pmatrix}$

has $\det \mathbf{A} = 3$ , while $a_{11}a_{22}a_{33} = 1\cdot(-1)\cdot(-1) = 1$ . So $\det \mathbf{A} > \prod_i a_{ii}$ , and a diagonal entry of an indefinite matrix carries no information about the size of the determinant. Part (b), by contrast, has no hypothesis at all — but it bounds by column norms. For rows, apply the same result to $\mathbf{B}^{\top}$ , whose determinant is unchanged (Theorem 7.4.5).

13.6.5. Exercises

A. Check your understanding

Exercise (A1)

(a) Write down the general form of a Hermitian matrix in $2 \times 2$ block form, and say what each block must satisfy.
(b) State Theorem 13.6.1 (b) in full, including its hypothesis.
(c) True or false: if $\mathbf{M} = \begin{psmallmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{B}^{*} & \mathbf{C}\end{psmallmatrix}$ is Hermitian with $\mathbf{A} \succeq 0$ and $\mathbf{C} \succeq 0$ , then $\mathbf{M} \succeq 0$ . Justify your answer.
(d) State both forms of Hadamard’s inequality, and say what hypothesis each one needs.
(e) In the proof of Fischer’s inequality, which matrix plays the role of $\mathbf{Q}$ in Lemma 13.6.2, and which plays the role of $\mathbf{P}$ ?

Solution.

(a) $\mathbf{M} = \begin{psmallmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{B}^{*} & \mathbf{C}\end{psmallmatrix}$ with $\mathbf{A} \in M_k(F)$ and $\mathbf{C} \in M_l(F)$ Hermitian and $\mathbf{B} \in M_{k\times l}(F)$ arbitrary. The condition $\mathbf{M}^{*} = \mathbf{M}$ forces the lower-left block to be $\mathbf{B}^{*}$ and both diagonal blocks to be Hermitian.
(b) If $\mathbf{A} \succ 0$ , then $\mathbf{A}$ is invertible, $\mathbf{M}/\mathbf{A} = \mathbf{C} - \mathbf{B}^{*}\mathbf{A}^{-1}\mathbf{B}$ is Hermitian, $\mathbf{M} \succ 0$ if and only if $\mathbf{M}/\mathbf{A} \succ 0$ , and $\mathbf{M} \succeq 0$ if and only if $\mathbf{M}/\mathbf{A} \succeq 0$ .
(c) False. Take $\mathbf{A} = (0)$ , $\mathbf{B} = (1)$ and $\mathbf{C} = (1)$ , so $\mathbf{M} = \begin{psmallmatrix} 0 & 1 \\ 1 & 1\end{psmallmatrix}$ . Both diagonal blocks are positive semidefinite, but $\det \mathbf{M} = -1 < 0$ , so $\mathbf{M} \not\succeq 0$ by Theorem 13.1.4 (e).
(d) By Theorem 13.6.4: for $\mathbf{A} \succeq 0$ , $\det \mathbf{A} \le a_{11}\cdots a_{nn}$ , and the hypothesis is positive semidefiniteness. For any square $\mathbf{B}$ : $\lvert\det \mathbf{B}\rvert \le \left\| \mathbf{b}_1 \right\|\cdots\left\| \mathbf{b}_n \right\|$ over the columns, with no hypothesis.
(e) In Corollary 13.6.3, $\mathbf{P} = \mathbf{M}/\mathbf{A}$ and $\mathbf{Q} = \mathbf{B}^{*}\mathbf{A}^{-1}\mathbf{B}$ , so that $\mathbf{P} + \mathbf{Q} = \mathbf{C}$ .

B. Practice

Exercise (B1: Definiteness by blocks)

Each matrix below is real symmetric and is displayed with a $2, 2$ partition. Determine whether it is positive definite. Justify your answer, and for any that is not, give a vector $\mathbf{x}$ with $\mathbf{x}^{\top}\mathbf{M}\mathbf{x} < 0$ .

(a) $\mathbf{M}_1 = \left(\begin{array}{cc|cc} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & -1 \\ \hline 1 & 1 & 3 & 0 \\ 1 & -1 & 0 & 3\end{array}\right)$
(b) $\mathbf{M}_2 = \left(\begin{array}{cc|cc} 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & -1 \\ \hline 1 & 1 & 2 & 0 \\ 1 & -1 & 0 & 1\end{array}\right)$

Solution. In both cases $\mathbf{A} = \mathbf{I}_2 \succ 0$ and $\mathbf{B} = \begin{psmallmatrix} 1 & 1 \\ 1 & -1\end{psmallmatrix}$ , so Theorem 13.6.1 (b) applies with $\mathbf{A}^{-1} = \mathbf{I}_2$ and

$\mathbf{B}^{\top}\mathbf{A}^{-1}\mathbf{B} = \mathbf{B}^{\top}\mathbf{B} = \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix} .$

(a) $\mathbf{M}_1/\mathbf{A} = \begin{psmallmatrix} 3 & 0 \\ 0 & 3\end{psmallmatrix} - \begin{psmallmatrix} 2 & 0 \\ 0 & 2\end{psmallmatrix} = \mathbf{I}_2 \succ 0$ . Hence $\mathbf{M}_1 \succ 0$ , and $\det \mathbf{M}_1 = \det \mathbf{A}\det(\mathbf{M}_1/\mathbf{A}) = 1$ .
(b) $\mathbf{M}_2/\mathbf{A} = \begin{psmallmatrix} 2 & 0 \\ 0 & 1\end{psmallmatrix} - \begin{psmallmatrix} 2 & 0 \\ 0 & 2\end{psmallmatrix} = \begin{psmallmatrix} 0 & 0 \\ 0 & -1\end{psmallmatrix}$ . This is the matrix of Section 1’s warning: its leading principal minors are $0$ and $0$ , and yet it is not positive semidefinite. So $\mathbf{M}_2$ is not positive definite, and not even positive semidefinite.

For the witness, $\mathbf{y}_2 = (0, 1)$ gives $\mathbf{y}_2^{\top}(\mathbf{M}_2/\mathbf{A})\mathbf{y}_2 = -1$ . With $\mathbf{S} = \begin{psmallmatrix} \mathbf{I}_2 & -\mathbf{B} \\ 0 & \mathbf{I}_2\end{psmallmatrix}$ and $\mathbf{y} = (0, 0, 0, 1)$ , the vector $\mathbf{x} = \mathbf{S}\mathbf{y} = (-1, 1, 0, 1)$ satisfies $\mathbf{x}^{\top}\mathbf{M}_2\mathbf{x} = -1$ .

Exercise (B2: A bordered matrix)

Let

$\mathbf{M} = \begin{pmatrix} 2 & 1 & 1 \\ 1 & 2 & 0 \\ 1 & 0 & 2 \end{pmatrix} .$

(a) Using the partition with $k = 1$ , compute $\mathbf{M}/\mathbf{A}$ and decide whether $\mathbf{M} \succ 0$ .
(b) Hence compute $\det \mathbf{M}$ , and check Fischer’s inequality for this partition.

Solution.

(a) Here $\mathbf{A} = (2) \succ 0$ , $\mathbf{B} = \begin{pmatrix} 1 & 1\end{pmatrix}$ and $\mathbf{C} = \begin{psmallmatrix} 2 & 0 \\ 0 & 2\end{psmallmatrix}$ . Then
$\mathbf{B}^{*}\mathbf{A}^{-1}\mathbf{B} = \tfrac12\begin{pmatrix} 1 \\ 1\end{pmatrix}\begin{pmatrix} 1 & 1\end{pmatrix} = \tfrac12\begin{pmatrix} 1 & 1 \\ 1 & 1\end{pmatrix}, \qquad \mathbf{M}/\mathbf{A} = \begin{pmatrix} 3/2 & -1/2 \\ -1/2 & 3/2 \end{pmatrix} .$

The leading principal minors of $\mathbf{M}/\mathbf{A}$ are $3/2$ and $9/4 - 1/4 = 2$ , both positive, so $\mathbf{M}/\mathbf{A} \succ 0$ and $\mathbf{M} \succ 0$ by Theorem 13.6.1 (b).
(b) By Theorem 8.3.2, $\det \mathbf{M} = 2 \cdot 2 = 4$ . Fischer’s inequality (Corollary 13.6.3) for this partition reads $\det \mathbf{M} \le \det \mathbf{A}\det \mathbf{C} = 2\cdot 4 = 8$ , and indeed $4 \le 8$ . The inequality is strict, as it must be, since $\mathbf{B} \ne 0$ .

Exercise (B3: Hadamard bounds)

(a) Bound $\lvert\det \mathbf{B}\rvert$ for $\mathbf{B} = \begin{psmallmatrix} 1 & 2 \\ 3 & 4\end{psmallmatrix}$ , and compare with the exact value.
(b) Let $\mathbf{H} = \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & 1 & -1 \\ 1 & -1 & -1 & 1\end{pmatrix} .$ Compute $\mathbf{H}^{\top}\mathbf{H}$ , and deduce $\lvert\det \mathbf{H}\rvert$ without expanding the determinant.

Solution.

(a) The columns are $(1, 3)$ and $(2, 4)$ , with norms $\sqrt{10}$ and $\sqrt{20}$ , so the bound is $\sqrt{200} = 10\sqrt2 \approx 14.14$ . The determinant is $4 - 6 = -2$ , so $\lvert\det \mathbf{B}\rvert = 2$ . The bound is true and very weak, because the columns are far from orthogonal.
(b) Every column of $\mathbf{H}$ has norm $2$ , and any two distinct columns are orthogonal: each of the six pairs agrees in two positions and disagrees in the other two, so the dot product is $1 + 1 - 1 - 1 = 0$ . Hence $\mathbf{H}^{\top}\mathbf{H} = 4\mathbf{I}_4$ . Taking determinants with Theorem 7.5.4 and Theorem 7.4.5, $(\det \mathbf{H})^2 = 4^4 = 256$ , so $\lvert\det \mathbf{H}\rvert = 16$ . This is exactly the Hadamard bound $\left\| \mathbf{h}_1 \right\|\cdots\left\| \mathbf{h}_4 \right\| = 2^4 = 16$ , as the equality case of Theorem 13.6.4 (b) predicts for orthogonal columns.

C. Going deeper

Exercise (C1: A zero corner kills its border)

(a) Prove that if $\mathbf{P} \succeq 0$ and $\mathbf{x}^{*}\mathbf{P}\mathbf{x} = 0$ , then $\mathbf{P}\mathbf{x} = \mathbf{0}$ .
(b) Deduce that if $\mathbf{M} = \begin{psmallmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{B}^{*} & \mathbf{C}\end{psmallmatrix} \succeq 0$ and $\mathbf{A} = 0$ , then $\mathbf{B} = 0$ .
(c) Deduce that if $\mathbf{M} \succeq 0$ and $\mathbf{A}$ is singular, then $\mathbf{M}$ is singular. What does Fischer’s inequality say in that case?

Hint for (a): write $\mathbf{P} = \mathbf{N}^{*}\mathbf{N}$ .

Solution.

(a) By Theorem 13.1.4 (c), $\mathbf{P} = \mathbf{N}^{*}\mathbf{N}$ for some $\mathbf{N}$ . Then $0 = \mathbf{x}^{*}\mathbf{P}\mathbf{x} = \left\| \mathbf{N}\mathbf{x} \right\|^2$ , so $\mathbf{N}\mathbf{x} = \mathbf{0}$ and $\mathbf{P}\mathbf{x} = \mathbf{N}^{*}(\mathbf{N}\mathbf{x}) = \mathbf{0}$ .
(b) Let $\mathbf{x} \in F^k$ and put $\mathbf{v} = (\mathbf{x}, \mathbf{0})$ . As computed in the proof of Theorem 13.6.1 (a), $\mathbf{v}^{*}\mathbf{M}\mathbf{v} = \mathbf{x}^{*}\mathbf{A}\mathbf{x} = 0$ . By (a), $\mathbf{M}\mathbf{v} = \mathbf{0}$ . But $\mathbf{M}\mathbf{v} = (\mathbf{A}\mathbf{x}, \mathbf{B}^{*}\mathbf{x}) = (\mathbf{0}, \mathbf{B}^{*}\mathbf{x})$ , so $\mathbf{B}^{*}\mathbf{x} = \mathbf{0}$ for every $\mathbf{x} \in F^k$ , that is $\mathbf{B}^{*} = 0$ and $\mathbf{B} = 0$ .
(c) Choose $\mathbf{x} \ne \mathbf{0}$ with $\mathbf{A}\mathbf{x} = \mathbf{0}$ , which is possible since $\mathbf{A}$ is singular (Theorem 3.4.4), and put $\mathbf{v} = (\mathbf{x}, \mathbf{0}) \ne \mathbf{0}$ . Then $\mathbf{v}^{*}\mathbf{M}\mathbf{v} = \mathbf{x}^{*}\mathbf{A}\mathbf{x} = 0$ , so $\mathbf{M}\mathbf{v} = \mathbf{0}$ by (a), and $\mathbf{M}$ is singular. Hence $\det \mathbf{M} = 0$ , while $\det \mathbf{A}\det \mathbf{C} = 0$ as well, so Corollary 13.6.3 holds with both sides equal to $0$ . It is true, and it says nothing; the informative case is $\mathbf{A} \succ 0$ .

Exercise (C2: A Cauchy–Schwarz inequality for blocks)

Let $\mathbf{M} = \begin{psmallmatrix} \mathbf{A} & \mathbf{B} \\ \mathbf{B}^{*} & \mathbf{C}\end{psmallmatrix} \succeq 0$ with $\mathbf{A} \in M_k(F)$ and $\mathbf{C} \in M_l(F)$ .

(a) Prove that for all $\mathbf{x} \in F^k$ and $\mathbf{y} \in F^l$ , $\lvert\mathbf{x}^{*}\mathbf{B}\mathbf{y}\rvert^2 \le (\mathbf{x}^{*}\mathbf{A}\mathbf{x})\,(\mathbf{y}^{*}\mathbf{C}\mathbf{y}) .$
(b) Deduce the Cauchy–Schwarz inequality $\lvert\langle \mathbf{y}, \mathbf{x} \rangle\rvert \le \left\| \mathbf{x} \right\|\,\left\| \mathbf{y} \right\|$ in $F^n$ .

Hint for (a): apply the definition of $\mathbf{M} \succeq 0$ to the vector $(\mathbf{x}, t\mathbf{y})$ , and choose the scalar $t$ well.

Solution.

(a) Write $p = \mathbf{x}^{*}\mathbf{A}\mathbf{x} \ge 0$ , $q = \mathbf{y}^{*}\mathbf{C}\mathbf{y} \ge 0$ and $z = \mathbf{x}^{*}\mathbf{B}\mathbf{y}$ . For a scalar $t \in F$ , block multiplication (Theorem 8.1.1) gives, for $\mathbf{v} = (\mathbf{x}, t\mathbf{y})$ ,
$\mathbf{v}^{*}\mathbf{M}\mathbf{v} = p + \overline{t}\,\overline{z} + tz + \lvert t\rvert^2 q = p + 2\operatorname{Re}(tz) + \lvert t\rvert^2 q \ge 0 ,$

where the middle step uses $\overline{t}\,\overline{z} = \overline{tz}$ and $w + \conj w = 2\operatorname{Re}(w)$ . Now take $t = r\omega$ with $r \ge 0$ real and $\omega$ a scalar of modulus $1$ chosen so that $\omega z = -\lvert z\rvert$ (over $\mathbb{R}$ , $\omega = \pm1$ ). Then

$p - 2r\lvert z\rvert + r^2 q \ge 0 \qquad\text{for every } r \ge 0 . \tag{$\ast$}$

If $q = 0$ , then $(\ast)$ says $p \ge 2r\lvert z\rvert$ for all $r \ge 0$ , which forces $\lvert z\rvert = 0$ , and the claim reads $0 \le 0$ . If $q > 0$ , take $r = \lvert z\rvert/q \ge 0$ in $(\ast)$ :

$p - \frac{2\lvert z\rvert^2}{q} + \frac{\lvert z\rvert^2}{q} = p - \frac{\lvert z\rvert^2}{q} \ge 0 ,$

so $\lvert z\rvert^2 \le pq$ , as claimed.
(b) Take $k = l = n$ and $\mathbf{A} = \mathbf{B} = \mathbf{C} = \mathbf{I}_n$ , so that $\mathbf{M} = \begin{psmallmatrix} \mathbf{I}_n & \mathbf{I}_n \\ \mathbf{I}_n & \mathbf{I}_n\end{psmallmatrix}$ . This $\mathbf{M}$ is positive semidefinite, since $\mathbf{M} = \mathbf{W}^{*}\mathbf{W}$ for $\mathbf{W} = \begin{psmallmatrix} \mathbf{I}_n & \mathbf{I}_n \\ 0 & 0\end{psmallmatrix}$ (Theorem 13.1.4 (c)). Part (a) then reads $\lvert\mathbf{x}^{*}\mathbf{y}\rvert^2 \le \left\| \mathbf{x} \right\|^2\left\| \mathbf{y} \right\|^2$ , and $\mathbf{x}^{*}\mathbf{y} = \langle \mathbf{y}, \mathbf{x} \rangle$ by the definition of the standard inner product. This is Theorem 11.1.5 for $F^n$ .

Exercise (C3: How large can a determinant be?)

(a) Let $\mathbf{B} \in M_n(F)$ have every entry of modulus at most $1$ . Prove that $\lvert\det \mathbf{B}\rvert \le n^{n/2}$ .
(b) Show that the bound is attained for $n = 1$ , $n = 2$ and $n = 4$ .
(c) Let $\mathbf{B} \in M_3(\mathbb{R})$ have every entry equal to $1$ or $-1$ . Prove that $\det \mathbf{B}$ is a multiple of $4$ , and deduce that $\lvert\det \mathbf{B}\rvert \le 4$ . Hence the bound of (a) is not attained for $n = 3$ .

Hint for (c): normalize the first row and the first column, then subtract the first column from the other two.

Solution.

(a) Each column $\mathbf{b}_j$ has $n$ entries of modulus $\le 1$ , so $\left\| \mathbf{b}_j \right\|^2 = \sum_i\lvert b_{ij}\rvert^2 \le n$ and $\left\| \mathbf{b}_j \right\| \le \sqrt n$ . By Theorem 13.6.4 (b), $\lvert\det \mathbf{B}\rvert \le (\sqrt n)^n = n^{n/2}$ .
(b) For $n = 1$ , $\mathbf{B} = (1)$ gives $1 = 1^{1/2}$ . For $n = 2$ , $\mathbf{B} = \begin{psmallmatrix} 1 & 1 \\ 1 & -1\end{psmallmatrix}$ has $\lvert\det \mathbf{B}\rvert = 2 = 2^{2/2}$ . For $n = 4$ , the matrix $\mathbf{H}$ of Exercise (B3: Hadamard bounds) (b) has $\lvert\det \mathbf{H}\rvert = 16 = 4^{4/2}$ . In each case all entries have modulus $1$ and the columns are orthogonal, which is exactly what is needed for equality both in $\left\| \mathbf{b}_j \right\| \le \sqrt n$ and in Theorem 13.6.4 (b).
(c) Multiplying a row or a column by $-1$ multiplies $\det \mathbf{B}$ by $-1$ (Theorem 7.5.1 (b) and (d)) and keeps all entries $\pm 1$ , so we may assume that the first row and the first column both consist of $1$ s: first scale the three columns to make the first row $(1, 1, 1)$ , then scale rows $2$ and $3$ to make the first column $(1, 1, 1)$ , which leaves the first row alone. Subtracting column $1$ from columns $2$ and $3$ leaves the determinant unchanged (Theorem 7.5.1 (c) and (d)) and gives a matrix whose first row is $(1, 0, 0)$ and whose remaining entries are $c_{ij} = b_{ij} - 1$ for $i, j \in \{2, 3\}$ ; each lies in $\{0, -2\}$ , since $b_{ij} \in \{1, -1\}$ . Expanding along the first row (Theorem 7.6.1),

$\det \mathbf{B} = c_{22}c_{33} - c_{23}c_{32}$

with every $c_{ij} \in \{0, -2\}$ . Each product lies in $\{0, 4\}$ , so $\det \mathbf{B} \in \{-4, 0, 4\}$ and in particular $\lvert\det \mathbf{B}\rvert \le 4$ . Since $3^{3/2} = 3\sqrt3 \approx 5.196 > 4$ , the bound of (a) is not attained. The value $4$ does occur, for instance for $\begin{psmallmatrix} 1 & 1 & 1 \\ 1 & -1 & 1 \\ 1 & 1 & -1\end{psmallmatrix}$ .