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$ Commented 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$ Commented 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$ Commented Mar 11, 2018 at 18:20

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.