Canonical basis

Linear algebra

If we are given an n × n matrix ${\displaystyle A}$ and wish to find a matrix ${\displaystyle J}$ in Jordan normal form, similar to ${\displaystyle A}$, we are interested only in sets of linearly independent generalized eigenvectors. A matrix in Jordan normal form is an "almost diagonal matrix," that is, as close to diagonal as possible. A diagonal matrix ${\displaystyle D}$ is a special case of a matrix in Jordan normal form. An ordinary eigenvector is a special case of a generalized eigenvector.

Every n × n matrix ${\displaystyle A}$ possesses n linearly independent generalized eigenvectors. Generalized eigenvectors corresponding to distinct eigenvalues are linearly independent. If ${\displaystyle \lambda }$ is an eigenvalue of ${\displaystyle A}$ of algebraic multiplicity ${\displaystyle \mu }$, then ${\displaystyle A}$ will have ${\displaystyle \mu }$ linearly independent generalized eigenvectors corresponding to ${\displaystyle \lambda }$.

For any given n × n matrix ${\displaystyle A}$, there are infinitely many ways to pick the n linearly independent generalized eigenvectors. If they are chosen in a particularly judicious manner, we can use these vectors to show that ${\displaystyle A}$ is similar to a matrix in Jordan normal form. In particular,

Definition: A set of n linearly independent generalized eigenvectors is a canonical basis if it is composed entirely of Jordan chains.

Thus, once we have determined that a generalized eigenvector of rank m is in a canonical basis, it follows that the m − 1 vectors ${\displaystyle {\mathbf{x}}_{m-1},{\mathbf{x}}_{m-2},\dots ,{\mathbf{x}}_1}$ that are in the Jordan chain generated by ${\displaystyle {\mathbf{x}}_m}$ are also in the canonical basis.

Computation

Let ${\displaystyle {\lambda }_i}$ be an eigenvalue of ${\displaystyle A}$ of algebraic multiplicity ${\displaystyle {\mu }_i}$. First, find the ranks (matrix ranks) of the matrices ${\displaystyle (A-{\lambda }_{i}I),(A-{\lambda }_{i}I{)}^2,\dots ,(A-{\lambda }_{i}I{)}^{m_i}}$. The integer ${\displaystyle m_i}$ is determined to be the first integer for which ${\displaystyle (A-{\lambda }_{i}I{)}^{m_i}}$ has rank ${\displaystyle n-{\mu }_i}$ (n being the number of rows or columns of ${\displaystyle A}$, that is, ${\displaystyle A}$ is n × n).

Now define

${\displaystyle {\rho }_k=\mathrm{rank}(A-{\lambda }_{i}I{)}^{k-1}-\mathrm{rank}(A-{\lambda }_{i}I{)}^k(k=1,2,\dots ,m_i).}$

The variable ${\displaystyle {\rho }_k}$ designates the number of linearly independent generalized eigenvectors of rank k (generalized eigenvector rank; see generalized eigenvector) corresponding to the eigenvalue ${\displaystyle {\lambda }_i}$ that will appear in a canonical basis for ${\displaystyle A}$. Note that

${\displaystyle \mathrm{rank}(A-{\lambda }_{i}I{)}^0=\mathrm{rank}(I)=n.}$

Once we have determined the number of generalized eigenvectors of each rank that a canonical basis has, we can obtain the vectors explicitly (see generalized eigenvector).

Example

This example illustrates a canonical basis with two Jordan chains. Unfortunately, it is a little difficult to construct an interesting example of low order. The matrix

${\displaystyle A=\left(\begin{array}{cccccc}4& 1& 1& 0& 0& -1\\ 0& 4& 2& 0& 0& 1\\ 0& 0& 4& 1& 0& 0\\ 0& 0& 0& 5& 1& 0\\ 0& 0& 0& 0& 5& 2\\ 0& 0& 0& 0& 0& 4\end{array}\right)}$

has eigenvalues ${\displaystyle {\lambda }_1=4}$ and ${\displaystyle {\lambda }_2=5}$ with algebraic multiplicities ${\displaystyle {\mu }_1=4}$ and ${\displaystyle {\mu }_2=2}$, but geometric multiplicities ${\displaystyle {\gamma }_1=1}$ and ${\displaystyle {\gamma }_2=1}$.

For ${\displaystyle {\lambda }_1=4,}$ we have ${\displaystyle n-{\mu }_1=6-4=2,}$

${\displaystyle (A-4I)}$ has rank 5,

${\displaystyle (A-4I{)}^2}$ has rank 4,

${\displaystyle (A-4I{)}^3}$ has rank 3,

${\displaystyle (A-4I{)}^4}$ has rank 2.

Therefore ${\displaystyle m_1=4.}$

${\displaystyle {\rho }_4=\mathrm{rank}(A-4I{)}^3-\mathrm{rank}(A-4I{)}^4=3-2=1,}$

${\displaystyle {\rho }_3=\mathrm{rank}(A-4I{)}^2-\mathrm{rank}(A-4I{)}^3=4-3=1,}$

${\displaystyle {\rho }_2=\mathrm{rank}(A-4I{)}^1-\mathrm{rank}(A-4I{)}^2=5-4=1,}$

${\displaystyle {\rho }_1=\mathrm{rank}(A-4I{)}^0-\mathrm{rank}(A-4I{)}^1=6-5=1.}$

Thus, a canonical basis for ${\displaystyle A}$ will have, corresponding to ${\displaystyle {\lambda }_1=4,}$ one generalized eigenvector each of ranks 4, 3, 2 and 1.

For ${\displaystyle {\lambda }_2=5,}$ we have ${\displaystyle n-{\mu }_2=6-2=4,}$

${\displaystyle (A-5I)}$ has rank 5,

${\displaystyle (A-5I{)}^2}$ has rank 4.

Therefore ${\displaystyle m_2=2.}$

${\displaystyle {\rho }_2=\mathrm{rank}(A-5I{)}^1-\mathrm{rank}(A-5I{)}^2=5-4=1,}$

${\displaystyle {\rho }_1=\mathrm{rank}(A-5I{)}^0-\mathrm{rank}(A-5I{)}^1=6-5=1.}$

Thus, a canonical basis for ${\displaystyle A}$ will have, corresponding to ${\displaystyle {\lambda }_2=5,}$ one generalized eigenvector each of ranks 2 and 1.

A canonical basis for ${\displaystyle A}$ is

${\displaystyle \left\{{\mathbf{x}}_1,{\mathbf{x}}_2,{\mathbf{x}}_3,{\mathbf{x}}_4,{\mathbf{y}}_1,{\mathbf{y}}_2\right\}=\left\{\left(\begin{array}{c}-4\\ 0\\ 0\\ 0\\ 0\\ 0\end{array}\right),\left(\begin{array}{c}-27\\ -4\\ 0\\ 0\\ 0\\ 0\end{array}\right),\left(\begin{array}{c}25\\ -25\\ -2\\ 0\\ 0\\ 0\end{array}\right),\left(\begin{array}{c}0\\ 36\\ -12\\ -2\\ 2\\ -1\end{array}\right),\left(\begin{array}{c}3\\ 2\\ 1\\ 1\\ 0\\ 0\end{array}\right),\left(\begin{array}{c}-8\\ -4\\ -1\\ 0\\ 1\\ 0\end{array}\right)\right\}.}$

${\displaystyle {\mathbf{x}}_1}$ is the ordinary eigenvector associated with ${\displaystyle {\lambda }_1}$. ${\displaystyle {\mathbf{x}}_2,{\mathbf{x}}_3}$ and ${\displaystyle {\mathbf{x}}_4}$ are generalized eigenvectors associated with ${\displaystyle {\lambda }_1}$. ${\displaystyle {\mathbf{y}}_1}$ is the ordinary eigenvector associated with ${\displaystyle {\lambda }_2}$. ${\displaystyle {\mathbf{y}}_2}$ is a generalized eigenvector associated with ${\displaystyle {\lambda }_2}$.

A matrix ${\displaystyle J}$ in Jordan normal form, similar to ${\displaystyle A}$ is obtained as follows:

${\displaystyle M=\left(\begin{array}{cccccc}{\mathbf{x}}_1& {\mathbf{x}}_2& {\mathbf{x}}_3& {\mathbf{x}}_4& {\mathbf{y}}_1& {\mathbf{y}}_2\end{array}\right)=\left(\begin{array}{cccccc}-4& -27& 25& 0& 3& -8\\ 0& -4& -25& 36& 2& -4\\ 0& 0& -2& -12& 1& -1\\ 0& 0& 0& -2& 1& 0\\ 0& 0& 0& 2& 0& 1\\ 0& 0& 0& -1& 0& 0\end{array}\right),}$

${\displaystyle J=\left(\begin{array}{cccccc}4& 1& 0& 0& 0& 0\\ 0& 4& 1& 0& 0& 0\\ 0& 0& 4& 1& 0& 0\\ 0& 0& 0& 4& 0& 0\\ 0& 0& 0& 0& 5& 1\\ 0& 0& 0& 0& 0& 5\end{array}\right),}$

where the matrix ${\displaystyle M}$ is a generalized modal matrix for ${\displaystyle A}$ and ${\displaystyle AM=MJ}$.