Determinant of arbitrary sum of positive semidefinite hermitian matrices

Question

Suppose that $A_i$, $i=1,\ldots,m$ are positive semidefinite Hermitian $n\times n$ matrices, with $a_i^{(j)}$ being the $j$-th eigenvalue of $A_i$. Let $A_0=I$.

QUESTION. Can we extend the result of M. Fiedler for $m=2$ (Bounds for the Determinant of the Sum of Hermitian Matrices, Proc. Amer. Math. Soc. 30 (1971) 27-31) to establish the bound $$ \det \sum_{i=0}^mA_i \le\max_{\sigma_0,\dots,\sigma_m\in S_n}\prod_{j=1}^n\sum_{i=0}^m a_i^{(\sigma_i(j))}\,\,? $$ ($S_n$ is the group of permutations of $n$ elements)

Edit: it should be noted $A_0$ is superfluous, since the statement would hold for singular matrices too. I didn't want the answers below to have to consider the additional case.

Answer 1

The previous answer was incorrect due to an incorrect use of majorization. I decided to replace it by a correct version below for completeness, and to remedy the embarrassing error (though now the answer becomes essentially equivalent to the OPs own answer, so feel free to ignore!). $\newcommand{\da}{\downarrow} \newcommand{\ua}{\uparrow} \newcommand{\nlsum}{\sum\nolimits}$

---

Recall that for Hermitian matrices $A$ and $B$, Lidskii's eigenvalue majorization inequality implies that there exist doubly stochastic matrices $D_1$ and $D_2$ such that $\lambda(A+B)=D_1\lambda(A)+D_2\lambda(B)$.

Introduce the shorthand $a_{m+1}=\lambda(A_1+\cdots+A_m)$, and $a_j = \lambda(A_j)$ for $1\le j\le m$. Then, applying Lidskii's result repeatedly and noting that doubly stochastic matrices are closed under multiplication, it follows that there exist doubly stochastic matrices $D_1,\ldots,D_m$ such that \begin{equation*} a_{m+1} = D_1a_1+\cdots+D_ma_m. \end{equation*}

We wish to upper bound $\det(A_{m+1}):=\prod_i a_{m+1,i}$. Consider the function \begin{equation*} f(D_1,\ldots,D_m) := \prod_i (D_1a_1+\cdots+D_ma_m)_i. % \le \left(\frac{\nlsum_i e_i^T(D_1a_1+\cdots+D_ma_m)}{n} \right)^n. \end{equation*}

We now show that $f$ is maximized over permutation matrices. First, we make the change of variables $(D_l)_{ij}=D_{l,ij} = e^{u_{l,ij}}$. Moreover, we relax the doubly-stochastic constraints on each $D_l$ to \begin{equation*} \Omega_n := \left\lbrace(U_1,\ldots,U_m) \in \mathbb{R}^{m\times n \times n}\mid \nlsum_i e^{u_{l,ij}} \le 1,\ \forall i,\quad \nlsum_j e^{u_{l,ij}} \le 1,\forall j, \quad\text{for}\ 1 \le l \le m\right\rbrace. \end{equation*} Then, we consider the optimization problem \begin{equation*} \sup_{(U_1,\ldots,U_m) \in \Omega_n}\quad g(U_1,\ldots,U_m) := \nlsum_{i=1}^n \log\left(\nlsum_{lj} a_{l,j}e^{u_{l,ij}}\right). \end{equation*} Since all the matrices $A_1,\ldots,A_m$ are positive definite, each $a_{l,j}\ge0$. Thus, $g$ is a convex function of the $U_i$. Hence its supremum will be at an extreme point of $\Omega_n$. These points correspond to the permutation matrices. Thus, mapping back to the $D_i$ space, we observe that $f$ will be maximized at permutation matrices.

This reasoning immediately yields the desired inequality: \begin{equation*} \det(A_{m+1})=\det(A_1+\cdots+A_m) \le \sup_{\sigma_1,\ldots,\sigma_m \in S_n}\prod_{i=1}^n\left(\nlsum_{l=1}^m a_{l,\sigma_l(i)} \right). \end{equation*}

Answer 2

Thank you to @FedorPetrov for helping me complete the proof.

Let $S=\sum_{i=0}^mA_i$, positive definite by its first term. Let its positive eigenvalues be $\lambda_i$ in any order, with corresponding eigenvectors $\textbf{v}_i$.

Let $\textbf{a}_i^{(j)}$ be the eigenvector of $A_i$ corresponding to the eigenvalue $a_i^{(j)}$. Since $\textbf{v}_k^\top\textbf{v}_k=1$, we have for any $k$:

$$ \textbf{v}_k^\top S\textbf{v}_k=\sum_{i=1}^n\sum_{j=1}^na_i^{(j)}\langle \textbf{a}_i^{(j)},\textbf{v}_k\rangle^2 $$

From now on, iterations will implicitly on $i\in[m]$ and $j,k\in[n]$.

We continue: $$ \det S = \prod_k\lambda_k=\prod_k\sum_{ij}a_i^{(j)}\langle \textbf{a}_i^{(j)},\textbf{v}_k\rangle^2 $$

Next for a fixed ${i_*}$, let us consider the following function on $n^2$ parameters $\{b_{jk}\}_{jk}$, represented as the matrix $B$: $$ f_{i_*} (B)=\prod_k\left(c_k+\sum_ja_{i_*}^{(j)}b_{jk}\right) $$ For some constants $c_k,a_{i_*}^{(j)}$ positive. To prove the conjecture it would suffice to show the lemma that: $$ f_{i_*}(B)\le\max_{\sigma\in S_n}f_{i_*}(P_\sigma) $$ Where again $S_n$ is the permutation group of $[n]$ and $P_\sigma$ is the corresponding permutation matrix. Applying the above bound $m$ times would actually yield something better than the conjecture (since our iterative bound is at most the global one).

Since $\left\{\textbf{v}_k\right\}_k$ form a full basis, expressing $\textbf{a}_i^{(j)}$ in those coordinates implies for any $j$: $$\sum_k\langle \textbf{a}_{i_*}^{(j)},\textbf{v}_k\rangle ^2=1$$

Similarly for the basis $\left\{\textbf{a}_{i_*}^{(j)}\right\}_j$ and any $k$: $$\sum_j\langle \textbf{a}_{i_*}^{(j)},\textbf{v}_k\rangle ^2=1$$

The above two statements imply $B$ with $b_{jk}=\langle\textbf{a}_{i_*}^{(j)},\textbf{v}_k\rangle ^2$ is bistochastic. By the Birkhoff–von Neumann Theorem, the set of bistochastic matrices is the convex hull of $C=\{P_\sigma|\sigma\in S_n\}$, where $P_\sigma$ is the permutation matrix of $\sigma$.

Then, since $f_{i_*}$ is convex (at least on $[0,1]^{n\times n}$, a superset of the domain of bistochastic matrices), the maximum value must be on $\partial\,\text{hull}(C)$. Since the face of a simplex is just a lower-dimensional one, we repeat this logic, eventually finding that the maximum must be located at one of the boundary points, some element in $C$.