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$
  • $\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$ – martin cripps May 19 '17 at 11:40
  • $\begingroup$ @martincripps: $A$ must be symmetric positive definite and such that $\mathrm{tr}(A)=1$. $\endgroup$ – Ludwig May 19 '17 at 11:54
  • $\begingroup$ Maybe edit the question then to make this clear? $\endgroup$ – martin cripps May 19 '17 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 May 19 '17 at 13:24
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.

| cite | improve this answer | |
$\endgroup$
  • $\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 May 20 '17 at 5:55
  • 1
    $\begingroup$ @Ludwig 1) Correct 2) As written, it does not. Are you interested in that case too? $\endgroup$ – fedja May 20 '17 at 10:13

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.