### A Simple Jordan Canonical Form Algorithm

This document is intended for anyone who has been exposed to a second course in
linear algebra and who has been mystified by the usual lengthy treatments of
the Jordan canonical form and who simply wants an algorithm which can be
implemented by an exact arithmetic matrix calculator such as my
CMAT. For the moment, we omit
proofs and present such an algorithm for finding a nonsingular matrix
*P* such that *P*^{-1}AP=J_{A}, the Jordan canonical form
of *A*. (Proofs can be found in my 1991 MP274 lecture notes.)
### Motivation

Let *A* be an *n x n* matrix over a field *F* and let the
characteristic polynomial *ch*_{A}(x) split completely as a
product of linear factors over *F*.
Let *c* be an eigenvalue of *A* having algebraic multiplicity
*a* and geometric multiplicity *g*.
Then *A* is similar to a direct sum of *elementary Jordan*
matrices; that is matrices *J*_{e}(c), with *c* on the
diagonal, *1* on the subdiagonal and *0* elsewhere.

Let *B = A - cI*_{n}.
Also let *N(B*^{h}) stand for the null space of
*B*^{h}. Then *N(B)* and *N(B*^{a}) are
the eigenspace and generalized eigenspace of *A*, corresponding to the
eigenvalue *c*.

Let *n*_{h}=dim(N(B^{h})). Then
*g=n*_{1} ≤ n_{a}=a. If *g=a* for all
eigenvalues, then *J*_{A} is diagonal and there are no difficulties.
However if *g < a*, the situation is more complicated.
Our aim is to choose a basis for *N(B)* having the form

*B*^{e1-1}X_{1}, . . . ,
B^{eg-1}X_{g}, (1)

where *e*_{1}≥ · · · ≥ e_{g}≥1
and *e*_{1}+ · · · +e_{g}=a.

For then the following *generalized eigenvectors*:
*X*_{1}, BX_{1}, . . . , B^{e1-1}X_{1};

*
**·*

·

·

X_{g}, BX_{g}, . . . , B^{eg-1}X_{g}

will together form a basis for the generalized eigenspace
*N(B*^{a}). (See for example either the aforementioned MP274 notes or Lemma, p. 308, *Linear Algebra*, S.H. Friedberg, A.J. Insel, L.E. Spence, Prentice-Hall 1979.)

Then if *P*_{c} is the matrix whose columns are formed from the above list, we have
*AP*_{c} = P_{c}diag(J_{e1}(c), . . . , J_{eg}(c)).

We then let *P* be the result
of juxtaposing the *P*_{c} for the distinct eigenvalues. Then
*P* will be a nonsingular *n x n* matrix and *P*^{-1}AP=J_{A}.
It helps to visualize the generalized eigenvectors in the following
tabular form:

If *e*_{1},...e_{k} are the exponents
*>= h*, the vectors *B*^{e1-1}X_{1}, . . . , B^{ek-1}X_{k}, can be shown to form a basis
for *N*_{h}, the intersection of *C(B*^{h-1})
(the column space of *B*^{h-1}) and the eigenspace *N(B)*.

In fact *k = n*_{h} - n_{h-1}.

The numbers *e*_{1}, . . . , e_{g} are called the
*Segre characteristic* for the eigenvalue *c* and form a
"vertical" partition of the algebraic multiplicity *a*.
The numbers *n*_{h} increase strictly and then become equal:
*n*_{1}<· · · < n_{b} = · · · = n_{a} = a.

Here *b=e*_{1}.

The numbers *µ*_{h} = n_{h} - n_{h-1}
decrease monotonically:
*µ*_{1} = n_{1}≥· · ·
≥ µ_{b}

and are called the
*Weyr characteristic* for the eigenvalue *c* and form a
"horizontal" partition of *a*.
We remark that the vectors *B*^{j}X_{i},i=1,...,g,
j=0,...,e_{i}-1, form a basis for *N(B*^{h}).

### The construction

The above discussion shows that the subspaces *N*_{h} hold the key to the construction of the basis (1). We start with a basis for
*N*_{b} and extend to bases of the successive distinct
*N*_{h}, until a basis is obtained for *N*_{1} of
the form (1). The process is facilitated by the observation that
*N*_{h} = < B^{h-1}Y_{1}, . . . , B^{h-1}Y_{r} >,

if *Y*_{1}, . . . , Y_{r} is a basis for
*N(B*^{h}). We also make use of the "Left-To-Right" algorithm, which selects a basis from a list of spanning vectors.
### An example

Let *ch*_{A}(x)=x^{11}. Also suppose that
* n*_{1} = 4,
n_{2} = 7,
n_{3} = 9,
n_{4} = 11.

Then *
µ*_{1} = n_{1} = 4,
µ_{2} = n_{2} - n_{1} = 3,
µ_{3} = n_{3} - n_{2} = 2,
µ_{4} = n_{4} - n_{3} = 2.

Also *B=A* and our table of generalized eigenvectors is

**A basis for ***N*_{4}:
*N(B*^{4}) = <Y_{1}, . . . ,
Y_{11}>
and hence *N*_{4}=
< B^{3}Y_{1}, . . . ,
B^{3}Y_{11}>.

The Left-To-Right algorithm will give:
* N*_{4}=
<
B^{3}X_{1}, B^{3}X_{2}>.
**A basis for ***N*_{2}:
*N(B*^{2}) = <Z_{1}, . . . ,
Z_{7}>, so

*N*_{2}=
< BZ_{1}, . . . ,
BZ_{7}> =
< B^{3}X_{1}, B^{3}X_{2},
BZ_{1}, . . . ,
BZ_{7}>.

The Left-To-Right algorithm gives:
*N*_{2}=
< B^{3}X_{1}, B^{3}X_{2},
BX_{3}>.
**A basis for ***N*_{1}:
*N(B) =
<W*_{1}, . . . ,
W_{4}>
=
< B^{3}X_{1}, B^{3}X_{2},
BX_{3},
W_{1}, . . . ,
W_{4}>.

The Left-To-Right algorithm gives:
*N(B) = < B*^{3}X_{1}, B^{3}X_{2},
BX_{3},
X_{4}
>.

Then P = [*
X*_{1}|*
BX*_{1}|*
B*^{2}X_{1}|*
B*^{3}X_{1}|*
X*_{2}|*
BX*_{2}|*
B*^{2}X_{2}|*
B*^{3}X_{2}|*
X*_{3}|*
BX*_{3}|*
X*_{4}] has the property that
*P*^{-1}AP = diag(J_{4}(0),
J_{4}(0),
J_{2}(0),
J_{1}(0))*.*

*
** Last modified 2nd June 2010*