Page 242 - DMTH502_LINEAR_ALGEBRA

Linear Algebra

Notes explicit algorithm for reducing a polynomial matrix to diagonal form. Theorem 3 suggests that
we may also arrange that successive elements on the main diagonal divide one another.
Definition: Let N be a matrix in F[xJ m n . We say that N is in (Smith) normal form if

(a) every entry off the main diagonal of N is 0;
(b) on the main diagonal of N there appear (in order) polynomials f , ... , f such that f divides
1 l k
f , 1 k l – 1.
k + j
In the definition, the number l is l = min (m, n). The main diagonal entries are f = N , k = 1, ..., l.
k kk
Theorem 4: Let M be an m n matrix with entries in the polynomial algebra F[x]. Then M is
equivalent to a matrix N which is in normal form.

Proof: If M = 0, there is nothing to prove. If M 0, we shall give an algorithm for finding a matrix
M' which is equivalent to M and which has the form

f 1 0  0
0
M’ = ...(8)
 R
0
where R is an (m – 1) (n – 1) matrix and f divides every entry of R. We shall then be finished,
1
because we can apply the same procedure to R and obtain f , etc.
2
Let l(M) be the minimum of the degrees of the non-zero entries of M. Find the first column which
contains an entry with degree l(M) and interchange that column with column 1. Call the resulting
(0)
matrix M . We describe a procedure for finding a matrix of the form
g 0  0
0
...(9)
 S
0
(0)
which is equivalent to M . We begin by applying to the matrix M the procedure of the lemma
(0)
before Theorem 1, a procedure which we shall call PL6. There results a matrix
p a  b
0 c  d
M (1) = ...(10)
  
0 e  f
If the entries a, ... , b are all 0, fine. If not, we use the analogue of PL6 for the first row, a procedure
which we might call PL6'. The result is a matrix
q 0  0
' a ' c  ' e
M (2) = ...(11)
  
' b ' d  ' f

(2)
where q is the greatest common divisor of p, a, ... , b. In producing M , we may or may not have
disturbed the nice form of column 1. If we did, we can apply PL6 once again. Here is the point.
In not more than l(M) steps:
(0) PL6 (1) PL6 (2) PL6 ( )
t
M M M ... M

236 LOVELY PROFESSIONAL UNIVERSITY