Eigenvalues of block matrix/Related non-linear eigenvalue problem

[pasmith]

TL;DR

I need to determine whether the eigenvalues of a large $2n$ by $2n$ block matrix are inside the unit circle, and have reduced the problem to an $n$-dimensional non-linear eigenvalue problem.

I have a matrix M which in block form is defined as follows: <br /> \begin{pmatrix} A (\equiv I + 3\alpha J) &amp; B (\equiv -\alpha J) \\ I &amp; 0 \end{pmatrix} where J is an n-by-n complex matrix, I is the identity and \alpha \in (0,1] is a parameter. The problem is to determine whether the eigenvalues of M lie in the unit circle.

This comes from the discretization of a PDE, so n is potentially on the order of 5000 and I'm looking for a numerical method. I would prefer not to have to find the eigenvalues of a 2n by 2n matrix if there's a more efficient way to solve an equivalent n-dimensional problem.

By definition \lambda is an eigenvalue of M if and only if there exist (p_1, p_2) \in (\mathbb{C}^{n})^2 \setminus \{(0,0)\} such that <br /> \begin{pmatrix}A &amp; B \\ I &amp; 0 \end{pmatrix} <br /> \begin{pmatrix} p_1 \\ p_2 \end{pmatrix} = \lambda \begin{pmatrix} p_1 \\ p_2 \end{pmatrix}. This leads me to the non-linear eigenvalue problem <br /> \lambda(A - \lambda I)p_2 = -B p_2 with p_1 = \lambda p_2, which in terms of J is
<br /> \lambda(3 \alpha J - (\lambda - 1)I)p_2 = \alpha J p_2.<br /> Is there an efficient algorithm to solve this?

Alternatively, if the eigenvalues of M can be determined directly from those of J then so much the better.

 

[pasmith]

On further reflection, given the relationship between A and B, we can obtain eigenvalues of M in terms of those of B as follows:

Since A = I - 3B, if p_2 is an eigenvector of B with eigenvalue \mu then p_2 is also an eigenvector of A with eigenvalue 1 - 3\mu, since
Ap_2 = (I - 3B)p_2 = (1 - 3\mu)p_2. Thus <br /> (\lambda(1 - 3\mu) + \mu)p_2 = \lambda^2 p_2 and as p_2 \neq 0 we must have <br /> \lambda^2 - (1 - 3\mu)\lambda - \mu = 0.

Conversely, if p_2 \neq 0 is a solution of the non-linear eigenproblem with eigenvalue \lambda then <br /> \begin{align*}<br /> &amp;\lambda(I - 3B)p_2 + Bp_2 = \lambda^2 p_2 \\<br /> \Leftrightarrow \qquad&amp; B(1 - 3 \lambda)p_2 = (\lambda^2 - \lambda) p_2<br /> \end{align*} Now if \lambda = \frac13 then the left hand side is zero and the right hand side is -\frac29 p_2, which by assumption is not zero. Thus \lambda \neq \frac13 and so <br /> Bp_2 = \frac{\lambda^2 - \lambda}{1 - 3\lambda}p_2 as required.

Problem solved.