Is each diagonal entry of a positive semidefinite doubly stochastic matrix the largest element on its own row?

364 Views Asked by At

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?

1

There are 1 best solutions below

3
On BEST ANSWER

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.