# Matrix with non-negative eigenvalues

Let $A \in \mathbb{R}^{n \times n}$ be a positive semi-definite $A \succcurlyeq 0$, and with positive diagonal elements ($A_{i,i} > 0$ for all $i$). Let $A$ have at least one eigenvalue equal to $0$.

Let $b, c \in \mathbb{R}^n$ be element-wise non-negative vectors ($b, c \geq 0$), with $c^\top b > 0$.

Prove that the matrix $$M := \left[ \begin{matrix} A & b \\ c^\top A & c^\top b\end{matrix} \right] \in \mathbb{R}^{(n+1) \times (n+1)}$$ has non-negative eigenvalues.

Comments. Since $A$ has at least one $0$ eigenvalue, $M$ has determinant $0$, hence at least one $0$ eigenvalue. The trace of $M$ is positive, thus the sum of its eigenvalues is positive. In addition, the traces of all the square sub-matrices is positive. I am not sure whether this fact can be exploited. If $A$ were positive definite, then one could use the Schur determinant formula to prove the claim.

This is not true. After some fiddling with matlab, I found this counter-example. Take $$A=\pmatrix{1&1\\1&1}, \ b=\pmatrix{1\\2}, \ c=\pmatrix{2\\1},$$ then $$M= \pmatrix{1 & 1 & 1\\1&1&2\\3&3&4},$$ with characteristic polynomial $$p_M= t ( t^2-6t-1) = t \big( (t-3)^2- 10\big),$$ which has roots $$0, \ 3+\sqrt{10}, \ 3-\sqrt{10},$$ with the last one being negative.
The statement is true if for instance $c^TA=0$. Then $M$ is upper block-diagonal with positive semidefinite blocks.
Another possibility to investigate positive definiteness is the following splitting, which works if $b=Ad$ for some vector $d$: $$\pmatrix{A & b \\ c^TA& c^Tb} = \pmatrix{I&0\\c^T& 1} \pmatrix{ A&b\\0&0}\\ = \pmatrix{I&0\\c^T& 1} \pmatrix{ A&0\\0&0} \pmatrix{I&d\\0&1},$$ hence $M$ is positive semidefinite if $d=c$ which is $b=Ac$.
• Thanks a lot. What additional assumptions can make the statement true? In my case, both the rows and the columns of $A$ sum up to $0$. – user693 Jun 9 '15 at 20:37
• I formulated again the question with additional assumptions on $A$ in here: math.stackexchange.com/questions/1327411/…. – user693 Jun 16 '15 at 11:56