Editing Canonical basis (section)

==Linear algebra==
If we are given an ''n'' × ''n'' [[matrix (mathematics)|matrix]] <math>A</math> and wish to find a matrix <math>J</math> in [[Jordan normal form]], [[matrix similarity|similar]] to <math>A</math>, 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]] <math>D</math> is a special case of a matrix in Jordan normal form.  An [[eigenvector|ordinary eigenvector]] is a special case of a generalized eigenvector.

Every ''n'' × ''n'' matrix <math>A</math> possesses ''n'' linearly independent generalized eigenvectors.  Generalized eigenvectors corresponding to distinct [[eigenvalues]] are linearly independent.  If <math>\lambda</math> is an eigenvalue of <math>A</math> of [[algebraic multiplicity]] <math>\mu</math>, then <math>A</math> will have <math>\mu</math> linearly independent generalized eigenvectors corresponding to <math>\lambda</math>.

For any given ''n'' × ''n'' matrix <math>A</math>, 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 <math>A</math> 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 [[generalized eigenvector#Overview and definition|rank]] ''m'' is in a canonical basis, it follows that the ''m'' − 1 vectors <math> \mathbf x_{m-1}, \mathbf x_{m-2}, \ldots , \mathbf x_1 </math> that are in the Jordan chain generated by <math> \mathbf x_m </math> are also in the canonical basis.<ref>{{harvtxt|Bronson|1970|pp=196,197}}</ref>

===Computation===
Let <math> \lambda_i </math> be an eigenvalue of <math>A</math> of algebraic multiplicity <math> \mu_i </math>.  First, find the [[rank (linear algebra)|ranks]] (matrix ranks) of the matrices <math> (A - \lambda_i I), (A - \lambda_i I)^2, \ldots , (A - \lambda_i I)^{m_i} </math>.  The integer <math>m_i</math> is determined to be the ''first integer'' for which <math> (A - \lambda_i I)^{m_i} </math> has rank <math>n - \mu_i </math> (''n'' being the number of rows or columns of <math>A</math>, that is, <math>A</math> is ''n'' × ''n'').

Now define

:<math> \rho_k = \operatorname{rank}(A - \lambda_i I)^{k-1} - \operatorname{rank}(A - \lambda_i I)^k \qquad (k = 1, 2, \ldots , m_i).</math>

The variable <math> \rho_k </math> designates the number of linearly independent generalized eigenvectors of rank ''k'' (generalized eigenvector rank; see [[generalized eigenvector#Overview and definition|generalized eigenvector]]) corresponding to the eigenvalue <math> \lambda_i </math> that will appear in a canonical basis for <math>A</math>.  Note that

:<math> \operatorname{rank}(A - \lambda_i I)^0 = \operatorname{rank}(I) = n .</math>

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#Computation of generalized eigenvectors|generalized eigenvector]]).<ref>{{harvtxt|Bronson|1970|pp=197,198}}</ref>

===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.<ref>{{harvtxt|Nering|1970|pp=122,123}}</ref>
The matrix

:<math>A = \begin{pmatrix} 
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{pmatrix}</math>

has eigenvalues <math> \lambda_1 = 4 </math> and <math> \lambda_2 = 5 </math> with algebraic multiplicities <math> \mu_1 = 4 </math> and <math> \mu_2 = 2 </math>, but [[geometric multiplicity|geometric multiplicities]] <math> \gamma_1 = 1 </math> and <math> \gamma_2 = 1 </math>.

For <math> \lambda_1 = 4,</math> we have <math> n - \mu_1 = 6 - 4 = 2, </math>

:<math> (A - 4I) </math> has rank 5,
:<math> (A - 4I)^2 </math> has rank 4,
:<math> (A - 4I)^3 </math> has rank 3,
:<math> (A - 4I)^4 </math> has rank 2.

Therefore <math>m_1 = 4.</math>

:<math> \rho_4 = \operatorname{rank}(A - 4I)^3 - \operatorname{rank}(A - 4I)^4 = 3 - 2 = 1,</math>
:<math> \rho_3 = \operatorname{rank}(A - 4I)^2 - \operatorname{rank}(A - 4I)^3 = 4 - 3 = 1,</math>
:<math> \rho_2 = \operatorname{rank}(A - 4I)^1 - \operatorname{rank}(A - 4I)^2 = 5 - 4 = 1,</math>
:<math> \rho_1 = \operatorname{rank}(A - 4I)^0 - \operatorname{rank}(A - 4I)^1 = 6 - 5 = 1.</math>

Thus, a canonical basis for <math>A</math> will have, corresponding to <math> \lambda_1 = 4,</math> one generalized eigenvector each of ranks 4, 3, 2 and 1.

For <math> \lambda_2 = 5,</math> we have <math> n - \mu_2 = 6 - 2 = 4, </math>

:<math> (A - 5I) </math> has rank 5,
:<math> (A - 5I)^2 </math> has rank 4.

Therefore <math>m_2 = 2.</math>

:<math> \rho_2 = \operatorname{rank}(A - 5I)^1 - \operatorname{rank}(A - 5I)^2 = 5 - 4 = 1,</math>
:<math> \rho_1 = \operatorname{rank}(A - 5I)^0 - \operatorname{rank}(A - 5I)^1 = 6 - 5 = 1.</math>

Thus, a canonical basis for <math>A</math> will have, corresponding to <math> \lambda_2 = 5,</math> one generalized eigenvector each of ranks 2 and 1.

A canonical basis for <math>A</math> is

:<math>
\left\{ \mathbf x_1, \mathbf x_2, \mathbf x_3, \mathbf x_4, \mathbf y_1, \mathbf y_2 \right\} =
\left\{
\begin{pmatrix} -4 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix},
\begin{pmatrix} -27 \\ -4 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix},
\begin{pmatrix} 25 \\ -25 \\ -2 \\ 0 \\ 0 \\ 0 \end{pmatrix},
\begin{pmatrix} 0 \\ 36 \\ -12 \\ -2 \\ 2 \\ -1 \end{pmatrix},
\begin{pmatrix} 3 \\ 2 \\ 1 \\ 1 \\ 0 \\ 0 \end{pmatrix},
\begin{pmatrix} -8 \\ -4 \\ -1 \\ 0 \\ 1 \\ 0 \end{pmatrix} 
\right\}.
</math>

<math> \mathbf x_1 </math> is the ordinary eigenvector associated with <math> \lambda_1 </math>.  
<math> \mathbf x_2, \mathbf x_3 </math> and <math> \mathbf x_4 </math> are generalized eigenvectors associated with <math> \lambda_1 </math>.  
<math> \mathbf y_1 </math> is the ordinary eigenvector associated with <math> \lambda_2 </math>.  
<math> \mathbf y_2 </math> is a generalized eigenvector associated with <math> \lambda_2 </math>.

A matrix <math>J</math> in Jordan normal form, similar to <math>A</math> is obtained as follows:

:<math>
M =
\begin{pmatrix} \mathbf x_1 & \mathbf x_2 & \mathbf x_3 & \mathbf x_4 & \mathbf y_1 & \mathbf y_2 \end{pmatrix} =
\begin{pmatrix}
-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{pmatrix},
</math>
:<math> J = \begin{pmatrix}
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{pmatrix},
</math>

where the matrix <math>M</math> is a [[generalized modal matrix]] for <math>A</math> and <math>AM = MJ</math>.<ref>{{harvtxt|Bronson|1970|p=203}}</ref>