10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If you assume PSD, do you need the permutations on the RHS? The way you posed the problem (with permutations), you may drop the PSD condition. $\endgroup$ – T. Amdeberhan Oct 24 '16 at 1:17
  • $\begingroup$ This product does not depend on $\sigma$. Maybe, you need different permutations for different $i$? $\endgroup$ – Fedor Petrov Oct 24 '16 at 6:26
  • $\begingroup$ @FedorPetrov That's what I had before, it seems to have been edited away. How can I revert? $\endgroup$ – VF1 Oct 24 '16 at 11:49
  • $\begingroup$ @VF1 I do not know how to revert, now I edited once again. Hopefully it becomes ok. $\endgroup$ – Fedor Petrov Oct 24 '16 at 11:53
  • $\begingroup$ @FedorPetrov Yes, this is what I had before. Thank you. Though of course the permutation $\sigma_0$ does not matter, nor wlog $\sigma_1$. $\endgroup$ – VF1 Oct 24 '16 at 11:57
8
$\begingroup$

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*}

$\endgroup$
  • $\begingroup$ Amazing, thanks. The constructive proof here is very helpful (and your tighter bound is much easier to compute, too!). Does your proof, along with mine, imply a theorem about combinatoric product optimization (that the maximum is reached in one of the $m$ arrangements you supplied)? $\endgroup$ – VF1 Oct 25 '16 at 20:58
  • $\begingroup$ Not sure if the maximum is reached. Consider all diagonal matrices. Unless they are already permuted in the right way we may not get equality. However, the bound above does tell us one set of sufficient permutations to apply to the diagonal matrices to obtain equality and to saturate the inequality. $\endgroup$ – Suvrit Oct 25 '16 at 22:00
  • 2
    $\begingroup$ @Suvrit there may be a problem in the majorization below the Lemma. $x^\downarrow \succ y^\downarrow$ does not imply $x^\downarrow+z^\uparrow \succ y^\downarrow+z^\uparrow$. Eg. $x=(3,2,1)$, $y=(2,2,2)$, $z=(1,2,3)$. $\endgroup$ – M. Lin Oct 26 '16 at 7:44
  • $\begingroup$ @M.Lin You are right! I reveresed the argument when going through it. I think by introducing a suitable permutation on the involved vectors of eigenvalues one can recover the inductive step, but that will end up looking like VF's original proof. I will have to delete this answer and search for a fix! $\endgroup$ – Suvrit Oct 26 '16 at 13:52
  • 1
    $\begingroup$ @Suvrit I believe that the end of your proof still requires the additional care does; namely $\partial \Sigma_n$ is not merely composed of the permutation points. However, at any lower-dimensional boundary the optimization function looks the same so we can apply your logic recursively. If we were to be very formal about this it would be tiresome to check this property; is there any way out? $\endgroup$ – VF1 Oct 30 '16 at 22:00
4
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Any bistochastic matrix is indeed a convex combination of permutation matrices. It is Birkhoff theorem. $\endgroup$ – Fedor Petrov Oct 24 '16 at 16:42
  • $\begingroup$ @FedorPetrov Ah, excellent, thank you again. I think with your modification, this brings the proof nearer to completion. Unfortunately, it is only $B^2$ that is bistochastic, not $B$. I think there may be a workaround. $\endgroup$ – VF1 Oct 24 '16 at 17:06
  • $\begingroup$ @FedorPetrov Ah, I made a typo - you are correct, this completes the proof! $\endgroup$ – VF1 Oct 25 '16 at 0:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.