1
$\begingroup$

\begin{array}{ll} \text{minimize} & \mbox{tr} (\mathrm A)\\ \text{subject to} & \mathrm A - \mathrm N \succeq \mathrm O_n\end{array} where $A$ and $N$ are pd matrices, and $A$ is diagonal.

There is a related post: Minimize trace of $A$ given that $A-N$ is positive semi-definite. . However, in that case $A$ is not diagonal thus, $tr(A)=tr(N)$ is possible, while in current case not.

For $A\in \mathbb{R}^{2\times2}$, I believe $\min tr(A)=\sum n_{ij}$, however for $A\in \mathbb{R}^{3\times3}$ we have inequality $\min tr(A)\leq\sum n_{ij}$. Can you please help with analytical approach so solve it

$\endgroup$
  • $\begingroup$ $A =\lambda_{max}(N)I$ is feasible, so $n \lambda_{max}(N)$ is an obvious bound. I do not see an easy way to get a tighter bound. $\endgroup$ – LinAlg Nov 19 '18 at 14:14
  • $\begingroup$ If $N=\begin{bmatrix}3 & 1 & -1\\1 & 2 &1 \\-1 & 1 &2\end{bmatrix}>0$, then $n\lambda_{max}(N)=11.1963$. Let $A=\begin{bmatrix}4 & & \\ & 3 & \\ & &3\end{bmatrix}$, then $A-N\geq 0$ and $trace(A)=10$ $\endgroup$ – Lee Nov 20 '18 at 1:57
  • $\begingroup$ if $A=\begin{bmatrix}4 & & \\ & 3 & \\ & &2\end{bmatrix}$, then again $A-N\geq 0$ and $trace(A)=9$. I think this is minimum, but I don't have a proof $\endgroup$ – Lee Nov 20 '18 at 2:19
  • $\begingroup$ if $N$ is one of following structures $\begin{bmatrix}+& + & +\\+ & + &+ \\+ & + &+\end{bmatrix}$, $\begin{bmatrix}+& - & +\\- & + &- \\+ & - &+\end{bmatrix}$, $\begin{bmatrix}+& - &-\\- & + &+ \\- & + &+\end{bmatrix}$, $\begin{bmatrix}+& + & -\\+ & + &- \\- & - &+\end{bmatrix}$, then I believe $\min tr(A)=\sum n_{ij}$. $\endgroup$ – Lee Nov 20 '18 at 2:26
  • $\begingroup$ if $N$ is one of following structures $\begin{bmatrix}+& + & -\\+ & + &+ \\- & + &+\end{bmatrix}$, $\begin{bmatrix}+& - & +\\- & + &+ \\+ & + &+\end{bmatrix}$, $\begin{bmatrix}+& + &+\\+ & + &- \\+ & - &+\end{bmatrix}$, then I believe $\min tr(A)=\sum |n_{ij}|-4|n_{12}| $, assuming $|n_{12}|\leq |n_{13}| \leq |n_{23}|$. $\endgroup$ – Lee Nov 20 '18 at 9:12

Your Answer

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

Browse other questions tagged or ask your own question.