I am studying n by n doubly-stochastic entry-wise positive matrices.
I was wondering if there are any necessary and sufficient conditions for the existence of a negative eigenvalue for such a matrix.
What if I added that the matrix was also symmetric?
How about sufficient conditions?
Best Answer
If you have negative-definiteness of the symmetric matrix, then all of its eigenvalues are negative. If you can deduce, that it is negative-semidefinite then all of its eigenvalues are nonpositive.
One thing you can look at is the matrix's gershgorin circles. If there exists Gershgorin circles of appropriate size and location in the complex plane, then there might exist an eigenvalue that is negative. In particular, every eigenvalue of the matrix lies in at least one of the matrix's Gershgorin circles. Now denote your matrix $A$ as $A=(a_{ij})_{i,j\le n}$. The $i^{th}$ Gershgorin circle is defined as: $$ \Gamma_i(A) = \{z\in \mathbb{C}: |z-a_{ii}|\le r_i(A)=\sum_{j=1,j\ne i}a_{i,j}= 1-a_{ii}\} $$ Now it follows that if the $a_{ii}$ are such that $a_{ii} > r_i(A)$, $(a_{ii}>\frac{1}{2})$, for all $i$ then there is no chance that an eigenvalue will be negative as $a_{ii}$ is positive real valued and the radius is not large enough. So if we have that for all $i$, $a_{ii} > \frac{1}{2}$ then $A$ does not have a negative eigenvalue. Therefore, if $A$ has a negative eigenvalue, then there exists an $i$ such that $a_{ii} \le\frac{1}{2}$. As for the converse, if $A=(a_{ij})$ is a doubly stochastic matrix such that there exists an $a_{ii}$ with $a_{ii}\le 1/2$, does it follow that $A$ has a negative eigenvalue? Answer: Not necessarily. $$ \begin{pmatrix} 1/2 & 1/2 \\ 1/2 & 1/2 \end{pmatrix} $$ is a stupid example that satisfies the hypothesis, but its eigenvalues are $0$ and $1$. Do we require that $A$ is non-singular? Sadly, no the below matrix is doubly stochastic, and nonsingular, satisfies that there exists an $i$ such that $a_{ii}\le 1/2$ and yet has no negative real eigenvalue. Counterexample: $$ \begin{pmatrix}1/2 & 1/2 & 0 \\ 0 & 1/2 & 1/2 \\ 1/2 & 0 & 1/2\end{pmatrix} $$
has eigenvalues: $(\lambda_1,\lambda_2,\lambda_3) = (1, \approx 0.25+0.433013 i,\approx 0.25-0.433013 i)$
You might be interested in: http://www.hindawi.com/journals/aaa/2014/902383/ which discusses the inverse eigenvalue problem at great length.
You also might have a look at Eigenvalues of doubly stochastic matrices.
There are many examples of doubly stochastic matrices with negative eigenvalues. Here is one such example: $$\begin{pmatrix} 0 & 1/2 & 1/2 \\ 1/2 & 0 & 1/2 \\ 1/2 & 1/2 & 0 \end{pmatrix}$$ The above matrix has eigenvalues: $(\lambda_1,\lambda_2,\lambda_3)=(1,-1/2,-1/2)$
Here is a $2\times 2$ example: $$\begin{pmatrix} 1/3 & 2/3 \\ 2/3 & 1/3 \end{pmatrix}$$ with eigenvalues $(\lambda_1,\lambda_2) = (1,-1/3)$.
Note that a doubly stochastic matrix need not be symmetric in order to have a negative eigenvalue as: $${1\over15}\pmatrix{8&1&6\cr3&5&7\cr4&9&2\cr}$$ is an example of an asymmetric doubly stochastic matrix with eigenvalues: $$ (\lambda_1, \lambda_2 \lambda_3) = (1,\approx -0.32659, \approx 0.32659) $$ This is an example taken from Asymmetric doubly stochastic matrix. that shows that it is not necessary for a doubly stochastic matrix with a negative eigenvalue to be symmetric.
It is also very easy to concoct examples of symmetric, doubly stochastic matrices that have no negative eigenvalues such as: $$ \begin{pmatrix}2/3 & 1/3 \\ 1/3 & 2/3 \end{pmatrix} $$ that has eigenvalues $(\lambda_1, \lambda_2) = (1,1/3)$
Therefore, (easily),symmetric doubly stochastic matrices do not necessarily have a negative eigenvalue.
On the other hand, if you're dealing with a doubly stochastic symmetric matrix, you're guaranteed that its eigenvalues are real, as opposed to asymmetric matrices.