9
$\begingroup$

Let $D\in\mathbb{R}^{n\times n}$ be a diagonal positive definite matrix s.t. $D\leq I$ ($I$ denotes the $n$-dim. identity matrix) and let $\alpha$ be a strictly positive real number. Consider the optimization problem over the set of positive semidefinite matrices with trace less or equal than one $$ \max_{A\in\mathbb{R}^{n\times n}\,:\,A\geq 0,\, \mathrm{tr}(A)\leq 1}\frac{\det(A+\alpha I)}{\det(AD + \alpha I)}. $$

My question: Is the optimal matrix $$ A^\star:=\arg\max_{A\in\mathbb{R}^{n\times n}\,:\, A\geq 0,\,\mathrm{tr}(A)\leq 1}\frac{\det(A+\alpha I)}{\det(AD + \alpha I)} $$ diagonal?

$\endgroup$
4
  • $\begingroup$ Suppose $A$ has only two non-zero elements, $a_{12}$ and $a_{21}$, satisfying $\alpha=a_{12}d_1$ and $\alpha=a_{21}d_2$ (where $D$ has $(d_1,d_2,\dots,d_n)$ on the diagonal), then isn't the bottom of this equal to zero? $\endgroup$ Commented May 19, 2017 at 11:40
  • $\begingroup$ @martincripps: $A$ must be symmetric positive definite and such that $\mathrm{tr}(A)=1$. $\endgroup$
    – Ludwig
    Commented May 19, 2017 at 11:54
  • $\begingroup$ Maybe edit the question then to make this clear? $\endgroup$ Commented May 19, 2017 at 12:38
  • $\begingroup$ Yes. Sorry, but in my previous answer I meant $A$'s positive semidefinite with $\mathrm{tr}(A)\leq 1$. $\endgroup$
    – Ludwig
    Commented May 19, 2017 at 13:24

1 Answer 1

6
$\begingroup$

Yes, of course (provided that you mean that the maximum is attained on a diagonal matrix, not that every matrix on which it is attained is diagonal).

First notice that it is a bit more convenient to have the denominator in the form $\det(A+Q)$ where $Q$ is $\alpha D^{-1}$. Now $A=R^*BR$ where $B$ is diagonal and $R$ is orthogonal. Notice that the numerator does not depend on $R$ or on the order of the diagonal elements in $B$. Using just all permutations $R$, we see that WLOG we may assume that the diagonal elements of $B$ and $Q$ are arranged in the same order. So, WLOG, $B_{11}\ge B_{22}\ge\dots$ and the same for $Q$. We want to show that in this case $\det(R^*BR+Q)$ over all orthogonal $R$ is minimized at $R=I$. Recall that for a positive definite $X$, $(\det X)^{\frac 1n}=\frac 1n\inf \operatorname{Tr}YX$ where $Y$ runs over all positive definite matrices of determinant $1$. Now fix the eigenvalues of $Y$ (say $y_1\le y_2\le\dots\le y_n$) (note that I arranged them in the opposite order comparing to the order of $B_{ii}$ and $Q_{ii}$. Note also that $\operatorname{Tr}YR^*BR=\operatorname{Tr}RYR^*B$ and $RYR^*$ has the same eigenvalues as $Y$. At last, note that if $Y=\operatorname{diag }(y_1,\dots,y_n)$ and $R=I$, then $\operatorname{Tr}RYR^*B=\sum_i y_iB_{ii}$ and similarly for $Q$. Thus it will suffice to show that if $Y$ and $X$ are positive semi-definite with the eigenvalues $y_1\le y_2\le\dots\le y_n$ and $x_1\ge x_2\ge\dots\ge x_n$, then $\operatorname{Tr}YX\ge\sum_i x_iy_i$.

That, without any doubt, can be found in textbooks, but let me provide a proof just in case. Using the spectral decomposition $X=x_nP_n+(x_{n-1}-x_{n})P_{n-1}+\dots+(x_1-x_2)P_1$, we see that it is enough to prove the desired inequality for the case when $X$ is an orthogonal projection to a $k$-dimensional space. Let $e_i$ be the eigenvector of $Y$ corresponding to the eigenvalue $y_i$. There is a unit vector $u_k$ in $H$ orthogonal to $e_1,\dots,e_{k-1}$. Then $\langle YPu_k,u_k\rangle\ge y_k$. Next, there exists a unit vector $u_{k-1}\in H$ orthogonal to $e_1,\dots,e_{k-2};u_k$. Thus, $\langle YPu_{k-1},u_{k-1}\rangle\ge y_{k-1}$, and so on. This gives an orthonormal basis $u_1,\dots,u_k$ in $H$ with $\sum_{i=1}^k\langle YPu_i,u_i\rangle\ge \sum_{i=1}^k y_i$. Complementing it by an orthonormal basis of $H^\perp$ (which will be killed by $P$ anyway), we see that the LHS equals $\operatorname{Tr}YP$ and we are done.

$\endgroup$
2
  • $\begingroup$ Nice proof! Two further questions: 1. From your argument, It seems to me that the assumption $D\le I$ is not needed, am I right? 2. In case we replace the numerator by $\det(\Delta A+\alpha I)$, where $\Delta$ is diagonal, positive definite and in general $\Delta\neq D$, does your argument still apply? $\endgroup$
    – Ludwig
    Commented May 20, 2017 at 5:55
  • 1
    $\begingroup$ @Ludwig 1) Correct 2) As written, it does not. Are you interested in that case too? $\endgroup$
    – fedja
    Commented May 20, 2017 at 10:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .