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$.

  • $\begingroup$ 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$. $\endgroup$
    – user693
    Jun 9 '15 at 20:37
  • $\begingroup$ I formulated again the question with additional assumptions on $A$ in here: math.stackexchange.com/questions/1327411/…. $\endgroup$
    – user693
    Jun 16 '15 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.