1
$\begingroup$

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?

$\endgroup$
0

1 Answer 1

Reset to default
2
+50
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks, especially for the remarks about how you discovered it. What did you use as your objective function? $\endgroup$
    – user3281410
    Mar 11, 2018 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, 2018 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, 2018 at 18:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .