# Solving a generalised eigenvalue problem with non-square matrices

I need to solve a generalised eigenvalue problem of the form

$$A\mathbf{x}=\lambda B \mathbf{x}$$

where $$A$$ and $$B$$ are $$m \times n$$ complex matrices, that are not symmetric with $$m>n$$.

I am aware that this problem can be solved in the case that $$A$$ and $$B$$ are square via the QZ decomposition. However, is there an analogous method for the case, when $$A$$ and $$B$$ are not square?

For context, it is known a priori that a solution exists, because this problem is physically motivated.

• There may be no solutions as demonstrated by taking $A,B$ to be (say) $2\times 1$ columns that are linearly independent. Candidates for $\lambda$ are identifiable from $A^* A x = \lambda A^* B x$ with square matrices.
– hardmath
Commented Jul 22 at 12:30
• @nicoguaro: I'm happy to do so, and hoped that the OP would first clarify with any context that promises solutions exist. Real world problems are often so.
– hardmath
Commented Jul 22 at 13:10
• Yes, I am trying to compare a numerical solution with an analytical solution. The numerical solution involves an ansatz, that involves coefficients that need to be determined from certain boundary conditions, which is where this eigenvalue problem stems from. So yes, I am certain solutions do exist Commented Jul 22 at 13:26
• Do you mind elaborating, why there is no solution in general? Furthermore, how would I be able to determine if a solution can be computed in a stable way? Sorry for the questions, I am somewhat of a beginner to numerical linear algebra. Commented Jul 22 at 16:10
• I've written up an answer, which includes a small example of $A,B$ for which there is no generalized eigenvalue solution. Read it over and comment if you still have questions.
– hardmath
Commented Jul 22 at 19:39

Note that any solution $$\lambda$$ of $$Ax = \lambda Bx$$, the generalized eigenproblem involving $$m\times n$$ matrices, is also a solution of:

$$C Ax = \lambda C Bx$$

However the converse is of course not generally true. A suitable choice of matrix $$C$$ will produce a superset of the solutions to the original problem.

It is attractive to choose a matrix $$C$$ which is $$n\times m$$, so that the revised problem will involve square matrices $$CA$$ and $$CB$$. One such choice is the conjugate transpose of $$A$$, making $$CA$$ be a positive semi-definite (complex) matrix.

However there might be better choices for the specific problem you have. My first inclination is to take $$C$$ to be an $$n\times m$$ matrix whose rows are unit binary vectors corresponding to a linearly independent subset of the rows of $$A$$ (or perhaps of $$B$$).

A toy example

Let $$A = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 2 & 3 \end{bmatrix}, B = \begin{bmatrix} 5 & 3 \\ -1 & 1 \\ 2 & 3 \end{bmatrix}$$.

Choosing the first two rows of $$A$$ as our linearly independent subset yields $$C = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix}$$.

Then our revised generalized eigenvalue problem $$CA x = \lambda CB x$$ is:

$$\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} x = \lambda \begin{bmatrix} 5 & 3 \\ -1 & 1 \end{bmatrix} x$$

Since now $$CA$$ is the identity matrix, $$\lambda$$ must be a reciprocal of one of the eigenvalues of $$CB$$, which are $$2,4$$. We would then check whether either $$\lambda = 0.5,0.25$$ is a solution of the original problem.

In my contrived examples the nullspaces of $$A - \lambda B$$ are trivial for both candidate values of $$\lambda$$. (Actually I used $$(1/\lambda)A - B$$ to keep my computation with integers, and did double check my manual reductions with an online nullspace calculator).

In a comment, you asked why I think that the case $$m>n$$ will not, in general, have a solution. Here's an answer too long for a comment:

• My first line of reasoning is that the case $$m, the situation is clearly underdetermined: You only have $$m$$ equations to determine the $$n$$ components of the eigenvectors if I tell you what the eigenvalue is. Furthermore, if you have an eigenvalue-eigenvector pair, I can add $$m-n$$ zero rows to the bottoms of $$A$$ and $$B$$ and the eigenvalue-eigenvector pair is still an eigenvalue-eigenvector pair of the augmented system. Since $$m is underdetermined, it is reasonable to conjecture that the case $$m>n$$ is overdetermined and will, in general, not have solutions.

• Indeed, this is easy to see. Take, for example, the matrices $$A,B$$ of @hardmath's answer. Then the last row of the eigenvalue problem reads $$2 x_1 + 3 x_2 = \lambda (2 x_1 + 3 x_2),$$ which only allows $$\lambda=1$$ as answer. But there is no guarantee that $$\lambda=1$$ is an eigenvalue of the first two rows of the eigenvalue problem, much less that the first two rows have only $$\lambda=1$$ as eigenvalues.