View source for Generalized eigenvector

{{Short description|Vector satisfying some of the criteria of an eigenvector}}
{{Distinguish|Generalized eigenvalue problem}}

In [[linear algebra]], a '''generalized eigenvector''' of an ''n'' × ''n'' [[matrix (mathematics)|matrix]] <math>A</math> is a [[vector (mathematics and physics)|vector]] which satisfies certain criteria which are more relaxed than those for an (ordinary) [[eigenvector]].<ref>{{harvtxt|Bronson|1970|p=189}}</ref>

Let <math>V</math> be an ''n''-dimensional [[vector space]]; let <math>\phi</math> be a [[linear map]] in {{math|''L''(''V'')}}, the set of all linear maps from <math>V</math> into itself; and let <math>A</math> be the [[Linear map#Examples|matrix representation]] of <math>\phi</math> with respect to some ordered [[basis (linear algebra)|basis]].

There may not always exist a full set of ''n'' [[linear independence|linearly independent]] eigenvectors of <math>A</math> that form a complete basis for <math>V</math>.  That is, the matrix <math>A</math> may not be [[diagonalizable matrix|diagonalizable]].<ref>{{harvtxt|Beauregard|Fraleigh|1973|p=310}}</ref><ref>{{harvtxt|Nering|1970|p=118}}</ref>  This happens when the [[algebraic multiplicity]] of at least one [[eigenvalue]] <math>\lambda_i</math> is greater than its [[geometric multiplicity]] (the [[kernel (linear algebra)#Representation as matrix multiplication|nullity]] of the matrix <math>(A-\lambda_i I)</math>, or the [[dimension (vector space)|dimension]] of its [[kernel (linear algebra)|nullspace]]).  In this case, <math>\lambda_i</math> is called a [[defective eigenvalue]] and <math>A</math> is called a [[defective matrix]].<ref>{{harvtxt|Golub|Van Loan|1996|p=316}}</ref>

A generalized eigenvector <math>x_i</math> corresponding to <math>\lambda_i</math>, together with the matrix <math>(A-\lambda_i I)</math> generate a Jordan chain of linearly independent generalized eigenvectors which form a basis for an [[invariant subspace]] of <math>V</math>.<ref>{{harvtxt|Beauregard|Fraleigh|1973|p=319}}</ref><ref>{{harvtxt|Bronson|1970|pp=194–195}}</ref><ref>{{harvtxt|Golub|Van Loan|1996|p=311}}</ref>

Using generalized eigenvectors, a set of linearly independent eigenvectors of <math>A</math> can be extended, if necessary, to a complete basis for <math>V</math>.<ref>{{harvtxt|Bronson|1970|p=196}}</ref>  This basis can be used to determine an "almost diagonal matrix" <math>J</math> in [[Jordan normal form]], [[matrix similarity|similar]] to <math>A</math>, which is useful in computing certain [[matrix function]]s of <math>A</math>.<ref>{{harvtxt|Bronson|1970|p=189}}</ref>  The matrix <math>J</math> is also useful in solving the [[Ordinary differential equation#System of ODEs|system of linear differential equations]] <math>\mathbf x' = A \mathbf x,</math> where <math>A</math> need not be diagonalizable.<ref>{{harvtxt|Beauregard|Fraleigh|1973|pp=316–318}}</ref><ref>{{harvtxt|Nering|1970|p=118}}</ref>

== Overview and definition ==
There are several equivalent ways to define an '''ordinary eigenvector'''.<ref>{{harvtxt|Anton|1987|pp=301–302}}</ref><ref>{{harvtxt|Beauregard|Fraleigh|1973|p=266}}</ref><ref>{{harvtxt|Burden|Faires|1993|p=401}}</ref><ref>{{harvtxt|Golub|Van Loan|1996|pp=310–311}}</ref><ref>{{harvtxt|Harper|1976|p=58}}</ref><ref>{{harvtxt|Herstein|1964|p=225}}</ref><ref>{{harvtxt|Kreyszig|1972|pp=273,684}}</ref><ref>{{harvtxt|Nering|1970|p=104}}</ref>  For our purposes, an eigenvector <math>\mathbf u</math> associated with an eigenvalue <math>\lambda</math> of an <math>n</math> × <math>n</math> matrix <math>A</math> is a nonzero vector for which <math>(A - \lambda I) \mathbf u = \mathbf 0</math>, where <math>I</math> is the <math>n</math> × <math>n</math> [[identity matrix]] and <math>\mathbf 0</math> is the [[zero vector]] of length <math>n</math>.<ref>{{harvtxt|Burden|Faires|1993|p=401}}</ref>  That is, <math>\mathbf u</math> is in the [[kernel (linear algebra)|kernel]] of the [[linear transformation|transformation]] <math>(A - \lambda I)</math>.  If <math>A</math> has <math>n</math> linearly independent eigenvectors, then <math>A</math> is similar to a diagonal matrix <math>D</math>.  That is, there exists an [[invertible matrix]] <math>M</math> such that <math>A</math> is diagonalizable through the similarity transformation <math>D = M^{-1}AM</math>.<ref>{{harvtxt|Beauregard|Fraleigh|1973|pp=270–274}}</ref><ref>{{harvtxt|Bronson|1970|pp=179–183}}</ref>  The matrix <math>D</math> is called a [[spectral matrix]] for <math>A</math>.  The matrix <math>M</math> is called a [[modal matrix]] for <math>A</math>.<ref>{{harvtxt|Bronson|1970|p=181}}</ref>  Diagonalizable matrices are of particular interest since matrix functions of them can be computed easily.<ref>{{harvtxt|Bronson|1970|p=179}}</ref>

On the other hand, if <math>A</math> does not have <math>n</math> linearly independent eigenvectors associated with it, then <math>A</math> is not diagonalizable.<ref>{{harvtxt|Beauregard|Fraleigh|1973|pp=270–274}}</ref><ref>{{harvtxt|Bronson|1970|pp=179–183}}</ref>

'''Definition:'''  A vector <math>\mathbf x_m</math> is a '''generalized eigenvector of rank ''m''''' of the matrix <math>A</math> and corresponding to the eigenvalue <math>\lambda</math> if

:<math>(A - \lambda I)^m \mathbf x_m = \mathbf 0</math>

but

:<math>(A - \lambda I)^{m-1} \mathbf x_m \ne \mathbf 0.</math> <ref>{{harvtxt|Bronson|1970|p=189}}</ref>

Clearly, a generalized eigenvector of rank 1 is an ordinary eigenvector.<ref>{{harvtxt|Bronson|1970|pp=190,202}}</ref>  Every <math>n</math> × <math>n</math> matrix <math>A</math> has <math>n</math> linearly independent generalized eigenvectors associated with it and can be shown to be similar to an "almost diagonal" matrix <math>J</math> in Jordan normal form.<ref>{{harvtxt|Bronson|1970|pp=189,203}}</ref>  That is, there exists an invertible matrix <math>M</math> such that <math>J = M^{-1}AM</math>.<ref>{{harvtxt|Bronson|1970|pp=206–207}}</ref>  The matrix <math>M</math> in this case is called a [[generalized modal matrix]] for <math>A</math>.<ref>{{harvtxt|Bronson|1970|p=205}}</ref>  If <math>\lambda</math> is an eigenvalue of algebraic multiplicity <math>\mu</math>, then <math>A</math> will have <math>\mu</math> linearly independent generalized eigenvectors corresponding to <math>\lambda</math>.<ref>{{harvtxt|Bronson|1970|p=196}}</ref>  These results, in turn, provide a straightforward method for computing certain matrix functions of <math>A</math>.<ref>{{harvtxt|Bronson|1970|pp=189,209–215}}</ref>

{{anchor|Note}}Note:  For an <math>n \times n</math> matrix <math>A</math> over a [[Field (mathematics)|field]] <math>F</math> to be expressed in Jordan normal form, all eigenvalues of <math>A</math> must be in <math>F</math>.  That is, the [[characteristic polynomial]] <math>f(x)</math> must factor completely into linear factors.  For example, if <math>A</math> has [[Real number|real-valued]] elements, then it may be necessary for the eigenvalues and the components of the eigenvectors to have [[Complex number|complex values]].<ref>{{harvtxt|Golub|Van Loan|1996|p=316}}</ref><ref>{{harvtxt|Herstein|1964|p=259}}</ref><ref>{{harvtxt|Nering|1970|p=118}}</ref>

The set [[Linear span#Definition|spanned]] by all generalized eigenvectors for a given <math> \lambda </math>, forms the '''generalized eigenspace''' for <math> \lambda </math>.<ref>{{harvtxt|Nering|1970|p=118}}</ref>

==Examples==
Here are some examples to illustrate the concept of generalized eigenvectors.  Some of the details will be described later.

===Example 1===
This example is simple but clearly illustrates the point.  This type of matrix is used frequently in textbooks.<ref>{{harvtxt|Nering|1970|p=118}}</ref><ref>{{harvtxt|Herstein|1964|p=261}}</ref><ref>{{harvtxt|Beauregard|Fraleigh|1973|p=310}}</ref>
Suppose
:<math> A = \begin{pmatrix} 1 & 1\\ 0 & 1 \end{pmatrix}. </math>
Then there is only one eigenvalue, <math> \lambda = 1</math>, and its algebraic multiplicity is ''m'' = 2.

Notice that this matrix is in Jordan normal form but is not [[diagonal matrix|diagonal]]. Hence, this matrix is not diagonalizable.  Since there is one [[superdiagonal]] entry, there will be one generalized eigenvector of rank greater than 1 (or one could note that the vector space <math> V </math> is of dimension 2, so there can be at most one generalized eigenvector of rank greater than 1).  Alternatively, one could compute the dimension of the [[nullspace]] of  <math> A - \lambda I </math> to be ''p'' = 1, and thus there are ''m'' – ''p'' = 1 generalized eigenvectors of rank greater than 1.

The ordinary eigenvector <math> \mathbf v_1=\begin{pmatrix}1 \\0 \end{pmatrix}</math> is computed as usual (see the [[Eigenvalues and eigenvectors#Calculation|eigenvector]] page for examples).  Using this eigenvector, we compute the generalized eigenvector  <math> \mathbf v_2 </math> by solving

:<math> (A-\lambda I) \mathbf v_2 = \mathbf v_1. </math>
Writing out the values:
:<math> \left(\begin{pmatrix} 1 & 1\\ 0 & 1 \end{pmatrix} - 1 \begin{pmatrix} 1 & 0\\ 0 & 1 \end{pmatrix}\right)\begin{pmatrix}v_{21} \\v_{22} \end{pmatrix} = \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix}v_{21} \\v_{22} \end{pmatrix} =
\begin{pmatrix}1 \\0 \end{pmatrix}.</math>
This simplifies to

:<math> v_{22}= 1. </math>

The element <math>v_{21}</math> has no restrictions. The generalized eigenvector of rank 2 is then <math> \mathbf v_2=\begin{pmatrix}a \\1 \end{pmatrix}</math>, where ''a'' can have any scalar value.  The choice of ''a'' = 0 is usually the simplest.

Note that

:<math> (A-\lambda I) \mathbf v_2 =  \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix}a \\1 \end{pmatrix} =
\begin{pmatrix}1 \\0 \end{pmatrix} = \mathbf v_1,</math>

so that <math> \mathbf v_2 </math> is a generalized eigenvector,

:<math> (A-\lambda I) \mathbf v_1 =  \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix}1 \\0 \end{pmatrix} =
\begin{pmatrix}0 \\0 \end{pmatrix} = \mathbf 0,</math>

so that <math> \mathbf v_1 </math> is an ordinary eigenvector, and that <math> \mathbf v_1</math> and <math> \mathbf v_2</math> are linearly independent and hence constitute a basis for the vector space <math> V </math>.

===Example 2===
This example is more complex than [[Generalized eigenvector#Example 1|Example 1]].  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} 
1 & 0 & 0 & 0 & 0 \\
3 & 1 & 0 & 0 & 0 \\
6 & 3 & 2 & 0 & 0 \\
10 & 6 & 3 & 2 & 0 \\
15 & 10 & 6 & 3 & 2
\end{pmatrix}</math>

has ''eigenvalues'' <math> \lambda_1 = 1 </math> and <math> \lambda_2 = 2 </math> with ''algebraic multiplicities'' <math> \mu_1 = 2 </math> and <math> \mu_2 = 3 </math>, but ''geometric multiplicities'' <math> \gamma_1 = 1 </math> and <math> \gamma_2 = 1</math>.

The ''generalized eigenspaces'' of <math>A</math> are calculated below.
<math> \mathbf x_1 </math> is the ordinary eigenvector associated with <math> \lambda_1 </math>.
<math> \mathbf x_2 </math> is a generalized eigenvector 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> and <math> \mathbf y_3 </math> are generalized eigenvectors associated with <math> \lambda_2 </math>.

:<math>(A-1 I) \mathbf x_1
 = \begin{pmatrix} 
0 & 0 & 0 & 0 & 0 \\
3 & 0 & 0 & 0 & 0 \\
6 & 3 & 1 & 0 & 0 \\
10 & 6 & 3 & 1 & 0 \\
15 & 10 & 6 & 3 & 1
\end{pmatrix}\begin{pmatrix}
0 \\ 3 \\ -9 \\ 9 \\ -3
\end{pmatrix} = \begin{pmatrix}
0 \\ 0 \\ 0 \\ 0 \\ 0
\end{pmatrix} = \mathbf 0 ,</math>

:<math>(A - 1 I) \mathbf x_2
 = \begin{pmatrix} 
0 & 0 & 0 & 0 & 0 \\
3 & 0 & 0 & 0 & 0 \\
6 & 3 & 1 & 0 & 0 \\
10 & 6 & 3 & 1 & 0 \\
15 & 10 & 6 & 3 & 1
\end{pmatrix} \begin{pmatrix}
1 \\ -15 \\ 30 \\ -1 \\ -45
\end{pmatrix} = \begin{pmatrix}
0 \\ 3 \\ -9 \\ 9 \\ -3
\end{pmatrix} = \mathbf x_1 ,</math>

:<math>(A - 2 I) \mathbf y_1
 = \begin{pmatrix} 
-1 & 0 & 0 & 0 & 0 \\
3 & -1 & 0 & 0 & 0 \\
6 & 3 & 0 & 0 & 0 \\
10 & 6 & 3 & 0 & 0 \\
15 & 10 & 6 & 3 & 0
\end{pmatrix} \begin{pmatrix}
0 \\ 0 \\ 0 \\ 0 \\ 9
\end{pmatrix} = \begin{pmatrix}
0 \\ 0 \\ 0 \\ 0 \\ 0
\end{pmatrix} = \mathbf 0 ,</math>

:<math>(A - 2 I) \mathbf y_2 = \begin{pmatrix} 
-1 & 0 & 0 & 0 & 0 \\
3 & -1 & 0 & 0 & 0 \\
6 & 3 & 0 & 0 & 0 \\
10 & 6 & 3 & 0 & 0 \\
15 & 10 & 6 & 3 & 0
\end{pmatrix} \begin{pmatrix}
0 \\ 0 \\ 0 \\ 3 \\ 0
\end{pmatrix} = \begin{pmatrix}
0 \\ 0 \\ 0 \\ 0 \\ 9
\end{pmatrix} = \mathbf y_1 ,</math>

:<math>(A - 2 I) \mathbf y_3 = \begin{pmatrix} 
-1 & 0 & 0 & 0 & 0 \\
3 & -1 & 0 & 0 & 0 \\
6 & 3 & 0 & 0 & 0 \\
10 & 6 & 3 & 0 & 0 \\
15 & 10 & 6 & 3 & 0
\end{pmatrix} \begin{pmatrix}
0 \\ 0 \\ 1 \\ -2 \\ 0
\end{pmatrix} = \begin{pmatrix}
0 \\ 0 \\ 0 \\ 3 \\ 0
\end{pmatrix} = \mathbf y_2 .</math>

This results in a basis for each of the ''generalized eigenspaces'' of <math>A</math>.
Together the two ''chains'' of generalized eigenvectors span the space of all 5-dimensional column vectors.

:<math>
\left\{ \mathbf x_1, \mathbf x_2 \right\} =
\left\{
\begin{pmatrix} 0 \\ 3 \\ -9 \\ 9 \\ -3 \end{pmatrix}
\begin{pmatrix} 1 \\ -15 \\ 30 \\ -1 \\ -45 \end{pmatrix} 
\right\},
\left\{ \mathbf y_1, \mathbf y_2, \mathbf y_3 \right\} =
\left\{ 
\begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 9 \end{pmatrix}
\begin{pmatrix} 0 \\ 0 \\ 0 \\ 3 \\ 0 \end{pmatrix}
\begin{pmatrix} 0 \\ 0 \\ 1 \\ -2 \\ 0 \end{pmatrix}
\right\}.
</math>

An "almost diagonal" 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 y_1 & \mathbf y_2 & \mathbf y_3 \end{pmatrix} =
\begin{pmatrix}
0 &  1 & 0 &0& 0 \\
3 &  -15 & 0 &0& 0 \\
-9 &  30 & 0 &0& 1 \\
9 &  -1 & 0 &3& -2 \\
-3 &  -45 & 9 &0& 0
\end{pmatrix},</math>
:<math>J = \begin{pmatrix}
1 & 1 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 \\
0 & 0 & 2 & 1 & 0 \\
0 & 0 & 0 & 2 & 1 \\
0 & 0 & 0 & 0 & 2
\end{pmatrix},
</math>

where <math>M</math> is a [[generalized modal matrix]] for <math>A</math>, the columns of <math>M</math> are a [[Canonical basis#Linear algebra|canonical basis]] for <math>A</math>, and <math>AM = MJ</math>.<ref>{{harvtxt|Bronson|1970|pp=189–209}}</ref>

== Jordan chains ==
'''Definition:'''  Let <math>\mathbf x_m</math> be a generalized eigenvector of rank ''m'' corresponding to the matrix <math>A</math> and the eigenvalue <math>\lambda</math>.  The '''chain generated by''' <math>\mathbf x_m</math> is a set of vectors <math>\left\{ \mathbf x_m, \mathbf x_{m-1}, \dots , \mathbf x_1 \right\}</math> given by

:{{NumBlk|:|
<math> \mathbf x_{m-1} = (A - \lambda I) \mathbf x_m, </math><br>
<math> \mathbf x_{m-2} = (A - \lambda I)^2 \mathbf x_m = (A - \lambda I) \mathbf x_{m-1}, </math><br>
<math> \mathbf x_{m-3} = (A - \lambda I)^3 \mathbf x_m = (A - \lambda I) \mathbf x_{m-2}, </math><br>
::<math> \vdots </math>
<math> \mathbf x_1 = (A - \lambda I)^{m-1} \mathbf x_m = (A - \lambda I) \mathbf x_2. </math>
|{{EquationRef|1}}}}

Thus, in general,

:{{NumBlk|:|<math> \mathbf x_j = (A - \lambda I)^{m-j} \mathbf x_m = (A - \lambda I) \mathbf x_{j+1} \qquad (j = 1, 2, \dots , m - 1). </math>|{{EquationRef|2}}}}

The vector <math>\mathbf x_j </math>, given by ({{EquationNote|2}}), is a generalized eigenvector of rank ''j'' corresponding to the eigenvalue <math>\lambda</math>.  A chain is a linearly independent set of vectors.<ref>{{harvtxt|Bronson|1970|pp=194–195}}</ref>

== Canonical basis ==
{{Main|Canonical basis#Linear algebra}}
'''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 <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>

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 = rank(A - \lambda_i I)^{k-1} - 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'' corresponding to the eigenvalue <math> \lambda_i </math> that will appear in a canonical basis for <math>A</math>.  Note that

:<math> rank(A - \lambda_i I)^0 = rank(I) = n </math>.<ref>{{harvtxt|Bronson|1970|pp=197,198}}</ref>

== Computation of generalized eigenvectors ==
In the preceding sections we have seen techniques for obtaining the ''n'' linearly independent generalized eigenvectors of a canonical basis for the vector space <math>V</math> associated with an ''n'' × ''n'' matrix <math>A</math>.  These techniques can be combined into a procedure:

:Solve the [[characteristic polynomial|characteristic equation]] of <math>A</math> for eigenvalues <math> \lambda_i </math> and their algebraic multiplicities <math> \mu_i </math>;
:For each <math> \lambda_i :</math>
::Determine <math>n - \mu_i</math>;
::Determine <math>m_i</math>;
::Determine <math>\rho_k</math> for <math>(k = 1, \ldots , m_i)</math>;
::Determine each Jordan chain for <math>\lambda_i</math>;

=== Example 3 ===
The matrix

:<math>
A = 
\begin{pmatrix}
 5 &  1 & -2 &  4 \\
 0 &  5 &  2 &  2 \\
 0 &  0 &  5 &  3 \\
 0 &  0 &  0 &  4
\end{pmatrix}
</math>

has an eigenvalue <math>\lambda_1 = 5</math> of algebraic multiplicity <math>\mu_1 = 3</math> and an eigenvalue <math>\lambda_2 = 4</math> of algebraic multiplicity <math>\mu_2 = 1</math>.  We also have ''n'' = 4.  For <math>\lambda_1</math> we have <math>n - \mu_1 = 4 - 3 = 1</math>.

:<math>
(A - 5I) =
\begin{pmatrix}
 0 &  1 & -2 &  4 \\
 0 &  0 &  2 &  2 \\
 0 &  0 &  0 &  3 \\
 0 &  0 &  0 & -1
\end{pmatrix},
\qquad rank(A - 5I) = 3.
</math>
:<math>
(A - 5I)^2 =
\begin{pmatrix}
 0 &  0 &  2 & -8 \\
 0 &  0 &  0 &  4 \\
 0 &  0 &  0 & -3 \\
 0 &  0 &  0 &  1
\end{pmatrix},
\qquad rank(A - 5I)^2 = 2.
</math>
:<math>
(A - 5I)^3 =
\begin{pmatrix}
0 &  0 &  0 & 14 \\
 0 &  0 &  0 & -4 \\
 0 &  0 &  0 &  3 \\
 0 &  0 &  0 & -1
\end{pmatrix},
\qquad rank(A - 5I)^3 = 1.
</math>

The first integer <math>m_1</math> for which <math>(A - 5I)^{m_1}</math> has rank <math>n - \mu_1 = 1</math> is <math>m_1 = 3</math>.

We now define

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

Consequently, there will be three linearly independent generalized eigenvectors; one each of ranks 3, 2 and 1.  Since <math>\lambda_1</math> corresponds to a single chain of three linearly independent generalized eigenvectors, we know that there is a generalized eigenvector <math> \mathbf x_3 </math> of rank 3 corresponding to <math>\lambda_1</math> such that

::{{NumBlk|:|<math>(A - 5I)^3 \mathbf x_3 = \mathbf 0</math>|{{EquationRef|3}}}}

but

::{{NumBlk|:|<math>(A - 5I)^2 \mathbf x_3\neq \mathbf 0 .</math>|{{EquationRef|4}}}}

Equations ({{EquationNote|3}}) and ({{EquationNote|4}}) represent [[system of linear equations|linear systems]] that can be solved for <math> \mathbf x_3 </math>.  Let

:<math>
\mathbf x_3 = 
\begin{pmatrix}
x_{31} \\
x_{32} \\
x_{33} \\
x_{34}
\end{pmatrix}.
</math>

Then

:<math>
(A - 5I)^3 \mathbf x_3 = 
\begin{pmatrix}
 0 &  0 &  0 & 14 \\
 0 &  0 &  0 & -4 \\
 0 &  0 &  0 &  3 \\
 0 &  0 &  0 & -1
\end{pmatrix}
\begin{pmatrix}
x_{31} \\
x_{32} \\
x_{33} \\
x_{34}
\end{pmatrix} = 
\begin{pmatrix}
14 x_{34} \\
-4 x_{34} \\
 3 x_{34} \\
-  x_{34}
\end{pmatrix} = 
\begin{pmatrix}
 0 \\
 0 \\
 0 \\
 0
\end{pmatrix}
</math>

and

:<math>
(A - 5I)^2 \mathbf x_3 = 
\begin{pmatrix}
 0 &  0 &  2 & -8 \\
 0 &  0 &  0 &  4 \\
 0 &  0 &  0 & -3 \\
 0 &  0 &  0 &  1
\end{pmatrix}
\begin{pmatrix}
x_{31} \\
x_{32} \\
x_{33} \\
x_{34}
\end{pmatrix} = 
\begin{pmatrix}
 2 x_{33} - 8 x_{34} \\
 4 x_{34} \\
-3 x_{34} \\
    x_{34}
\end{pmatrix} \ne 
\begin{pmatrix}
 0 \\
 0 \\
 0 \\
 0
\end{pmatrix}.
</math>

Thus, in order to satisfy the conditions ({{EquationNote|3}}) and ({{EquationNote|4}}), we must have <math>x_{34} = 0</math> and <math>x_{33} \ne 0</math>.  No restrictions are placed on <math>x_{31}</math> and <math>x_{32}</math>.  By choosing <math>x_{31} = x_{32} = x_{34} = 0, x_{33} = 1</math>, we obtain

:<math>
\mathbf x_3 = 
\begin{pmatrix}
0 \\
 0 \\
 1 \\
 0
\end{pmatrix}
</math>

as a generalized eigenvector of rank 3 corresponding to <math> \lambda_1 = 5 </math>.  Note that it is possible to obtain infinitely many other generalized eigenvectors of rank 3 by choosing different values of  <math>x_{31}</math>, <math>x_{32}</math> and <math>x_{33}</math>, with <math>x_{33} \ne 0</math>.  Our first choice, however, is the simplest.<ref>{{harvtxt|Bronson|1970|pp=190–191}}</ref>

Now using equations ({{EquationNote|1}}), we obtain <math> \mathbf x_2 </math> and <math> \mathbf x_1 </math> as generalized eigenvectors of rank 2 and 1 respectively, where

:<math>
\mathbf x_2 = (A - 5I) \mathbf x_3 = 
\begin{pmatrix}
-2 \\
 2 \\
 0 \\
 0
\end{pmatrix},
</math>

and

:<math>
\mathbf x_1 = (A - 5I) \mathbf x_2 = 
\begin{pmatrix}
 2 \\
 0 \\
 0 \\
 0
\end{pmatrix}.
</math>

The [[simple eigenvalue]] <math>\lambda_2 = 4</math> can be dealt with using [[Eigenvalues and eigenvectors#Calculation|standard techniques]] and has an ordinary eigenvector

:<math>
\mathbf y_1 = 
\begin{pmatrix}
-14 \\
  4 \\
 -3 \\
  1
\end{pmatrix}.
</math>

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

:<math>
\left\{ \mathbf x_3, \mathbf x_2, \mathbf x_1, \mathbf y_1 \right\} =
\left\{
\begin{pmatrix} 0 \\ 0 \\ 1 \\ 0 \end{pmatrix}
\begin{pmatrix} -2 \\ 2 \\ 0 \\ 0 \end{pmatrix}
\begin{pmatrix} 2 \\ 0 \\ 0 \\ 0 \end{pmatrix}
\begin{pmatrix} -14 \\ 4 \\ -3 \\ 1 \end{pmatrix}
\right\}.
</math>

<math> \mathbf x_1, \mathbf x_2 </math> and <math> \mathbf x_3 </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>.

This is a fairly simple example.  In general, the numbers <math>\rho_k</math> of linearly independent generalized eigenvectors of rank ''k'' will not always be equal.  That is, there may be several chains of different lengths corresponding to a particular eigenvalue.<ref>{{harvtxt|Bronson|1970|pp=197–198}}</ref>

== Generalized modal matrix ==
{{Main|Generalized modal matrix}}
Let <math>A</math> be an ''n'' × ''n'' matrix.  A '''generalized modal matrix''' <math>M</math> for <math>A</math> is an ''n'' × ''n'' matrix whose columns, considered as vectors, form a canonical basis for <math>A</math> and appear in <math>M</math> according to the following rules:

* All Jordan chains consisting of one vector (that is, one vector in length) appear in the first columns of <math>M</math>.
* All vectors of one chain appear together in adjacent columns of <math>M</math>.
* Each chain appears in <math>M</math> in order of increasing rank (that is, the generalized eigenvector of rank 1 appears before the generalized eigenvector of rank 2 of the same chain, which appears before the generalized eigenvector of rank 3 of the same chain, etc.).<ref>{{harvtxt|Bronson|1970|p=205}}</ref>

== Jordan normal form ==
[[File:Jordan blocks.svg|right|thumb|250px|An example of a matrix in Jordan normal form. The grey blocks are called Jordan blocks.]]
{{Main|Jordan normal form}}
Let <math>V</math> be an ''n''-dimensional vector space; let <math>\phi</math> be a linear map in {{math|''L''(''V'')}}, the set of all linear maps from <math>V</math> into itself; and let <math>A</math> be the matrix representation of <math>\phi</math> with respect to some ordered basis.  It can be shown that if the [[characteristic polynomial]] <math>f(\lambda)</math> of <math>A</math> factors into linear factors, so that <math>f(\lambda)</math> has the form

:<math> f(\lambda) = \pm (\lambda - \lambda_1)^{\mu_1}(\lambda - \lambda_2)^{\mu_2} \cdots (\lambda - \lambda_r)^{\mu_r} ,</math>

where <math> \lambda_1, \lambda_2, \ldots , \lambda_r </math> are the distinct eigenvalues of <math>A</math>, then each <math>\mu_i</math> is the algebraic multiplicity of its corresponding eigenvalue <math>\lambda_i</math> and <math>A</math> is similar to a matrix <math>J</math> in '''Jordan normal form''', where each <math>\lambda_i</math> appears <math>\mu_i</math> consecutive times on the diagonal, and the entry directly above each <math>\lambda_i</math> (that is, on the [[superdiagonal]]) is either 0 or 1: the entry above the first occurrence of each <math>\lambda_i</math> is always 0; all other entries on the superdiagonal are 1.  All other entries (that is, off the diagonal and superdiagonal) are 0.  The matrix <math>J</math> is as close as one can come to a diagonalization of <math>A</math>.  If <math>A</math> is diagonalizable, then all entries above the diagonal are zero.<ref>{{harvtxt|Beauregard|Fraleigh|1973|p=311}}</ref>  Note that some textbooks have the ones on the [[subdiagonal]], that is, immediately below the main diagonal instead of on the superdiagonal.  The eigenvalues are still on the main diagonal.<ref>{{harvtxt|Cullen|1966|p=114}}</ref><ref>{{harvtxt|Franklin|1968|p=122}}</ref>

Every ''n'' × ''n'' matrix <math>A</math> is similar to a matrix <math>J</math> in Jordan normal form, obtained through the similarity transformation <math> J = M^{-1}AM </math>, where <math>M</math> is a generalized modal matrix for <math>A</math>.<ref>{{harvtxt|Bronson|1970|p=207}}</ref> (See [[#Note|Note]] above.)

=== Example 4 ===
Find a matrix in Jordan normal form that is similar to

:<math>
A = 
\begin{pmatrix}
 0 &  4 &  2 \\
-3 &  8 &  3 \\
 4 & -8 & -2
\end{pmatrix}.
</math>

'''Solution:'''  The characteristic equation of <math>A</math> is <math>(\lambda - 2)^3 = 0</math>, hence, <math>\lambda = 2</math> is an eigenvalue of algebraic multiplicity three.  Following the procedures of the previous sections, we find that

:<math> rank(A - 2I) = 1</math>

and

:<math>rank(A - 2I)^2 = 0 = n - \mu .</math>

Thus, <math>\rho_2 = 1</math> and <math>\rho_1 = 2</math>, which implies that a canonical basis for <math>A</math> will contain one linearly independent generalized eigenvector of rank 2 and two linearly independent generalized eigenvectors of rank 1, or equivalently, one chain of two vectors <math> \left\{ \mathbf x_2, \mathbf x_1 \right\} </math> and one chain of one vector <math> \left\{ \mathbf y_1 \right\} </math>.  Designating <math> M = \begin{pmatrix} \mathbf y_1 & \mathbf x_1 & \mathbf x_2 \end{pmatrix} </math>, we find that

:<math>
M = 
\begin{pmatrix}
 2 &  2 &  0 \\
 1 &  3 &  0 \\
 0 & -4 &  1
\end{pmatrix},
</math>

and

:<math>
J = 
\begin{pmatrix}
 2 &  0 &  0 \\
 0 &  2 &  1 \\
 0 &  0 &  2
\end{pmatrix},
</math>

where <math>M</math> is a generalized modal matrix for <math>A</math>, the columns of <math>M</math> are a canonical basis for <math>A</math>, and <math>AM = MJ</math>.<ref>{{harvtxt|Bronson|1970|pp=208}}</ref>  Note that since generalized eigenvectors themselves are not unique, and since some of the columns of both <math>M</math> and <math>J</math> may be interchanged, it follows that both <math>M</math> and <math>J</math> are not unique.<ref>{{harvtxt|Bronson|1970|p=206}}</ref>

=== Example 5 ===
In [[Generalized eigenvector#Example 3|Example 3]], we found a canonical basis of linearly independent generalized eigenvectors for a matrix <math>A</math>.  A generalized modal matrix for <math>A</math> is

:<math>
M =
\begin{pmatrix} \mathbf y_1 & \mathbf x_1 & \mathbf x_2 & \mathbf x_3 \end{pmatrix} =
\begin{pmatrix}
-14 &   2 &  -2 &   0 \\
   4 &   0 &   2 &   0 \\
  -3 &   0 &   0 &   1 \\
   1 &   0 &   0 &   0
\end{pmatrix}.</math>

A matrix in Jordan normal form, similar to <math>A</math> is

:<math>J = \begin{pmatrix}
 4 &  0 &  0 &  0 \\
 0 &  5 &  1 &  0 \\
 0 &  0 &  5 &  1 \\
 0 &  0 &  0 &  5
\end{pmatrix},
</math>

so that <math>AM = MJ</math>.

== Applications ==

=== Matrix functions ===
{{Main|Matrix function}}
Three of the most fundamental operations which can be performed on [[square matrix|square matrices]] are matrix addition, multiplication by a scalar, and matrix multiplication.<ref>{{harvtxt|Beauregard|Fraleigh|1973|pp=57–61}}</ref>  These are exactly those operations necessary for defining a [[polynomial]] function of an ''n'' × ''n'' matrix <math>A</math>.<ref>{{harvtxt|Bronson|1970|p=104}}</ref>  If we recall from basic [[calculus]] that many functions can be written as a [[Maclaurin series]], then we can define more general functions of matrices quite easily.<ref>{{harvtxt|Bronson|1970|p=105}}</ref>  If <math>A</math> is diagonalizable, that is

:<math> D = M^{-1}AM ,</math>

with

:<math>
D = 
\begin{pmatrix}
 \lambda_1 & 0 & \cdots & 0 \\
     0 &  \lambda_2 & \cdots & 0 \\
\vdots &     \vdots & \ddots & \vdots \\
     0 &          0 & \cdots & \lambda_n
\end{pmatrix},
</math>

then

:<math>
D^k = 
\begin{pmatrix}
 \lambda_1^k &           0 & \cdots & 0 \\
           0 & \lambda_2^k & \cdots & 0 \\
      \vdots &      \vdots & \ddots & \vdots \\
           0 &           0 & \cdots & \lambda_n^k
\end{pmatrix}
</math>

and the evaluation of the Maclaurin series for functions of <math>A</math> is greatly simplified.<ref>{{harvtxt|Bronson|1970|p=184}}</ref>  For example, to obtain any power ''k'' of <math>A</math>, we need only compute <math>D^k</math>, premultiply <math>D^k</math> by <math>M</math>, and postmultiply the result by <math>M^{-1}</math>.<ref>{{harvtxt|Bronson|1970|p=185}}</ref>

Using generalized eigenvectors, we can obtain the Jordan normal form for <math>A</math> and these results can be generalized to a straightforward method for computing functions of nondiagonalizable matrices.<ref>{{harvtxt|Bronson|1970|pp=209–218}}</ref>  (See [[Matrix function#Jordan decomposition]].)

=== Differential equations ===
{{Main|Ordinary differential equation}}
Consider the problem of solving the system of linear ordinary differential equations

:{{NumBlk|:|<math> \mathbf x' = A \mathbf x ,</math>|{{EquationRef|5}}}}

where

:<math>
\mathbf x = 
\begin{pmatrix}
x_1(t) \\
x_2(t) \\
\vdots \\
x_n(t)
\end{pmatrix}, \quad
\mathbf x' = 
\begin{pmatrix}
x_1'(t) \\
x_2'(t) \\
\vdots \\
x_n'(t)
\end{pmatrix},
</math> {{spaces|4}} and {{spaces|4}} <math> A = (a_{ij}) .</math>

If the matrix <math>A</math> is a diagonal matrix so that <math> a_{ij} = 0 </math> for <math>i \ne j</math>, then the system ({{EquationNote|5}}) reduces to a system of ''n'' equations which take the form

:{{NumBlk|:|
<math> x_1' = a_{11} x_1 </math><br>
<math> x_2' = a_{22} x_2 </math><br>
:<math> \vdots </math>
<math> x_n' = a_{nn} x_n .</math>
|{{EquationRef|6}}}}

In this case, the general solution is given by

:<math> x_1 = k_1 e^{a_{11}t} </math>
:<math> x_2 = k_2 e^{a_{22}t} </math>
::<math> \vdots </math>
:<math> x_n = k_n e^{a_{nn}t} .</math>

In the general case, we try to diagonalize <math>A</math> and reduce the system ({{EquationNote|5}}) to a system like ({{EquationNote|6}}) as follows.  If <math>A</math> is diagonalizable, we have <math> D = M^{-1}AM </math>, where <math>M</math> is a modal matrix for <math>A</math>.  Substituting <math> A = MDM^{-1} </math>, equation ({{EquationNote|5}}) takes the form <math> M^{-1} \mathbf x' = D(M^{-1} \mathbf x) </math>, or

:{{NumBlk|:|<math> \mathbf y' = D \mathbf y ,</math>|{{EquationRef|7}}}}

where

:{{NumBlk|:|<math> \mathbf x = M \mathbf y .</math>|{{EquationRef|8}}}}

The solution of ({{EquationNote|7}}) is

:<math> y_1 = k_1 e^{\lambda_1 t} </math>
:<math> y_2 = k_2 e^{\lambda_2 t} </math>
::<math> \vdots </math>
:<math> y_n = k_n e^{\lambda_n t} .</math>

The solution <math> \mathbf x </math> of ({{EquationNote|5}}) is then obtained using the relation ({{EquationNote|8}}).<ref>{{harvtxt|Beauregard|Fraleigh|1973|pp=274–275}}</ref>

On the other hand, if <math>A</math> is not diagonalizable, we choose <math>M</math> to be a generalized modal matrix for <math>A</math>, such that <math> J = M^{-1}AM </math> is the Jordan normal form of <math>A</math>.  The system <math> \mathbf y' = J \mathbf y </math> has the form

:{{NumBlk|:|
<math>
\begin{align}
y_1' & = \lambda_1 y_1 + \epsilon_1 y_2 \\
& \vdots \\
y_{n-1}' & = \lambda_{n-1} y_{n-1} + \epsilon_{n-1} y_n \\
y_n' & = \lambda_n y_n ,
\end{align}
</math>
|{{EquationRef|9}}}}

where the <math> \lambda_i </math> are the eigenvalues from the main diagonal of <math>J</math> and the <math> \epsilon_i </math> are the ones and zeros from the superdiagonal of <math>J</math>.  The system ({{EquationNote|9}}) is often more easily solved than ({{EquationNote|5}}).  We may solve the last equation in ({{EquationNote|9}}) for <math>y_n</math>, obtaining <math>y_n = k_n e^{\lambda_n t} </math>.  We then substitute this solution for <math>y_n</math> into the next to last equation in ({{EquationNote|9}}) and solve for <math>y_{n-1}</math>.  Continuing this procedure, we work through ({{EquationNote|9}}) from the last equation to the first, solving the entire system for <math> \mathbf y </math>.  The solution <math> \mathbf x </math> is then obtained using the relation ({{EquationNote|8}}).<ref>{{harvtxt|Beauregard|Fraleigh|1973|p=317}}</ref>

==Notes==
{{reflist|30em}}

== References ==
* {{ citation | first1 = Howard | last1 = Anton | year = 1987 | isbn = 0-471-84819-0 | title = Elementary Linear Algebra | edition = 5th | publisher = [[John Wiley & Sons|Wiley]] | location = New York }}
*{{Cite book
  | last = Axler
  | first = Sheldon
  | title = Linear Algebra Done Right
  | publisher = Springer
  | year = 1997
  | edition = 2nd
  | isbn = 978-0-387-98258-8}}
* {{ citation | first1 = Raymond A. | last1 = Beauregard | first2 = John B. | last2 = Fraleigh | year = 1973 | isbn = 0-395-14017-X | title = A First Course In Linear Algebra: with Optional Introduction to Groups, Rings, and Fields | publisher = [[Houghton Mifflin Co.]] | location = Boston }}
* {{ citation | first1 = Richard | last1 = Bronson | year = 1970 | lccn = 70097490 | title = Matrix Methods:  An Introduction | publisher = [[Academic Press]] | location = New York }}
* {{citation | first1 = Richard L. | last1 = Burden | first2 = J. Douglas | last2 = Faires | year = 1993 | isbn = 0-534-93219-3 | title = Numerical Analysis | edition = 5th | publisher = [[Prindle, Weber and Schmidt]] | location = Boston | url = https://archive.org/details/numericalanalysi00burd }}
* {{ citation | first1 = Charles G. | last1 = Cullen | title = Matrices and Linear Transformations | location = Reading | publisher = [[Addison-Wesley]] | year = 1966 | lccn = 66021267 }}
* {{ citation | first1 = Joel N. | last1 = Franklin | title = Matrix Theory | location = Englewood Cliffs | publisher = [[Prentice-Hall]] | year = 1968 | lccn = 68016345 }}
* {{ citation | first1 = Gene H. | last1 = Golub | first2 = Charles F. | last2 = Van Loan | year = 1996 | isbn = 0-8018-5414-8 | title = Matrix Computations | edition = 3rd | publisher = [[Johns Hopkins University Press]] | location = Baltimore }}
* {{ citation | first1 = Charlie | last1 = Harper | year = 1976 | isbn = 0-13-487538-9 | title = Introduction to Mathematical Physics | publisher = [[Prentice-Hall]] | location = New Jersey }}
* {{ citation | first1 = I. N. | last1 = Herstein | year = 1964 | isbn = 978-1114541016 | title = Topics In Algebra | publisher = [[Blaisdell Publishing Company]] | location = Waltham }}
* {{citation | first1 = Erwin | last1 = Kreyszig | year = 1972 | isbn = 0-471-50728-8 | title = Advanced Engineering Mathematics | edition = 3rd | publisher = [[John Wiley & Sons|Wiley]] | location = New York | url = https://archive.org/details/advancedengineer00krey }}
* {{ citation | first1 = Evar D. | last1 = Nering | year = 1970 | title = Linear Algebra and Matrix Theory | edition = 2nd | publisher = [[John Wiley & Sons|Wiley]] | location = New York | lccn = 76091646 }}

{{Linear algebra|collapsed}}
{{Areas of mathematics|collapsed}}

[[Category:Linear algebra]]
[[Category:Matrix theory]]