02 poly
PDF · 33 pages · 233.0 KB
Open PDF file
Chapter 2 of a linear algebra course (folder suggests Matthews' notes), covering polynomials over a field F. Topics include polynomial multiplication and its properties, Lagrange interpolation polynomials as a basis, Euclid's division theorem and algorithm with gcd, irreducible polynomials and unique factorization, and existence of irreducibles of every degree over a finite field. It ends with minimum polynomials of square matrices and companion matrices.
AI-written summary; may contain errors.
Extracted text (machine-read; may contain errors)
2 Polynomials over a eld
A polynomial over a eld Fis a sequence
(a0;a1;a2;:::;an;:::) where ai2F8i
withai= 0 from some point on. aiis called the i{th coecient of f.
We de ne three special polynomials. . .
0 = (0;0;0;:::)
1 = (1;0;0;:::)
x= (0;1;0;:::):
The polynomial ( a0;:::) is called a constant and is written simply as a0.
LetF[x] denote the set of all polynomials in x.
Iff6= 0, then the degree off, written deg f, is the greatest nsuch
thatan6= 0. Note that the polynomial 0 has no degree.
anis called the `leading coecient' of f.
F[x] forms a vector space over Fif we de ne
(a0; a1;:::) = (a0; a 1;:::); 2F:
DEFINITION 2.1
(Multiplication of polynomials )
Letf= (a0;a1;:::)andg= (b0;b1;:::). Thenfg= (c0;c1;:::)where
cn=a0bn+a1bn 1++anb0
=nX
i=0aibn i
=X
0i;0j
i+j=naibj:
EXAMPLE 2.1
x2= (0;0;1;0;:::); x3= (0;0;0;1;0;:::):
More generally, an induction shows that xn= (a0;:::), wherean= 1and
all otheraiare zero.
If degf=n, we havef=a01 +a1x++anxn.
20
THEOREM 2.1 (Associative Law)
f(gh) = (fg)h
PROOF Take f;gas above and h= (c0;c1;:::). Thenf(gh) = (d0;d1;:::),
where
dn=X
i+j=n(fg)ihj
=X
i+j=n X
u+v=ifugv!
hj
=X
u+v+j=nfugvhj:
Likewise (fg)h= (e0;e1;:::), where
en=X
u+v+j=nfugvhj
Some properties of polynomial arithmetic:
fg =gf
0f= 0
1f=f
f(g+h) =fg+fh
f6= 0 andg6= 0)fg6= 0
and deg(fg) = degf+ degg:
The last statement is equivalent to
fg= 0)f= 0 org= 0:
The we deduce that
fh=fgandf6= 0)h=g:
2.1 Lagrange Interpolation Polynomials
LetPn[F] denote the set of polynomials a0+a1x++anxn, where
a0;:::;an2F. Thena0+a1x++anxn= 0 implies that a0= 0;:::;an= 0.
Pn[F] is a subspace of F[x] and 1;x;x2;:::;xnform the `standard' basis
forPn[F].
21
Iff2Pn[F] andc2F, we write
f(c) =a0+a1c++ancn:
This is the\value of fatc". This symbol has the following properties:
(f+g)(c) =f(c) +g(c)
(f)(c) =(f(c))
(fg)(c) =f(c)g(c)
DEFINITION 2.2
Letc1;:::;cn+1be distinct members of F. Then the Lagrange inter-
polation polynomials p1;:::;pn+1are polynomials of degree nde ned
by
pi=n+1Y
j=1
j6=ix cj
ci cj
;1in+ 1:
EXAMPLE 2.2
p1=x c2c1 c2 x c3c1 c3
x cn+1c1 cn+1
p2=x c1c2 c1
x c3c2 c3
x cn+1c2 cn+1
etc. . .
We now show that the Lagrange polynomials also form a basis for Pn[F].
PROOF Noting that there are n+ 1 elements in the `standard' basis, above,
we see that dim Pn[F] =n+ 1 and so it suces to show that p1;:::;pn+1
are LI.
We use the following property of the polynomials pi:
pi(cj) =ij=1 ifi=j
0 ifi6=j.
Assume that
a1p1++an+1pn+1= 0
whereai2F;1in+ 1. Evaluating both sides at c1;:::;cn+1gives
a1p1(c1) ++an+1pn+1(c1) = 0
...
a1p1(cn+1) ++an+1pn+1(cn+1) = 0
22
)
a11 +a20 ++an+10 = 0
a10 +a21 ++an+10 = 0
...
a10 +a20 ++an+11 = 0
Henceai= 08ias required.
COROLLARY 2.1
Iff2Pn[F]then
f=f(c1)p1++f(cn+1)pn+1:
Proof : We know that
f=1p1++n+1pn+1 for somei2F.
Evaluating both sides at c1;:::;cn+1then, gives
f(c1) =1;
...
f(cn+1) =n+1
as required.
COROLLARY 2.2
Iff2Pn[F]andf(c1) = 0;:::;f (cn+1) = 0 wherec1;:::;cn+1are dis-
tinct, then f= 0. (I.e. a non-zero polynomial of degree ncan have at most
nroots.)
COROLLARY 2.3
Ifb1;:::;bn+1areanyscalars inF, andc1;:::;cn+1are again distinct,
then there exists a unique polynomial f2Pn[F]such that
f(c1) =b1;:::;f (cn+1) =bn+1;
namely
f=b1p1++bn+1pn+1:
23
EXAMPLE 2.3
Find the quadratic polynomial
f=a0+a1x+a2x22P2[R]
such that
f(1) = 8;f(2) = 5;f(3) = 4:
Solution :f= 8p1+ 5p2+ 4p3where
p1=(x 2)(x 3)
(1 2)(1 3)
p2=(x 1)(x 3)
(2 1)(2 3)
p3=(x 1)(x 2)
(3 1)(3 2)
2.2 Division of polynomials
DEFINITION 2.3
Iff;g2F[x], we sayfdividesgif9h2F[x]such that
g=fh:
For this we write \ fjg", and \f6jg" denotes the negation \ fdoes not di-
videg".
Some properties :
fjgandg6= 0)degfdegg
and thus of course
fj1)degf= 0:
2.2.1 Euclid's Division Theorem
Letf;g2F[x] andg6= 0.
Then9q;r2F[x] such that
f=qg+r; (3)
wherer= 0 or degr<degg. Moreover qandrare unique.
Outline of Proof:
24
Iff= 0 or degf <degg, (3) is trivially true (taking q= 0 andr=f).
So assume deg fdegg, where
f=amxm+am 1xm 1+a0;
g=bnxn++b0
and we have a long division process, viz:
amb 1
nxm n+
bnxn++b0amxm+am 1xm 1++a0
amxm
etc. . .
(See S. Perlis, Theory of Matrices, p.111.)
2.2.2 Euclid's Division Algorithm
f=q1g+r1 with deg r1<degg
g=q2r1+r2 with deg r2<degr1
r1=q3r2+r3 with deg r3<degr2
. . . .... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
rn 2=qnrn 1+rnwith degrn<degrn 1
rn 1=qn+1rn
Thenrn= gcd(f;g), the greatest common divisor offandg|i.e.
rnis a polynomial dwith the property that
1.djfanddjg, and
2.8e2F[x],ejfandejg)ejd.
(This de nes gcd( f;g) uniquely up to a constant multiple.)
We select the monic (i.e. leading coecient = 1) gcd as \the" gcd.
Also,9u;v2F[x] such that
rn= gcd(f;g)
=uf+vg
| nduandvby `forward substitution' in Euclid's algorithm; viz.
r1=f+ ( q1)g
r2=g+ ( q2)r1
25
=g+ ( q2)(f+ ( q1)g)
=g+ ( q2)f+ (q1q2)g
= ( q2)f+ (1 +q1q2)g
...
rn= (:::)|{z}
uf+ (:::)|{z}
vg:
In general, rk=skf+tkgfor 1kn, where
r 1=f; r 0=g; s 1= 1; s0= 0; t 1= 0; t0= 1
and
sk= qksk 1+sk 2; tk= qktk 1+tk 2
for 1kn. (Proof by induction.)
The special case gcd( f;g) = 1 (i.e.fandgarerelatively prime ) is of
great importance: here 9u;v2F[x] such that
uf+vg= 1:
EXERCISE 2.1
Find gcd(3x2+ 2x+ 4;2x4+ 5x+ 1) inQ[x]and express it as uf+vg
for two polynomials uandv.
2.3 Irreducible Polynomials
DEFINITION 2.4
Letfbe a non-constant polynomial. Then, if
gjf)gis a constant
or g =constantf
we callfanirreducible polynomial .
Note : (Remainder theorem )
f= (x a)q+f(a) wherea2F. Sof(a) = 0 i (x a)jf.
EXAMPLE 2.4
f(x) =x2+x+ 12Z2[x]is irreducible, for f(0) =f(1) = 16= 0, and
hence there are no polynomials of degree 1 which divide f.
26
THEOREM 2.2
Letfbe irreducible. Then if f6jg,gcd(f;g) = 1 and9u;v2F[x]such
that
uf+vg= 1:
PROOF Suppose fis irreducible and f6jg. Letd= gcd(f;g) so
djfanddjg:
Then either d=cffor some constant c, ord= 1. But if d=cfthen
fjdanddjg
)fjg|a contradiction.
Sod= 1 as required.
COROLLARY 2.4
Iffis irreducible and fjgh, thenfjgorfjh.
Proof : Supposefis irreducible and fjgh,f6jg. We show that fjh.
By the above theorem, 9u;vsuch that
uf+vg= 1
)ufh+vgh =h
)fjh
THEOREM 2.3
Any non-constant polynomial is expressible as a product of irreducible
polynomials where representation is unique up to the order of the irreducible
factors.
Some examples:
(x+ 1)2=x2+ 2x+ 1
=x2+ 1 inZ2[x]
(x2+x+ 1)2=x4+x2+ 1 inZ2[x]
(2x2+x+ 1)(2x+ 1) =x3+x2+ 1 inZ3[x]
= (x2+ 2x+ 2)(x+ 2) inZ3[x]:
PROOF
27
Existence of factorization: Iff2F[x] is not a constant polynomial, then
fbeing irreducible implies the result.
Otherwise, f=f1F1, with 0<degf1;degF1<degf. Iff1andF1are
irreducible, stop. Otherwise, keep going.
Eventually we end with a decomposition of finto irreducible poly-
nomials.
Uniqueness: Let
cf1f2fm=dg1g2gn
be two decompositions into products of constants ( candd) and monic
irreducibles ( fi;gj). Now
f1jf1f2fm=)f1jg1g2gn
and sincefi;giare irreducible we can cancel f1and somegj.
Repeating this for f2;:::;fm, we eventually obtain m=nandc=d|
in other words, each expression is simply a rearrangement of the factors
of the other, as required.
THEOREM 2.4
LetFqbe a eld with qelements. Then if n2N, there exists an irred-
ucible polynomial of degree ninF[x].
PROOF First we introduce the idea of the Riemann zeta function :
(s) =1X
n=11
ns=Y
pprime1
1 1
ps:
To see the equality of the latter expressions note that
1
1 x=1X
i=0xi= 1 +x+x2+
and so
R.H.S. =Y
pprime 1X
i=01
pis!
=
1 +1
2s+1
22s+
1 +1
3s+1
32s+
= 1 +1
2s+1
3s+1
4s+
28
|note for the last step that terms will be of form
1
pa1
1paR
Rs
up to some prime pR, withai08i= 1;:::;R . and asR!1 , the prime
factorizations
pa1
1paR
R
map onto the natural numbers, N.
We letNmdenote the number of monic irreducibles of degree minFq[x].
For example, N1=qsincex+a;a2Fqare the irreducible polynomials of
degree 1.
Now letjfj=qdegf, andj0j= 0. Then we have
jfgj=jfjjgjsince degfg= degf+ degg
and, because of the uniqueness of factorization theorem,
X
fmonic1
jfjs=Y
fmonic and
irreducible1
1 1
jfjs:
Now the left hand side is
1X
n=0X
fmonic and
degf=n1
jfjs
=1X
n=0qn
qns
(there areqnmonic polynomials of degree n)
=1X
n=01
qn(s 1)
=1
1 1
qs 1
and R.H.S. =1Y
n=11
1 1
qnsNn:
29
Equating the two, we have
1
1 1
qs 1=1Y
n=11
1 1
qnsNn: (4)
We now take logs of both sides, and then use the fact that
log1
1 x
=1X
n=1xn
nifjxj<1;
so (4) becomes
log1
1 q (s 1)=1Y
n=11
1 1
qnsNn
)1X
k=11
kq(s 1)k= 1X
n=1Nnlog
1 1
qns
=1X
n=1Nn1X
m=11
mqmns
so1X
k=1qk
kqsk=1X
n=1Nn1X
m=1n
mnqmns
=1X
k=1P
mn=knNn
kqks:
Puttingx=qs, we have
1X
k=1qkxk
k=1X
k=1xkX
mn=knNn;
and since both sides are power series, we may equate coecients of xkto
obtain
qk=X
mn=knNn=X
njknNn: (5)
We can deduce from this that Nn>0 asn!1 (see Berlekamp's \ Algebraic
Coding Theory ").
Now note that N1=q, so ifkis a prime|say k=p, (5) gives
qp=N1+pNp=q+pNp
)Np=qp q
p>0 asq>1 andp2.
30
This proves the theorem for n=p, a prime.
But what if kis not prime? Equation (5) also tells us that
qkkNk:
Now letk2. Then
qk=kNk+X
njk
n6=knNn
kNk+X
njk
n6=kqn(asnNnqn)
kNk+bk=2cX
n=1qn
< kNk+bk=2cX
n=0qn(adding 1)
=kNk+qbk=2c+1 1
q 1(sum of geometric series).
But
qt+1 1
q 1<qt+1ifq2,
so
qk< kNk+qbk=2c+1
)Nk>qk qbk=2c+1
k
0 ifqkqbk=2c+1.
Sinceq>1 (we cannot have a eld with a single element, since the additive
and multiplicative identities cannot be equal by one of the axioms), the
latter condition is equivalent to
kbk=2c+ 1
which is true and the theorem is proven.
31
2.4 Minimum Polynomial of a (Square) Matrix
LetA2Mnn(F), andg= chA. Theng(A) = 0 by the Cayley{Hamilton
theorem.
DEFINITION 2.5
Any non{zero polynomial gof minimum degree and satisfying g(A) = 0
is called a minimum polynomial ofA.
Note: Iffis a minimum polynomial of A, thenfcannot be a constant
polynomial. For if f=c, a constant, then 0 = f(A) =cInimpliesc= 0.
THEOREM 2.5
Iffis a minimum polynomial of Aandg(A) = 0 , thenfjg. (In partic-
ular,fjchA.)
PROOF Let g(A) = 0 andfbe a minimum polynomial. Then
g=qf+r;
wherer= 0 or degr<degf. Hence
g(A) =q(A)0 +r(A)
0 =r(A):
So ifr6= 0, the inequality deg r<degfwould give a contradict the de ni-
tion off. Consequently r= 0 andfjg.
Note : It follows that if fandgare minimum polynomials of A, thenfjg
andgjfand consequently f=cg, wherecis a scalar. Hence there is a
unique monic minimum polynomial and we denote it by mA.
EXAMPLES (of minimum polynomials):
1.A= 0,mA=x
2.A=In,mA=x 1
3.A=cIn,mA=x c
4.A2=AandA6= 0 andA6=In,mA=x2 x:
EXAMPLE 2.5
F=Qand
A=2
45 6 6
1 4 2
3 6 43
5:
32
Now
A6=c0I3; c02Q;somA6=x c0;
A2= 3A 2I3
)mA=x2 3x+ 2
This is an special case of a general algorithm:
(Minimum polynomial algorithm ) LetA2Mnn(F). Then we nd the
least positive integer rsuch thatAris expressible as a linear combination
of the matrices
In; A;:::;Ar 1;
say
Ar=c0+c1A++cr 1Ar 1:
(Such an integer must exist as In; A;:::;An2form a linearly dependent
family in the vector space Mnn(F) and this latter space has dimension
equal ton2.)
ThenmA=xr cr 1xr 1 c1x c0.
THEOREM 2.6
Iff=xn+an 1xn 1++a1x+a02F[x], thenmC(f)=f, where
C(f) =2
6666640 0 0 a0
1 00 a1
0 1 0 a2
.........
0 01 an 13
777775
.
PROOF For brevity denote C(f) byA. Then post-multiplying Aby the
respective unit column vectors E1;:::;Engives
AE1=E2
AE2=E3)A2E1=E3
...
AEn 1=En)An 1E1=En
AEn= a0E1 a2E2 an 1En
= a0E1 a2AE1 an 1An 1E1=AnE1;
33
so
)f(A)E1= 0) rst column of f(A) zero
Now although matrix multiplication is not commutative, multiplication of
two matrices, each of which is a polynomial in a given square matrix A, is
commutative. Hence f(A)g(A) =g(A)f(A) iff; g2F[x]. Takingg=x
gives
f(A)A=Af(A):
Thus
f(A)E2=f(A)AE1=Af(A)E1= 0
and so the second column of Ais zero. Repeating this for E3;:::;En, we
see that
f(A) = 0
and thusmAjf.
To showmA=f, we assume deg mA=t<n ; say
mA=xt+bt 1xt 1++b0:
Now
mA(A) = 0
)At+bt 1At 1++b0In= 0
)(At+bt 1At 1++b0In)E1= 0;
and recalling that AE1=E2etc., andt<n , we have
Et+1+bt 1Et++b1E2+b0E1= 0
which is a contradiction|since the Eiare independent, the coecient of
Et+1cannot be 1.
HencemA=f.
Note : It follows that ch A=f. Because both ch AandmAhave degree n
and moreover mAdivides ch A.
EXERCISE 2.2
IfA=Jn(a)fora2F, anelementary Jordan matrix of sizen, show
34
thatmA= (x a)nwhere
A=Jn(a) =2
66666664a0 0
1a
0 1
.........
0 0a0
0 0 1 a3
77777775
(i.e.Ais annnmatrix with a's on the diagonal and 1's on the subdiag-
onal).
Note : Again, the minimum polynomial happens to equal the characteristic
polynomial here.
DEFINITION 2.6
(Direct Sum of Matrices )
LetA1;:::;Atbe matrices over F. Then the direct sum of these matrices
is de ned as follows:
A1A2At=2
6664A10:::
0A2
.........
0At3
7775:
Properties:
1.
(A1At) + (B1Bt) = (A1+B1) (At+Bt)
2. If2F,
(A1At) = (A1) (At)
3.
(A1At)(B1Bt) = (A1B1) (AtBt)
4. Iff2F[x]andA1;:::;Atare square,
f(A1At) =f(A1)f(At)
DEFINITION 2.7
Iff1;:::;ft2F[x], we callf2F[x]a least common multiple ( lcm) of
f1;:::;ftif
35
1.f1jf;:::ftjf, and
2.f1je;:::ftje)fje.
This uniquely de nes the lcmup to a constant multiple and so we set \the"
lcmto be the monic lcm.
EXAMPLES 2.1
Iffg6= 0,lcm (f;g)jfg.
(Recursive property)
lcm (f1;:::;ft+1) = lcm ( lcm ( f1;:::;ft);ft+1):
THEOREM 2.7
mA1At= lcm (mA1;:::;mAt);
Also
chA1At=tY
i=1chAi:
PROOF Let f= L.H.S. and g= R.H.S. Then
f(A1At) = 0
)f(A1)f(At) = 0 0
)f(A1) = 0;:::;f (At) = 0
)mA1jf;:::;mAtjf
)gjf:
Conversely,
mA1jg;:::;mAtjg
)g(A1) = 0;:::;g (At) = 0
)g(A1)g(At) = 0 0
)g(A1At) = 0
)f=mA1Atjg:
Thusf=g.
EXAMPLE 2.6
LetA=C(f)andB=C(g).
ThenmAB= lcm (f;g).
36
Note : If
f=cpa1
1:::pat
t
g=dpb1
1:::pbt
t
wherec;d6= 0 are inFandp1;:::;ptare distinct monic irreducibles, then
gcd(f;g) =pmin(a1;b1)
1:::pmin(at;bt)
t;
lcm (f;g) =pmax(a1;b1)
1:::pmax(at;bt)
t
Note
min(ai;bi) + max(ai;bi) =ai+bi:
so
gcd(f; g) lcm (f; g) =fg:
EXAMPLE 2.7
IfA= diag (1;:::;n), thenmA= (x c1)(x ct), wherec1;:::;ct
are the distinct members of the sequence 1;:::;n.
PROOF. For Ais the direct sum of the 1 1 matrices 1;:::;nhaving
minimum polynomials x 1;:::;n. Hence
mA= lcm (x 1;:::;x n) = (x c1)(x ct):
We know that mAjchA. Hence if
chA=pa1
1:::pat
t
wherea1>0;:::;at>0, andp1;:::;ptare distinct monic irreducibles, then
mA=pb1
1:::pbt
t
where 0biai;8i= 1;:::;t .
We soon show that each bi>0, i.e. ifpjchAandpis irreducible then
pjmA.
37
2.5 Construction of a eld of pnelements
(wherepis prime and n2N)
Letfbe a monic irreducible polynomial of degree ninZp[x]|that is,
Fq=Zphere.
For instance,
n= 2;p= 2)x2+x+ 1 =f
n= 3;p= 2)x3+x+ 1 =forx3+x2+ 1 =f:
LetA=C(f), the companion matrix of f. Then we know f(A) = 0.
We assert that the set of all matrices of the form g(A), whereg2Zp[x],
forms a eld consisting of precisely pnelements. The typical element is
b0In+b1A++btAt
whereb0;:::;bt2Zp.
We need only show existence of a multiplicative inverse for each element
except 0 (the additive identity), as the remaining axioms clearly hold.
So letg2Zp[x] such thatg(A)6= 0. We have to nd h2Zp[x] satisfying
g(A)h(A) =In:
Note thatg(A)6= 0)f6jg, since
fjg)g=ff1
and hence
g(A) =f(A)f1(A) = 0f1(A) = 0:
Then since fis irreducible and f6jg, there exist u; v2Zp[x] such that
uf+vg= 1:
Henceu(A)f(A) +v(A)g(A) =Inandv(A)g(A) =In, as required.
We now show that our new eld is a Zp{vector space with basis consisting
of the matrices
In; A;:::;An 1:
Firstly the spanning property: By Euclid's division theorem,
g=fq+r
38
whereq;r2Zp[x] and degr<degg. So let
r=r0+r1x++rn 1xn 1
wherer0;:::;rn 12Zp. Then
g(A) =f(A)q(A) +r(A)
= 0q(A) +r(A)
=r(A)
=r0In+r1A++rn 1An 1
Secondly, linear independence over Zp: Suppose that
r0In+r1A++rn 1An 1= 0;
wherer0; r1;:::;rn 12Zp. Thenr(A) = 0, where
r=r0+r1x++rn 1xn 1:
HencemA=fdividesr. Consequently r= 0, as deg f=nwhereas
degr<n ifr6= 0.
Consequently, there are pnsuch matrices g(A) in the eld we have con-
structed.
Numerical Examples
EXAMPLE 2.8
Letp= 2,n= 2,f=x2+x+ 12Z2[x], andA=C(f). Then
A=0 1
1 1
=0 1
1 1
;
and
F4=fa0I2+a1Aja0;a12Z2g
=f0; I2; A; I 2+Ag:
We construct addition and multiplication tables for this eld, with B=
I2+A(as an exercise, check these):
0I2AB
00I2AB
I2I20BA
AAB0I2
BBAI20
0I2AB
00000
I20I2AB
A0ABI2
B0BI2A
39
EXAMPLE 2.9
Letp= 2,n= 3,f=x3+x+ 12Z2[x]. Then
A=C(f) =2
40 0 1
1 0 1
0 1 03
5=2
40 0 1
1 0 1
0 1 03
5;
and our eight-member eld F8(usually denoted by GF(8)[\GF" corresponds
to \Galois Field", in honour of Galois]) is
F8=fa0I3+a1A+a2A2ja0;a1;a22Z2g
=f0;I3;A;A2;I3+A;I 3+A2;A+A2;I3+A+A2g:
Now nd (A2+A) 1.
Solution : use Euclid's algorithm.
x3+x+ 1 = (x+ 1)(x2+x) + 1:
Hence
x3+x+ 1 + (x+ 1)(x2+x) = 1
A3+A+I3+ (A+I3)(A2+A) =I3
(A+I3)(A2+A) =I3:
Hence (A2+A) 1=A+I3.
THEOREM 2.8
Every nite eld has precisely pnelements for some prime p|the least
positive integer with the property that
1 + 1 + 1 ++ 1|{z}
p= 0:
pis then called the characteristic of the eld.
Also, ifx2F, a eld ofqelements, then it can be shown that if x6= 0,
then
xq 1= 1:
In the special case F=Zp, this reduces to Fermat's Little Theorem :
xp 11 (modp);
ifpis prime not dividing x.
40
2.6 Characteristic and Minimum Polynomial of a Transform-
ation
DEFINITION 2.8
(Characteristic polynomial of T:V7!V)
Let be a basis for VandA= [T]
.
Then we de ne chT= chA. This polynomial is independent of the basis
:
PROOF ( ch Tis independent of the basis.)
If
is another basis for VandB= [T]
, then we know A=P 1BP
wherePis the change of basis matrix [ IV]
.
Then
chA= chP 1BP
= det(xIn P 1BP) wheren= dimV
= det(P 1(xIn)P P 1BP)
= det(P 1(xIn B)P)
= detP 1chBdetP
= chB:
DEFINITION 2.9
Iff=a0++atxt, wherea0;:::;at2F, we de ne
f(T) =a0IV++atTt:
Then the usual properties hold:
f; g2F[x])(f+g)(T) =f(T)+g(T) and (fg)(T) =f(T)g(T) =g(T)f(T):
LEMMA 2.1
f2F[x])[f(T)]
=f
[T]
:
Note : The Cayley-Hamilton theorem for matrices says that ch A(A) = 0.
Then ifA= [T]
, we have by the lemma
[ chT(T)]
= chT(A) = chA(A) = 0;
so chT(T) = 0V.
41
DEFINITION 2.10
LetT:V!Vbe a linear transformation over F. Then any polynomial
of least positive degree such that
f(T) = 0V
is called a minimum polynomial of T.
We have corresponding results for polynomials in a transformation Tto
those for polynomials in a square matrix A:
g=qf+r)g(T) =q(T)f(T) +r(T):
Again, there is a unique monic minimum polynomial of Tis denoted by mT
and called \the" minimum polynomial of T.
Also note that because of the lemma,
mT=m[T]
:
For (withA= [T]
)
(a)mA(A) = 0, somA(T) = 0V. HencemTjmA.
(b)mT(T) = 0V, so [mT(T)]
= 0. Hence mT(A) = 0 and so mAjmT.
EXAMPLES 2.2
T= 0V,mT=x.
T=IV,mT=x 1.
T=cIV,mT=x c.
T2=TandT6= 0VandT6=IV,mT=x2 x:
2.6.1Mnn(F[x])|Ring of Polynomial Matrices
Example:x2+ 2x5+ 5x+ 1
x+ 3 1
2M22(Q[x])
=x50 1
0 0
+x21 0
0 0
+x0 5
1 0
+2 1
3 1
|we see that any element of Mnn(F[x]) is expressible as
xmAm+xm 1Am 1++A0
whereAi2Mnn(F). We write the coecient of xiafterxi, to distinguish
these entities from corresponding objects of the following ring.
42
2.6.2Mnn(F)[y]|Ring of Matrix Polynomials
This consists of all polynomials in ywith coecients in Mnn(F).
Example:
0 1
0 0
y5+1 0
0 0
y2+0 5
1 0
y+2 1
3 1
2M22(F)[y]:
THEOREM 2.9
The mapping
:Mnn(F)[y]7!Mnn(F[x])
given by
(A0+A1y++Amym) =A0+xA1++xmAm
whereAi2Mnn(F), is a 1{1 correspondence and has the following prop-
erties:
(X+Y) = (X) + (Y)
(XY) = (X)(Y)
(tX) =t(X)8t2F:
Also
(Iny A) =xIn A8A2Mnn(F):
THEOREM 2.10 ((Left) Remainder theorem for matrix polynomials)
LetBmym++B02Mnn(F)[y]andA2Mnn(F).
Then
Bmym++B0= (Iny A)Q+R
where
R=AmBm++AB1+B0
andQ=Cm 1ym 1++C0
whereCm 1;:::;C 0are computed recursively:
Bm=Cm 1
Bm 1= ACm 1+Cm 2
...
B1= AC1+C0:
43
PROOF. First we verify that B0= AC0+R:
R=AmBm=AmCm 1
+Am 1Bm 1 AmCm 1+Am 1Cm 2
+ +
......
+AB1 A2C1+AC0
+B0B0
=B0+AC0:
Then
(Iny A)Q+R= (Iny)(Cm 1ym 1++C0)
A(Cm 1ym 1++C0) +AmBm++B0
=Cm 1ym+ (Cm 2 ACm 1)ym 1++ (C0 AC1)y+
AC0+R
=Bmym+Bm 1ym 1++B1y+B0:
Remark. There is a similar \right" remainder theorem.
THEOREM 2.11
Ifpis an irreducible polynomial dividing chA, thenpjmA.
PROOF (From Burton Jones, "Linear Algebra").
LetmA=xt+at 1xt 1++a0and consider the matrix polynomial
iny
1(mAIn) =Inyt+ (at 1In)yt 1++ (a0In)
= (Iny A)Q+AtIn+At 1(at 1In) ++a0In
= (Iny A)Q+mT(A)
= (Iny A)Q:
Now take of both sides to give
mAIn= (xIn A)(Q)
and taking determinants of both sides yields
fmAgn= chAdet (Q):
44
So lettingpbe an irreducible polynomial dividing ch A, we havepjfmAgn
and hencepjmA.
Alternative simpler proof (MacDu ee):
mA(x) mA(y) = (x y)k(x;y), wherek(x;y)2F[x;y]. Hence
mA(x)In=mA(xIn) mA(A) = (xIn A)k(xIn;A):
Now take determinants to get
mA(x)n=chA(x) detk(xIn;A):
Exercise: If ( x) is the gcd of the elements of adj(xIn A), use the
equation (xIn a)adj(xIn A) =chA(x)Inand an above equation to deduce
thatmA(x) =chA(x)=(x).
EXAMPLES 2.3
WithA= 02Mnn(F), we have chA=xnandmA=x.
A= diag (1;1;2;2;2)2M55(Q). Here
chA= (x 1)2(x 2)3andmA= (x 1)(x 2):
DEFINITION 2.11
A matrixA2Mnn(F)is called diagonable overFif there exists a
non{singular matrix P2Mnn(F)such that
P 1AP= diag (1;:::;n);
where1;:::;nbelong toF.
THEOREM 2.12
IfAis diagonable, then mAis a product of distinct linear factors.
PROOF
IfP 1AP= diag (1;:::;n) (with1;:::;n2F) then
mA=mP 1AP=mdiag (1;:::;n)
= (x c1)(x c2):::(x ct)
wherec1;:::;ctare the distinct members of the sequence 1;:::;n.
The converse is also true, and will (fairly) soon be proved.
45
EXAMPLE 2.10
A=Jn(a):
We saw earlier that mA= (x a)nso ifn2we see that Ais not diago-
nable.
DEFINITION 2.12
(Diagonable LTs )
T:V7!Vis called diagonable overFif there exists a basis forV
such that [T]
is diagonal.
THEOREM 2.13
Ais diagonable,TAis diagonable.
PROOF (Sketch)
)SupposeP 1AP= diag (1;:::;n). Now pre-multiplying by Pand
lettingP= [P1jjPn] we see that
TA(P1) =AP1=1P1
...
TA(Pn) =APn=nPn
and we let be the basis P1;:::;PnoverVn(F). Then
[TA]
=2
66641
2
...
n3
7775:
(Reverse the argument and use Theorem 1.17.
THEOREM 2.14
LetA2Mnn(F):Then ifis an eigenvalue of Awith multiplicity m,
(that is (x )mis the exact power of x which divides chA), we have
nullity (A In)m:
46
REMARKS. (1) If m= 1, we deduce that nullity ( A In) = 1. For the
inequality
1nullity (A In)
always holds.
(2) The integer nullity ( A In) is called the geometric multiplicity of
the eigenvalue , whilemis referred to as the algebraic multiplicity of.
PROOF. Let v1;:::;vrbe a basis for N(A In), whereis an eigenvalue
ofAhaving multiplicity m. Extend this linearly independent family to a
basisv1;:::;vr; vr+1;:::;vnofVn(F). Then the following equations hold:
Av1=v1
...
Avr=vr
Avr+1=b11v1++bn1vn
...
Avn=b1n rv1++bnn rvn:
These equations can be combined into a single matrix equation:
A[v1jjvrjvr+1jjvn] = [Av1jjAvrjAvr+1jjAvn]
= [v1jjvrjb11v1++bn1vnjjb1n rv1++bnn rvn]
= [v1jjvn]IrB1
0B2
:
Hence ifP= [v1jjvn], we have
P 1AP=IrB1
0B2
:
Then
chA= chP 1AP= chIrchB2= (x )rchB2
and because ( x )mis the exact power of x dividing ch A, it follows
that
nullity (A In) =rm:
THEOREM 2.15
Suppose that chT= (x c1)a1(x ct)at. ThenTis diagonable if
nullity (T ciIv) =aifor1it:
47
PROOF. We rst prove that the subspaces Ker ( T ciIV) are independent.
(Subspaces V1;:::;Vtare called independent if
v1++vt= 0;vi2Vi;i= 1;:::t;)v1= 0;:::;vt= 0:
Then dim (V1++Vt) = dim (V1) ++ dimVt).)
Assume that
v1++vt= 0;
wherevi2Ker (T ciIv) for 1it. Then
T(v1++vt) =T(0)
c1v1++ctvt= 0:
Similarly we deduce that
c2
1v1++c2
tvt= 0
...
ct 1
1v1++ct 1
tvt= 0:
We can combine these tequations into a single matrix equation
2
66641 1
c1ct
...
ct 1
1ct 1
t3
77752
64v1
...
vt3
75=2
64o
...
03
75:
However the coecient matrix is the Vandermonde matrix, which is non{
singular as ci6=cjifi6=j, so we deduce that v1= 0;;vt= 0:Hence with
Vi= Ker (T ciIV), we have
dim (V1++Vt) =tX
i=1dimVi=tX
i=1ai= dimV:
Hence
V=V1++Vt:
Then if iis a basis for Viforiitand = 1[[ t, it follows that
is a basis for V. Moreover
[T]
=tM
i=1(ciIai)
48
andTis diagonable.
EXAMPLE. Let
A=2
45 2 2
2 5 2
2 2 53
5:
(a) We nd that ch A= (x 3)2(x 9). Next we nd bases for each of the
eigenspaces N(A 9I3) andN(A 3I3):
First we solve ( A 3I3)X= 0. We have
A 3I3=2
42 2 2
2 2 2
2 2 23
5!2
41 1 1
0 0 0
0 0 03
5:
Hence the eigenspace consists of vectors X= [x; y; z ]tsatisfyingx= y+z,
withyandzarbitrary. Hence
X=2
4 y+z
y
z3
5=y2
4 1
1
03
5+z2
41
0
13
5;
soX11= [ 1;1;0]tandX12= [1;0;1]tform a basis for the eigenspace
corresponding to the eigenvalue 3.
Next we solve ( A 9I3)X= 0. We have
A 9I3=2
4 4 2 2
2 4 2
2 2 43
5!2
41 0 1
0 1 1
0 0 03
5:
Hence the eigenspace consists of vectors X= [x; y; z ]tsatisfyingx= z
andy= z, withzarbitrary. Hence
X=2
4 z
z
z3
5=z2
4 1
1
13
5
and we can take X21= [ 1; 1;1]tas a basis for the eigenspace correspond-
ing to the eigenvalue 9.
ThenP= [X11jX12jX21] is non{singular and
P 1AP=2
43 0 0
0 3 0
0 0 93
5:
49
THEOREM 2.16
If
mT= (x c1):::(x ct)
forc1;:::;ctdistinct inF, thenTis diagonable and conversely. Moreover
there exist unique linear transformations T1;:::;Ttsatisfying
IV=T1++Tt;
T=c1T1++ctTt;
TiTj= 0Vifi6=j;
T2
i=Ti;1it:
Also rankTi=ai, wherechT= (x c1)a1(x ct)at.
Remarks.
1.T1;:::;Ttare called the principal idempotents ofT.
2. Ifg2F[x], theng(T) =g(c1)T1++g(ct)Tt. For example
Tm=cm
1T1++cm
tTt:
3. Ifc1;:::;ctare non{zero (that is the eigenvalues of Tare non{zero),
theT 1is given by
T 1=c 1
1T1++c 1
tTt:
Formulae 2 and 3 are useful in the corresponding matrix formulation. PROOF
SupposemT= (x c1)(x ct), wherec1;:::;ctare distinct. Then
chT= (x c1)a1(x ct)at. To prove Tis diagonable, we have to prove
that nullity ( T ciIV) =ai;1it
Letp1;:::;ptbe the Lagrange interpolation polynomials based on c1;:::;ct,
i.e.
pi=tY
j=1
j6=ix cj
ci cj
;1it:
Then
g2F[x])g=g(c1)p1++g(ct)pt:
In particular,
g= 1)1 =p1++pt
50
and
g=x)x=c1p1++ctpt:
Hence with Ti=pi(T),
IV=T1++Tt
T=c1T1++ctTt:
Next
mT= (x c1):::(x ct)jpipj ifi6=j
)(pipj)(T) = 0V ifi6=j
)pi(T)pj(T) = 0VorTiTj= 0V ifi6=j:
ThenT2
i=Ti(T1++Tt) =TiIV=Ti.
Next
0V=mT(T) = (T c1IV)(T ctIV):
Hence
dimV= nullity 0 VtX
i=1nullity (T ciIV)tX
i=1ai= dimV:
Consequently nullity ( T ciIV) =ai;1itandTis therefore diago-
nable.
Next we prove that rank Ti=ai. From the de nition of pi, we have
nullitypi(T)tX
j=1
j6=inullity (T cjIV) =tX
j=1
j6=iaj= dimV ai:
Alsopi(T)(T ciIV) = 0, so Im ( T ciIV)Kerpi(T). Hence
dimV ainullitypi(T)
and consequently nullity pi(T) = dim (V) ai, so rankpi(T) =ai.
We next prove the uniqueness of T1;:::;Tt. Suppose that S1;:::;Stalso
satisfy the same conditions as T1;:::;Tt. Then
TiT=TTi=ciTi
SjT=TSj=cjSj
Ti(TSj) =Ti(cjSj) =cjTiSj= (TiT)Sj=ciTiSj
51
so (cj ci)TiSj= 0VandTiSj= 0Vifi6=j. Hence
Ti=TiIV=Ti(tX
j=1Sj) =TiSi
Si=IVSi= (tX
j=1Tj)Si=TiSi:
HenceTi=Si.
Conversely, suppose that Tis diagonable and let be a basis of Vsuch
that
A= [T]
= diag (1;:::;n):
ThenmT=mA= (x c1)(x ct), wherec1;:::;ctare the distinct
members of the sequence 1;:::;n.
COROLLARY 2.5
If
chT= (x c1):::(x ct)
withcidistinct members of F, thenTis diagonable.
Proof : HeremT= chTand we use theorem 3.3.
EXAMPLE 2.11
Let
A=0a
b0
a;b2F; ab6= 0;1 + 16= 0:
ThenAis diagonable if and only if ab=y2for somey2F.
ForchA=x2 ab, so ifab=y2,
chA=x2 y2= (x+y)(x y)
which is a product of distinct linear factors, as y6= yhere.
Conversely suppose that Ais diagonable. Then as Ais not a scalar
matrix, it follows that mAis not linear and hence
mA= (x c1)(x c2);
wherec16=c2. Also chA=mA, sochA(c1) = 0 . Hence
c2
1 ab= 0;orab=c2
1:
For example, take F=Z7and leta= 1 andb= 3. Thenab6=y2and
consequently Ais not diagonable.
52