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.
Answer
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])
No comments:
Post a Comment