Eigenvalues of block matrix/Related non-linear eigenvalue problem

In summary, the problem is to determine if the eigenvalues of a matrix M, defined in block form, lie in the unit circle. This comes from the discretization of a PDE, with a potentially large n value. The non-linear eigenvalue problem can be solved using an efficient algorithm or by directly using the eigenvalues of J. Additionally, the eigenvalues of M can also be determined from those of B.
  • #1
pasmith
Science Advisor
Homework Helper
3,133
1,707
TL;DR Summary
I need to determine whether the eigenvalues of a large [itex]2n[/itex] by [itex]2n[/itex] block matrix are inside the unit circle, and have reduced the problem to an [itex]n[/itex]-dimensional non-linear eigenvalue problem.
I have a matrix [itex]M[/itex] which in block form is defined as follows: [tex]
\begin{pmatrix} A (\equiv I + 3\alpha J) & B (\equiv -\alpha J) \\ I & 0 \end{pmatrix}[/tex] where [itex]J[/itex] is an [itex]n[/itex]-by-[itex]n[/itex] complex matrix, [itex]I[/itex] is the identity and [itex]\alpha \in (0,1][/itex] is a parameter. The problem is to determine whether the eigenvalues of [itex]M[/itex] lie in the unit circle.

This comes from the discretization of a PDE, so [itex]n[/itex] 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 [itex]2n[/itex] by [itex]2n[/itex] matrix if there's a more efficient way to solve an equivalent [itex]n[/itex]-dimensional problem.

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

Alternatively, if the eigenvalues of [itex]M[/itex] can be determined directly from those of [itex]J[/itex] then so much the better.
 
Last edited:
Physics news on Phys.org
  • #2
On further reflection, given the relationship between [itex]A[/itex] and [itex]B[/itex], we can obtain eigenvalues of [itex]M[/itex] in terms of those of [itex]B[/itex] as follows:

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

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

Problem solved.
 
  • Like
Likes Keith_McClary

Related to Eigenvalues of block matrix/Related non-linear eigenvalue problem

1. What are eigenvalues of a block matrix?

Eigenvalues of a block matrix are the special set of values that satisfy the equation Ax = λx, where A is a square matrix and λ is a scalar value. These values represent the scaling factor by which the corresponding eigenvectors are stretched or compressed.

2. How are eigenvalues of a block matrix computed?

The eigenvalues of a block matrix can be computed by solving the characteristic equation det(A - λI) = 0, where A is the given matrix and I is the identity matrix. This equation results in a polynomial of degree n, where n is the size of the matrix, and its roots are the eigenvalues.

3. What is a non-linear eigenvalue problem?

A non-linear eigenvalue problem is a generalization of the traditional eigenvalue problem, where the matrix A in the equation Ax = λx is replaced by a non-linear function f(x). This results in a non-linear equation f(x) = λx, which may have multiple solutions for λ and x.

4. How is a non-linear eigenvalue problem solved?

Solving a non-linear eigenvalue problem involves finding the values of λ and x that satisfy the equation f(x) = λx. This can be done numerically using methods such as the power method or the inverse iteration method. Alternatively, it can be solved analytically for specific cases.

5. What are some applications of eigenvalues of block matrices and non-linear eigenvalue problems?

Eigenvalues of block matrices and non-linear eigenvalue problems have various applications in fields such as physics, engineering, and data analysis. They are used in the study of oscillating systems, stability analysis, and machine learning algorithms. They also play a crucial role in solving differential equations and understanding the behavior of complex systems.

Similar threads

  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Linear and Abstract Algebra
Replies
10
Views
1K
Replies
4
Views
2K
  • Linear and Abstract Algebra
Replies
8
Views
1K
  • Linear and Abstract Algebra
Replies
9
Views
2K
  • Linear and Abstract Algebra
Replies
8
Views
1K
  • Linear and Abstract Algebra
Replies
15
Views
1K
  • Linear and Abstract Algebra
Replies
8
Views
1K
Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
34
Views
2K
Back
Top