Trace, Determinant, and Matrix Inequalities

Let $\mathbf{A} \in \mathbb{C}^{m \times n}$ and $\mathbf{B} \in \mathbb{C}^{n \times m}$. Then $\mathbf{A}\mathbf{B}$ is $m \times m$ and $\mathbf{B}\mathbf{A}$ is $n \times n$. We compute each trace using the definition: $$\operatorname{tr}(\mathbf{A}\mathbf{B}) = \sum_{i=1}^{m} (\mathbf{A}\mathbf{B})_{ii} = \sum_{i=1}^{m} \sum_{k=1}^{n} a_{ik} b_{ki}.$$ $$\operatorname{tr}(\mathbf{B}\mathbf{A}) = \sum_{k=1}^{n} (\mathbf{B}\mathbf{A})_{kk} = \sum_{k=1}^{n} \sum_{i=1}^{m} b_{ki} a_{ik}.$$ Both double sums run over the same set of index pairs $(i, k) \in \{1, \ldots, m\} \times \{1, \ldots, n\}$ and involve the same summands $a_{ik} b_{ki}$. By commutativity of scalar multiplication and the fact that the order of a finite sum is immaterial, the two expressions are equal: $$\operatorname{tr}(\mathbf{A}\mathbf{B}) = \operatorname{tr}(\mathbf{B}\mathbf{A}).$$

For $k \geq 3$ matrices, define $\mathbf{M} = \mathbf{A}_1$ and $\mathbf{N} = \mathbf{A}_2 \mathbf{A}_3 \cdots \mathbf{A}_k$. Then $\mathbf{M} \in \mathbb{C}^{n_1 \times n_2}$ and $\mathbf{N} \in \mathbb{C}^{n_2 \times n_1}$. By the two-matrix case: $$\operatorname{tr}(\mathbf{A}_1 \mathbf{A}_2 \cdots \mathbf{A}_k) = \operatorname{tr}(\mathbf{M}\mathbf{N}) = \operatorname{tr}(\mathbf{N}\mathbf{M}) = \operatorname{tr}(\mathbf{A}_2 \mathbf{A}_3 \cdots \mathbf{A}_k \mathbf{A}_1).$$ Repeating this argument $k - 1$ times produces all $k$ cyclic permutations. $\blacksquare$

Since $\mathbf{A} \succ 0$, it admits a unique Cholesky factorization $\mathbf{A} = \mathbf{L}\mathbf{L}^H$, where $\mathbf{L} = [l_{ij}]$ is lower triangular with strictly positive diagonal entries $l_{ii} > 0$. By the multiplicativity of determinants: $$\det(\mathbf{A}) = \det(\mathbf{L})\det(\mathbf{L}^H) = |\det(\mathbf{L})|^2 = \left(\prod_{i=1}^{n} l_{ii}\right)^2 = \prod_{i=1}^{n} l_{ii}^2.$$

The $(i,i)$ entry of $\mathbf{A} = \mathbf{L}\mathbf{L}^H$ is $$a_{ii} = \sum_{k=1}^{i} |l_{ik}|^2 = |l_{i1}|^2 + |l_{i2}|^2 + \cdots + |l_{i,i-1}|^2 + l_{ii}^2.$$ (Here $l_{ii}$ is real and positive by the Cholesky construction.)

Since all terms in the sum are nonneg-ative and $l_{ii}^2$ is one of them, we obtain $$a_{ii} \geq l_{ii}^2,$$ with equality if and only if $l_{ik} = 0$ for all $k < i$, i.e., if and only if the $i$-th row of $\mathbf{L}$ has only the diagonal entry nonzero.

Taking the product over all $i$: $$\prod_{i=1}^{n} a_{ii} \geq \prod_{i=1}^{n} l_{ii}^2 = \det(\mathbf{A}).$$ This proves $\det(\mathbf{A}) \leq \prod_{i=1}^{n} a_{ii}$.

Equality holds if and only if $a_{ii} = l_{ii}^2$ for every $i$, which by Step 2 occurs if and only if $l_{ik} = 0$ for all $k < i$ and all $i$. This means $\mathbf{L}$ is diagonal, so $\mathbf{A} = \mathbf{L}\mathbf{L}^H$ is also diagonal.

Conversely, if $\mathbf{A}$ is diagonal (with positive diagonal entries, since $\mathbf{A} \succ 0$), then $\det(\mathbf{A}) = \prod_{i=1}^n a_{ii}$ trivially. $\blacksquare$

A function on $\mathbb{S}_{++}^n$ is concave if and only if it is concave along every line segment in $\mathbb{S}_{++}^n$. Fix $\mathbf{A} \succ 0$ and a Hermitian matrix $\mathbf{V}$, and define $$g(t) = \log\det(\mathbf{A} + t\mathbf{V})$$ for all $t$ such that $\mathbf{A} + t\mathbf{V} \succ 0$. It suffices to show that $g$ is concave in $t$.

Write $$\mathbf{A} + t\mathbf{V} = \mathbf{A}^{1/2}\bigl(\mathbf{I} + t\mathbf{A}^{-1/2}\mathbf{V}\mathbf{A}^{-1/2}\bigr)\mathbf{A}^{1/2}.$$ Taking the log-det: $$g(t) = \log\det(\mathbf{A}) + \log\det\bigl(\mathbf{I} + t\mathbf{C}\bigr),$$ where $\mathbf{C} = \mathbf{A}^{-1/2}\mathbf{V}\mathbf{A}^{-1/2}$ is Hermitian. Since $\log\det(\mathbf{A})$ is a constant in $t$, it suffices to show that $h(t) = \log\det(\mathbf{I} + t\mathbf{C})$ is concave in $t$.

Since $\mathbf{C}$ is Hermitian, by the spectral theorem there exists a unitary $\mathbf{Q}$ such that $\mathbf{C} = \mathbf{Q}\operatorname{diag}(\mu_1, \ldots, \mu_n)\mathbf{Q}^H$. Then $$\mathbf{I} + t\mathbf{C} = \mathbf{Q}\operatorname{diag}(1 + t\mu_1, \ldots, 1 + t\mu_n)\mathbf{Q}^H,$$ and $$h(t) = \log\det(\mathbf{I} + t\mathbf{C}) = \sum_{i=1}^{n} \log(1 + t\mu_i).$$ (This is valid for $t$ in the range where all $1 + t\mu_i > 0$.)

Each function $\phi_i(t) = \log(1 + t\mu_i)$ has second derivative $$\phi_i''(t) = -\frac{\mu_i^2}{(1 + t\mu_i)^2} \leq 0.$$ Since $\phi_i''(t) \leq 0$ for all $t$ in the domain, each $\phi_i$ is concave.

A sum of concave functions is concave. Therefore $$h(t) = \sum_{i=1}^{n} \log(1 + t\mu_i)$$ is concave in $t$, which implies $g(t) = \log\det(\mathbf{A}) + h(t)$ is concave in $t$. Since this holds for every line in $\mathbb{S}_{++}^n$, $f(\mathbf{X}) = \log\det(\mathbf{X})$ is concave on $\mathbb{S}_{++}^n$. $\blacksquare$

Since $\mathbf{M} \succ 0$, the diagonal block $\mathbf{A}$ is itself positive definite (as a principal submatrix of a positive definite matrix). The Schur complement of $\mathbf{A}$ in $\mathbf{M}$ is $$\mathbf{S} = \mathbf{D} - \mathbf{B}^H \mathbf{A}^{-1} \mathbf{B}.$$

The block LDU factorization of $\mathbf{M}$ gives $$\mathbf{M} = \begin{pmatrix} \mathbf{I} & \mathbf{0} \\ \mathbf{B}^H \mathbf{A}^{-1} & \mathbf{I} \end{pmatrix} \begin{pmatrix} \mathbf{A} & \mathbf{0} \\ \mathbf{0} & \mathbf{S} \end{pmatrix} \begin{pmatrix} \mathbf{I} & \mathbf{A}^{-1}\mathbf{B} \\ \mathbf{0} & \mathbf{I} \end{pmatrix}.$$

We verify this by direct multiplication. The $(1,1)$ block: $\mathbf{I} \cdot \mathbf{A} \cdot \mathbf{I} + \mathbf{I} \cdot \mathbf{A} \cdot \mathbf{A}^{-1}\mathbf{B} \cdot \mathbf{0}^T + \cdots = \mathbf{A}$. The $(1,2)$ block: $\mathbf{A} \cdot \mathbf{A}^{-1}\mathbf{B} = \mathbf{B}$. The $(2,1)$ block: $\mathbf{B}^H \mathbf{A}^{-1} \cdot \mathbf{A} = \mathbf{B}^H$. The $(2,2)$ block: $\mathbf{B}^H \mathbf{A}^{-1} \mathbf{A} \mathbf{A}^{-1}\mathbf{B} + \mathbf{S} = \mathbf{B}^H \mathbf{A}^{-1}\mathbf{B} + \mathbf{D} - \mathbf{B}^H\mathbf{A}^{-1}\mathbf{B} = \mathbf{D}$. $\checkmark$

The two outer matrices in the LDU factorization are unit lower and upper triangular, so each has determinant $1$. Therefore: $$\det(\mathbf{M}) = \det(\mathbf{A}) \cdot \det(\mathbf{S}) = \det(\mathbf{A}) \cdot \det\bigl( \mathbf{D} - \mathbf{B}^H \mathbf{A}^{-1} \mathbf{B} \bigr).$$

Since $\mathbf{M} \succ 0$, the Schur complement $\mathbf{S} = \mathbf{D} - \mathbf{B}^H \mathbf{A}^{-1} \mathbf{B}$ is also positive definite (a standard result: $\mathbf{M} \succ 0$ if and only if $\mathbf{A} \succ 0$ and $\mathbf{S} \succ 0$).

Now, $\mathbf{A}^{-1} \succ 0$, so $\mathbf{B}^H \mathbf{A}^{-1} \mathbf{B} \succeq 0$ (it is positive semidefinite for any $\mathbf{B}$). Therefore: $$\mathbf{S} = \mathbf{D} - \mathbf{B}^H \mathbf{A}^{-1} \mathbf{B} \preceq \mathbf{D}.$$

For positive definite matrices, $\mathbf{S} \preceq \mathbf{D}$ implies $\det(\mathbf{S}) \leq \det(\mathbf{D})$. (Proof of this auxiliary fact: write $\mathbf{S} = \mathbf{D}^{1/2}(\mathbf{I} - \mathbf{D}^{-1/2}\mathbf{B}^H\mathbf{A}^{-1}\mathbf{B}\mathbf{D}^{-1/2}) \mathbf{D}^{1/2}$; the matrix in the middle has eigenvalues in $(0, 1]$, so its determinant is $\leq 1$.)

From Steps 2 and 3: $$\det(\mathbf{M}) = \det(\mathbf{A}) \det(\mathbf{S}) \leq \det(\mathbf{A}) \det(\mathbf{D}).$$

Equality holds if and only if $\det(\mathbf{S}) = \det(\mathbf{D})$, which occurs if and only if $\mathbf{B}^H \mathbf{A}^{-1} \mathbf{B} = \mathbf{0}$. Since $\mathbf{A}^{-1} \succ 0$, this holds if and only if $\mathbf{B} = \mathbf{0}$. $\blacksquare$