The largest entry of a positive semidefinite matrix $A$ always lies on the diagonal, but that doesn't mean every diagonal entry of $A$ is the largest element among its row/column. E.g. $$A=\pmatrix{5&2\\ 2&1}$$ is positive semidefinite, but $1$ is not the largest entry on the its row/column.

However, if $A$ is both positive semidefinite and doubly stochastic, is it true that each diagonal element is the largest entry on its respective row?


This is false. Here is a counterexample.

$$A =\begin{bmatrix}0.37 & 0.23 & 0.40\\0.23&0.66&0.11\\0.40&0.11&0.49\end{bmatrix}$$

Eigenvalues of $A$ are $0.007611410717521, 0.512388589282479, 1.000000000000000$ so it is positive semidefinite.

Here is the matrix in MATLAB notation, for ease of verifying the eigenvalues.

A=[0.37 0.23 0.40;0.23 0.66 0.11;0.40 0.11 0.49]

How did I find a counterexample? It was easy to do by using YALMIP to solve a non-convex semidefinite optimization problem to find a matrix satisfying all the properties to be a counterexample. Then I rounded to nicer numbers in a way which preserved it as a counterexample. Clearly there is no counterexample for 2 by 2 matrices, so 3 by 3 is the lowest possible dimensionality for which there is a counterexample.

  • $\begingroup$ Thanks, especially for the remarks about how you discovered it. What did you use as your objective function? $\endgroup$ – user3281410 Mar 11 '18 at 18:07
  • 1
    $\begingroup$ I didn't use an objective function. I ran it as a feasibility problem, specifying only constraints (essentially the same thing as making the objective function a constant, such as 0). n=3;A=sdpvar(n,n);optimize([sum(A,1)==1,0<=A(:)<=1,A>=0,max(A(:,1)) >= A(1,1)+1e-2]) . If it had been a close call, I would have had to be more careful on tolerances, but there was room to spare here. I then cleaned up the solution. $\endgroup$ – Mark L. Stone Mar 11 '18 at 18:12
  • 1
    $\begingroup$ I haven't checked carefully, but it might be that up to, but not more than, $n - 2$ rows of n by n doubly stochastic positive semidefinite matrix can have largest element not on diagonal. I'll let you look into that. $\endgroup$ – Mark L. Stone Mar 11 '18 at 18:20

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.