The Minimal Polynomial, Cyclic Subspaces, and Jordan Normal Form
A polynomial f of degree n over an algebraically closed field factors into a product of n linear terms: f(x) = \prod_{i} (x-\lambda_{i})^{n_{i}}
Here the \lambda_i are the roots of f(x) and the number n_{i} is called the multiplicity of the root \lambda_{i}.
If f(x)=P_{A}(x) is the characteristic polynomial of a linear map/matrix over F and all n_{i}=1, then we know that L (resp. A) is diagonalizable. If not, then the question is open: sometimes the matrix is diagonalizable, sometimes not.
To understand the situation more fully, we need some theory of polynomials.
We write F[x] for the polynomials with coefficients in a field F. For now, we need not assume F algebraically closed.
A polynomial f(x) = a_0+a_1x+\cdots+a_nx^n has degree \deg(f)=n if a_n\not=0 and is monic if a_n=1.
Proposition: (The Division Algorithm) Let f and g be two polynomials in F[x]. Then there exist unique polynomials q(x) and r(x), with 0\le \deg(r(x))<\deg(g(x)), such that f(x) = q(x)g(x)+r(x).
Definition: A polynomial u(x) is a divisor of f(x) if there is a polynomial v(x) with f(x)=u(x)v(x). A polynomial h(x) is a common divisor of f(x) and g(x) if it is a divisor of each.
Proposition: (Euclid’s Algorithm) Given nonzero polynomials f(x) and g(x), there is a unique nonzero monic polynomial d(x)=(f(x),g(x)) of minimal degree of the form a(x)f(x)+b(x)g(x) where a(x) and b(x) are polynomials. This polynomial d(x) is the greatest common divisor of f(x) and g(x), meaning:
- d(x) is a common divisor of f(x) and g(x), and
- if h(x) is a common divisor of f(x) and g(x), then d(x) is a divisor of h(x).
Proposition: The roots of d(x)=(f(x),g(x)) are exactly the common roots of f(x) and g(x). If \lambda is a common root of multiplicity a in f and multiplicity b in g then the multiplicity of \lambda in d(x) is the smaller of a and b.
Corollary: Two polynomials f(x) and g(x) over F have no roots in common in some algebraic closure of F, if and only if there are polynomials a(x) and b(x) such that a(x)f(x)+b(x)g(x)=1.
A polynomial f(x) is irreducible if it cannot be factored into a product f(x) = g(x)h(x) where g(x) and h(x) each have degree at least one.
Suppose that f(x) is irreducible and a(x)b(x) is a multiple of f(x), so a(x)b(x) = f(x) u(x) for some polynomial u(x).
From Euclid’s algorithm, we can write t(x)a(x) +s(x)f(x) = d(x).
Since f(x) is irreducible and is a multiple of d(x), d(x) must either be f(x) or have degree zero (so we might as well assume d(x)=1.)
If d(x)=f(x), then a(x) is a multiple of f(x). Otherwise, multiply through by b(x) to obtain t(x)a(x)b(x) + s(x)f(x)b(x) = b(x). and so b(x) is a multiple of f(x).
We’ve proven:
Proposition: If f(x) is irreducible and a(x)b(x) is a multiple of f(x), then either a(x) is a multiple of f(x) or b(x) is.
Proposition: A monic polynomial f(x) is a product f(x) = \prod_{i} p_{i}(x)^{n_{i}} where the p_{i}(x) are distinct monic irreducible polynomials and the set of p_{i} and the n_{i} are unique (up to order).
Proof: Given f(x), either f(x) is irreducible or it factors f(x)=a(x)b(x). By induction this gives a factorization into irreducibles.
For uniqueness, suppose p(x) is monic and occurs in one factorization of f(x) into powers of irreducibles. Given another factorization f(x) = \prod_{i} q_{i}(x)^{m_{i}}, since f(x) is a multiple of p(x), one of the q_{i} must be a multiple of p(x), which means some q_{i}(x) = p(x). Continuing inductively shows that the two factorizations are the same.
Decomposition
Now let L:V\to V be a linear map and factor P_{L}(x) into a product of powers of distinct irreducibles: P_{L}(x) = p_{1}(x)^{n_{1}}\cdots p_{k}(x)^{n_{k}}.
Then the greatest common divisor of p_{1}(x)^{n_{1}} and H(x) = p_{2}(x)^{n_{2}}\cdots p_{k}(x)^{n_{k}} must be one, so we can write a(x) H(x) + b(x) p_1(x)^{n_{1}} = 1.
Let V_{1} be the image of H(L) and let W be the image of p_{1}(L)^{n_{1}} in V. Notice that V_1+W=V since v = a(L) H(L)v + b(L)p_1(L)^{n_{1}} v.
On the other hand, p_1(L)^{n_{1}}V_1=0 and H(L)W=0 and by Cayley-Hamilton.
So if v\in V_1\cap W, then
v = a(L)H(L)v + b(L) p_{1}(L)^{n_1} v = 0.
Thus V is the (internal) direct sum of V_1 and W.
Continuing inductively by looking at the factorization of H acting on the space W, we can eventually decompose V into a direct sum
V = V_1 \oplus V_2 \oplus \cdots \oplus V_k
where p_{i}(L)^{n_{i}}V_i=0.
The Minimal Polynomial
Suppose V is a finite dimensional vector space of dimension n over a field F and L:V\to V is a linear map. We know from Cayley-Hamilton that P_{L}(L)V=0.
Definition: Let m_{L}(x) be the monic polynomial of smallest degree such that m_L(L)V=0. This polynomial is called the minimal polynomial of L.
Proposition: The minimal polynomial m_{L}(x) is a divisor of the characteristic polynomial P_{L}(x).
Proof: Divide P_{L}(x) by m_{L}(x) and let r(x) be the remainder. Since r(x) = P_{L}(x)-q(x)m_{L}(x), we have r(L)V=0. But the degree of r(x) is less than that of m_L(x), so the minimality of m_L(x) means that r(x)=0.
Cyclic Subspaces
If V is a finite dimensional vector space over F of dimension n, and L:V\to V is a linear map, then V is called a cyclic space for L if there is a v\in V such that the set of vectors L^{i}(v), for i=0,\ldots, n-1 span V. A v with this property is called a generator for V.
If V is cyclic for L, and v is a generator for V, then we must have a relation: L^{n}v = -\sum_{i=0}^{n-1} a_{i}L^{i}v. This gives a polynomial q(x) = x^n+a_{n-1}x^{n-1}+\cdots+a_{0}
such that q(L)V=0. In this situation, q(x) is the minimal polynomial for L acting on V.
If v is a generator for V, and q(x) is the polynomial described above, we can write the matrix A of the linear map L in the basis \{L^{i}v\}_{i=0}^{n-1}. Since L(L^{i}v)=L^{i+1}v\mathrm{\ for\ }i=0,\ldots, n-2 and L(L^{n-1}v) = L^{n}v = -\sum_{i=0}^{n-1}a_{i}L^{i}v
we see that
A=\begin{pmatrix} 0 & 0 & 0 & \cdots & 0 & -a_{0} \\ 1 & 0 & 0 & \cdots & 0 & -a_{1} \\ 0 & 1 & 0 & \cdots & 0 & -a_{2} \\ 0 & 0 & 1 & \cdots & 0 & -a_{3} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & -a_{n-1} \end{pmatrix}
Remark: A matrix of this shape for the polynomial q(x) is called the companion matrix for q(x).
Proposition: The characteristic polynomial of A is q(x).
Proof: If q(x) is degree 1, this is easy to check by a computation. Inductively, if we strike out the first row and column of A, we obtain the companion matrix A_1 of the polynomial b(x) = x^{n-1}+a_{n-1}x^{n-2}+\cdots+a_{1} so \det(A_1)=b(x) by induction. Then the cofactor expansion of \det(A) along the first row gives x\det(A_1)+a_{0}=xb(x)+a_0=q(x).
Corollary: If V is cyclic for L, then the minimal polynomial and characteristic polynomials of L coincide.
Decomposition into Cyclic Subspaces
Our goal now is to prove the following.
Theorem: Let L:V\to V be a linear map, where V is a vector space of dimension n over F. Then there is a decomposition V = V_{1}\oplus V_{2}\oplus \cdots \oplus V_{k}
of V into cyclic subspaces where the minimal polynomial of V_{i} is a power p(x)^{k_{i}} of a monic irreducible polynomial over F.
In addition, the minimal polymomials p(x)^{k_{i}} are unique up to order.
This result is very powerful but let’s observe two consequences right off the bat.
First, we see from the decomposition that the minimal polynomial m_{L}(x) on V is the least common multiple of the p_{i}(x)^{k_{i}}.
Second, the characteristic polynomial of V is the product of the characteristic polynomials of the V_{i}, which is the product of the p_{i}(x)^{k_{i}}.
Consequently, if p(x) is an irreducible factor of P_{L}(x), then p(x) must occur among the p_{i}(x). Therefore every irreducible factor of the characteristic polynomial P_{L}(x) is a factor of the minimal polynomial of L.
To prove the decomposition result, we start with our earlier decomposition of V into a sum V_{i} where each V_{i} is killed by p_{i}(L)^{n_{i}}, the p_{i}(x) are distinct irreducibles, and
P_{L}(x) =\prod_{i} p_{i}(x)^{n_{i}}
is the factorization of P_{L}(x) into irreducible factors.
Now we will show that if V is finite dimensional and there is an irreducible polynomial p(x) of degree d so that p(L)^{n}V=0, then V can be further split into a direct sum of cyclic subspaces corresponding to p(x)^{k_{i}} where \sum k_{i} = n.
To start, choose a vector v_1\in V so that p(L)^{k_{1}}v_1=0, p(L)^{k_1-1}v_1\not=0, and k_1 is maximal among all such choices. The vector v_1 generates a cyclic subspace of V with basis v_1, Lv_1, \cdots, L^{k_1d-1}v_{1}.
These vectors are independent since a dependence relation would yield a polynomial h(x) in L of degree less than dk_1 such that h(L)v_1=0. Then the greatest common divisor s(x) of h(x) and p(x)^{k_1} would also satisfy s(L)v_1=0, and since p(x) is irreducible and s(x) is a divisor of p(x)^{k_1} of degree less than or equal to dk_1-1, we’d have s(x)=p(x)^{k} with k<k_1, contradicting the choice of k_1.
Let V_1 be the subspace of V generated by v_1. Our next goal is to construct a subspace W of V such that W is L-invariant and V=V_1\oplus W.
Since W is of smaller dimension than V and satisfies the same hypotheses, we can continue inductively to completely decompose V.
The construction of W is itself an inductive process. To start, choose w_1'\not\in V_1 so that p(L)^{s_{1}}w_1'\in V_1, p(L)^{s_1-1}w_1'\not\in V_1 and s_1 is maximal with this property.
Now we have p(L)^{s_1}w_1' = a(L)v_1
for some polynomial a(x) of degree at most dk_1-1 since V_1 is cyclic. Since p(L)^{k_1-s_1} kills the left side, it kills the right side as well. It follows that a(x) is divisible by p(x)^{s_1}, so a(x)=a_1(x)p(x)^{s_1}. Let w_1 = w_1'-a_1(L)v_1.
Then p(L)^{s_1}w_1=0. Now let W_1 be the cyclic subspace generated by w_1, so W_1\cap V_1=0.
Now suppose we have constructed W_j so that V_1\cap W_j=0. Choose w_{j+1}' in V but not in V_1\oplus W_j. Repeat the same argument inductively to adjust w_{j+1}', yielding w_{j+1} such that if s_{j+1} is the minimal power with p(L)^{s_{j+1}}w_{j+1}'\in V_1, then p(L)^{s_{j+1}}w_{j+1}=0.
This constructs the “complementary subspace” W.
To finish the proof of existence, now split off a cyclic subspace of W and continue.
For now, we skip the proof of uniqueness.
The Jordan Normal Form
Now let’s take a look at what the cyclic decomposition theorem tells us in the case where the characteristic polynomial of L factors into linear factors: P_{L}(x) = \prod_{i} (x-\lambda_{i})^{n_{i}}.
This always happens if the field F is algebraically closed, but that’s not required.
In this situation, the decomposition writes V as a sum of cyclic subspaces V_{i} with minimal polynomial (x-\lambda_{i})^{k_{i}}.
Choose one of these cyclic subspaces V_{i} and let v=v_{0} be a generator. The vectors v_{j} = (L-\lambda_i)^{j}v_0\mathrm{\ for\ }j=0,\ldots, k_{i}-1 are linearly independent and in fact give a basis for V_{i}.
Notice that Lv_{j} = (L-\lambda_i)v_{j}+\lambda_i v_{j} = v_{j+1}+\lambda_i v_{j}\mathrm{\ for\ }j=0,\ldots, k_{i}-2 while Lv_{k_i-1}=\lambda_i v_{k_{i}-1}.
In the basis \{v_0,v_1,\ldots,v_{k_i-1}\}, the matrix of L restricted to V_i is therefore J_{k_i}(\lambda_i)=\begin{pmatrix} \lambda_i & 0 & 0 & \cdots & 0 & 0 \\ 1 & \lambda_i & 0 & \cdots & 0 & 0 \\ 0 & 1 & \lambda_i & \cdots & 0 & 0 \\ 0 & 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & \lambda_i \end{pmatrix}
Definition: The k\times k matrix with \lambda on the diagonal, 1 on the subdiagonal, and 0 elsewhere is called the Jordan block J_{k}(\lambda).
Carrying this out for every i and assembling the resulting bases of the V_i into a single basis for V gives:
Theorem: (Jordan Normal Form) If the characteristic polynomial of L factors into linear factors, then there is a basis of V in which the matrix of L is block diagonal, with blocks J_{k_i}(\lambda_i), where the (x-\lambda_i)^{k_i} are the minimal polynomials of the cyclic subspaces V_i in the decomposition of V.
It’s worth pointing out that one way to read the Jordan Normal Form is that every matrix A whose characteristic polynomial factors into linear factors is a sum A = D + N
where D is a diagonal matrix whose diagonal entries are the eigenvalues repeated according to their multiplicity, and N is a nilpotent matrix - that is, N^{k}=0 for some k.
In a single Jordan Block or dimension k, the matrix has the form \lambda I + N
where N^{k}=0 but N^{k-1}\not=0.
It’s also worth observing that each Jordan Block has exactly one eigenvector, so the number of independent eigenvectors is equal to the number of Jordan Blocks.