# An Extension to the Generalized Eigenvalue Problem

Given two square matrices $A,B \in \mathbb{R}^{n\times n}$, the generalized eigenvalue problem is finding the scalar $\lambda \in \mathbb{C}$ and vector $x \in \mathbb{C}^{n}$ such that $$A x=\lambda B x.$$ There are efficient algorithms that solve this problem.

Now consider $m+1$ square matrices $A,B_1,B_2,...,B_m \in \mathbb{R}^{n\times n}$ where matrices are not full rank. The goal is to find scalars $\lambda_1,\lambda_2,...,\lambda_m \in \mathbb{C}$ and vector $x \in \mathbb{C}^{n}$ such that $$Ax = \lambda_1 B_1 x =\lambda_2 B_2 x = ... = \lambda_m B_m x \tag{1}$$

Is there an algorithm for finding all nontrivial solutions $\lambda_1,\lambda_2, ...,\lambda_m$ and $x$ that satisfy $(1)$? What are the necessary and sufficient conditions for $(1)$ to have a solution?

• Example: Consider matrices $$A = \begin{bmatrix} 1& 1& 2 \\ 1& 4& 1 \\ 0& 0& 0 \end{bmatrix}, B_1 = \begin{bmatrix} -1& -1& -3 \\ 1& 1& 1 \\ 0& 0& 0 \end{bmatrix}, B_2 = \begin{bmatrix} 1& 2& 3 \\ 1& 0& 1 \\ 0& 0& 0 \end{bmatrix}, B_3 = \begin{bmatrix} -4& -11& -3 \\ 2& -7& -3 \\ 0& 0& 0 \end{bmatrix}$$ where rank of $A,B_1,B_2,B_3$ is 2. We want to find all nontrivial solutions $\lambda_1, \lambda_2, \lambda_3$ and $x$ such that $$A x = \lambda_1 B_1 x = \lambda_2 B_2 x = \lambda_3 B_3 x. \tag{2}$$ – Kaveh Fathian Jun 3 '15 at 21:43
• Solving the generalized eigenvalue problem for individual equations $A x = \lambda_i B_i x$ is equivalent to finding all nontrivial $\lambda_i$ and $x$ such that $$(A - \lambda_i B_i)x = 0.$$ However for all $\lambda_i \in \mathbb{C}$ the matrix $A - \lambda_i B_i$ is rank deficient. Therefore for all $\lambda_i \in \mathbb{C}$ there exists a nontrivial $x \in \mathbb{C}^3$ such that $(A - \lambda_i B_i) x = 0$, i.e., there are infinitely many solutions. – Kaveh Fathian Jun 3 '15 at 21:44
• Despite the non-finite number of solutions for the individual equations $A x = \lambda_i B_i x$, it can be shown that the system of equations $(2)$ has only finitely many solutions. For example, $\lambda_1 = 2,~ \lambda_2 = 3,~ \lambda_3 =1,~ x = [-19, -5, 9]^T$ is a solution for $(2)$. – Kaveh Fathian Jun 3 '15 at 21:45

Well, just solve the generalized eigenvalue for

$A_1 x = \lambda_1 A_2 x$

One gets finitely many $\lambda_1$ and for each a basis for all solutions for $x$. So for each such $\lambda_1$ can write $x = W z$ with $z$ a vector from the $R^d$ with $d$ the dimension of the eigenspace.

Now we solve the generalized eigenvalue system $A_1 W z = \lambda_2 A_3 W z$

to obtain all $\lambda_2$ (corresponding to the previous $\lambda_1$) and to obtain all nontrivial solutions for $z$. With $x = W z$ we get all solutions $x$. This allows to enumerate all solutions of for the triple generalized eigenvalue system.It also generalizes to four or more equations.

• Thanks for your answer Andreas! I want to check if I understood it correctly. If $\lambda_1$ and $w$ are respectively a generalized eigenvalue and eigenvector for the equation $$A_1 x = \lambda A_2 x$$ with the dimension of the eigenspace equal to 1 (i.e. $d=1$), then $z$ is a scalar and from $$A_1 w z = \lambda_2 A_2 w z$$ we can conclude that $$A_1 w = \lambda_2 A_2 w$$ which may not hold since $w$ may not be an eigenvector for $A_2$. Do you agree or did I misunderstand your answer? – Kaveh Fathian May 27 '15 at 22:24
• Yes this is correct. Both the first and second generalized eigenvalue equation may have no solution. What I wrote is still correct. When I say "all solutions" this does not imply that there is at least one solution (it actually means "none" if no solutions exist). If the second eigenvalue equation has no solution one has to try the next eigenvalue of the first eigenvalue equation and see if equation 2 has solutions for this... And so on. If equation 1 has no solution or equation 2 has no solution for all eigenvalues of equation 1. the whole problem has no solutions. – Andreas H. May 28 '15 at 20:02
• Thanks again! I modified the problem statement a little bit and added an example in the comments to describe the problem more clearly. The problem with the generalized eigenvalues is that since matrices are not full rank there are infinitely many solutions. However the system of equations has only finitely many solutions. The question is how to find them! Do you think your method work for the example that I gave in the comments? – Kaveh Fathian Jun 3 '15 at 22:12