San José State University

applet-magic.com
Thayer Watkins
Silicon Valley
& Tornado Alley
USA

The Theorem on the Canonical Form
of Matrices by Camille Jordan


Camille Jordan

In 1870 Camille Jordan in France published a very important theorem concerning square matrices. It can be called a boss theorem in that it provides the basis of simple proofs of other theorem concerning matrices. It is amazing given the power and the complexity of the proof that Jordan could have formulated and proved such a theorem all by himself at such an early date. In order to state the theorem it is convenient to define a few concepts.

Jordan Block Matrices

An m×m matrix is of the Jordan block form if it has a constant on the principal diagonal and 1's for all the elements next to the principal diagonal on the right. All other elements are zero. For example, suppose m=3. Then

10|
|0λ1|
|00λ|

is a Jordan block. Such blocks can be represented as λI+H, where H is a square matrix of zeroes except for elements of 1 to the immediate right of the principal diagonal.

For m=1 a Jordan block is just a constant, say λ, a 1×1 matrix.

The determinant of an m×m Jordan block with λ on the principal diagonal is just λm.

The Jordan Canonical Form of a Matrix

Suppose an n×n matrix A of complex values has k eigenvalues of {λ1, λ2, …, λk} of mulitiplicities {m1, m2, …, mk}, respectively, and Σmj=n.

Let Λk be the Jordan block for λk and mk. Let J be an n×n matrix with the principal diagonals of the Λk's aligned along its principal diagonal and zeros everywhere else.

| Λ100  |
| 0Λ20  |
| 00  |
| 00Λk|

This is a Jordan canonical form of the matrix A. There may be a number of such canonical forms because the ordering of the eigenvalues is arbitrary. If all of the eigenvalues are different then the canonical form is a diagonal matrix with the eigenvalues on the principal diagonal.

There is no question that such canonical forms exist for any square matrix. Such canonical forms for a matrix are determined solely by its eigenvalues and their multiplicities.

The Eigenvalues and Eigenvectors of a Matrix

An eigenvalue λ and eigenvector V for an n×n matrix A are such that

AV = λV
which is equivalent to
(A−λI)V = 0

where I is the n×n identity matrix and 0 is a column vector of zeroes.

This latter equation has nontrivial solutions only if

det(A−λI) = 0

This determinantal equation reduces to an n-th degree polynomial equation, say φ(λ)=0. This polynomial has n solutions counting multiplicities. Let us say it has k different solutions {λ1, λ2, …, λk} of mulitiplicities {m1, m2, …, mk}, respectively, with Σmj=n.

Thus to obtain a Jordan canonical form for an n×n matrix A one can first create the determinantal equation and establish its roots and their multiplicities, say {ki, i=1, 2, …, m} and {mi, i=1, 2, …, m} where Σmi=n. Then Jordan bases {Ji, i=1, 2, …, m} can be created. The n×n matrix with the Jordan bases aligned along the principal diagonal is a Jordan form matrix. It is a Jordan canonical form matrix for the matrix A.

Principal Vectors

The concept of a principal vector of a matrix is a generalization of the concept of an eigenvector.

A vector P, zero or nonzero, is a principal vector of grade g belonging to the eigenvalue λ of a matrix A if

(λI−A)gP = 0
where g is a non-negative integer

and there is no smaller non-negative integer γ for which (λI−A)γP = 0

This means that P=0 is a principal vector of grade 0 and any eigenvector of A is a principal vector of grade 1.

Now define the linear vector space Ug(λ) as being the space spanned by all principal vectors of λ which are of grade g or less. Ug(λ) is the null space of (λI−A)g; i.e., the space of all vectors which (λI−A)g maps into the zero vector.

Because (λI−A)gP=0 implies that (λI−A)g+1P=0 it follows that

U0(λ) ⊂ U1(λ) ⊂ U2(λ) ⊂ …

Jordan Bases

Let M=A−λI. Then

Um(λ) = [P: MgP=0 for g=0, 1, … m]

where m is the multiplicity of λ

A sequence of vectors {V1, V2, …, Vm} is a Jordan basis for Um(λ) if it can be partitioned into chains such that

[Vβ+1, Vβ+2=MVβ+1, …, Vβ+α=MVβ+α-1]
with MVβ+α=0

where the lengths of the chains are less than or equal to m.

What this looks like for a specific case is as follows:

V1Vα+1Vγ+1
V2=MV1Vα+2=MVα+1 Vγ+2=MVγ+1
V3=MVVα+3=MVα+2 Vγ+3=MVγ+2
Vα=MVα-1Vβ=MVβ-1 Vδ=MVδ-1

Where
MVα=0      MVβ=0   MVδ=0

On the Existence of a Jordan Basis
for an Eigenvalue of a Matrix

Theorem: Let λ be an eigenvalue of an n×n matrix A and m be its multiplicity. Let A−λI be denoted as M. Let W be the set of vectors such that Mgw=0 for g=0, 1, 2, …,m. Then W has a Jordan basis.

Proof by Induction:

For m=1 all of the vectors satisfying Mw=0 are eigenvectors for λ. Any basis for this set is a Jordan basis.

Suppose it is true for m=k there is a Jordan basis B={V1, V2, …, Vk}.

(Under construction)

For an n×n matrix A with an eigenvalue of λ of multiplicity m, an (n-1)×(n-1) matrix A' be constructed which has the same eigenvalues as A except that λ is of multiplicity (m-1). If nothing else A' can simply be a canonical Jordan form for A with the Jordan block for λ reduced from m×m to (m-1)×(m-1). The determinantal equation for A' is easily constructed. It is

φ(μ) = det(μI−A)/(μ−λ) = 0

The question is what vectors need to be appended to a Jordan basis for λ in A' to create a Jordan basis for λ in A. This is a matter of which vectors satisfy the condition Mmw=0 but do not satisfy Mm-1w=0. This would have to be vectors such that Mm-1w is equal to an eigenvector of A.

(To be continued.)

The Jordan Theorem

For an n×n matrix A there exists an n×n matrix Q such that QA = JQ, where J is a Jordan canonical form.

Proof:

Let B=[V1, V2, …, Vα, Vα+1, …, Vz] be a Jordan basis for the principal vectors for λ. Let M=A−λI. Then

MB = [[MV1, MV2, …, MVα, MVα+1, …, MVz]
which reduces to
MB = [V2, V3, …,0, Vα, …, Vz-2, 0]

But M=A−λI so λI+M and hence

AB = λB + MB

Therefore

AB = [λV1+V2, λV2+V3, …, λVα, …, λVz-1+Vz, λVz]
but this is the same as
[V1, V2, …, Vα, Vα+1, …, Vz

where Λ is the Jordan block for λ in A.

But the above says

AB = BΛ

When this construction is applied to all of the eigenvalues of A the result is

AQ = QJ

where Q is the matrix of the Jordan bases of the eigenvalues adjoined.

The Similarity of Any Square Matrix
to a Canonical Jordan Form

A matrix A is said to be similar to another matrix C if there exists a matrix M such that M-1AM=C.

Let A be an n×n matrix of complex elements. From the previous theorem there exists a matrix Q such that AQ=QJ where J is of canonical Jordan form. It then only needs to be proven that Q is invertible. Q is n×n and maps n-dimensional vectors to n-dimensional vectors. In the construction of Q it is made up by adjoining Jordan bases for the subspaces of the space of n-dimensional vectors and the sum of the dimensions of the subspaces is equal to n. Therefore Q maps the n-dimensional vector space onto the n-dimensional vector space and hence has an inverse. Alternatively it can be shown that the column vectors of Q arelinearly independent and thus Q cannot be singular. Thus

Q-1AQ = J

A slightly different form of the proof of the Jordan Canonical Form Theorem is given at Similarity.


Sources:

Joel N. Franklin, Matrix Theory, Prentice-Hall, New York, 1968.

Richard Bronson, Matrix Methods: An Introduction, Academic Press, New York, 1969.


HOME PAGE OF applet-magic
HOME PAGE OF Thayer Watkins