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: $$\begin{pmatrix} A (\equiv I + 3\alpha J) & B (\equiv -\alpha J) \\ I & 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 $$\begin{pmatrix}A & B \\ I & 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 $$\lambda(A - \lambda I)p_2 = -B p_2$$ with $p_1 = \lambda p_2$, which in terms of $J$ is
$$\lambda(3 \alpha J - (\lambda - 1)I)p_2 = \alpha J p_2.$$ 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 $$(\lambda(1 - 3\mu) + \mu)p_2 = \lambda^2 p_2$$ and as $p_2 \neq 0$ we must have $$\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 $$\begin{align*}<br /> &\lambda(I - 3B)p_2 + Bp_2 = \lambda^2 p_2 \\<br /> \Leftrightarrow \qquad& 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 $$Bp_2 = \frac{\lambda^2 - \lambda}{1 - 3\lambda}p_2$$ as required.

Problem solved.