Month: October 2023

What Is an Invariant Subspace?

A subspace S of \mathbb{C}^n is an invariant subspace for A\in\mathbb{C}^{n \times n} if AS \subseteq S, that is, if x\in S implies Ax \in S.

Here are some examples of invariant subspaces.

  • \{0\} and \mathbb{C}^n are trivially invariant subspaces of any A.
  • The null space \mathrm{null}(A) = \{ x: Ax = 0\} is an invariant subspace of A because x\in\mathrm{null}(A) implies Ax = 0\in\mathrm{null}(A).
  • If x is an eigenvector of A then \mathrm{span}(x) = \{\, \alpha x: \alpha\in\mathbb{C} \,\} is a 1-dimensional invariant subspace, since A\alpha x = \lambda \alpha x \in S, where \lambda is the eigenvalue corresponding to x.

  • The matrix

    \notag \begin{bmatrix} 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}

    has a one-dimensional invariant subspace \mathrm{span}(e_1) and a two-dimensional invariant subspace \mathrm{span}(e_1, e_2), where e_i denotes the ith column of the identity matrix.

Let x_1,x_2, \dots,x_p\in\mathbb{C}^n be linearly independent vectors. Then S = \mathrm{span}(x_1,x_2, \dots,x_p) is an invariant subspace of A if and only if Ax_i\in S for i=1\colon p. Writing X = [x_1,x_2,\dots,x_p]\in\mathbb{C}^{n \times p}, this condition can be expressed as

\notag AX = XB, \qquad(1)

for some B\in\mathbb{C}^{p \times p}.

If p = n in (1) then AX = XB with X square and nonsingular, so X^{-1}AX = B, that is, A and B are similar.

Eigenvalue Relations

We denote by \Lambda(A) the spectrum (set of eigenvalues) of A and by A^+ the pseudoinverse of A.

Theorem.

Let A\in\mathbb{C}^{n\times n} and suppose that (1) holds for some full-rank X\in\mathbb{C}^{n\times p} and B\in\mathbb{C}^{p\times p}. Then \Lambda(B)\subseteq\Lambda(A). Furthermore, if (\lambda,x) is an eigenpair of A with x\in\mathrm{range}(X) then (\lambda,X^+x) is an eigenpair of B.

Proof. If (\lambda,z) is an eigenpair of B then AXz = XBz = \lambda Xz, and X z\ne 0 since the columns of X are independent, so (\lambda,Xz) is an eigenpair of A.

If (\lambda,x) is an eigenpair of A with x\in\mathrm{range}(X) then x = Xz for some z\ne0, and z = X^+x, since X being full rank implies that X^+X = I. Hence

\notag \lambda x = Ax = AXz = XBz.

Multiplying on the left by X^+ gives \lambda z = Bz, so (\lambda,z) is an eigenpair of B.

Block Triangularization

Assuming that X in (1) has full rank p we can choose Y\in\mathbb{C}^{p \times (n-p)} so that W = [X,\,Y] is nonsingular. Let W^{-1} = \left[\begin{smallmatrix} G \\ H \end{smallmatrix}\right] and note that W^{-1}W = I implies GX = I and HX = 0. We have

\notag W^{-1}AW = \begin{bmatrix} G \\H \end{bmatrix} [AX,\, AY] = \begin{bmatrix} G \\H \end{bmatrix} [XB,\, AY] = \begin{bmatrix} B & GAY\\ 0 & HAY \end{bmatrix}, \qquad (2)

which is block upper triangular. This construction is used in the proof of the Schur decomposition with p=1, x an eigenvector of unit 2-norm, and W chosen to be unitary.

The Schur Decomposition

Suppose A\in\mathbb{C}^{n \times n} has the Schur decomposition Q^*AQ = R, where Q is unitary and R is upper triangular. Then AQ = QR and writing Q = [Q_1,\,Q_2], where Q_1 is n\times p, and

\notag R = \begin{bmatrix} R_{11} & R_{12} \\ 0 & R_{22} \\ \end{bmatrix},

where R_{11} is p\times p, we have A Q_1 = Q_1 R_{11}. Hence Q_1 is an invariant subspace of A corresponding to the eigenvalues of A that appear on the diagonal of R_{11}. Since p can take any value from 1 to n, the Schur decomposition provides a nested sequence of invariant subspaces of A.

Notes and References

Many books on numerical linear algebra or matrix analysis contain material on invariant subspaces, for example

  • David S. Watkins. Fundamentals of Matrix Computations Third edition, Wiley, New York, USA, 2010.

The ultimate reference is perhaps the book by Gohberg, Lancaster, and Rodman, which has an accessible introduction but is mostly at the graduate textbook or research monograph level.

  • Israel Gohberg, Peter Lancaster, and Leiba Rodman, Invariant Subspaces of Matrices with Applications, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2006 (unabridged republication of book first published by Wiley in 1986).

Related Blog Posts

This article is part of the “What Is” series, available from https://nhigham.com/index-of-what-is-articles/ and in PDF form from the GitHub repository https://github.com/higham/what-is.

What Is a Submatrix?

A submatrix of a matrix is another matrix obtained by forming the intersection of certain rows and columns, or equivalently by deleting certain rows and columns. More precisely, let A be an m\times n matrix and let 1\le i_1 < i_2 < \cdots < i_p \le m and 1\le j_1 < j_2 < \cdots < j_q \le n. Then the p\times q matrix B with b_{rs} = a_{i_rj_s} is the submatrix of A comprising the elements at the intersection of the rows indexed by i_1,\dots,i_p and the columns indexed by j_1,\dots,j_q. For example, for the matrix

\notag \begin{bmatrix} ~\fbox{1} & \fbox{2} & 3\mskip2mu \\ ~~4 & 5 & 6\mskip2mu~ \\ ~\fbox{7} & \fbox{8} & 9~\mskip2mu \end{bmatrix} = \begin{bmatrix} ~\fbox{1} & \fbox{2} & 3\mskip2mu~ \\[1pt] ~\fbox{4} & 5 & 6\mskip2mu~ \\ 7 & \fbox{8} & 9\mskip2mu \end{bmatrix},

shown with four elements highlighted in two different ways,

\notag \begin{bmatrix} 1 & 2 \\ 7 & 8 \\ \end{bmatrix}

is a submatrix (the intersection of rows 1 and 3 and columns 1 and 2, or what is left after deleting row 2 and column 3), but

\notag \begin{bmatrix} 1 & 2 \\ 4 & 8 \\ \end{bmatrix}

is \emph{not} a submatrix.

Submatrices include the mn matrix elements and the matrix itself, but there are many of intermediate size: an m\times n matrix has (2^m-1)(2^n-1) submatrices in total (counting both square and nonsquare submatrices).

If p = q and i_k = j_k, k = 1\colon p, then B is a principal submatrix of A, which is a submatrix symmetrically located about the diagonal. If, in addition, i_k = k, k=1\colon p, then B is a leading principal submatrix of A, which is one situated in the top left corner of A.

The determinant of a square submatrix is called a minor. The Laplace expansion of the determinant expresses the determinant as a weighted sum of minors.

The Colon Notation

In various programming languages, notably MATLAB, and in numerical linear algebra, a colon notation is used to denote submatrices consisting of contiguous rows and columns.

For integers p and q we denote by p\colon q the sequence p,p+1,\dots,q. Thus i = 1\colon n is another way of writing i = 1,2,\dots,n.

We write A(p\colon q,r \colon s) for the submatrix of A comprising the intersection of rows p to q and columns r to s, that is,

A(p\colon q,r \colon s) = \begin{bmatrix}a_{pr} & \cdots & a_{ps} \\ \vdots & \ddots & \vdots\cr a_{qr} & \cdots & a_{qs} \end{bmatrix}.

We can think of A(p\colon q,r \colon s) as a projection of A using the corresponding rows and columns of the identity matrix:

\notag A(p\colon q,r \colon s) = I(p\colon q,:) \,A \,I(:,r\colon s).

As special cases, A(k,\colon) denotes the kth row of A and A(\colon,k) the kth column of A.

Here are some examples of using the colon notation to extract submatrices in MATLAB. Rows and columns can be indexed by a range using the colon notation or by specifying the required indices in a vector. The matrix used is from the Anymatrix collection. 

>> A = anymatrix('core/beta',5)
A =
     1     2     3     4     5
     2     6    12    20    30
     3    12    30    60   105
     4    20    60   140   280
     5    30   105   280   630

>> A(3:4, [2 4 5]) % Rectangular submatrix.
ans =
    12    60   105
    20   140   280

>> A(1:2,4:5)      % Square, but nonprincipal, submatrix.
ans =
     4     5
    20    30

>> A([3 5],[3 5])  % Principal submatrix.
ans =
    30   105
   105   630

Block Matrices

Submatrices are intimately associated with block matrices, which are matrices in which the elements are themselves matrices. For example, a 4\times 4 matrix A can be regarded as a block 2\times 2 matrix, where each element is a 2\times 2 submatrix of A:

\notag A = \left[\begin{array}{cc|cc} a_{11} & a_{12} & a_{13} & a_{14}\\ a_{21} & a_{22} & a_{23} & a_{24}\\\hline a_{31} & a_{32} & a_{33} & a_{34}\\ a_{41} & a_{42} & a_{43} & a_{44}\\ \end{array}\right] = \begin{bmatrix} A_{11} & A_{12} \\ A_{21} & A_{22} \end{bmatrix},

where

\notag A_{11} = A(1\colon2,1\colon2) = \begin{bmatrix} a_{11} & a_{12} \\ a_{21} & a_{22} \end{bmatrix},

and likewise for the other three blocks.

Related Blog Posts

This article is part of the “What Is” series, available from https://nhigham.com/index-of-what-is-articles/ and in PDF form from the GitHub repository https://github.com/higham/what-is.