# Matrix with non-negative eigenvalues (and additional assumption)

Let $A \in \mathbb{R}^{n \times n}$ be positive semi-definite ($A = A^\top \succcurlyeq 0$) and with positive diagonal elements ($A_{i,i} > 0$ for all $i$).

Assume that both the column and the row sum of $A$ is $0$, i.e., for all $i$, $\sum_{j} A_{i,j} = 0$, and for all $j$, $\sum_{i} A_{i,j} = 0$. Also assume that $A$ has exactly one eigenvalue equal to $0$.

Let $b, c \in \mathbb{R}^n$ be element-wise positive and non-negative vectors respectively, i.e., $b > 0$ and $c \geq 0$. Assume that $c^\top b > 0$.

Prove that the $(n+1)$-dimensional matrix $$\left[ \begin{matrix} A & b \\ c^\top A & c^\top b\end{matrix} \right]$$ has eigenvalues with non-negative real part.

Comments. Numerics show that the claim is true. In here it is shown that $A \succcurlyeq 0$ is not enough for the claim to be true, thus the additional assumption on $A$ would be needed.

• What if the matrix has complex eigenvalues? – Algebraic Pavel Jun 16 '15 at 12:30
• Thanks for the remark. In that case, I mean the real part. – user693 Jun 16 '15 at 12:33
• It suffices to show that $M + M^T$ is positive semidefinite. I'm not sure if this is easier. – Omnomnomnom Jun 16 '15 at 15:56
• I think it is sufficient to find $P \succ 0$ such that $M^\top P + P M \succcurlyeq 0$, which seems as hard as the question. – user693 Jun 16 '15 at 20:20
• if A is $n \times n$, then how come your new matrix is $(n+1) \times (n+1)$ if $b,c \in \mathbb{R}^n$ (I assume you mean $n$ is not unity). If $n$ IS unity, then $c^\text{T}b$ will be a positive number which means trace of new matrix is greater or equal than trace of $A$ and thus the added eigenvalue has a nonnegative real part. – kbau Jun 25 '15 at 13:06

The matlab code below can be used to construct a counterexample. (The result is probably true if $A$ is also an $M$-matrix.) The motivation is the Sherman-Morrison-Woodbury formula. You write out the equations that an eigenvalue eigenvector pair $\lambda$, $[x, y]^T$ must satisfy:

$Ax+by=\lambda x,$

$c^Tx+c^Tby=\lambda y.$

Observe that the last equation is almost $c^T$ times the leading equations, and this gives rise to a constraint on the last entry of the eigenvector,

$c^Tx=y$

which then gives rise to a matrix to which the Sherman-Morrison-Woodbury formula can be applied if $\lambda$ is not an eigenvalue $Ax+bc^Tx=\lambda x$

$(A-\lambda I+bc^T)x=0$

Then for a given negative $\lambda$, the game is finding b and c where the Sherman-Morrison-Woodbury formula cannot be applied.

n=10;
D=diag(abs(rand(n,1)+1));
D(1,1)=0
D(2,2)=1e-1
[V R]=qr([ones(n,1) randn(n)],0)
A=V*D*V'

%Let's force -1 to be an eigenvalue of our matrix
lambda=-1;

inv(A-lambda*eye(n))
%Examine this matrix, it is highly likely that
%the matrix will have a negative entry in one of the columns
%Column n for example
%Let c_j=0 j\neq n and 1 otherwise
%Since b must be postive
%Make most of the entries of b small with the exception of
%the entry that is negative

c=zeros(n,1)
c(2)=1
(A-lambda*eye(n))\c
b=.001*ones(n,1)
b(1)=10
b'*inv(A-lambda*eye(n))*c
t=(-1/(c'*inv(A-lambda*eye(n))*b))
(c'*inv(A-lambda*eye(n))*b)
eig(A-lambda*eye(n)*t*b*c')
eig([A t*b ; c'*A c'*b])

• Thank you very much for your answer. Can you please also comment on the statement "The result is probably true if $A$ has real positive eigenvalues"? Would you think that the result is true if $A$ has integer elements? – user693 Jun 25 '15 at 17:02