$A \in \mathbb{R}^{m \times n}$ is an arbitrary data matrix. Moreover, $w \in \mathbb{R}^m$ is a data vector which is a probability vector, i.e., $w\succeq 0, \sum_{i=1}^m w_i = 1$.

I have a symmetric matrix variable $V \in \mathbb{S}^{m \times m}$ and I am solving:

\begin{align*} \begin{array}{cll} \max \limits_{V \in \mathbb{S}^{n\times n}} & \mathrm{tr}(A^\top V A) & \\ \mathrm{s.t.}& \sum \limits_{j=1}^m V_{ij} = \sum\limits_{j=1}^m V_{ji} = w_i, & i=1,\ldots,m \\[0.2cm] & \sum\limits_{i=1}^m \sum\limits_{j=1}^m V_{ij} =1 &\\ & V_{i,j} \geq 0, & i=1,\ldots,m, j=1,\ldots,m. \end{array} \end{align*} So we can see that the $i$-th row and column of $V$ should sum to $w_i$ from the first constraint. The second constraint also implies that the elements of $V$ should sum to $1$. Last constraint says the elements of $V_{i,j}$ are nonnegative.

The thing is, in my various numerical experiments, I always have $V = \mathrm{Diag}(w)$, i.e., $V$ is a diagonal matrix where $i$-th diagonal element is $w_i$. Is this also observable from this maximization problem above (without any assumptions on $A$)?

The MATLAB code to observe this with various data (thanks to the improvement of Mark L. Stone) is:

n = 5;
m = 5;
A = rand(m,n)2; $generate whatever you like
w = [0.1;0.3;0.5;0.05; 0.05]; %sums to 1
V = sdpvar(m); %symmetric
Objective = trace(A'*V*A);
Constraints = [V(:) >= 0, sum(V(:)) == 1];
Constraints = [Constraints, sum(V,2)==w]; 
soltn = optimize(Constraints, -Objective, sdpsettings('solver', 'cplex'))
V = value(V)
w = value(w)

My attempt:

\begin{align} \mathrm{tr}(A^\top V A) = \mathrm{tr}( (AA^\top) V) = \sum_{i=1}^m \sum_{j=1}^m (AA^\top)_{i,j}V_{i,j} \end{align}

and if I can show that the coefficient of $V_{ii}$ which is $(AA^\top)_{ii}$ is larger than $(AA^\top)_{ij}$ for any $j$ then I guess we are done.

Edit: I proved it. It is a bit tedious, but I will type it soon.

  • $\begingroup$ I was within a couple of seconds of posting a counterexample, which has some negative elements in V. $\endgroup$ Apr 7, 2020 at 19:52
  • $\begingroup$ So sorry Mark! I hate it when I steal someone's time, and apparently I just did... This problem kills me though, I checked many example and these are all optimized for $V = diag(w)$. Example: n = 5; m = 5; A = rand(m,n); w = [0.1;0.3;0.5;0.05; 0.05]; %sums to 1 V = sdpvar(m); Objective = trace(A'*V*A); Constraints = [V(:) >= 0, sum(V(:)) == 1]; for i=1:m Constraints = [Constraints, sum(V(:,i))==w(i)]; end soltn = optimize(Constraints, -Objective, sdpsettings('solver', 'cplex')) V = value(V) w = value(w) $\endgroup$ Apr 7, 2020 at 19:54
  • $\begingroup$ A little tip, instead of for loop, you can just do sum(V,2)==w,sum(V,1)==w'. And of course, sum(V(:)) == 1 is redundant (which the LP presolve should recognize). $\endgroup$ Apr 7, 2020 at 20:06
  • $\begingroup$ @MarkL.Stone Very nice, yes you are right. also since $V$ is symmetric only $ \operatorname{sum}(V,2)==w$ is enough. Do you think what I want to prove is easy? $\endgroup$ Apr 7, 2020 at 20:12
  • 1
    $\begingroup$ Good, you passed the pop quiz I embedded in the previous comment. $\endgroup$ Apr 7, 2020 at 21:07

1 Answer 1


Consider a feasible matrix $V$ for which $V \neq \text{Diag}(w)$. Then there exist indices $i \neq j$ such that $V_{ij} = V_{ji} > 0$.

Now construct a new matrix $W$ which is equal to $V$, except for the following four elements:

  • $W_{ij} = W_{ji} = 0$,
  • $W_{ii} = V_{ii} + V_{ij}$,
  • $W_{jj} = V_{jj} + V_{ij}$.

It is straightforward to verify that $W$ is feasible.

By changing $V$ to $W$, the change in objective value is $$-2 (AA^\top)_{ij} + (AA^\top)_{ii} + (AA^\top)_{jj}.$$ Because $AA^\top$ is positive semi-definite, this value is non-negative, and the solution $W$ is not worse than $V$. By repeating this argument, it follows that $\text{Diag}(w)$ is optimal.

  • 1
    $\begingroup$ Really good answer! Thanks for this. I did the same, but I had to expand the matrices in open form. This is shorter, nicer. $\endgroup$ Apr 8, 2020 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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