328 B. PRELIMINARIES ON MATRIX RINGS

Proof. Deﬁne

F =

A −I

B 0

. (B.27)

Then G is the Schur complement of F with respect to A. By Fact B.1.9,

|A|·g

JK

= f

N

∪ ({n}+J),N ∪({n}+K),

=

A −I

.K

B

J.

0

. (B.28)

Note that each of the last l columns of the minor consists of all zeros except for a single 1. If we

expand this minor about the last l columns using Laplace’s expansion (Fact B.1.4),then the expansion

consists of a single term, since the submatrix consisting of the last l columns has only nonzero l × l

minor. Thus, if K ={k

1

, ···,k

l

}, then

|A|·g

JK

= (−1)

v

(−1)

l

A

N\K

B

J.

, (B.29)

where

v =

l

i=1

(n + i) +

l

i=1

k

i

. (B.30)

Now the minor on the right side of (B.29) is not quite in the form stated in Fact B.1.10, since

the rows of B occur below those of A, rather than substituting for them (as in Example B.26, for

instance). It is a matter of detail to verify that the parity factor (−1)

v+l

accounts for this difference.

2

Fact B.1.12 Suppose A ∈ F

n×n

,B ∈ F

n×m

, |A| = 0 and let G = A

−1

B. Suppose J ∈

S(l, n), K ∈ S(l,m). Then |A|·g

JK

equals the determinant of the n × n matrix obtained from

A by replacing the columns in J of A by the columns in K of B.

The proof is similar to that of Fact B.1.10 and is left to the reader.

B.2 CANONICAL FORMS

Let R be a principal ideal domain, and let F be the ﬁeld of fractions associated with R. In this section,

we study the sets R

n×m

and F

n×m

, consisting of n × m matrices whose elements belong to R and

F, respectively. We prove the existence of two canonical forms, namely the Smith form on R

n×m

and

the Smith-McMillan form on F

n×m

.

A matrix A ∈ R

n×m

is a le ft associate of B ∈ R

n×m

(denoted by A =

L

B) if there is a unimod-

ular matrix U ∈ R

n×n

such that A = UB. A is a right associate of B (denoted by A =

R

B) if there

is a unimodular matrix V ∈ R

m×m

such that A = BV . A is equivalent to B (denoted by A ∼ B)if

B.2. CANONICAL FORMS 329

there are unimodular matrices U ∈ R

n×n

,V ∈ R

m×m

. such that A = UBV. It is left to the reader

to verify that =

L

, =

R

, ∼ are all equivalence relations.

We now commence our study of canonical forms.

Lemma B.2.1 Suppose a

1

, ···,a

n

∈ R, and let d

n

be a GCD of this set of elements. Then there exists

a matrix P

n

∈ R

n×n

whose ﬁrst row is [a

1

···a

n

] and whose determinant is d

n

.

Proof. The proof is by induction on n.Ifn = 2, by Theorem A.3.3 there exist p

1

,p

2

∈ R such that

p

1

a

1

+ p

2

a

2

= d

2

. Now let

P

2

=

a

1

a

2

−p

2

p

1

(B.1)

For larger values of n, let d

n−1

be a GCD of a

1

, ···,a

n−1

. By the inductive hypothesis, we can

construct a matrix P

n−1

∈ R

n−1×n−1

whose ﬁrst row is [a

1

···a

n−1

] and whose determinant is

d

n−1

. By Fact B.1.3,

n−1

j=1

a

j

(−1)

1+j

m

1j

(P

n−1

) = d

n−1

. (B.2)

so that

n−1

j=1

a

j

d

n−1

(−1)

1+j

m

1j

(P

n−1

) = 1 . (B.3)

For convenience, let z

j

=−a

j

/d

n−1

. Next, by Problem A.3.3, d

n

is a GCD of d

n−1

and a

n

.By

Theorem A.3.3, there exist x,y ∈ R such that xd

n−1

+ ya

n

= d

n

. Now deﬁne

P

n

=

⎡

⎢

⎢

⎢

⎢

⎢

⎣

a

n

P

n−1

0

.

.

.

0

yz

1

··· yz

n−1

x

⎤

⎥

⎥

⎥

⎥

⎥

⎦

. (B.4)

Expanding |P

n

| about the last column and using (B.3) gives |P

n

|=xd

n−1

+ ya

n

= d

n

. 2

Theorem B.2.2 (Hermite Form) Every A ∈ R

n×n

is a left associate of a matrix B that is lower-

triangular (i.e., b

ij

= 0 for j>i).

330 B. PRELIMINARIES ON MATRIX RINGS

Proof. Let d

n

be a GCD of {a

1n

, ···,a

nn

}, i.e., the elements of the last column of A. By Theo-

rem A.3.5, there exist elements p

1

, ···,p

n

∈ R such that

n

i=1

p

i

a

in

= d

n

. (B.5)

By Problem A.3.4, 1 is a GCD of the set p

1

, ···,p

n

. Hence, by a slight variation of Lemma B.2.1,

there exists a unimodular matrix U ∈ R

n×n

such that its last row is [p

1

···p

n

].Now(U A)

nn

= d

n

.

Also, for i = 1, ···,n− 1,(UA)

in

belongs to the ideal generated by a

1n

, ···,a

nn

and is thus a

multiple of d

n

.Letz

i

= (U A)

in

/d

n

for i = 1, ···,n− 1, and deﬁne

U

n

=

⎡

⎢

⎢

⎢

⎢

⎢

⎣

10··· 0 −z

1

01··· 0 −z

2

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

00··· 1 −z

n−1

00··· 01

⎤

⎥

⎥

⎥

⎥

⎥

⎦

. (B.6)

Then U

n

is unimodular since its determinant is 1. Moreover, U

n

UA is of the form

U

n

UA =

⎡

⎢

⎢

⎢

⎣

0

A

n−1

.

.

.

0

a

n−1

d

n

⎤

⎥

⎥

⎥

⎦

. (B.7)

In other words, the last column of A has been reduced to zero above the diagonal by means of left

multiplication by an appropriate unimodular matrix. One can now repeat the procedure with the

n − 1 ×n − 1 matrix A

n−1

, and eventually arrive at a lower triangular matrix. For clarity, the next

step of the algorithm is brieﬂy outlined: Let d

n−1

denote a GCD of the elements of the last column

of A

n−1

. As above, there exists a unimodular matrix

¯

U

n−1

∈ R

n−1×n−1

such that

¯

U

n−1

A

n−1

=

⎡

⎢

⎢

⎢

⎣

0

A

n−2

.

.

.

0

a

n−2

d

n−1

⎤

⎥

⎥

⎥

⎦

. (B.8)

Now deﬁne the n × n unimodular matrix

U

n−1

= Block Diag{

¯

U

n−1

, 1} . (B.9)

Get *Control System Synthesis* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.