06 smith
PDF · 11 pages · 143.1 KB
Open PDF file
Chapter of lecture notes or a textbook (folder suggests Matthews' linear algebra), not shown to be Phil's own work. It covers units in matrices over F[x], equivalence, determinantal divisors, the Smith canonical form algorithm and its uniqueness, and invariant factors. It connects xI-B to similarity and Jordan form, with worked examples including a 4x4 rational matrix.
AI-written summary; may contain errors.
Extracted text (machine-read; may contain errors)
6 The Smith Canonical Form
6.1 Equivalence of Polynomial Matrices
DEFINITION 6.1
A matrixP2Mnn(F[x])is called a unit inMnn(F[x])if9Q2
Mnn(F[x])such that
PQ=In:
Clearly ifPandQare units, so is PQ.
THEOREM 6.1
A matrixP2Mnn(F[x])is a unit in Mnn(F[x])if and only if detP=
c, wherec2Fandc6= 0.
proof
\only if". Suppose Pis a unit. Then PQ=Inand
detPQ= detPdetQ= detIn= 1:
However det Pand detQbelong toF[x], so both are in fact non{zero ele-
ments ofF.
\if". Suppose P2Mnn(F[x]) satis es det P=c, wherec2Fand
c6= 0. Then
PadjP= (detP)In=cIn:
HencePQ=In, whereQ=c 1adjP2Mnn(F[x]). HencePis a unit in
Mnn(F[x]).
EXAMPLE 6.1
P=1 +x x
x 1 x
2M22(F[x])is a unit, as detP= 1.
THEOREM 6.2
Elementary row matrices in Mnn(F[x])are units:
(i)Eij: interchange rows iandjofIn;
(ii)Ei(t): multiply row iofInbyt2F; t6= 0;
(iii)Eij(f): addftimes rowjofInto rowi; f2F[x].
In fact detEij= 1; detEi(t) =t; detEij(f) = 1 .
Similarly for elementary column matrices in Mnn(F[x]):
Fij; Fi(t); Fij(f):
120
Remark : It follows that a product of elementary matrices in Mnn(F[x])
is a unit. Later we will be able to prove that the converse is also true.
DEFINITION 6.2
LetA; B2Mmn(F[x]). ThenAis equivalent to BoverF[x]if units
P2Mmm(F[x])andQ2Mnn(F[x])exist such that
PAQ =B:
THEOREM 6.3
Equivalence of matrices over F[x]de nes an equivalence relation on
Mmn(F[x]).
6.1.1 Determinantal Divisors
DEFINITIONS 6.1
LetA2Mmn(F[x]). Then for 1kmin (m; n ), letdk(A)denote the
gcdof allkkminors ofA.
dk(A)is sometimes called the kthdeterminantal divisor of A.
Note :gcd (f1;:::;fn)6= 0,at least one of f1;:::;fnis non{zero.
(A), thedeterminantal rank ofA, is de ned to be the largest integer r
for which there exists a non{zero rrminor ofA.
THEOREM 6.4
For1k(A), we havedk(A)6= 0. Alsodk(A)dividesdk+1(A)for
1k(A) 1.
proof
Letr=(A). Then there exists an rrnon{zero minor and hence
dr(A)6= 0. Then because each rrminor is a linear combination over F[x]
of (r 1)(r 1) minors of A, it follows that some ( r 1)(r 1) minor of
Ais also non{zero and hence dr 1(A)6= 0; alsodr 1(A) divides each minor
of sizer 1 and consequently divides each minor of size r; hencedr 1(A)
dividesdr(A), the gcd of all minors of size r. This argument can be repeated
withrreplaced by r 1 and so on.
THEOREM 6.5
LetA; B2Mmn(F[x]). Then ifAis equivalent to BoverF[x], we
have
(i)(A) =(B) =r;
121
(ii)dk(A) =dk(B)for1kr.
proof
SupposePAQ =B, wherePandQare units. First consider PA. The
rows ofPAare linear combinations over F[x] of the rows of A, so it follows
that eachkkminor ofPAis a linear combination of the kkminors of
A. Similarly each column of ( PA)Qis a linear combinations over F[x] of
the columns of PA, so it follows that each kkminor ofB= (PA)Qis a
linear combination over F[x] of thekkminors ofPAand consequently of
thekkminors ofA.
It follows that all minors of Bwith sizek> (A) must be zero and hence
(B)(A). However Bis equivalent to A, so we deduce that (A)(B)
and hence(A) =(B).
Alsodk(B) is a linear combination over F[x] of allkkminors ofB
and hence of all kkminors ofA. Hencedk(A)jdk(B) and by symmetry,
dk(B)jdk(A). Hencedk(A) =dk(B) if 1kr.
6.2 Smith Canonical Form
THEOREM 6.6 (Smith canonical form)
Every non{zero matrix A2Mmn(F[x])withr=(A)is equivalent to
a matrix of the form
D=2
666666664f10 00
0f2 00
..................
0 0fr0
..................
0 0 003
777777775=PAQ
wheref1;:::;fr2F[x]are monic,fkjfk+1for1kr 1,Pis a product of
elementary row matrices, and Qis a product of elementary column matrices.
DEFINITION 6.3
The matrix Dis said to be in Smith canonical form .
proof
This is presented in the form of an algorithm which is in fact used by
Cmat to nd unit matrices PandQsuch thatPAQ is in Smith canonical
form.
122
Our account is based on that in the book \Rings, Modules and Linear
Algebra," by B. Hartley and T.O. Hawkes.
We describe a sequence of elementary row and column operations over
F[x], which when applied to a matrix Awitha116= 0 either yields a matrix
Cof the form
C=2
6664f100
0
...
0C3
7775
wheref1is monic and divides every element of C, or else yields a matrix
Bin whichb116= 0 and
degb11<dega11: (28)
Assuming this, we start with our non{zero matrix A. By performing suitable
row and column interchanges, we can assume that a116= 0. Now repeatedly
perform the algorithm mentioned above. Eventually we must reach a ma-
trix of type C, otherwise we would produce an in nite strictly decreasing
sequence of non{negative integers by virtue of inequalities of type (28).
On reaching a matrix of type C, we stop ifC= 0. Otherwise we perform
the above argument on Cand so on, leaving a trail of diagonal elements as
we go.
Two points must be made:
(i) Any elementary row or column operation on Ccorresponds to an
elementary operation on C, which does not a ect the rst row or
column ofC.
(ii) Any elementary operation on Cgives a new Cwhose new entries
are linear combinations over F[x] of the old ones; consequently these
new entries will still be divisible by f1.
Hence in due course we will reach a matrix Dwhich is in Smith canonical
form.
We now detail the sequence of elementary operations mentioned above.
Case 1.9a1jin row 1 with a11not dividing a1j. Then
a1j=a11q+b;
by Euclid's division theorem, where b6= 0 and deg b <dega11. Subtract q
times column 1 from column jand then interchange columns 1 and j. This
yields a matrix of type Bmentioned above.
123
Case 2.9ai1in column 1 with a11not dividing ai1. Proceed as in Case 1,
operating on rows rather than columns, again reaching a matrix of type B.
Case 3. Here a11divides every element in the rst row and rst column.
Then by subtracting suitable multiples of column 1 from the other columns,
we can replace all the entries in the rst row other than a11by 0. Similarly
for the rst column. We then have a matrix of the form
E=2
6664e1100
0
...
0E3
7775:
Ife11divides every element of E, we have reached a matrix of type C.
Otherwise9eijnot divisible by e11. We then add row ito row 1, thereby
reaching Case 1.
EXAMPLE 6.2
(of the Smith Canonical Form)
A=1 +x2x
x 1 +x
We wantD=PAQ in Smith canonical form. So we construct the augmented
matrix
work on rows work on columns
# #
1 0 1 +x2x 1 0
0 1 x 1 +x 0 1
R1!R1 xR2) 1 x 1 x21 0
0 1 x 1 +x 0 1
C2!C2+x2C1) 1 x 1 0 1x2
0 1 x 1 +x+x30 1
R2!R2 xR1) 1 x 1 0 1x2
x1 +x20 1 +x+x30 1
" " "
P D Q
Invariants are f1= 1,f2= 1 +x+x3. Note also
f1=d1(A); f 2=d2(A)
d1(A):
124
6.2.1 Uniqueness of the Smith Canonical Form
THEOREM 6.7
Every matrix A2Mmn(F[x])is equivalent to precisely one matrix is
Smith canonical form.
proof Suppose Ais equivalent to a matrix Bin Smith canonical form.
That is,
B=2
6664f1
...
fr0
0 03
7775andf1jf2jjfr:
Thenr=(A), the determinantal rank of A. But if 1kr,
dk(A) =dk(B) =f1f2:::fk
and so the fiare uniquely determined by
f1=d1(A)
f2=d2(A)
d1(A)
...
fr=dr(A)
dr 1(A):
6.3 Invariant factors of a polynomial matrix
DEFINITION 6.4
The polynomials f1;:::;frin the Smith canonical form of Aare called
theinvariant factors ofA.3
Note :Cmat calls the invariant factors of xI B, whereB2Mnn(F), the
\similarity invariants" of B.
We next nd these similarity invariants. They are
1;1;:::; 1|{z}
n s;d1;:::;ds
whered1;:::;dsare what earlier called the invariant factors of TB.
3NB. This is a slightly di erent, though similar, form of \invariant factor" to that we
met a short while ago.
125
LEMMA 6.1
The Smith canonical form of xIn C(d)wheredis a monic polynomial
of degreenis
diag (1;:::; 1|{z}
n 1;d):
proof Letd=xn+an 1xn 1++a02F[x], so
xIn C(d) =2
66666664x 0 a0
1x a1
0 1 a2
.........
x an 2
0 1x+an 13
77777775:
Now use the row operation
R1!R1+xR2+x2R3++xn 1Rn
to obtain 2
666666640 0 d
1x a1
0 1 a2
.........
x an 2
0 1x+an 13
77777775
(think about it!) and then column operations
C2!C2+xC1;:::;Cn 1!Cn 1+xCn 2
and then
Cn!Cn+a1C1+a2C2++an 2Cn 2+ (x+an 1)Cn 1
yielding2
6666640 0::: 0d
1 0 0
0 1
......
0 1 03
777775:
126
Trivially, elementary operations now form the matrix
diag (1;:::; 1|{z}
n 1;d):
THEOREM 6.8
LetB2Mnn(F). Then if the invariant factors of Bared1;:::;ds, then
the invariant factors of xIn Bare
1;:::; 1|{z}
n s;d1;d2;:::;ds:
proof There exists non-singular P2Mnn(F) such that
P 1BP=sM
k=1C(dk):
Then
P 1(xIn B)P=xIn sM
k=1C(dk)
=sM
k=1(xImk C(dk)) where mk= degdk:
But by the lemma, each xImk C(dk) is equivalent over F[x] to
diag (1;:::; 1;dk) and hence xIn Bis equivalent to
sM
k=1diag (1;:::; 1;dk)2
6666666641
...
1
d1
...
ds3
777777775:
EXAMPLE 6.3
Find the invariant factors of
B=2
6642 0 0 0
1 1 0 0
0 1 0 1
1 1 1 23
7752M44(Q)
127
by nding the Smith canonical form of xI4 B.
Solution:
xI4 B=2
664x 2 0 0 0
1x 1 0 0
0 1 x 1
1 1 1x 23
775
We start o with the row operations
R1!R1 (x 2)R2
R1$R2
R4!R4+R1
and get
2
6641x 1 0 0
0 (x 1)(x 2) 0 0
0 1 x 1
0x 2 1x 23
775
(column ops :))2
6641 0 0 0
0 (x 1)(x 2) 0 0
0 1x 1
0 x 2 1x 23
775
)2
6641 0 0 0
0 1 x 1
0 (x 1)(x 2) 0 0
0x 2 1x 23
775
)2
666641 0 0 0
0 1 x 1
0 0x(x 1)(x 2) (x 1)(x 2)
0 0 1 x(x 2)
f= (x 1)2g03
77775
)2
6641 0 0 0
0 1 0 0
0 0x(x 1)(x 2) (x 1)(x 2)
0 0 (x 1)203
775:
Now, for brevity, we work just on the 22block in the bottom right corner:
)(x 1)(x 2)x(x 1)(x 2)
0 (x 1)2
128
C2!C2 xC1)(x 1)(x 2) 0
0 (x 1)2
R1!R1+R2)(x 1)(x 2) (x 1)2
0 (x 1)2
C2!C2 C1)(x 1)(x 2)x 1
0 (x 1)2
C1$C2)x 1 (x 1)(x 2)
(x 1)20
C2!C2 (x 2)C1)x 1 0
(x 1)2(x 2)(x 1)2
R2!R2+ (x 1)R1)x 1 0
0 (x 2)(x 1)2
and here we stop, as we have a matrix in Smith canonical form. Thus
xI4 B2
6641
1
x 1
(x 1)2(x 2)3
775
so the invariant factors of Bare the non-trivial ones of xI4 B, i.e.
(x 1) and ( x 1)2(x 2):
Also, the elementary divisors of Bare
(x 1);(x 1)2and(x 2)
so the Jordan canonical form of Bis
J2(1)J1(1)J1(2):
THEOREM 6.9
LetA;B2Mnn(F). ThenAis similar to B
,xIn Ais equivalent to xIn B
,xIn AandxIn Bhave the same
Smith canonical form.
proof
129
)Obvious. If P 1AP=B,P2Mnn(F) then
P 1(xIn A)P=xIn P 1AP
=xIn B:
(IfxIn AandxIn Bare equivalent over F[x], then they have the
same invariant factors and so have the same non-trivial invariant fac-
tors. That is, AandBhave the same invariant factors and hence are
similar.
Note : It is possible to start from xIn Aand ndP2Mnn(F) such that
P 1AP=sM
k=1C(dk)
where
P1(xIn B)Q1= diag (1;:::; 1;d1;:::;ds):
(See Perlis, Theory of matrices, p. 144, Corollary 8{1 and p. 137, Theorem
7{9.)
THEOREM 6.10
Every unit in Mnn(F[x])is a product of elementary row and column
matrices.
Proof: Problem sheet 7, Question 12.
130