Hamathster
§ DS-20 Caylay-Hamilton Theorem
2024-05-20
Algebra-I
00

Contents

§20 Cayley-Hamilton Theorem
§20.1 Matrices of Linear Transformations
§20.2 Jordan Normal Form
§20.3 Characteristic Polynomials
§20.4 Cayley-Hamilton Theorem

§20 Cayley-Hamilton Theorem

§20.1 Matrices of Linear Transformations

Definition 20.1 Let MM be a vector space over FF, and fix a basis

v⃗1,…,v⃗k\vec{v}_{1},\ldots,\vec{v}_{k}

of MM.

Assume that MM is finite-dimensional.

Given any linear transformation

A:M→M,A:M\to M,

the matrix of AA with respect to the basis v⃗∗1,…,v⃗∗k\vec{v}*{1},\ldots,\vec{v}*{k} is the matrix satisfying

Av⃗i=∑j=1kAjiv⃗j.A\vec{v}_{i} = \sum_{j=1}^{k} A_{ji}\vec{v}_{j}.

Example 20.1

Let

(A)=(A11A12A13A21A22A23A31A32A33).(A) = \begin{pmatrix} A_{11}&A_{12}&A_{13}\\ A_{21}&A_{22}&A_{23}\\ A_{31}&A_{32}&A_{33} \end{pmatrix}.

Then

Av⃗1=A11v⃗1+A21v⃗2+A31v⃗3.A\vec{v}_{1} = A_{11}\vec{v}_{1} + A_{21}\vec{v}_{2} + A_{31}\vec{v}_{3}.

Exercise Write down the matrix of multiplication by tt on each of the following F[t]F[t]-modules with the specified basis.

(1)

M=F[t]/(t),v⃗1=1‾.M=F[t]/(t), \qquad \vec{v}_{1}=\overline{1}.

(2)

M=F[t]/(t−α),v⃗1=1‾.M=F[t]/(t-\alpha), \qquad \vec{v}_{1}=\overline{1}.

(3)

M=F[t]/(t−α)2,v⃗2=1‾,v⃗1=t−α‾.M=F[t]/(t-\alpha)^2, \qquad \vec{v}_{2}=\overline{1}, \qquad \vec{v}_{1}=\overline{t-\alpha}.

(4)

M=F[t]/(t−α)3,v⃗3=1‾,v⃗2=t−α‾,v⃗1=(t−α)2‾.M=F[t]/(t-\alpha)^3, \qquad \vec{v}_{3}=\overline{1}, \qquad \vec{v}_{2}=\overline{t-\alpha}, \qquad \vec{v}_{1}=\overline{(t-\alpha)^2}.

Solution: In general, the action of F[t]F[t] on

F[t]/IF[t]/I

is

f⋅g‾=fg‾.f\cdot\overline{g} = \overline{fg}.

(2)

t⋅1‾=t⋅1‾=t−α‾+α‾=α1‾.t\cdot\overline{1} = \overline{t\cdot1} = \overline{t-\alpha} + \overline{\alpha} = \alpha\overline{1}.

Therefore, tt sends 1‾\overline{1} to α1‾\alpha\overline{1}, so

(A)=(α).(A) = (\alpha).

(3)

t⋅1‾=t⋅1‾=t−α‾+α‾=v⃗1+αv⃗2.t\cdot\overline{1} = \overline{t\cdot1} = \overline{t-\alpha} + \overline{\alpha} = \vec{v}_{1} + \alpha\vec{v}_{2}.

Thus

(A)=(?1α).(A) = \begin{pmatrix} ? & 1\\ & \alpha \end{pmatrix}.

Now compute:

t⋅(t−α)‾=(t−α)⋅(t−α)‾+α⋅(t−α)‾=(t−α)2‾+α(t−α)‾=0+αv⃗1.\begin{aligned} t\cdot\overline{(t-\alpha)} &= (t-\alpha)\cdot\overline{(t-\alpha)} + \alpha\cdot\overline{(t-\alpha)}\\ &= \overline{(t-\alpha)^2} + \alpha\overline{(t-\alpha)}\\ &= 0+\alpha\vec{v}_{1}. \end{aligned}

Therefore,

A=(α10α).A = \begin{pmatrix} \alpha & 1\\ 0 & \alpha \end{pmatrix}.

Proposition 20.1 For

M=F[t]/(t−α)n,M=F[t]/(t-\alpha)^n,

with respect to the basis

(t−α)‾n−1,(t−α)‾n−2,…,(t−α)‾1,1‾,\overline{(t-\alpha)}^{n-1}, \overline{(t-\alpha)}^{n-2}, \ldots, \overline{(t-\alpha)}^{1}, \overline{1},

the matrix of the linear transformation

M→Mv⃗↦tv⃗\begin{aligned} M&\to M\\ \vec{v}&\mapsto t\vec{v} \end{aligned}

is

(α10000α10000α00⋱000α10000α),\begin{pmatrix} \alpha & 1 & 0 & & 0 & 0\\ 0 & \alpha & 1 & & 0 & 0\\ 0 & 0 & \alpha & & 0 & 0\\ & & & \ddots & &\\ 0 & 0 & 0 & & \alpha & 1\\ 0 & 0 & 0 & & 0 & \alpha \end{pmatrix},

where the diagonal entries are α\alpha, and the entry immediately above each α\alpha is 11, except above the topmost α\alpha.

Proof:

tvi=t(t−α)n−i‾=((t−α)+α)(t−α)‾n−i=(t−α)(t−α)‾n−i+α(t−α)‾n−i=(t−α)‾n−i+1+αv⃗i={v⃗i−1+αv⃗i,i⩽n−1,αv⃗n,i=n.\begin{aligned} tv_i = t\overline{(t-\alpha)^{n-i}} &= ((t-\alpha)+\alpha) \overline{(t-\alpha)}^{n-i}\\ &= (t-\alpha) \overline{(t-\alpha)}^{n-i} + \alpha \overline{(t-\alpha)}^{n-i}\\ &= \overline{(t-\alpha)}^{n-i+1} + \alpha\vec{v}_i\\ &= \begin{cases} \vec{v}_{i-1}+\alpha\vec{v}_i, & i\leqslant n-1,\\ \alpha\vec{v}_n, & i=n. \end{cases} \end{aligned}
 □~\tag*{$\square$}

Remark

Suppose MM and NN are finite-dimensional F[t]F[t]-modules, and there are bases

v1,…,vm for M,w1,…,wn for N,\begin{aligned} v_1,\ldots,v_m &~\text{for }M,\\ w_1,\ldots,w_n &~\text{for }N, \end{aligned}

such that multiplication by tt is given respectively by

the matrix A on M,the matrix B on N.\begin{aligned} &\text{the matrix }A~\text{on }M,\\ &\text{the matrix }B~\text{on }N. \end{aligned}

Then the action of tt on

M⊕NM\oplus N

is given by the matrix

(A00B),\begin{pmatrix} A&0\\ 0&B \end{pmatrix},

i.e. a block-diagonal matrix.

§20.2 Jordan Normal Form

Since every F[t]F[t]-module is isomorphic to

⨁iF[t]/(pini),\bigoplus_iF[t]/(p_in_i),

we obtain the following corollary.

Corollary 20.2 Let

T:Fn→FnT:F^n\to F^n

be an FF-linear transformation, and suppose that FF is algebraically closed.

Then there exists a basis of FnF^n with respect to which the matrix of TT is

(A10⋯00A2⋯0⋮⋱⋮0⋯0Ae),\begin{pmatrix} A_1&0&\cdots&0\\ 0&A_2&\cdots&0\\ \vdots&&\ddots&\vdots\\ 0&\cdots&0&A_e \end{pmatrix},

where

A1=(α11⋯00⋱⋮⋮⋱10⋯0α1),A_1 = \begin{pmatrix} \alpha_1&1&\cdots&0\\ 0&\ddots&&\vdots\\ \vdots&&\ddots&1\\ 0&\cdots&0&\alpha_1 \end{pmatrix},
A2=(α21⋯00⋱⋮⋮⋱10⋯0α2),A_2 = \begin{pmatrix} \alpha_2&1&\cdots&0\\ 0&\ddots&&\vdots\\ \vdots&&\ddots&1\\ 0&\cdots&0&\alpha_2 \end{pmatrix},

and so on, up to

Ae=(αe1⋯00⋱⋮⋮⋱10⋯0αe).A_e = \begin{pmatrix} \alpha_e&1&\cdots&0\\ 0&\ddots&&\vdots\\ \vdots&&\ddots&1\\ 0&\cdots&0&\alpha_e \end{pmatrix}.

Definition 20.2 This is called the Jordan normal form of TT.

§20.3 Characteristic Polynomials

Definition 20.3 The characteristic polynomial is

det⁡(tI−A)∈F[t].\det(tI-A)\in F[t].

Example 20.2 If

A=(A11A12A21A22),A = \begin{pmatrix} A_{11}&A_{12}\\ A_{21}&A_{22} \end{pmatrix},

then

tI−A=(t−A11A12A21t−A22).tI-A = \begin{pmatrix} t-A_{11}&A_{12}\\ A_{21}&t-A_{22} \end{pmatrix}.

Therefore,

det⁡(tI−A)=t2−(A11+A22)t+(A11A22−A12A21).\det(tI-A) = t^2-(A_{11}+A_{22})t + (A_{11}A_{22}-A_{12}A_{21}).

Remark If AA is a k×kk\times k matrix, then the coefficient of each term in the characteristic polynomial is an invariant of AA, remaining unchanged under conjugation:

det⁡(B(tI−A)B−1)=det⁡BB−1det⁡(tI−A)=det⁡(tI−A).\det(B(tI-A)B^{-1}) = \det BB^{-1}\det(tI-A) = \det(tI-A).

Definition 20.4 Any

A∈Mk×k(F)A\in M_{k\times k}(F)

determines a map

f:F[t]→Mk×k(F).f:F[t]\to M_{k\times k}(F).

Since F[t]F[t] is a principal ideal domain,

ker⁡(f)=(p),\ker(f) = (p),

where

p∈F[t].p\in F[t].

Choose the unique pp such that

p=td+adtd−1+⋯ ;p = t^d+a_dt^{d-1}+\cdots;
ker⁡(f)=(p).\ker(f)=(p).

We call pp the minimal polynomial of AA.

§20.4 Cayley-Hamilton Theorem

Theorem 20.3 (Cayley-Hamilton)

Every matrix AA satisfies its characteristic polynomial.

Remark This theorem is also true when FF is not algebraically closed.

Proof: With respect to the basis above,

det⁡(tI−A)=∏i=1e(t−αi)ni.\det(tI-A) = \prod_{i=1}^{e} (t-\alpha_i)^{n_i}.

Therefore, we need to prove

∏i=1e(A−αiI)ni=0.\prod_{i=1}^{e} (A-\alpha_iI)^{n_i} = 0.

But

1‾1,…,1‾e\overline{1}_1,\ldots,\overline{1}_e

generate vv as a module, and

(A−αiI)ni1‾j=0.(A-\alpha_iI)^{n_i}\overline{1}_j = 0.

This is because

(A−αiI)ni−1(1‾i)(A-\alpha_iI)^{n_i-1} (\overline{1}_i)

is an eigenvector.

 □~\tag*{$\square$}

Example 20.3 If

A=(abcd),A = \begin{pmatrix} a&b\\ c&d \end{pmatrix},

then its characteristic polynomial is

t2−t(a+d)+(ad−bc).t^2-t(a+d)+(ad-bc).

The theorem says that

A2−A(a+d)+I(ad−bc)=0∈M2×2(F).A^2-A(a+d)+I(ad-bc) = 0 \in M_{2\times2}(F).

Example 20.4 In another form, if

A∈Mk×k(F),A\in M_{k\times k}(F),

then its characteristic polynomial has the form

tk+bk−1tk−1+⋯+b1t+b0.t^k + b_{k-1}t^{k-1} + \cdots + b_1t + b_0.

The theorem says that for every

v⃗∈Fk,\vec{v}\in F^k,

we have

Akv⃗+bk−1Ak−1v⃗+⋯+b1Av⃗+b0v⃗=0.A^k\vec{v} + b_{k-1}A^{k-1}\vec{v} + \cdots + b_1A\vec{v} + b_0\vec{v} = 0.

Corollary 20.4 The minimal polynomial of AA divides its characteristic polynomial.

Proposition 20.5 Let

A∈Mk×k(F).A\in M_{k\times k}(F).

Then AA is invertible if and only if its columns form a basis.

Proof: Let

TAT_A

be the linear transformation

Fk→FkF^k\to F^k

defined by AA.

We need to prove that TAT_A is invertible, i.e. that TAT_A is injective and surjective.

TA(e⃗i)=v⃗i,where v⃗i is the ith column of A.T_A(\vec{e}_i) = \vec{v}_i, \quad \text{where }\vec{v}_i~\text{is the }i\text{th column of }A.
(⋮⋮v⃗1⋯v⃗k⋮⋮)(0⋮1⋮0)=(  v⃗i  ).\begin{pmatrix} \vdots&&\vdots\\ \vec{v}_1&\cdots&\vec{v}_k\\ \vdots&&\vdots \end{pmatrix} \begin{pmatrix} 0\\ \vdots\\ 1\\ \vdots\\ 0 \end{pmatrix} = \begin{pmatrix} ~\\ ~\\ \vec{v}_i\\ ~\\ ~ \end{pmatrix}.

Thus

TA(∑bie⃗i)=0⃗⟺∑biv⃗i=0⟺bi=0.T_A\left(\sum b_i\vec{e}_i\right) = \vec{0} \Longleftrightarrow \sum b_i\vec{v}_i = 0 \Longleftrightarrow b_i=0.

Since

ker⁡TA={0},\ker T_A = \{0\},

and TAT_A is a linear map from FkF^k to FkF^k, which have the same dimension, TAT_A is invertible.

 □~\tag*{$\square$}

Proposition 20.6 Let A′A^{\prime} be the matrix of TAT_A with respect to some basis

v1,…,vk.v_1,\ldots,v_k.

Let

B=(⋮⋮v⃗1⋯v⃗k⋮⋮).B = \begin{pmatrix} \vdots&&\vdots\\ \vec{v}_1&\cdots&\vec{v}_k\\ \vdots&&\vdots \end{pmatrix}.

Then

A′=BAB−1.A^{\prime} = BAB^{-1}.

Proof:

BAB−1(v⃗i)=BAe⃗i=B(∑Ajie⃗j)=∑Ajiv⃗j=A′(v⃗i).\begin{aligned} BAB^{-1}(\vec{v}_i) &= BA\vec{e}_i\\ &= B\left( \sum A_{ji}\vec{e}_j \right)\\ &= \sum A_{ji}\vec{v}_j\\ &= A^{\prime}(\vec{v}_i). \end{aligned}
 □~\tag*{$\square$}

Proposition 20.7 If BB is invertible and

A′=BAB−1,A^{\prime} = BAB^{-1},

then

det⁡(tI−A′)=det⁡(tI−A)∈F[t].\det(tI-A^{\prime}) = \det(tI-A) \in F[t].

Proof: In general,

det⁡(BCB−1)=det⁡Bdet⁡Cdet⁡B−1=det⁡Bdet⁡B−1det⁡C=det⁡BB−1det⁡C=det⁡Idet⁡C=det⁡C.\begin{aligned} \det(BCB^{-1}) &= \det B\det C\det B^{-1}\\ &= \det B\det B^{-1}\det C\\ &= \det BB^{-1}\det C\\ &= \det I\det C\\ &= \det C. \end{aligned}

Therefore,

det⁡(B(tI−A)B−1)=det⁡(tI−A).\det(B(tI-A)B^{-1}) = \det(tI-A).

Also,

det⁡(B(tI−A)B−1)=det⁡(BtIB−1−BAB−1)=det⁡(tI−BAB−1).\begin{aligned} \det(B(tI-A)B^{-1}) &= \det(BtIB^{-1}-BAB^{-1})\\ &= \det(tI-BAB^{-1}). \end{aligned}
 □~\tag*{$\square$}

So how do we compute the characteristic polynomial of an arbitrary

A∈Mk×k(F)?A\in M_{k\times k}(F)?

If FF is algebraically closed, then

A=BA′B−1,A = BA^{\prime}B^{-1},

where

A′=(A10⋯00A2⋯0⋮⋯⋱⋮0⋯0Ae)A^{\prime} = \begin{pmatrix} A_1&0&\cdots&0\\ 0&A_2&\cdots&0\\ \vdots&\cdots&\ddots&\vdots\\ 0&\cdots&0&A_e \end{pmatrix}

is a block-diagonal matrix, with

Ai=(αi10⋯00αi1⋯000αi⋯0⋮⋯⋯⋱⋮0⋯⋯0αi),αi∈F.A_i = \begin{pmatrix} \alpha_i&1&0&\cdots&0\\ 0&\alpha_i&1&\cdots&0\\ 0&0&\alpha_i&\cdots&0\\ \vdots&\cdots&\cdots&\ddots&\vdots\\ 0&\cdots&\cdots&0&\alpha_i \end{pmatrix}, \qquad \alpha_i\in F.

The entries αi\alpha_i lie on the diagonal, and immediately above each αi\alpha_i is a 11.

Therefore, we only need to compute

det⁡(tI−A′)=det⁡(t−α1−1⋯00t−α1⋯0⋮⋯⋱⋮0⋯⋯−10⋯⋯t−αe)=(t−α1)n1⋅(t−α2)n2⋅⋯⋅(t−αe)ne.\begin{aligned} \det(tI-A^{\prime}) &= \det \begin{pmatrix} t-\alpha_1&-1&\cdots&0\\ 0&t-\alpha_1&\cdots&0\\ \vdots&\cdots&\ddots&\vdots\\ 0&\cdots&\cdots&-1\\ 0&\cdots&\cdots&t-\alpha_e \end{pmatrix}\\ &= (t-\alpha_1)^{n_1} \cdot (t-\alpha_2)^{n_2} \cdot \cdots \cdot (t-\alpha_e)^{n_e}. \end{aligned}

This is because tI−A′tI-A^{\prime} is upper triangular, so its determinant is the product of its diagonal entries.

To prove

(A−α1)n1⋅⋯⋅(A−αe)ne=0,(A-\alpha_1)^{n_1} \cdot \cdots \cdot (A-\alpha_e)^{n_e} = 0,

it is enough to prove that for every vector v⃗\vec{v},

(A−α1)n1⋅⋯⋅(A−αe)nev⃗=0.(A-\alpha_1)^{n_1} \cdot \cdots \cdot (A-\alpha_e)^{n_e} \vec{v} = 0.

Now choose a basis

v⃗1,n1=1‾,…,v⃗1,1=(t−α1)‾n1−1∈F[t]/(t−α1)n1⋮v⃗e,ne=1‾,…,v⃗e,1=(t−αe)‾ne−1∈F[t]/(t−αe)ne.\begin{aligned} \vec{v}_{1,n_1} &= \overline{1}, \ldots, \vec{v}_{1,1} = \overline{(t-\alpha_1)}^{n_1-1} \in F[t]/(t-\alpha_1)^{n_1}\\ &\vdots\\ \vec{v}_{e,n_e} &= \overline{1}, \ldots, \vec{v}_{e,1} = \overline{(t-\alpha_e)}^{n_e-1} \in F[t]/(t-\alpha_e)^{n_e}. \end{aligned}

Then

{v⃗i,nj}\{\vec{v}_{i,n_j}\}

forms a basis of the vector space on which AA acts.

Moreover,

(A−α1)n1⋅⋯⋅(A−αi)ni⋅⋯⋅(A−αe)nev⃗i,j=(A−α1)n1⋅⋯⋅(A−αe)ne(A−αi)niv⃗i,j=(A−α1)n1⋅⋯⋅(A−αe)ne0⃗=0⃗.\begin{aligned} & (A-\alpha_1)^{n_1} \cdot \cdots \cdot (A-\alpha_i)^{n_i} \cdot \cdots \cdot (A-\alpha_e)^{n_e} \vec{v}_{i,j}\\ ={}& (A-\alpha_1)^{n_1} \cdot \cdots \cdot (A-\alpha_e)^{n_e} (A-\alpha_i)^{n_i} \vec{v}_{i,j}\\ ={}& (A-\alpha_1)^{n_1} \cdot \cdots \cdot (A-\alpha_e)^{n_e} \vec{0}\\ ={}& \vec{0}. \end{aligned}

The second and third equalities hold because, by our choice of basis,

Av⃗i,j=v⃗i,j−1+αiv⃗i,j.A\vec{v}_{i,j} = \vec{v}_{i,j-1} + \alpha_i\vec{v}_{i,j}.

On the other hand,

Av⃗i,1=αiv⃗i,1.A\vec{v}_{i,1} = \alpha_i\vec{v}_{i,1}.

Therefore,

(A−αi)v⃗i,j={v⃗i,j−1,j>1,0,j=1.(A-\alpha_i)\vec{v}_{i,j} = \begin{cases} \vec{v}_{i,j-1}, & j>1,\\ 0, & j=1. \end{cases}

Thus we have proved that if FF is algebraically closed, then every

A∈Mk×k(F)A\in M_{k\times k}(F)

satisfies its characteristic polynomial

det⁡(tI−A).\det(tI-A).

What if FF is not algebraically closed?

Let

F‾\overline{F}

be an algebraically closed field containing FF.

Then we have inclusion maps

Mk×k(F)↪Mk×k(F‾)M_{k\times k}(F) \hookrightarrow M_{k\times k}(\overline{F})

and

F[t]↪F‾[t].F[t] \hookrightarrow \overline{F}[t].

We may regard any matrix with coefficients in FF as a matrix with coefficients in F‾\overline{F}.

Similarly, any polynomial with coefficients in FF may also be regarded as a polynomial with coefficients in F‾\overline{F}.

Putting these observations together, the diagram

commutes.

Therefore, if

?→0,?\to0,

then this shows that

??

must itself be zero.

In simpler terms, substituting a matrix into its characteristic polynomial gives the same result whether we regard the matrix as having coefficients in FF or in F‾\overline{F}.