6
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ What if the matrix has complex eigenvalues? $\endgroup$ – Algebraic Pavel Jun 16 '15 at 12:30
  • $\begingroup$ Thanks for the remark. In that case, I mean the real part. $\endgroup$ – user693 Jun 16 '15 at 12:33
  • 1
    $\begingroup$ It suffices to show that $M + M^T$ is positive semidefinite. I'm not sure if this is easier. $\endgroup$ – Omnomnomnom Jun 16 '15 at 15:56
  • $\begingroup$ 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. $\endgroup$ – user693 Jun 16 '15 at 20:20
  • $\begingroup$ 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. $\endgroup$ – kbau Jun 25 '15 at 13:06
1
+50
$\begingroup$

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])
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – user693 Jun 25 '15 at 17:02

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.