# Generalized Eigenvalue Problem with one matrix having low rank

I have a specific Generalized Eigenvalue Problem (GEVP) where i am primary not interested in solving this problem but concluding from a standard EVP the spectrum of the GEVP.

The Problem
Let $A$ be a $n\times x$ possibly complex matrix and $B$ a diagonal, real $n\times n$ matrix with maximal rank of $n-1$ (e.g. the matrix $B$ has at minimum 1 zero column and row).
Solving

$(B\lambda-A)\cdot v=0$

with $|v|=1$, so that we have $n+1$ equations for $n+1$ unknown is the GEVP. The GEVP can not be reformulated as EVP because $det(B)=0$ and therefore $B$ is not invertible.

As I said the goal is not just solving this problem (this could be done by solving $det(\lambda B I-A)=0$ to obtain the eigenvalues) but to conclude eigenvalues for the stated GEVP from the following, already solved, EVP (the $n$ eigenvalues $\mu_1\leq\mu_2\leq\dots\leq \mu_n$ of $A$ are known):

$(I\mu-A)\cdot w=0$.

What I have already learned
*As $A$ and $B$ in general do not commutate it is not possible to diagonalize $A$ and $B$ simultanously. Therefore the spectra will be different.
*If the EVP results in eigenvalues $\mu=0$, so there will be the same number of eigenvalues $\lambda=0$ in the GEVP. (Because in both cases $det(A)=0$ must be fullfilled and the geometric multiplicity comes from the dimension of $kern(A)$.)
*For every zero-row in $B$ the number of eigenvalues $\mu$ is one less then in the EVP. This is because the order of the characteristic polynom (CP) goes one down for every zero-row in $B$ compared to the order of the CP in the EVP.

Questions
*Can be said which eigenvalues (in addition to the zeros) of the EVP are also eigenvalues of the GEVP (the eigenvectors may not be the same in both cases, but the eigenvalues).
*Is there a pertubation theory? Can I somehow make a taylor series of the CP in the GEVP where the zeroth-term is the CP of the EVP?
*The number of eigenvalues in the GEVP is less than in the EVP, can be concluded which eigenvalues vanish?

In case anybody wants to know, where my question emerges from (this is not essential for my questions but possibly from general interest):

If one wants to conclude the stability of a fix point $x^*$ of ODEs one needs to solve the variational ODE $\dot{\delta x}(t)=D_xf(x^*)\delta x(t)$. Where $\delta x$ is a small pertubation away from the fix point: $\delta x(t)=x(t)-x^*$. Solving this with $\delta x(t)=\delta x_0 e^{\mu t}$ results in the EVP
$\mu\delta x_0 = D_x f(x^*) \delta x_0$.
Using $D_xf(x^*)=A$ and $w=\delta x_0$ results in the stated EVP.

If one has additional constraints in a implicit way
$g(x(t))=0$
the stability of a fix point in the ODE may change (e.g. the constraint acts in a unstable direction. The eigenvalue of $A$ in this direction is still greater zero (obviously the matrix $A$ does not change if constraints are imposed) but it is a "forbidden" direction as the corrisponding eigenvector is in a direction which is not allowed due to the constraint).
Taking the time derivative of $g$ results in $D_x g(x)\cdot \dot{x}(t)=0$. Inserting the pertubation away from the fix point results in
$(D_xg(x^*)+D_x(D_xg(x^*))\cdot \delta x)\cdot \dot{\delta x}(t)+\dots=0$
$D_xg(x^*)\cdot \dot{\delta x}(t)+O(\delta x^2)=0$
Inserting the exp-ansatz results in
$D_xg(x^*)\cdot \delta x_0\mu\approx0$
This means that the small pertubations need to be orthogonal to the gradient on the invariant manifold near the fix point (e.g. they are inside the invariant manifold).

One possible way to go to study the change of stability of the fix point when constraints are imposed, is to solve the EVP and then to check consistency with the last equation.
I want to include the constraint directly in the EVP, which leads to the GEVP by simply adding the last equation to the EVP (with $D_x g(x^*)=\hat{B}$ and $w=\delta x_0$):
$(\hat{B}\mu+I\mu-A)\cdot w=0$
and with $\hat{B}+I=B$
$(B\mu-A)\cdot w=0$
The criterion of "low rank $B$" comes from the generic constraints like $g(x_1,\dots,x_n)=x_0^1-x_1\rightarrow D_xg=(-1,0,\dots,0)\rightarrow B=\mbox{diag}(0,1,\dots,1)$.

Let's write this in block matrices: $$B = \pmatrix{B_{11} & 0\cr 0 & 0\cr}, \ A = \pmatrix{A_{11} & A_{12}\cr A_{21} & A_{22}\cr}, u = \pmatrix{u_1 \cr u_2\cr}$$ where $B_{11}$ has full rank. Then the eigenvector equations $A u = \lambda B u$ become $A_{11} u_1 + A_{12} u_2 = \lambda B_{11} u_1$ and $A_{21} u_1 + A_{22} u_2 = 0$. Suppose $A_{22}$ is invertible. Then we have $u_2 = - A_{22}^{-1} A_{21} u_1$, and $(A_{11} - A_{12} A_{22}^{-1} A_{21}) u_1 = \lambda B_{11} u_1$. The eigenvalues and eigenvectors of the GEVP correspond to eigenvalues and eigenvectors of the matrix $B_{11}^{-1}(A_{11} - A_{12} A_{22}^{-1} A_{21})$.

• @Robert: everything correct, but I believe that in your last expression $B_{11}^{-1}$ should be the leftmost term, not the rightmost. @both: note also that if $A_{22}$ is singular, then either there is a nontrivial Jordan block at infinity, or the pencil is singular (i.e., $\det (A-\lambda B)=0$ for all $\lambda$. – Federico Poloni Jul 16 '12 at 21:49
• @FedericoPoloni: Oops, yes, thanks. I'll edit. Of course for the eigenvalues it doesn't make a difference. – Robert Israel Jul 16 '12 at 23:25

Thanks for this nice answer. For the stability-problem with only 1 constraint the formula is then really simple: $B_{11}=\mbox{diag}(1,\dots,1)=I_{n-1}$ and $A_{12},A_{21},A_{22}$ are only scalars. So that the GEVP is the solution of $(A_{11}-I_{n-1}(ac/b-\lambda))\cdot v=0$ with $a=A_{12},b=A_{22},c=A_{21}$ and $b\neq0$. Resacling $\lambda$ leads to
$(A_{11}-I_{n-1}\hat{\lambda})\cdot v=0$.

Essentially the eigenvalues of the GEVP are the same as in the EVP but shifted by $ac/b$ and one eigenvalue vanishes, right? Of course this is only a guess but it should be right for large $n$ and low number of zero-rows of $B$ ($m$).

Is there a theory for what happens to the spectrum of a matrix if one strikes certain rows and columns? I guess if all eigenvalues are different e.g. there are so many eigenspaces as dimensions of the matrix, striking one row and its respective line should only lead in vanishing of one eigenvalue and all other eigenvalues should stay constant, right?

• No, no eigenvalues will stay constant in general. For example, $\pmatrix{2 & 0 & -15\cr 0 & 1 & 2\cr 1 & 2 & -4\cr}$ has eigenvalues $-1$, $i$ and $-i$; if the last row and column are removed the eigenvalues are $1$ and $2$. – Robert Israel Jul 16 '12 at 23:46
• ok, but in your example more than the half of all elements of the matrix are removed. What happens for 40x40 matrices when i strike 1,2,3,4,5,... rows? I will try this in 2 weeks but at the moment i am "out of matlab" :D Any suggestions to the pertubation thought with the characteristic polynom? – Sven E Jul 16 '12 at 23:56
• @SvenE : what will happen in general is that all eigenvalues change. I don't know what else can be said, except that for symmetric matrices the Cauchy interlacing theorem gives inequalities: if the eigenvalues (counted with multiplicity) of the original matrix are $\alpha_1 \le \alpha_2 \le \ldots \alpha_n$ and after removing $n-m$ rows and the corresponding columns the eigenvalues are $\beta_1 \le \beta_2 \le \ldots \le \beta_m$, then $\alpha_j \le \beta_j \le \alpha_{n-m+j}$ for $1 \le j \le m$. – Robert Israel Jul 17 '12 at 16:21
• I should have said, hermitian matrices. – Robert Israel Jul 17 '12 at 16:22