Page 239 - DMTH502_LINEAR_ALGEBRA

Unit 22: Computation of Invariant Factors

Proof: We shall prove something more than we have stated. We shall show that there is an Notes
algorithm for finding N, i.e., a prescription which a machine could use to calculate N in a finite
number of steps. First, we need some notation.
Let M be any m n matrix with entries in F[x] which has a non-zero first column
f 1
M = 
1
f m
Define

I(M ) = min deg f
1 0 i
f i
p(M ) = g.c.d. (f , ... f ) ...(2)
1 1 m
Let j be some index such that deg f , = l(M ). To be specific, let j be the smallest index i for which
j 1
deg f , = I(M ). Attempt to divide each f, by f :
i 1 j
f = f g , + r , r = 0 or deg r < deg f ...(3)
i j i i i i j
For each i different from j, replace row i of M by row i minus g times row j. Multiply row j by the
i
reciprocal of the leading coefficient of f and then interchange rows j and 1. The result of all these
j
operations is a matrix M' which has for its first column
ˆ f j
r
2

r j 1
M’ = ...(4)
1
r 1
r j 1

r m
ˆ
where f is the monic polynomial obtained by normalizing f to have leading coefficient 1. We
j
j
have given a well-defined procedure for associating with each M a matrix M' with these properties.
(a) M' is row-equivalent to M.
(b) p(M’) = p(M ).
1 1
(c) Either l(M’) < l(M ) or
1 1
( p M 1 )
0
M’ = ...(4A)
1 
0

It is easy to verify (b) and (c) from (3) and (4). Property (c) is just another way of stating that either
ˆ
there is some i such that r, 0 and deg r , < deg f , or else r , = 0 for all i and f is (therefore) the
j
i j i
greatest common divisor of f , ..., f .
1 m
The proof of the lemma is now quite simple. We start with the matrix M and apply the above
procedure to obtain M'. Property (c) tells us that either M' will serve as the matrix N in the
lemma or l(M’ ) < l(M ). In the latter case, we apply the procedure to M' to obtain the matrix
1 1

LOVELY PROFESSIONAL UNIVERSITY 233