Jordan normal form

Encyclopedia : J : JO : JOR : Jordan normal form

---

In linear algebra, Jordan normal form or Jordan canonical form shows that a given square matrix M over a field K containing the eigenvalues of M can be transformed into a certain canonical form by changing the basis. This canonical from is almost diagonal in the sense that its only non-zero entries lie on the diagonal and the super-diagonal. One can compare this result with the spectral theorem for normal matrices, which is a special case of the Jordan canonical form.

It is named in honour of Camille Jordan.

Motivation

A n × n matrix A is diagonalizable if only only if the sum of the dimensions of the eigenspaces is n. Or, equivalently, if and only if A has n linearly independent eigenvectors. Not all matrices are diagonalizable. Consider the following matrix:

[A=\begin322 & -323 & -323 & 322 \\325 & -326 & -325 & 326 \\ -259 & 261 & 261 & -260 \\-237 & 237 & 238 & -237 \end.]

Including multiplicity, the eigenvalues of A are λ = 5, 5, 5, 5. The dimension of the kernel of A − 5I is 1, so A is not diagonalizable. However, one can show there exists invertible matrices P such that A = PJP^-1 where

[J = \begin5 & 1 & 0 & 0 \\0 & 5 & 1 & 0 \\ 0 & 0 & 5 & 1 \\0 & 0 & 0 & 5 \end.]

This is the Jordan canonical form of A.

Complex matrices

In general, a square complex matrix A is similar to a block diagonal matrix

[J = \beginJ_1 & \; & \; \\\; & \ddots & \; \\ \; & \; & J_p\end]

where each block J_i is a square matrix of the form

[J_i = \begin\lambda_i & 1 & \; & \; \\\; & \lambda_i & \ddots & \; \\\; & \; & \ddots & 1 \\\; & \; & \; & \lambda_i \end.]

In other words, there exists an invertible matrix P such that PAP-1 = J is in what is called the Jordan canonical form. The only non-zero entries of J are on the diagonal and the super-diagonal. Each Ji is called a Jordan block of A. 

Assuming this result, we can deduce the following properties:

• Counting multiplicity, the eigenvalues of J, therefore A, are the diagonal entries.

• Given an eigenvalue λ_i, its geometric multiplicity is the dimension of Ker(A - λ_i), and it is the number of Jordan blocks corresponding to λ_i.

• The sum of the sizes of all Jordan blocks corresponding to an eigenvalue λ_i is its algebraic multiplicity.

• A is diagonalizable if and only if, for any eigenvalue λ of A, its geometric and algebraic multiplicities coincide.

• Notice that the Jordan block corresponding to λ is of the form λ I + N, where N is a nilpotent matrix defined as N_ij = δ_i,j − 1 (where δ is the Kronecker delta). The nilpotency of N can be exploited when calculating f(A) where f is a complex analytic function. For example, in principle the Jordan form could give a closed-form expression for the exponential exp(A).

Generalized eigenvectors

Consider the matrix A from the example in the previous section. The Jordan canonical form is obtained by some similarity transformation P^-1AP = J, i.e.

[AP = PJ.]

Let P have column vectors p_i, i = 1...4, then

[A \begin p_1 & p_2 & p_3 & p_4 \end = \begin p_1 & p_2 & p_3 & p_4 \end\begin5 & 1 & 0 & 0 \\0 & 5 & 1 & 0 \\ 0 & 0 & 5 & 1 \\0 & 0 & 0 & 5 \end.]

We see that

[\; (A - 5 I) p_1 = 0 ]

and

[\; (A - 5 I) p_i = p_ ] for [i = 2, \; 3, \;4.]

While p₁ is an eigenvector of A corresponding to 5, i.e. p₁ ∈ Ker(A - 5 I), we have p_i ∈ Ker(A - 5 I)ⁱ for i = 2, 3, and 4. Such vectors are called the generalized eigenvectors of A.

Thus, given an eigenvalue λ, its corresponding Jordan block gives rise to a Jordan chain. The lead vector, say p₁, in the chain is a eigenvector corresponding to λ and a generalized eigenvectors p_i in the chain is a preimage of p_i-1 under A - λ.

Therefore, the statement that every square matrix A can be put in Jordan canonical form is equivalent to the claim that there exists a basis consisting only of eigenvectors and generalized eigenvectors of A

A proof

We give a proof by induction. The 1 × 1 case is trivial. Let A be an n × n matrix. Take any eigenvalue λ of A. The range of A - λ, denoted by Ran(A - λ), is an invariant subspace of A. Also, since λ is an eigenvalue of A, the dimension Ran(A - λ), r, is strictly less than n. Let A' denote the restriction of A to Ran(A - λ), By inductive hypothesis, there exists a basis such that A' , expressed in terms of this basis, is in Jordan canonical form.

Next consider the subspace Ker(A - λ). If

[Ran(A - \lambda) \cap Ker(A - \lambda) = \]

, the desired result follows immediately from the rank-nullity theorem. This would be the case, for example, if A was Hermitian.

Otherwise, if

[Q = Ran(A - \lambda) \cap Ker(A - \lambda) \neq \]

, let the dimension of Q be s ≤ r. Then the basis must contain s vectors, say , that are leading vectors in the Jordan chains from the Jordan canonical form of A'. Let q_i be such that

[\; (A - \lambda) q_i = p_i] for [i = r-s+1, \cdots, r.]

Clearly q_i does not lie in Ker(A - λ) for all i. Furthermore, q_i can not be in Ran(A - λ), for that would contradict the assumption that each p_i is a lead vector in a Jordan chain. The set , being the preimage of the linearly independent set under A - λ, is also linearly independent.

Finally, we can pick any linearly independent set that spans

[\; Ker(A - \lambda) - Q.]

By construction, the union the three sets , , and is linearly independent. Each vector in the union is either an eigenvector or a generalized eigenvector of A. Finally, by rank-nullity theorem, the cardinality of the union is n. In other words, we have found a basis that consists of eigenvectors and generalized eigenvectors of A, and this shows A can be put in Jordan canonical form.

Uniqueness

It can be shown that the Jordan canonical form of a given matrix A is unique up to the order of the Jordan blocks.

Knowing the algebraic and geometric multiplicities of the eigenvalues is not sufficient to determine the Jordan canonical form of A. Assuming the algebraic multiplicity m(λ) of an eigenvalue λ is known, the structure of the Jordan form can be ascertained by analysing the ranks of the powers (A - λ)^m(λ). To see this, suppose an n × n matrix A has only one eigenvalue λ. So m(λ) = n. The smallest integer k₁ such that

[(A - \lambda)^ = 0]

is the size of the largest Jordan block in the Jordan form of A. (This number k₁ is also called the index of λ. See discussion in a following section.) The rank of

[(A - \lambda)^]

is the the number of Jordan blocks of size k₁. Similarly, the rank of

[(A - \lambda)^]

is twice the number of Jordan blocks of size k₁ plus the number of Jordan blocks of size k₁ - 1. Iterating in this way gives the precise Jordan structure of A. The general case is similar.

This can be used to show the uniqueness of the Jordan form. Let J₁ and J₂ be two Jordan canonical forms of A. Then J₁ and J₂ are similar and have the same spectrum, including algebraic multiplicities of the eigenvalues. The procedure outlined in the previous paragraph can be used to determine the structure of these matrices. Since the rank of a matrix is preserved by similarity transformation, there is a bijection between the Jordan blocks of J₁ and J₂. This proves the uniqueness statement.

Consequences

One can see that the Jordan canonical form is essentially a classification result for square matrices, and as such several important results from linear algebra can be viewed as its consequences.

Spectral mapping theorem

Using the Jordan canonical form, direct calculation gives a spectral mapping theorem for the polynomial functional calculus: Let A be an n × n matrix with eigenvalues λ₁...λ_n, then for any polynomial p, p(A) has eigenvalues p(λ₁)...p(λ_n).

Cayley-Hamilton theorem

The Cayley-Hamilton theorem asserts that every matrix A satisfies its characteristic equation: if p is the characteristic polynomial of A, then p(A) = 0. This again can be shown via direct calculation in the Jordan form.

Minimal polynomial

The minimal polynomial of a square matrix A is the unique monic polynomial of least degree, m, such that m(A) = 0. Alternatively, the set of polynomials that annihilate a given A form an ideal I in C[x], the principle ideal domain of polynomials with complex coefficients. The element that generates I is precisely m.

Let λ₁...λ_q be the distinct eigenvalues of A, and s_i be the size of the largest Jordan block corresponding to λ_i. It is clear from the Jordan canonical form that the minimal polynomial of A has degree ∑s_i.

While the Jordan canonical form determines the minimal polynomial, the converse is not true. This leads to the notion of elementary divisors. The elementary divisors of a square matrix A are the characteristic polynomials of its Jordan blocks. The factors of the minimal polynomial m are the elementary divisors of the largest degree corresponding to distinct eigenvalues.

The degree of an elementary divisor is the size of the corresponding Jordan block, therefore the dimension of the corresponding invariant subspace. If all elementary divisors are linear, A is diagonalizable.

Invariant subspace decompositions

The Jordan form of a n × n matrix A is block diagonal, therefore gives a decomposition of the n dimensional Euclidean space into invariant subspaces of A. Every Jordan block J_i corresponds to an invariant subspace X_i. Symbolically, we put

[\mathbb^n = \oplus _ ^k X_i]

where each X_i is the span of the corresponding Jordan chain, and k is the number of Jordan chains.

One can also obtain a slightly different decomposition via the Jordan form. Given an eigenvalue λ_i, the size of its corresponding Jordan block s_i is called the index of λ_i and denoted by ν(λ_i). (Therefore the degree of the minimal polynomial is the sum of all indices.) Define a subspace Y_i by

[\; Y_i = Ker (\lambda_i - A)^]

This gives the decomposition

[\mathbb^n = \oplus _ ^l Y_i]

where l is the number of distinct eigenvalues of A.

Comparing the two decompositions, notice that, in general, l ≤ k. When A is normal, the subspaces X_i's in the first decomposition are one-dimensional and mutually orthogonal. This is the spectral theorem for normal operators. The second decomposition generalizes more easily for general compact operators on Banach spaces.

It might be of interest here to note some properties of the index, ν(λ). More generally, for a complex number λ, its index can be defined as the least non-negative integer ν(λ) such that

[Ker (\lambda - A)^ = Ker (\lambda - A)^m, \; \forall m \geq \nu(\lambda) .]

So ν(λ) > 0 if and only if λ is an eigenvalue of A. In the finite dimensional case, ν(λ) ≤ the algebraic multiplicity of λ.

Generalizations

Matrices with entries in a field

Jordan reduction can be extended to any square matrix M whose entries lie in a field K. The result states that any M can be written as a sum D + N where D is diagonalizable, N is nilpotent, and DN = ND. Whenever K contains the eigenvalues of M, in particular, when K is algebraically closed, the normal form can be expressed explicitly as the direct sum of Jordan blocks.

Similar to the case when K is the complex numbers, knowing the dimensions of the kernels of (M-λI)^k for 1 ≤ k ≤ m, where m is the algebraic multiplicity of the eigenvalue λ, allows one to determine the Jordan form of M. We may view the underlying vector space V as a K[x]-module by regarding the action of x on V as application of M and extending by K-linearity. Then the polynomials (x − λ)^k are the elementary divisors of M, and the Jordan canonical form is concerned with representing M in terms of blocks associated to the elementary divisors.

The proof of the Jordan normal form is usually carried out as an application to the ring K[x] of the structure theorem for finitely-generated modules over principal ideal domains, of which it is a corollary.

Compact operators

In a different direction, for compact operators on a Banach space, a result analogous to the Jordan canonical form holds. One restricts to compact operators because every point x in the spectrum of a compact operator T, the only exception being when x is the limit point of the spectrum, is an eigenvalue. This is not true for bounded operators in general. To give some idea of this generalization, we first reformulate the Jordan decomposition in the language of functional analysis.

Holomorphic functional calculus

Let X be a Banach space, L(X) be the bounded operators on X, and σ(T) denote the spectrum of T ∈ L(X). The holomorphic functional calculus is defined as follows:

Fix a bounded operator T. Consider the family Hol(T) of complex functions that is holomorphic on some open set G containing σ(T). Let Γ = be a finite collection of Jordan curves such that σ(T) lies in the inside of Γ, we define f(T) by

[f(T) = \frac \int_ f(z)(z - T)^ dz.]

The open set G could vary with f and need not be connected. The integral is defined as the limit of the Riemann sums, as in the scalar case. Although the integral makes sense for continuous f, we restrict to holomorphic functions to apply the machinery from classical function theory (e.g. the Cauchy integral formula). The assumption that σ(T) lie in the inside of Γ ensures f(T) is well defined; it does not depend on the choice of Γ. The functional calculus is the mapping Φ from Hol(T) to L(X) given by

[\; \Phi(f) = f(T).]

We will require the following properties of this functional calculus:

1. Φ extends the polynomial functional calculus.
2. The spectral mapping theorem holds: σ(f(T)) = f(σ(T)).
3. Φ is an algebra homomorphism.

The finite dimensional case

In the finite dimensional case, σ(T) = is a finite discrete set in the complex plane. Let e_i be the function that is 1 in some open neighborhood of λ_i and 0 elsewhere. By property 3 of the functional calculus, the operator

[\; e_i(T)]

is a projection. Moreoever, let ν_i be the index of λ_i and

[f(z)= (z - \lambda_i)^.]

The spectral mapping theorem tells us

[ f(T) e_i (T) = (T - \lambda_i)^ e_i (T)]

has spectrum . By property 1, f(T) can be directly computed in the Jordan form, and by inspection, we see that the operator f(T)e_i(T) is the zero matrix.

By property 3, f(T) e_i(T) = e_i(T) f(T). So e_i(T) is precisely the projection onto the subspace

[Ran \; e_i (T) = Ker (T - \lambda_i)^.]

The relation

[\; \sum_i e_i = 1]

implies

[\mathbb^n = \oplus_i \; Ran\; e_i (T) = \oplus_i \; Ker (T - \lambda_i)^]

where the index i runs through the distinct eigenvalues of T. This is exactly the invariant subspace decomposition

[\mathbb^n = \oplus_i Y_i]

given in a previous section.

This explicit identification of the operators e_i(T) in turn gives an explicit form of holomorphic functional calculus for matrices:

For all f ∈ Hol(T),

[f(T) = \sum_ \sum_^ \frac} (T - \lambda_i)^k e_i (T).]

Notice that the expression of f(T) is a finite sum because, on each neighborhood of λ_i, we have chosen the Taylor series expansion of f centered at λ_i.

Poles of an operator

Let T be a bounded operator λ be an isolated point of σ(T). (As stated above, when T is compact, every point in its spectrum is an isolated point, except possibly the limit point 0.)

The point λ is called a pole of operator T with order ν if the resolvent function R_T defined by

[\; R_T(\lambda) = (\lambda - T)^]

has a pole of order ν at λ.

We will show that, in the finite dimensional case, the order of an eigenvalue coincides with its index. The result also holds for compact operators.

Consider the annular region A centered at the eigenvalue λ with sufficiently small radius ε such that the intersection of the open disc B_ε(λ) and σ(T) is . The resolvent function R_T is holomorphic on A. Extending a result from classical function theory, R_T has a Laurent series representation on A:

[R_T(z) = \sum _ ^ a_m (\lambda - z)^m]

where

[a_ = - \frac \int_C (\lambda - z) ^ (z - T)^ d z] and C is a small circle centered at λ.

By the previous discussion on the functional calculus,

[\; a_ = -(\lambda - T)^ e_ (T)] where [\; e_] is 1 on [\; B_(\lambda)] and 0 elsewhere.

But we have shown that the smallest positive integer m such that

[a_ \neq 0] and [a_ = 0 \; \; \forall \; l \geq m]

is precisely the index of λ, ν(λ). In other words, the function R_T has a pole of order ν(λ) at λ.

Algorithms and methods

Let us examine the methods of determining the transition matrix by example.

Example 1

Consider the calculation of the transition matrix for the matrix above. Recall

[A=\begin322 & -323 & -323 & 322 \\325 & -326 & -325 & 326 \\ -259 & 261 & 261 & -260 \\-237 & 237 & 238 & -237 \end.]

We concern ourselves with obtaining generalized eigenvectors, that is, solutions to

[(A-\lambda I)^k\mathbf = \mathbf]

which will allow us to calculate "chains" of vectors, whose elements form the columns of the transition matrix.

For A above, we know there is only one Jordan block (see above), so we firstly obtain one generalized eigenvector - since (A − 5I)⁴ is the zero matrix, ker(A − 5I)⁴ is the entire space, so we can pick one of the standard basis vectors for the space, v = (1,0,0,0)^T, since none of the standard basis vectors is an eigenvector of (A − 5I)³, (A − 5I)², or A − 5I. Then, forming the chain

[\left\, (A-5I)^2\mathbf, (A-5I)\mathbf, \mathbf\right\}]

[=\left\ 5922 \\ 4230 \\ -3572 \\ -5170 \end, \begin 2857 \\ 2363 \\ -1962 \\ -2392 \end, \begin 317 \\ 325 \\ -259 \\ -237 \end,\begin 1 \\ 0 \\0 \\ 0 \end\right\}]

so, we can form the transition matrix as

[P=\begin5922 & 2857 & 317 & 1 \\4230 & 2363 & 325 & 0 \\ -3572 & -1962 & -259 & 0 \\-5170 & -2392 & -237 & 0 \\\end.]

Example 2

Say we have

[B =\begin 5 & 4 & 2 & 1 \\ 0 & 1 & -1 & -1 \\-1 & -1 & 3 & 0 \\ 1 & 1 & -1 & 2 \\\end.]

The eigenvalues of B are 4, 4, 2 and 1, and we have

[ \mathrm\ \ker = 1, \mathrm\ \ker = 1, \mathrm\ \ker = 1, \mathrm\ \ker()^2 = 2.]

So we can say that the Jordan form of the matrix is the direct sum

[J=J_1(1)\oplus J_1(2)\oplus J_2(4),]

since vectors in ker B − 4I are also in ker (B − 4I)².

We have that

[\ker^2 = \mathrm\ \left\ 0 \\ 0 \\ -1 \\ 1\end, \begin 1 \\ 0 \\ -1 \\ 1\end\right\}.]

We pick a vector in the above span that is not in the kernel of B − 4I. For this we choose v = (0,0,-1,1)^T , since (1,0,-1,1)^T is in the kernel of B − 4I.

Now, there are three chains, , , and , where w = (1,−1,0,1)^T is the basis vector of the 1-dimensional kernel of B-2I and likewise x = ( -1,1,0,0) is the basis vector of the 1-dimensional kernel of B − I. Form the transition matrix from these chain vectors as follows:

[P=\begin-1 & 0 & 1 & -1\\ 0 & 0 & -1 & 1\\ 1 & -1 & 0 & 0\\-1 & 1 & 1 & 0\end=\left((B-4I)\mathbf\left|\mathbf\left|\mathbf\left|\mathbf\right)\right.\right.\right.]

and

[P^BP=J=\begin4 & 1 & 0 & 0 \\0 & 4 & 0 & 0 \\0 & 0 & 2 & 0 \\0 & 0 & 0 & 1 \end.]

If we had interchanged the order of which the chain vectors appeared, that is, changing the order of w, x, and together, the Jordan blocks would be interchanged, giving equivalent Jordan forms, however.

 

---

From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.