# Minimize trace of $A$ given that $A−N$ is positive semi-definite and $A$ is diagonal

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

• $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. – LinAlg Nov 19 '18 at 14:14
• 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$ – Lee Nov 20 '18 at 1:57
• 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 – Lee Nov 20 '18 at 2:19
• 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}$. – Lee Nov 20 '18 at 2:26
• 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}|$. – Lee Nov 20 '18 at 9:12