Reference request: "Higher order eigentuples" as generalized eigenvectors?

Question

I stumbled upon a cute generalization of the eigenvalue problem and would like to know if anybody has seen something like this and can provide references.

The eigenvalue problem for a square matrix $M$ is to find a vector $v\neq 0$ and a scalar $\lambda$ such that $Mv = \lambda v$. Put differently: find the one-dimensional $M$-invariant subspaces and how the matrix acts on them. To make dimensions fit, we can also write the eigenvalue equation as $$ \underbrace{M}_{n\times n} \underbrace{v}_{n\times 1} = \underbrace{v}_{n\times 1} \underbrace{\lambda}_{1\times 1}. $$ Here is a generalization of this problem which I haven't seen before: Given a square matrix $M$ of size $n\times n$, find a matrix $V$ of size $n\times 2$ and a matrix $\Lambda$ of size $2\times 2$ such that $$ MV = V\Lambda. $$ This is also related to invariant subspaces as the columns of $V$ need to span an $M$-invariant subspace. The analogy with eigenvalues goes a little further. Using the Kronecker product and the column-wise vectorization we can write $MV = V\Lambda$ as $$ (I_2 \otimes M)\operatorname{vec}(V) = (\Lambda\otimes I_n)\operatorname{vec}(V) $$ (with $I_m$ being the $m\times m$ identity) and hence, such a $\Lambda$ has to fulfill that $$ \det(I_2\otimes M - \Lambda\otimes I_n) = 0. $$ Of course, this further generalizes to matrix $V$ of size $n\times m$ and $\Lambda$ of size $m\times m$…

Since this seems to be a very natural generalization with implications for matrix computations, I would be surprised if this has not been studied.

(I got interested in this question when I wondered if it is possible to obtain a $\Lambda$ (for given $A$ of size $m\times n$ and a (symmetric) $M$ of size $n\times n$) such that $(A^TA + M)^{-1}A^T = A^T(AA^T + \Lambda)^{-1}$. This always holds for $M = \alpha I_n$ with $\Lambda = \alpha I_m$ but for other $M$ it is necessary that the columns $A^T$ span an $M$-invariant subspace and that $MA^T = A^T\Lambda$.)

Answer 1

The observation that $MV = V\Lambda$ is essentially an invariant subspace relation is commonly used in methods to solve algebraic Riccati equations via Hamiltonian matrices; for instance, the Schur method and the matrix sign method. For instance, one can prove that if $M, V, \Lambda$ satisfy that relation (and $V$ has full column rank), then the spectrum of $\Lambda$ is a subset of that of $M$ (with multiplicities); moreover, $\operatorname{Im} V$ can be written as the span of the Jordan chains of $M$ associated to the eigenvalues in $\Lambda$ (if the spectrum of $\Lambda$, $\Sigma(\Lambda)$, is disjoint from $\Sigma(M) \setminus \Sigma(\Lambda)$).

You can find more for instance in the books

• Datta, Biswa Nath, Numerical methods for linear control systems. Design and analysis. With CD-ROM., Amsterdam: Elsevier/Academic Press (ISBN 0-12-203590-9/hbk). xxxviii, 695 p. (2004). ZBL1079.65072.

(chapter 13) and

• Bini, Dario A.; Iannazzo, Bruno; Meini, Beatrice, Numerical solution of algebraic Riccati equations., Fundamentals of Algorithms 9. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 978-1-611972-08-5/pbk; 978-1-611972-09-2/ebook). xvi, 250 p. (2012). ZBL1244.65058.

(Disclosure for conflict of interests purpose: the authors of this second book are close colleagues/collaborators of mine.)

The reformulation with Kronecker products does not seem too useful computationally, but similar techniques are used when working with Sylvester equations $AX-XB = C$; here $A$ and $B$ are square but $C$ and $X$ may be rectangular. That equation can be rewritten as a linear system with matrix $I\otimes A - B^\top \otimes I$.

Answer 2

Let me assume that $M$ is symmetric, then we can work in a basis where it is diagonal, $M=\operatorname{diag}(\mu_1,\mu_2,\ldots \mu_n)$. I denote the vectors $v_i=V_{i1}$ and $u_i=V_{i2}$, $i=1,2\ldots n$. The $2n$ equations I need to solve for the $2n+4$ elements of $v,u,\Lambda$ are $$X_i{{v_i}\choose{u_i}}=0,\;\;X_i=\begin{pmatrix} \mu_i-\Lambda_{11}& - \Lambda_{21} \\ -\Lambda_{12} & \mu_i-\Lambda_{22}\end{pmatrix}. $$ This problem is heavily underdetermined. For a solution which is not identically zero, set all $v_i,u_i$ to zero except one single $i\equiv i_0$. Then choose $\Lambda$ such that $\det X_{i_0}=0$.

Answer 3

This seems to be equivalent to finding invariant two dimensional subspaces. One way to algebraically describe two dimensional subspaces is the vector space $V'=\Lambda^2V$ (the second wedge product). The action of $M$ on $V$ induces an action on $V'$. Pick a basis for $V$ which induces a basis on $V'$, and then you can express the action induced by $M$ on $V'$ as some matrix $M'$. Now, find the eigenvectors of $M'$, if this is a pure wedge $v\wedge w$, the subspace spanned by $v$ and $w$ is left invariant under $M$ and the eigenvalue is the determinant of the transformation matrix you're looking for. In order to check if a vector $\omega\in \Lambda^2V$ is a pure wedge of two vectors, quadratic equations of the coefficients called the Plucker relations can be checked. This seems annoying to do by hand, but seems doable to code up.

Answer 4

$\newcommand\la\lambda\newcommand\La\Lambda$

Given a square matrix $M$ of size $n\times n$, find a matrix $V$ of size $n\times 2$ and a matrix $\Lambda$ of size $2\times 2$ such that $$ MV = V\Lambda. $$

There may be many such matrices, even with the additional condition that $\La$ be diagonal. E.g., if $u$ and $w$ are eigenvectors of $M$ with the corresponding eigenvalues $\la$ and $\mu$, $V$ is the $n\times2$ matrix with columns $u$ and $w$, and $\La$ is the diagonal matrix with $\la$ and $\mu$ on the diagonal, then $MV=V\La$ will hold.

Also, if $u$ and $w$ are "Jordan-form" vectors such that $Mw=\la w$ and $Mu=\la u+w$ for some complex $\la$, if $V$ is the $n\times2$ matrix with columns $u$ and $w$, and if $\La=\begin{bmatrix}\la&0\\1&\la \end{bmatrix}$, then $MV=V\La$ will again hold.