Introduction To Algebraic Theories

00 fc CD 160510 >m OSMANIA UNIVERSITY LIBRARY Call No. 5/3 # % 3 Accession No^, 33 . Author This book should he r...

Author: Adrian Albert A.

37 downloads 1241 Views 6MB Size Report

This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!

Report copyright / DMCA form

DOWNLOAD PDF

00

fc CD

160510

>m

OSMANIA UNIVERSITY LIBRARY Call No. 5/3 # % 3 Accession No^, 33 .

Author

This book should he returned on or before the date

last

marked below,

THE UNIVERSITY OF CHICAGO PRESS

.

CHICAGO

THE BAKER & TAYLOR COMPANY, NEW YORKJ THE CAMBRIDGE UNIVERSITY PRESS, LONDON; THE MARUZEN-KABUSHIKI-KAISHA, TOKYO, OSAKA, KYOTO, FUKUOKA, SENDAIJ THE COMMERCIAL PRESS, LIMITED, SHANGHAI

INTRODUCTION TO ALGEBRAIC THEORIES By A.

ADRIAN ALBERT THE UNIVERSITY OF CHICAGO

THE UNIVERSITY OF CHICAGO PRESS CHICAGO ILLINOIS

1941 BY THE UNIVERSITY OF CHICAGO. ALL RIGHTS RESERVED. PUBLISHED JANUARY 1941. SECOND IMPRESSION APRIL 1942. COMPOSED AND PRINTED BY THE UNIVERSITY OF CHICAGO PRESS, CHICAGO, ILLINOIS, U.S.A.

COPYRIGHT

PREFACE During recent years there has been an ever increasing interest in modern algebra not only of students in mathematics but also of those in physics, chemistry, psychology, economics, and statistics. My Modern Higher Algebra was intended, of course, to serve primarily the first of these groups, and its rather widespread use has assured me of the propriety of both its contents and its abstract mode of presentation. This assurance has been conits successful use as a text, the sole prerequisite being the subject matter of L. E. Dickson's First Course in the Theory of Equations. However, I am fully aware of the serious gap in mode of thought between the intuitive treatment of algebraic theory of the First Course and the rigorous abstract treatment of the Modern Higher Algebra, as well as the pedagogical difficulty which is a consequence.

firmed by

The

publication recently of more abstract presentations of the theory of equations gives evidence of attempts to diminish this gap. Another such at-

tempt has resulted in a supposedly less abstract treatise on modern algebra which is about to appear as these pages are being written. However, I have the feeling that neither of these compromises is desirable and that it would be far better to make the transition from the intuitive to the abstract by the addition of a

mathematics

new

course in algebra to the undergraduate curriculum in a curriculum which contains at most two courses in algebra

and these only partly algebraic in content. This book is a text for such a course. In

fact, its only prerequisite maa knowledge of that part of the theory of equations given as a chapter of the ordinary text in college algebra as well as a reasonably complete knowledge of the theory of determinants. Thus, it would actually be pos-

terial is

a student with adequate mathematical maturity, whose only training in algebra is a course in college algebra, to grasp the contents. I have used the text in manuscript form in a class composed of third- and fourth-year sible for

undergraduate and beginning graduate students, and they all seemed to find the material easy to understand. I trust that it will find such use elsewhere and that it will serve also to satisfy the great interest in the theory of matrices which has been shown me repeatedly by students of the social sciences. I wish to express my deep appreciation of the fine critical assistance of Dr. Sam Perils during the course of publication of this book. A. A.

UNIVERSITY OF CHICAGO September

9,

1940

v

ALBERT

TABLE OF CONTENTS CHAPTER I.

III.

1

1.

Polynomials in x

1

2.

The

4

3.

Polynomial

4. 5.

Polynomials in several variables Rational functions

6.

A greatest common divisor

7.

Forms

13

8.

Linear forms Equivalence of forms

15

9.

II.

PAQB

POLYNOMIALS division algorithm

5

divisibility

8 9

process

17

RECTANGULAR MATRICES AND ELEMENTARY TRANSFORMATIONS 1. The matrix of a system of linear equations

.

.

19 19

2.

Submatrices

3.

4.

Transposition Elementary transformations

5.

Determinants

6.

Special matrices

26 29

7.

Rational equivalence of rectangular matrices

32

21

22 24

*

EQUIVALENCE OF MATRICES AND OF FORMS 1.

Multiplication of matrices

2.

The

3. 4.

Products by diagonal and scalar matrices Elementary transformation matrices

5.

The determinant

6.

Nonsingular matrices

7.

Equivalence of rectangular matrices forms

associative law

of a product

8. Bilinear

-

.

36 36 38 39 42 44 45 47 48

Congruence of square matrices

51

10.

Skew matrices and skew

11.

Symmetric matrices and quadratic forms Nonmodular fields

52 53 56

13.

Summary

58

14.

Addition of matrices

15.

Real quadratic forms

9.

12.

IV.

6

of results

LINEAR SPACES 1.

2.

bilinear forms

.

.

.

Linear spaces over a Linear subspaces

59 62 .

66

:

66

field

66 vii

TABLE OF CONTENTS

viii

CHAPTBR

PAQBJ

3.

Linear independence

4.

The row and column spaces The concept of equivalence

5. 6.

7. 8. 9.

10.

11.

67 69 73 75 77 79 82 86 87

of a matrix

Linear spaces of finite order Addition of linear subspaces

Systems of linear equations Linear mappings and linear transformations Orthogonal linear transformations Orthogonal spaces

V, POLYNOMIALS

WITH MATRIC COEFFICIENTS

1.

Matrices with polynomial elements

2.

3.

Elementary divisors Matric polynomials

4.

The

characteristic matrix

and function

Similarity of square matrices 6. Characteristic matrices with prescribed invariant factors 5.

7.

VI.

Additional topics

FUNDAMENTAL CONCEPTS 1.

Groups

2.

Additive groups Rings Abstract fields

3. 4. 5. 6. 7.

8. 9.

Integral domains Ideals and residue class rings

The The

ring of ordinary integer^ ideals of the ring of integers

Quadratic extensions of a field quadratic fields

10. Integers of 11.

12.

INDEX

Gauss numbers An integral domain with nonprincipal

ideals

.

.

.

89 89 94 97 100 103 105 107 109 109 Ill 112 113 114 116 117 119 121 124 127 130

133

CHAPTER

I

POLYNOMIALS 1. Polynomials in x. There are certain simple algebraic concepts with which the reader is probably well acquainted but not perhaps in the terminology and form desirable for the study of algebraic theories. We shall thus begin our exposition with a discussion of these concepts. We shall speak of the familiar operations of addition, subtraction, and multiplication as the integral operations. A positive integral power is then

best regarded as the result of a finite repetition of the operation of multiplication.

A polynomial f(x) plication of a finite

in x is

any expression obtained number of integral operations

as the result of the apto x and constants. If

is a second such expression and it is possible to carry out the operations indicated in the given formal expressions for/(z) and g(x) so as to obtain two identical expressions, then we shall regard f(x) and g(x) as being the

g(x)

same polynomial. This concept is frequently indicated by saying that f(x) and g(x) are identically equal and by writing f(x) = g(x). However, we shall usually say merely that /(a;) and g(x) are equal polynomials and write the polynomial which is the constant f(x) = g(x). We shall designate by zero and shall call this polynomial the ze^o polynomial. Thus, in a discus-

= will mean that f(x) is the zero polynomial. confusion will arise from this usage for it will always be clear from the where context that, in the consideration of a conditional equation f(x) =

sion of polynomials f(x)

No

we seek a constant solution c such that /(c) = 0, the polynomial f(x) is not the zero polynomial. We observe that the zero polynomial has the properties g(x)

=

+ g(x)

,

=

g(x)

for every polynomial g(x). Our definition of a polynomial includes the use of the familiar

term conterm we shall mean any complex number or function independent of x. Later on in our algebraic study we shall be much more explicit about the meaning of this term. For the present, however, we shall merely make the unprecise assumption that our constants have the usual properties postulated in elementary algebra. In particular, we shall assume then either the properties that if a and 6 are constants such that ab = stant.

By

this

1

INTRODUCTION TO ALGEBRAIC THEORIES

2

a or 6 is zero; and 1 1 a"" such that aar

a

if

we

the label

If f(x) is

is

a nonzero constant then a has a constant inverse

1.

assign to a particular formal expression of a polyit occurs in f(x) by a constant c, we ob-

nomial and we replace x wherever tain a corresponding expression in

c which is the constant we designate by is that /(c). any different formal expression of a polyg(x) = nomial in x and that f(x) g(x) in the sense defined above. Then it is

Suppose now

evident that /(c) = g(c). Thus, in particular, if /&(x), q(x), T(X) are poly= h(c)q(c) nomials in x such that }(x) = h(x)q(x) r(x) then f(c) r(c)

+

for

any

+

2z 2 + 3z, h(x) = re For example, we have f(x) = a; 3 = 2z, and are stating that for any c we have x, r(x)

c.

= x2 g(x) 2 2c + 3c= (c-

l)(c

2

-

c)

+

1,

c8

2c.

the indicated integral operations in any given expression of a polynomial f(x) be carried out, we may express f(x) as a sum of a finite numIf

ber of terms of the form ax k Here k

a non-negative integer and a is a The terms with the same exponent fc

.

constant called the

coefficient of

x

k .

is

may be combined into a single term whose coefficients, and we may then write f(x)

(1)

The constants a unless f(x)

is

=

a xn

+ aixn ~ + l

.

.

.

+

a n -\x

are called the coefficients of /(x)

the zero polynomial,

sum

coefficient is the

+ an

.

and may be

we may always take

ao

^

is most important since, if g(x) pression (1) of f(x) with do 5^ polynomial and we write g(x) in the corresponding form

g(x)

(2)

=

6

zm

of all their

0. is

zero,

The

but ex-

a second

+ fciz"- +...+& 1

= n, a = 6* for then/(x) and g(x) are equal if and only if m n. In other words, we may say that the expression (1) of a i = 0, is polynomial unique, that is, two polynomials are equal if and only if their with 60

.

5^ 0, .

.

,

expressions (1) are identical.

The integer n of any expression (1) of f(x) is called the virtual degree of the expression (1). If a 7* we call n the degree* of f(x). Thus, either any = a n is a constant and will be f(x) has a positive integral degree, or /(#)

^

called a constant polynomial in x. If, then, a n we say that the constant polynomial f(x) has degree zero. But if a n = 0, so that f(x) is the zero polynomial, we shall assign to it the degree minus infinity. This will *

Clearly

any polynomial of degree no may be written as an expression of the form (1) any integer n ^ no. We may thus speak of any such n as a virtual de-

of virtual degree gree of /(a;).

POLYNOMIALS

3

be done so as to imply that certain simple theorems on polynomials shall hold without exception. The coefficient ao in (1) will be called the virtual leading coefficient of this expression of f(x) and will be called the leading coefficient oif(x) if and only if it is not zero. We shall call/(x) a monic polynomial if ao = 1. We then have the elementary results referred to above, whose almost trivial verifica-

we

tion

leave to the reader.

LEMMA

The degree of a product of two polynomials f (x) and g(x) is the and g(x). The leading coefficient of f(x) g(x) is the leading coefficients of f (x) and g(x), and thus, if f (x) and product of

sum the

1.

of the degrees of f(x)

g(x) are monic, so is f(x)

LEMMA stant if

2.

=

3.

if both factors are constants.

of

=

Let f(x) be nonzero and such that f(x)g(x)

f(x)h(x).

Then

h(x).

LEMMA 4. The f (x)

g(x).

product of two nonzero polynomials is nonzero and is a con-

and only

LEMMA g(x)

A

and

+ g(x)

degree of f (x)

is at

most the larger of the two degrees

g(x).

EXERCISES* State the condition that the degree of /(x)

1.

+ g(x)

be

+ g(x)

if

than the degree of

less

either /(x) or g(x).

What

2.

can one say about the degree of f(x)

and

/(x)

g(x)

have posi-

tive leading coefficients? 2 3 3. What can one say about the degree of/ of/ of/* for/ k a positive integer? ,

=

f(x) a polynomial,

State a result about the degree and leading coefficient of any polynomial

4.

= /i

s(x)

+.+/?

Make

5.

and

,

for

t

>

1,

/

= /(x)

a polynomial in x with real coefficients.

a corresponding statement about g(x)s(x) where g(x) has odd degree Ex. 4.

real coefficients, s(x) as in

6.

State the relation between the term of least degree in f(x)g(x) and those of

least degree in /(x) 7.

State

why

and

it is

g(x).

true that

if

x

is

not a factor of f(x) or g(x) then x

is

not a fac-

tor of f(x)g(x). 8. Use Ex. 7 to prove that if k and only if x is a factor of /(x). 9.

is

a positive integer then x

is

a factor of

[/(x)]*

if

Let / and g be polynomials in x such that the following equations are satisfied Show, then, that both /and g are zero. Hint: Verify first that other-

(identically).

* The early exercises in our sets should normally be taken up orally. choice of oral exercises will be indicated by the language employed.

The

author's

INTRODUCTION TO ALGEBRAIC THEORIES

4

=

wise bothf and g are not zero. Express each equation in the form a(x) apply Ex. 3. In parts (c) and (d) complete the squares. a) 6)

/ /

2

+ xg* = - zy =

+ 2xfY + (* + 2zfa - a# =

4

2

/ 2 /

c)

d)

*)0

4

b(x)

and

=

2

^

10. Use Ex. 8 to give another proof of (a), (6), and (5) of Ex. 9. Hint: Show that / and g are nonzero polynomial solutions of these equations of least possible de= xfi as well as g = xgi. But then/i and g\ are also solutions grees, then x divides/

if

a contradiction. "*

to show that if/, g, and h are polynomials in x with real coefficients the following equations (identically), then they are all zero: satisfying

Use Ex. 4

11.

b) c)

^

-

2

/ 2 / 2 /

a)

xg*

=

xh*

= xg* + h* + g + (x + 2)fc 2

2

=

Find solutions of the equations of Ex. 11 for polynomials/, coefficients and not all zero. 12.

g,

h with complex

2. The division algorithm. The result of the application of the process ordinarily called long division to polynomials is a theorem which we shall call the Division Algorithm for polynomials and shall state as

Theorem g(x)

7* 0.

1.

Let f (x) and g(x) be polynomials of respective degrees n and m, there exist unique polynomials q(x) and r(x) such that r(x)

Then

has virtual degree

m

f (x)

(3)

For

let /(a;)

Then, either

n

>

m.

n

and

n

q(x) is either zero or has degree

1,

=

q(x)g(x)

+ r(x)

g(x) be defined respectively

< m and we have

(3)

with q(x}

If Ck is the virtual leading coefficient of

m, and

.

by

=

(1)

and

(2)

=

0, r(x)

with 6

f(x),

ora

^

0.

j* 0,

a polynomial h(x) of virtual k l k 1. b^ CkX g(x) is

m+ m, a virtual degree of h(x) n'^n l 1, and a finite repetition b^ a Q x g(x) is n n~ l of this process yields a polynomial r(x) = f(x) + .)g(x) of b^ (a x m and leading for of virtual degree m hence n and (3) degree 1, q(x) degree

m+k>

Thus a virtual degree of f(x)

.

coefficient

degree

m

Lemma

a^ ^ 1

1,

1

states that

t(x)g(x) is the t(x)

=

0. If also f(x)

0, g(z)

=

q Q (x)g(x)

then a virtual degree of s(x)

sum

=

of

if

m

t(x)

and

?o(z), r(x)

The Remainder Theorem

=

=

+r

Q (x)

r(x) is

m

1.

But

the degree of s(x)

q Q (x) 7* the degree of t(x). This

is

=

impossible; and

r Q (x).

of Algebra states that

=

for r (z) of virtual

r Q (x)

q(x)

Algorithm to write /Or)

=

.

q(x)(x

-

c)

+r(x)

,

if

we

use the Division

POLYNOMIALS = x = /(c). The

has degree one and r = r(x) is necessarily a constant, obvious proof of this result is the use of the remark in = r c) paragraph of Section 1 to obtain /(c) = q(c)(c r, /(c)

so that g(x)

then r the

fifth

5

c

+

as desired. It

is

for this application that

we made

the remark.

The Division Algorithm and Remainder Theorem imply the Factor Theorem a result obtained and used frequently in the study of polynomial equations. We shall leave the statements of that theorem, and the subsequent and theorems on the roots and corresponding factorizations of polynomials* with real or complex coefficients, to the reader. * If f(x) is a polynomial in x and c is a constant such that /(c) = then we shall

definitions

call c

a root not only of the equation /(x)

=

but also of the polynomial /(x).

EXERCISES 1.

Show by formal

differentiation that

if

m

m of f(x) =

a root of multiplicity

c is

m

1 of the derivative /'(x) of /(x). (x c) q(x) then c is a root of multiplicity What then is a necessary and sufficient condition that /(x) have multiple roots? 2.

Let

cients.

be a root of a polynomial /(x) of degree n and ordinary integral coeffito show that any polynomial h(c) with rational

c

Use the Division Algorithm

may

coefficients

numbers 3.

6

,

.

.

.

l

c.

,

=

Let /(x)

+ + b n-ic n~ for rational + r(x) and replace x by

+

be expressed in the form 6 &ic 6 n-i. Hint: Write h(x) = q(x)f(x)

x3

+

3x 2

+

4 in Ex.

Compute

2.

the corresponding &< for each of

the polynomials 6 a) c

6)

3.

c

4

Polynomial

+ 10c + 25c + 4c + 6c + 4c + 2

4

3

c)

2

divisibility.

1

d)

c

6

(2c

Let f(x) and g(x)

by the statement that g(x) divides

f (x)

-

2c 4

+c

2

+ 3)(c + 3c)

2

3

^

be polynomials. Then there exists a poly-

we mean that

divides /(x) if and nomial q(x) such that/(x) = q(x)g(x). Thus, g(x) T only if the polynomial r(x) of (3) is the zero polynomial, and we shall say in this case that f(x) has g(x) as a factor, g(x) is a factor o/f(x). We shall call two nonzero polynomials/(x) and g(x) associated polynomials

= q(x)g(x)> g(x) = f(x) divides g(x) and g(x) divides /(#). Then f(x) = q(x)h(x)f(x). Applying Lemmas 3 and 2, we have h(x)f(x), so that/(x)

if

q(x)h(x)

=

1,

q(x)

and

h(x) are nonzero constants.

Thus

f(x)

andg(x)are

associated if and only if each is a nonzero constant multiple of the other. It is clear that every nonzero polynomial is associated with a monic polynomial. Observe thus that the familiar process of dividing out the leading coefficient in

a conditional equation f(x)

equation by the equation g(x) associated with/(x).

=0

=

is

where g(x)

that used to replace this is the monic polynomial

INTRODUCTION TO ALGEBRAIC THEORIES

6

We

Two associated monic polynomials are equal. see from this that if g(x) divides f(x) every polynomial associated with g(x) divides f(x) and that one possible way to distinguish a member of the set of all associates

We

shall use this property of g(x) is to assume the associate to be monic. ater when we discuss the existence of a unique greatest common divisor (abbreviated, g.c.d.) of polynomials in x.

In our discussion of the

g.c.d. of

polynomials

we

shall obtain

a property

which may best be described in terms of the concept of rational function. It will thus be desirable to arrange our exposition so as to precede the study

common divisors by a discussion of the elements of the theory of polynomials and rational functions of several variables, and we shall do so.

of greatest

EXERCISES be a polynomial in x and define m(f) = x mf(l/x) for every positive integer m. Show that m(f) is a polynomial in x of virtual degree m if and only if m is a virtual degree of /(x). 1.

Let/ =

2.

Show

3.

that m(0)

Define/

Show

f(x)

=

0,

=

m[m(f)}

=

and/ =

n(f)

/ 0, "n j for every

if

=

that m(f)

=

xm

/.

m>

Let g be a factor of/. Prove that $

4.

if /is

n and

any nonzero polynomial of degree n. that, if / 7* 0, x is not a factor of/.

a factor of m(f) for every

is

m which is at

least the degree of /.

Polynomials in several variables. Some of our results on polynomials extended easily to polynomials in several variables. We define a polynomial/ = f(x\, x q ) in xi, x q to be any expression obtained x q and as the result of a finite number of integral operations on #1, 4.

in x

may be

.

.

.

.

,

.

.

,

.

As in Section 1 we may express f(xi, number of terms of the form

constants. finite

azji

(4)

We

x$

.

.

x qk

.

.

.

.

,

.

x q ) as the

.

,

sum

of a

.

of the term (4) and define the virtual degree in k q the virtual degree of a parXi, jX q of such a term to be k\ ticular expression of / as a sum of terms of the form (4) to be the largest of call

a the

coefficient

+

.

the virtual degrees of kq exponents k\,

its

terms

(4).

.

If

.

.

+

,

two terms of / have the same

set of

we may combine them by adding their coefficients and thus write /as the unique sum, that is, the sum with unique coefficients, .

(5)

/

.

.

,

,

= f(xi, ...,*)= k

- 0,

1,

POLYNOMIALS coefficients a^ k q are constants and n/ is the degree of x q ) considered as a polynomial in Xj alone. Also / is the zero polynomial if and only if all its coefficients are zero. If / is a nonzero poly-

Here the .

.

.

.

.

.

,

nomial, then some a kl

maximum sum

+

fci

.

.

.

.

.

.

kq

T* 0,

+k

q

and the

for a kl

.

.

degree of

^

* fl

.

is

/

defined to be the

As before we

0.

assign the

and have the property that nonzero constant polynomials have degree zero. Note now that a polynomial may have several different terms of the same degree and that consequently the usual definition of leading term and coefficient do not apply. However, some of the most important simple properties of polynomials in x hold also for polynomials in several x and we shall proceed to their degree minus

infinity to the zero polynomial

v-,

derivation.

We

observe that a polynomial / in x\, polynomial (1) of degree n = n^in x = x q with .

.

.

,

xq

be regarded as a a a n all

may

its coefficients

,

.

.

.

,

x q -\ and a not zero. If, similarly, g be given by , polynomials in x\, with 6 then a virtual degree in x q oifg is ra not n, and a virtual (2) zero, = a 6 are then and nonzero polyof a If coefficient is &o. 2, leading q fg .

.

.

+

nomials in Xi and ao6 ^ by Lemma 2. Then we have proved that the product fg of two nonzero polynomials / and g in x\, x 2 is not zero. If we x q-i prove similarly that the product of two nonzero polynomials in x\ .

.

.

,

}

and hence have not zero, we apply the proof above to obtain ao&o ^ x q is not proved that the product fg of two nonzero polynomials in #1,

is

.

We have

zero.

Theorem

.

thus completed the proof of The product of any two nonzero polynomials in

2.

.

,

Xi,

.

.

.

,

XQ

is not zero.

We have

the immediate consequence 3. Let f, g, h be polynomials in

Theorem fg

=

Then g h. continue our discussion

fh.

To

we

shall

.

. ,

Xq

and

f

be nonzero,

need to consider an important special x q ) a homogeneous poly(5) have the same degree

type of polynomial. Thus we shall call /(xi, xq if all terms of nomial or a form in Xi, .

.

=

.

Xi,

=

+

+

.

.

,

.

.

,

Then, if / is given by (5) and we replace x> in (5) by + x is replaced by y k ^~ *Xj> power product x k x q ) identixq and thus that the polynomial/(i/xi, yx q ) = y f(xij x q ) is a form of degree k x q if and only if /(xi, cally in y Xi, in xi, xq The product of two forms / and g of respective degrees n and m in the same Xi, x q is clearly a form of degree m + n and, by Theorem 2, is nonzero if and only if / and g are nonzero. We now use this result to obtain the second of the properties we desire. It is a generalization of Lemma 1. k

ki

yx^ we .

.

.

.

.

kq

.

see that each

.

.

.

.

.

.

t

.

.

.

.

.

,

.

.

,

.

.

.

.

,

.

.

.

,

.

,

.

.

,

INTRODUCTION TO ALGEBRAIC THEORIES

8

all the terms of the same degree in a nonzero polybe grouped together into a form of this degree and then may express (5) uniquely as the sum

Observe nomial (5)

we may

first

that

/

(6)

=

/(*!,...,*,)

=/o+-..+/n,

where /o is a nonzero form of the same degree n as the polynomial/ and /< a form of degree n i. If also g

(7)

=

for forms g> of degree

g(xi,

m

.

fg

.

,

=

x q)

+

g

.

.

=

h

+

.

.

.

+

.

^

and such that g Q

i

(8)

.

h m+n

m+n

+ gm 0,

is

,

then clearly

,

=

By Theorem 2 /o(7o. Thus if we call/o the leading form of/, we clearly have Theorem 4. Let f and g be polynomials in xi, Xq. Then the degree of f g is the sum of the degrees of f and g and the leading form of f g is the prodwhere the

forms of degree

hi are

i

and

Ao

Ao T* 0.

.

.

.

,

forms of f and g. above is evidently fundamental for the study of polynomials in several variables a study which we shall discuss only briefly in these uct of the leading

The

result

pages. 5.

The integral operations together with the operaby a nonzero quantity form a set of what are called the

Rational functions.

tion of division

A

rational operations.

rational function of xi,

.

.

.

,

xq

is

now

defined to be

any function obtained as the result of a finite number of rational operations x q and constants. The postulates of elementary algebra were on xi f

seen

.

.

.

,

by the reader in his earliest algebraic study to imply that every rational

function of

x\>

.

.

.

,

xq

may

be expressed as a quotient

x q ) 7* 0. The coefficients of x q ) and 6(xi, x q ) and 6(xi, x q ) are then called coefficients of/. Let us obx q with complex serve then that the set of all rational functions in xi, coefficients has a property which we describe by saying that the set is

for polynomials a(xi, a(xi,

.

.

.

,

.

.

.

.

.

,

.

.

.

.

,

,

.

.

.

,

closed with respect to rational operations. By this we mean that every rational function of the elements in this set is in the set. This may be seen to be

due to the definitions a/6 + c/d Here b and d are necessarily not

=

(ad

zero,

+ 6c)/6d, (a/6)

(c/d)

=

and we may use Theorem 2

(ac)/(6d).

to obtain

POLYNOMIALS bd

7* 0.

erties if

/

9

Observe, then, that the set of rational functions satisfies the propin Section 1 for our constants, that is, fg = if and only

we assumed

=

or g

=

0,

while

if

/

then /- 1 exists such that //~ 1

j

=

1.

6. A greatest common divisor process. The existence of a g.c.d. of two polynomials and the method of its computation are essential in the study of what are called Sturm's functions and so are well known to the reader who has studied the Theory of Equations. We shall repeat this material here

because of

importance for algebraic theories. of polynomials f\(x), /,(x) not all zero to be any monic polynomial d(x) which divides all the fi(x), and is such that if g(x) divides every fj(x) then g(x) divides d(x). If do(x) is a second such polynomial, then d(x) and d Q (x) divide each other, d(x) and d (x) are associated monic its

We define the g.c.d.

.

.

.

,

polynomials and are equal. Hence, according to our definition, the g.c.d. f (x) is a unique polynomial. If g(x) divides all the/i(x), then g(x) divides d(x), and hence the degree

of /i(x),

.

.

.

,

t

of d(x) is at least that of g(x). Thus the g.c.d. d(x) is a common divisor of the /i(x) of largest possible degree and is clearly the unique monic com-

mon

divisor of this degree.

If dj(x) is the g.c.d. of /i(x),

.

.

.

,

/,<x)

and d

(x) is

the g.c.d. of

d,-(x)

and

the g.c.d. of /i(x), ,//+i(x). For every common divisor h(x) of /i(x), ,/,-+i(x) divides /i(x), ,/,-(x), and hence both

//+i(aO,

then d

(x) is

.

.

dj(x)

and

d,-(x)

.

.

.

//+i(x), h(x) divides

the divisor

The

.

.

of /i(x),

.

.

.

d

(z).

,/,-(x),

.

.

Moreover, d

(x) divides /,-+i(x)

d Q (x) divides /i(x),

.

.

.

and

,fs+i(x).

above evidently reduces the problems of the existence and construction of a g.c.d. of any number of polynomials in x not all zero to the case of two nonzero polynomials. We shall now study this latter problem and state the result we shall prove as Theorem 5. Let f (x) and g(x) be polynomials not both zero. Then there exist polynomials a(x) and b(x) such that (10)

result

d(x)

=

+ b(x)g(x)

a(x)f(x)

a monic common divisor o/f(x) and g(x). Moreover, d(x) is then the unique 0/f(x) and g(x). For if /(x) = 0, then d(x) is associated with g(x),a(x) = Iand6(x) = b^ 1 is a solution of ( 10) if g(x) is given by (2) Hence, there is no loss of generality if we assume that both f(x) and g(x) are nonzero and that the degree of is not the of than For of notation g(x) greater degree /(x). consistency

is

g.c.d.

.

we put (11)

*.(*)-/(*),

h l (x)

=

g(x).

INTRODUCTION TO ALGEBRAIC THEORIES

10

By Theorem

1

h

(12)

(x)

= q^h^x)

+ h (x) 2

,

where the degree of h z (x) is less than the degree of may apply Theorem 1 to obtain hi(x)

(13)

=

+ W*)

fc(x)M*)

hi(x). If ht(x)

^

we

0,

,

where the degree of hz(x) is less than that of h^(x). Thus our division process yields a sequence of equations of the form (14)

hi-
where hi(x)

is

n<

if

=

0.

=

qi-i(x)hi-i(x)

+ hi(x)

,

the degree of hi(x) then Hi > n > while n< > conclude that our sequence must terminate with .

.

.

,

unless

We

WX)

(15)

-

+ hr(x)

g r_i(oO/l r_i(z)

and (16) for r

*,(*)

>

^

A r_i(z)

,

[qr-i(x)qr (x)

+

be replaced by h r^(x) = divides both h r ~i(x) and h r-i(x). If we

that

implies

(16)

Thus h r (x) hi(x) and

l]h r (x).

hi-.$(x).

=

both ho(x)

Equation b*(x) bi(x)

f(x)

and

hi(x)

=

Ai- 2 ()

6i_i(o:)gr(a:)

Thus we obtain

/i r (o;)

=

divisor of /(#)

=

by

ar (x)f(x) gf(x)

= =

a\(x)j(x)

+ 6<-i(a?)g(x)

implies

(14)

+ b (x)g(x). r

and

is

= =

0,

Ai_i(x)

=

+ b^(x)g(x) with a^(x} + bi(x)g(x) with ai(x)

a*(x)f(x}

ai- 2 ()/(x)

then

and

then (14) implies that h r (x) induction shows that h r (x) divides

At_i(x),

g(x).

Clearly also h\(x)

now,

If,

+ common

evident proof

(12) implies that h z (x)

qi(x). 1.

An

may

(15)

assume that h r (x) divides

= =

qr (x)h r (x)

1.

Equation

divides

=

that

and

Ai(x)

1,

=

The polynomial

fe r (z)

associated with a monic

is

a

common

Then d(x) has the form (10) for a(x) = car (x),b(x) = cb r (x). We have already shown that d(x) is unique. The process used above was first discovered by Euclid, who utilized it in divisor d(x)

=

ch r (x).

his geometric formulation of the analogous result on the g.c.d. of integers. observe that it not only It is therefore usually called Euclid's process.

We

enables us to prove the existence of d(x) but gives us a finite process

by

POLYNOMIALS

11

means of which d(x) may be computed. Notice finally that d(x) is computed by a repetition of the Division Algorithm on /(#), g(x) and polynomials secured from f(x) and g(x) as remainders in the application of the Division Algorithm. But this implies the result we state as Theorem 6. The polynomials a(x), b(x), and hence the greatest common Theorem 5

divisor d(x) of

all

have coefficients which are rational functions

with rational number coefficients of the coefficients of f (x) and g(x). thus have the

We

COROLLARY. Let

the coefficients of f (x)

the coefficients of their g.c.d. are rational If the

and we

only

and g(x)

indicate this at times

are constants, then d(x)

1

shall also g(x) relatively prime polynomials. saying that f(x) is prime to g(x) and hence also

that g(x) is prime to/(x). When/(x) and g(x) are relatively prime, (10) to obtain polynomials a(x) and b(x) such that a(x)f(x)

(17)

=

We

and

by

Then

numbers.

common divisors of f(x) and g(x)

shall call f(x)

be rational numbers.

+ g(x)b(x) =

1

we use

.

It is interesting to observe that the polynomials a(x) and b(x) in (17) are not unique and that it is possible to define a certain unique pair and then determine all others in terms of this pair. To do this we first prove the

LEMMA is

prime

5.

to

Let f(x), g(x), and h(x) be nonzero polynomials such that f(x)

and

g(x)

divides g(x)h(x).

Then

f(x) divides h(x).

may write g(x)h(x) = f(x)q(x) and use = [a(x)h(x) + b(x)q(x)]f(x) = h(x) b(x)g(x)]h(x) For we

We now obtain Theorem 7. Let Then

f (x)

n and

of degree

(17) to obtain [a(x)f(x)

g(x) of degree

m

be relatively prime.

unique polynomials a (x) of degree at most 1 such that a (x)f(x) most n b (x)g(x) =

there exist

of degree at

+

as desired.

m

+

1.

1

and b

(x)

Every pair of

polynomials a(x) and b(x) satisfying (17) has the form a(x)

(18)

=

a

(x)

+

c(x)g(x)

,

b(x)

= b

(x)

-

c(x)f(x)

for a polynomial c(x).

For,

if

a(x)

is

any solution of

(17),

we apply Theorem

1

to obtain the

first equation of (18) with a$(x) the remainder on division of a(x) by g(x). = a Q (x)f(x) Then a (x) has degree at most 1, a(x)f(x) b(x}g(x) = = define b Q (x) 1. b(x) c(x)f(x) and see that [b(x) c(x)f(x)]g(x)

m

+ + + 6 (x)g(x) = By Lemma 1 ao(x)/(rc) + 1 has degree at most m + n the degree of 6 (z) is at most n - 1, a*(x)f(x) + b*(x)g(x) = 1 as desired. 1 and If now ai(s) has virtual degree m bi(x) virtual degree n +

We

1.

1,

INTRODUCTION TO ALGEBRAIC THEORIES

12 a\(x)f(x) [60(2)

+ bi(x)g(x) = bi(x)]g(x).

degree n &o(z)

and

a$(x)j(x)

1 is divisible

by

then /(x)

Q (x)g(x)j

clearly

divides

5 the polynomial 60(2) bi(x) of virtual of n and must be zero. Hence, /(x) degree

=

=

=

a (x)/(x),ai(x) a (x). This proves a (x) 6i(x),sothatai(x)/(x) 6o(#) unique. But the definition above of a$(x) as the remainder on

division of a(x)

There

by

shows that then (18) holds. which is somewhat analogous to Theorem 7 for the

g(x)

also a result

is

case where /(x)

Theorem

and

and g(x)

For

and only if

if f (x)

let (19) hold. If /(x) &o(z)gr(z)

=

But then

ao(x)6(x)]. 1

a(x)

1,

which

is

most

and g(x) are not

and

=

=

1

and b(x)

-^

m.

of degree

relatively prime.

a nonconstant polynomial d(x), we

is

0i(z)d(x), 0i(x)/(x)

m and /i(x)

+

has degree

[-/i(2)ff()l

of degree

than

less

g(x) are relatively prime,

a (x)a(x)/(x)

gr(x)

m

+ b(x)g(x) =

the g.c.d. of f(x) and g(x)

have/(x) = fi(x)d(x), g(x) g\(x) has degree less than

have respective degrees n and

7*

of degree at

a(x)f(x)

(19) exist if

We state it as

g(x) are not relatively prime.

Let f(x) T

8.

Then polynomials a(x) j 1 such that at most n

m

+b

By Lemma

a(x)6 (x)gf(x) divides a(x) ^

=

=

where

Conversely,

we have a

+

m

n.

+

(x)/(x)

flf(x)[o(x)6

-

(a;)

of degree at

most

impossible.

EXERCISES 1.

Extend Theorems

5, 6,

and the corollary to a

set of polynomials /i(x),

.

.

.

,

/<(*) 2.

Let/i(x),

sible g.c.d.'s 3.

.

.

.

,/t(x)

be

all

polynomials of the first degree. State their posfor each such possible g.c.d.

and the conditions on the/(x)

State the results corresponding to those above for polynomials of virtual

degree two. 4.

Prove that the

g.c.d. of f(x)

and

g(x)

is

the monic polynomial of least possible

= degree of the form (10). Hint: Show that if d(x) is this polynomial then f(x) and of that as less than has the form as well d(x) q(x)d(x) r(s), r(x) (10) degree

+

so

must be 5.

and

zero.

A polynomial /(x) is called rationally irreducible if f(x) has rational coefficients is

not the product of two nonconstant polynomials with rational coefficients. possible g.c.d. 's of a set of rationally irreducible /(z) of Ex. 1?

What are the 6.

Let f(x)

=

be rationally

irreducible, g(x)

have rational

that/(x) either divides g(x) or is prime to g(x). Thus, f(x) degree of g(x) is less than that of f(x).

is

coefficients.

prime to g(x)

Show if

the

POLYNOMIALS 7.

Use Ex.

Section 2 together with the results above to

1 of

ly irreducible polynomial has 8.

Find the

13

g.c.d. of

no multiple

show that a

rational-

roots.

each of the following sets of polynomials as well as of

all

possible pairs of polynomials in each case: a) /i

/2 6) /i /, c) /i

/2 /3 d) /i

/ /3

2

= = = = = = = = = =

-

x8

2x 2

-

-

6x

-

+ x x 2x 3x + 8x - 3 x + 2x + 3* + 6 x

4

8

4

x4

-

z8

+

x8 x2 x8

-

+4

= = / / = = /i = / / =

e)

jfi

2

2

2

8

x4

2

-

2x 3

2x 2

-

2x

+6 - 8x - 5x + 6 + 4x + x - 6 - 3x + 2 - 3x + x - 4x +

6x 2

/)

-

3

llx

x6 8

2

x

3

x4 x8

2

x2

3

z4

+ 2x - x - 5x + x + 3x + 3 +x -x- 1 + 2x - 3s - 6 +x-2 + 2x + x + 2 4

8

2

6x

-

3

2

3

2

8

2

2

2

3

4

Let /(x) be a rationally irreducible polynomial and c be a complex root of 0. Show that, if g(x) is a polynomial in x with rational coefficients and g(c) ^

9.

=

/(x) 0,

-

2x 5

there then exists a polynomial h(x) of degree less than that of /(x) and with

rational coefficients such that g(c)h(c)

=

1.

Let/(x) be a rationally irreducible quadratic polynomial and c be a complex = 0. Show that every rational function of c with rational coefficients

10.

root of /(x) is

uniquely expressible in the form a

Let /i,

11.

.

.

.

,

+

be

be polynomials in x of virtual degree n and/i ^ 0. Use Ex. 4 of /i, ...,/* then the g.c.d. of /i, ...,/<

ft

show that if d(x) is the g.c.d. Thus, show that the g.c.d. of n(/i),

of Section 3 to is 3.

.

fc>

with a and b rational numbers.

.

.

A

Forms.

7.

polynomial

The reader

polynomial.

cubic, quartic,

k n(f t ) has the form x d, for an integer

of degree

n

is

frequently spoken of as an n-ic

already familiar with the terms linear, quadratic, = 1, 2, 3, 4, 5. quintic polynomial in the respective cases n

and

is

In a similar fashion a polynomial in

As above, we

nomial. 4,

,

0.

x\,

.

.

.

,

xq

is

called a q-ary poly-

specialize the terminology in the cases q

=

1, 2, 3,

5 to be unary, binary, ternary, quaternary, and quinary. The terminology just described is used much more frequently in connec-

tion with theorems on forms than in the study of arbitrary polynomials.

In particular, we shall find that our principal interest

is

in n-ary quadratic

forms.

There are certain special forms which are quadratic in a set of variables xm 3/1, t/n and which have special importance because they Xi, .

.

.

,

.

,

.

.

,

INTRODUCTION TO ALGEBRAIC THEORIES

14

xm and yi, are linear in both xi, y n separately. such forms bilinear forms. They may be expressed as forms .

.

.

.

,

.

.

,

,

We

shall call

y-i ..... n

f=

(20)

so that

we may thus

write

/

(21)

t-1

;-l

and

see that

/ may be regarded as a

cients are linear forms in x\,

.

.

.

,

form

linear

xm

in yi,

.

.

.

y n whose

,

coeffi-

.

A bilinear form / is called symmetric if it is unaltered by the interchange of correspondingly labeled

members

clearly has meaning only if m = ZyidijXj. But / = S2/ IiXiaayj

ment / =

if

only

m=

= ;

two

sets of variables. This state-

n; and /

is symmetric if and only if and hence / is symmetric if and

a,;Zi,

n,

(22)

A

of its

aij

quadratic form

/

the type ctjx&j for

and have djXiXj

=

is

=

a ;i

sum

evidently a

(i,

of terms of the type

i 7* j.

We may write

a^XiXj

+

an

=

a, a

=

-

;

.

.

.

n)

,

.

a^ as well as

=

a,-i

1,

\ c/ for

i -^

j

a^x^x^ so that

/=

(23)

t,y

=

i

(a*y

We

=

j

=

a/<;

f,

j

=

1,

.

.

.

n)

,

.

with (22) and conclude that a quadratic form may be rej/i, y n in a symmetric z and yi, z n respectively. bilinear form in x\, y by a*,

compare

this

garded as the result of replacing the variables .

we

Later

.

.

.

,

.

.

,

.

.

.

.

,

.

,

,

shall obtain a theory of equivalence of quadratic

,

forms and shall

use the result just derived to obtain a parallel theory of symmetric bilinear forms.

A

type of form of considerable interest is the skew bilinear form. = n, and we call a bilinear form / skew if / = f(x\, Here again xn; final

m

yi,

-

-

,

yn)

=

.

/(yi,

,

yn;

forms of the type (24)

f

x\,

.

.

.

,

.

.

,

x n ). Thus skew bilinear forms are

POLYNOMIALS

15

where

It follows that

an

+ an =

a

is

sum

=

1,

.

.

.

=

1,

.

.

.

,

n)

.

,

n)

.

is

=

a

Hence /

j

(t,

*

that

0,

(26)

=

= -an

an

(25)

(i

#)

of terms an(xiyj

It is also evident that

we

for

j j,

i

=

i

1,

.

.

.

,

n

1,

replace the y/

by corresponding then the new quadratic form/(zi, x n ; xi, x n ) is the zero polynomial. It is important for the reader to observe thus that while (22) may be associated with both quadratic and symmetric bilinear forms we must

j

2,

.

.

.

,

ft.

if

Xjj

associate (25) only with

skew

.

.

.

.

,

.

.

,

bilinear forms.

ORAL EXERCISES Use the language above to describe the following forms:

1.

a) ft)

c)

+ Zxy* + xl + 2xiyi + x yi + x^ z3

3

d) x\

2

+ 2xfli

Xiy 2

e)

2/i

-

x#i

2

Express the following quadratic forms as sums of the kind given by (23)

2.

:

a) 2x\ ft)

Linear forms.

8.

A

linear

/

(27)

We

-

xf

=

x\

form

expressible as a

is

+

aixi

.

.

+

.

anx n

sum

.

x n with coefficients (27) a linear combination of xi, a n The concept of linear combination has already been used without the name in several instances. Thus any polynomial in # is a linear combination of a finite number of non-negative integral powers of x with x q is a linear combination constant coefficients, a polynomial in xi, ai,

shall call

.

.

.

,

.

the g.c.d.

.

.

.

of a finite

.

.

,

.

,

number of power products x$ xj with constant coefficients, of /(x) and g(x) is a linear combination (10) of f(x) and g(x) with .

.

polynomials in x as coefficients. The form (27) with a\ = a^

=

.

=

.

.

.

an

=

is

the zero form. If g

a second form, g

(28)

with constant coefficients (29)

/

+

g

=

= fti,

(a x

+

ftiXi

.

+

.

.

,

.

b ny

61)0:1

+

.

+

.

we .

.

b nx n

,

see that .

+

(a,

+ b n )xn

.

is

INTRODUCTION TO ALGEBRAIC THEORIES

16 Also

if

c is

any constant, we have

We

Then / = .

.

+

(cai)xi

.

.

.

/ to be the form such that /

define

(31)

.

=

cf

(30)

g

if

-/=-!./=

(-oi)si

and only

g

if

/

=

/

+

(ca n )x n

+

(

+

+

.

.

.

/)

=

+

(-a*)x n

=

g)

(

.

0,

and

that

is

see that

.

a<

=

bi (i

=

1,

n).

,

The properties just set down are only trivial consequences of the usual properties of polynomials and, as such, may seem to be relatively unimportant. They may be formulated abstractly, however, as properties of sequences of constants (which cients of linear forms)

and

may be

thought

of, if

we

in this formulation in

so desire, as the coeffi-

Chapter IV

will

be very

important for all algebraic theory. The reader is already familiar with these properties which he has used in the computation of determinants by operations

on

its

rows and columns. u be a sequence

Let, then,

of

n constants a

we

=

u

(32)

(ai,

.

.

.

a)

,

called the elements of the sequence u. If a

is

any constant,

define

au

(33)

and

call

au the

= ua =

scalar product of

(34)

and

define the

sum

of

u and

u

+

(35)

Then the (36)

v

=

(aai,

=

v

by

(ai

(61,

.

.

,

aa n )

We now consider a second sequence,

u by a.

v

.

.

+ 61,

.

.

6 n)

,

.

.

,

,

an

+

bn)

.

linear combination

au

+ bv =

(aai

+ bbi,

.

.

.

,

aa n

+ bbn

)

all constants a and b and all sequences u and v. The sequence all of whose elements are zero will be called the zero sequence and designated by 0. It is clearly the unique sequence z with the

has been uniquely defined for

POLYNOMIALS

17

z = u i or every sequence u. Evidently if a is the zero property that u for every u. constant au = We define the negative u of a sequence u to be the sequence v such v = 0. Evidently, then, u is the unique sequence that u

+

+

-u = -1

(37)

=

w

(-ai,

.

.

.

,

-a n )

,

u

and we

see that the unique solution of the equation v evidently call this sequence ( w). quence

+x=

v is the se-

We

+

v

(38)

u =

(61

ai,

.

.

.

a n}

bn

,

.

The reader should observe now that the definitions and properties derived for linear combinations of sequences are precisely those which hold for the sequences of coefficients of corresponding linear combinations of linear forms and that the usual laws of algebra for addition and multiplication hold for addition of sequences and multiplication of sequences by constants. 9. #i,

.

x g ) is a form of degree n in Equivalence of forms. If / = f(xi, x q and we replace every x> in/ by a corresponding linear form .

.

.

.

.

,

,

Xi

(39)

=

+

anyi

.

.

+

.

a ir y r

=

(i

1,

.

.

.

g)

,

,

we obtain a form g = g(y\, y r ) of the same degree n in t/i, yr Then we shall say that / is carried into g (or that g is obtained from /) by .

the linear mapping (39).

If q

.

.

=

.

,

r

.

.

,

.

and the determinant

(40).

not zero, we shall say that (39) seen that we may solve (39) for yi,

is

is

.

.

.

nonsingular. In this case y 9 as linear forms in #1,

it is

.

.

,

.

easily

x q and

,

obtain a linear mapping which we may call the inverse of (39). This termix q ) = g(yi, nology is justified by the fact that the equation f(xi, y q in g(y\, yq) y q} is an identity, and thus if we replace t/i, .

.

.

.

.

,

by the corresponding linear forms f(xi,...,x q ).

We now .

imply that

.

.

if

t

.

.

.

.

.

.

,

.

,

.

.

,

x q we obtain the original form

,

-

consider two forms /

=

x q ) and g

=

x q ) of / is carried y q ) by a nonsingular linear mapping. The statements above / is equivalent to g then g is also equivalent to /. Thus, we

the same degree n. into g(y\,

in x\

.

,

Then we

shall

f(xi,

.

.

.

say that /

,

is

g(x^

equivalent to g

if

.

.

.

,

INTRODUCTION TO ALGEBRAIC THEORIES

18

shall usually

We shall not study the

say simply that / and g are equivalent.

equivalence of forms of arbitrary degree but only of the special kinds of forms described in Section 7, and even of those forms only under restricted

types of linear mappings. We have now obtained the background needed for a clear understanding of matrix theory and shall proceed to its development.

1.

The

identical

linear

mapping

mapping. What

(39) of

EXERCISES the form x< =

is its effect

y* for

i

=

1,

.

.

.

,

q

is

called the

on any form/?

2. Apply a nonsingular linear mapping to carry each of the following forms to an cx 2) 2 ... by coma^yl Hint: Write / = ai(xi expression of the type a\y\ cx 2 = y\, x 2 = y*. pleting the square on the term in x\ and put Xi

+

+

+

+

b) c)

3.

4xiX 2

d) 2xf

-

XiX 2

3x1

+

2xiX 2

e)

-

xi

2

Find the inverses of the following linear mappings: .

'

4.

-

+ 3xi x? + 14^10:2 + 9x1 3x1 + 18xix + 24x1

a) 2x1

f2xi-|-

x*

\3xj 4- 2x 2

= =

M

2/i

b}

2/ 2

Xi

f

-2xi

+ ^2^2/1 +x = 2

2/2

Apply the linear mappings of Ex. 3 to the following forms / to obtain equivaand their inverses to g to obtain /.

lent forms g

6)

/

=

4x?

-

4x!X2

+ 3x1

CHAPTER

II

RECTANGULAR MATRICES AND ELEMENTARY TRANSFORMATIONS 1. The matrix of a system of linear equations. The concept of a rectangular matrix may be thought of as arising first in connection with the study of the solution of a system

km of

m linear equations in n unknowns y\,

an.

and

The array

is

.

.

.

,

y n with constant coefficients ,

of coefficients arranged as they occur in (1) has the

an

ai2

i

a22

form

We

called the coefficient matrix of the system (1). shall henceforth in s shall fc as scalar and derive our theoand (1) a/

speak of the coefficients

rems with the understanding that they are constants (with respect to the variables y\, y n ) according to the usual definitions and hence satisfy the properties usually assumed in algebra for rational operations. In a later .

.

.

chapter we shall

,

make a completely

explicit

statement about the nature

of these quantities. It is not only true that the concept of a matrix arises as above in the study of systems of linear equations, but many matrix properties are ob-

tainable

by observing the

effect,

on the matrix

of a system, of certain natu-

ral manipulations on the equations themselves with which the reader is shall devote this beginning chapter on matrices to that very familiar.

We

study.

Let us now recall some terminology with which the reader is undoubtedly familiar. (3)

The

line

Ui

=

(an,

.

19

.

.

,

a in )

1JNTKUJLJUUT1UJN

20

TU ALUEJBKA1U THEUK1ES

of coefficients in the ith equation of (1) occurs in (2) as its ith horizontal line. Thus, it is natural to call u* the ith row of the matrix A. Similarly, the coefficients of the unknowns y,- in (1) form a vertical line

(4)

which we

the jth column of A. speak of A as a matrix of

call

We may now

m

rows and n columns, as an

m by n matrix. Then m by 1 matrices. We

ra-rowed and n-columned matrix the rows of

A

are 1

by n

or, briefly, as an matrices and its columns are

ay as the elements of A, and they may be regarded The notation a^ which we adopt for the element of A in its ith row and jth column will be used consistently, and this usage will be of some importance in the clarity of our exposition. To avoid bulky

shall speak of the scalars

as one

by one

matrices.

displayed equations we shall usually not use the notation (2) for a matrix but shall write instead

A =

(5)

m=

(i

=

1,

]

j

=

1,

.

.

.

,

n)

n then A

w-rowed

is a square matrix, and we shall speak of A simply as an matrix. This, too, is a concept and terminology which we square

shall use

very frequently.

If

ORAL EXERCISES 1.

Read

off

the elements an,

ai2, 024,

4050^ -1 -2 -3 c)

3147 0-1 6

a^ in the following matrices

3

2

4

-l

1

6

-6

8/

2.

Read

off

the second row and the third column in each of the matrices of Ex.

3.

Read

off

the systems of equations (1) with constants &,

of coefficients as in Ex.

1.

all

1.

zero and matrices

RECTANGULAR MATRICES Submatrices. In solving the system

2.

<

(1)

21

by the usual methods the

equations in certain t < n of the unknowns. The corresponding coefficient matrix has s rows and t columns, and its elements lie in certain s of the rows and t of the columns of A. reader

We

led to study subsystems of s

is

call

such a matrix an

s

by

t

m

s

by n

t

submatrix

C

A

of

B

B of A. rows and n

submatrix

m

the elements in the remaining

in

s

and we

<m

If s

shall call

C

and

t

<

n,

columns form an

t

the complementary

the complementary submatrix of <7. time to regard a matrix as being made to It will be desirable from time

submatrix of B. Clearly, then,

up

of certain of its submatrices.

is

Thus we

write

A = (A)

(6)

(t

=

l,

...,s;j=l, ...,*),

where now the symbols At, themselves represent rectangular matrices. We A it all have the same assume that for any fixed i the matrices A n, An, number of rows, and for fixed k the matrices AU, A 2 A,* have the same number of columns. It is then clear how each row of A is a 1 by t matrix whose elements are rows of AH, AH in adjacent positions and thus have columns. We for accomplished what we shall call the similarly to drawing lines mentally parallel to amounts A what of by partitioning (6) the rows and columns of A and between them and designating the arrays of elements in the smallest rectangles so formed by A
.

.

,

;t,

.

.

.

.

.

.

,

,

matrix

(A,

A

whose elements AI, A 2 As, A 4 are themselves rectangular matrices. Then AI and A 2 have the same number of rows, A 3 and A 4 have the same number of rows, and every row of A consists partially of a row of AI and of a corresponding row of A 2 or of a row of A 3 and a corresponding row of A 4 ,

.

Note our usage

We

in (2), (5), (6), (7) of the

symbol of

equality for matrices.

always mean that two matrices are equal if and only if they are identical, that is, have the same size and equal corresponding elements. shall

EXERCISES 1.

how

State

A*, and

A4

the columns of

A

of (7) are connected with the

columns of AI,

A

2,

.

2. Introduce a notation of an arbitrary six-rowed square matrix A and partition A into a three-rowed square matrix whose elements are two-rowed square matrices.

INTRODUCTION TO ALGEBRAIC THEORIES

22

Also partition

A

into a two-rowed square matrix

whose elements are three-rowed

square matrices.

Write out

3.

all

submatrices of the matrix

2

-1

3

4

1

02-1

7

3

5\

-2

1

01236 and,

if

they

exist,

Which

4.

2

1

the complementary submatrices.

of the submatrices in Ex, 3 occur in

some partitioning

of

A

as a matrix

of submatrices? 5.

rices

Partition the following matrices so that they become three-rowed square matwhose elements are two-rowed square matrices and state the results in the

notation

(6).

a)

Partition the matrices of Ex. 5 into two-rowed square matrices

6.

whose elements

are three-rowed square matrices. Partition the matrices of Ex. 5 into the form (7) such that A\ is a by six matrix; a two by two matrix. Read off A 2; A 3

7.

matrix; a one

,

two by three and A 4 and

state their sizes. 3. Transposition. The theory of determinants arose in connection with the solution of the system (1). The reader will recall that many of the prop-

determinants were only proved as properties of the rows of a determinant, and then the corresponding column properties were merely stated as results obtained by the process of interchanging rows and columns.

erties of

We

call

rices.

the induced process transposition and define it as follows for matA be an by n matrix, a notation for which is given by (5),

Let

m

and define the matrix (8)

,

w)

,

A. It is an n by m matrix obtained from and columns. rows Thus, the element a*,- in the ith by interchanging row and jfth column of A occurs in A 7 as the element in its jth row and ith

which we

A

shall call the transpose of its

RECTANGULAR MATRICES

23

column. Note then that in accordance with our conventions been written as

A'

(9)

=

-

(j

((a,-,-),-,)

1,

.

.

.

,

n;

t

(8)

=

could have

1,

.

.

.

,

m)

.

We also observe the evident theorem which we state simply as (AJ = A.

(10)

The operation

of transposition may be regarded as the result of a certain matrix which we shall now describe. If A is our m by n motion of the rigid matrix and m < n we put q = m and write

A =

(11)

(A,, A,}

,

where A\ is a g-rowed square matrix. On the other hand, q = n and have l

if

n

<

m, we put

\

W'

(A

(12)

where the matrix A\ is again a #-rowed square matrix. The line of elements a aq of A and hence of A\ is called the principal diagonal of A an, a 22 or, simply, the diagonal of A. It is a diagonal of the square matrix Ai and is its principal diagonal. We shall call the a,- the diagonal elements of A. Notice now that A' is obtained from A by using the diagonal of A as an axis for a rigid rotation of A so that each row of A becomes a column of A'. We should also observe that if A has been partitioned so that it has the ,

form

.

(6)

.

.

,

then

A

1

(13)

We

is

the

A'

=

t

by

(G/0

s

matrix of matrices given by

(On

=

A'rfj**

1,

...,*;<=

1,

...,

).

have now given some simple concepts in the theory of matrices and on to a study of certain fundamental operations.

shall pass

EXERCISES

A

have the form

Give the corresponding notation

for A'. Give also (7). any matrix of Ex. 1 of Section 1. 2. In Ex. 1 assume that A = A'. What then is the form (7) of A ? Obtain the A is the matrix whose elements are the negaA', where analogous result if A =

A'

1.

Let

if

A

is

tives of those of 3.

also

A be a three-rowed square matrix. A = A'.

Let if

A.

Find the form

(2) of

A

if

A =

A' and

INTRODUCTION TO ALGEBRAIC THEORIES

24 4.

Prove that the determinant of every three-rowed square matrix

property that A! 5.

=

A

Solve the system

is

(1)

A

with the

zero.

with matrix /

4=

1

-2

V

2

1\

3-2

-1

-4

3/ 3

for

2/1, 2/2, 2/s

in terms of fo, & 2 ,

pute the matrix

B =

(&*/).

Jt 8 .

Write the results as

Do this

also for the

2/

system

==

(1)

x

&

A' and thus

com-

with matrix A' and com-

pare the results. 4.

Elementary transformations. The system

of elimination, and the reader equations Which are permitted in this

method

is

(1)

may

be solved by the

familiar with the operations

on

method and which

yield systems said to be equivalent to (1). The resulting operations on the rows of the of the system and corresponding operations on the columns of matrix

A

are called elementary transformations on tools in the theory of matrices.

A A and will turn out to be very useful

of our transformations is the result on the rows of A of the intertwo equations of the defining system. We define this and the corresponding column transformation in the DEFINITION 1. Let i 5^ r and B be the matrix obtained from A by interchanging its ith and rth rows (columns). Then B is said to be obtained from A by an elementary row (column) transformation of type 1. The rows (columns) of an m by n matrix are sequences of n (of m) elements, and the operations of addition and scalar multiplication (i.e., multiplication by a scalar) of such sequences were defined in Section 1.8.* The

The

first

change of

members of (1) are linear forms. The addition of a scalar multiple of one equation of (1) to another results in the addition of a corresponding multiple of a corresponding linear form to another and hence to a corresponding result on the rows of A. Thus we make the following DEFINITION 2. 'Let i and r be distinct integers, c be a scalar, and B be me matrix obtained by the addition to the ith row (column) of A of the multiple by c of its Tth row (column). Then B is said to be obtained from A by an elementary row (column) transformation of type 2. Our final type of transformation is induced by the multiplication of an

left

*

We shall use a corresponding notation henceforth when we make references anywhere in our text to results in previous chapters. Thus, for example, by Section 4.7, Theorem 4.8, Lemma 4.9, equation (4.10) we shall mean Section 7, Theorem 8, Lemma 9, equation (10) in Chapter IV. However, if the prefix is omitted, as, for example, Theorem 8, we shall mean that theorem of the chapter in which the reference is made.

RECTANGULAR MATRICES

25

equation of the system (1) by a nonzero scalar a. The restriction a 7* is made so that A will be obtainable from B by the like transformation for or 1 Later we shall discuss matrices whose elements are polynomials .

in x

and use elementary transformations with polynomial

scalars a.

We

a to be a polynomial with a polynomial inverse and hence to be a constant not zero. In view of this fact we shall phrase the definition in our present environment so as to be usable in this other shall then evidently require

and hence state it as DEFINITION 3, Let the scalar a possess an inverse or 1 and the matrix B be obtained as the result of the multiplication of the ith row (column) of A by a. Then B is said to be obtained from A by an elementary row (column*) trans-

situation

formation of type

8.

The fundamental theorems

in the theory of matrices are connected with the study of the matrices obtained from a given matrix A by the application of a finite sequence of elementary transformations, restricted by the

particular results desired, to A. Thus, it is of basic importance to study first what occurs if we make no restriction whatever on the elementary

transformations allowed. For convenience in our discussion

we

first

make

the

DEFINITION. Let

A and Rbembyn matrices and let B be obtainable from A

by the successive application of finitely tions.

Then we

by writing

We now

shall say that

A ^

A is

many

arbitrary elementary transforma-

rationally equivalent to

B

and

indicate this

B.

observe some simple consequences of our definition. First,

we

A

if is rationally equivalent to B and B is rationally equivalent to to C, the combination of the elementary transformations which carry

see that,

A

A

with those which carry B to C will carry equivalent to C. Observe next that every equivalent to c

=

itself.

to C.

Then

A A

is

B

rationally

m by n matrix is rationally For the elementary transformations of type 2 with

and of type 3 with a

=

1

are identical transformations leaving

all

matrices unaltered.

is

Finally, we see that if an elementary transformation carries A to B there an inverse transformation of the same type carrying B to A. In fact, the

any transformation of type 2 defined for c is that defined for c, of type 3 defined by a is that defined for a" of type 1 is itself. But then A is rationally equivalent to B if and only if B is rationally equivalent to A.

inverse of

1

,

*

verify the fact that, if we apply any elementary row transformaand then any column transformation to the result, the matrix obtained is the same as that which we obtain by applying first the column transformation and then the row transformation.

The reader should

tion to

A

INTRODUCTION TO ALGEBRAIC THEORIES

26

Thus we may and

shall replace the

A

is rationally equivalent are rationally equivalent. have now shown that in order to prove that and are rationally both rationally equivalent to the and equivalent it suffices to prove

to

B

in the definition above

by A

terminology

and

B

We

A

B

A

same matrix

LEMMA

C.

As a

Let r

1.

<

tool in such proofs

m,

s

<

n,

we then prove

A and B

and \

A,

B

_

be

the following

m by n matrices of the form

/B,

m

r by n s rafor T by 8 rationally equivalent matrices AI and BI and B B A and and are Then matrices 2 2 rationally equivalent. tionally equivalent For it is clear that any elementary transformation on the first r rows and s

A

.

columns of

A

induces a corresponding transformation on A\ and leaves A* it above unaltered. Clearly the sequence

and the zero matrices bordering of such transformations induced will replace

A

by the transformations carrying A\

by the matrix

A -

Bl <

-\0

We

M

A*)'

similarly follow this sequence of elementary transformations

mentary transformations on the last which carry A 2 to B 2 and obtain B.

to B\

m

r

rows and n

s

by

ele-

columns of

A

important also to observe that we may arbitrarily permute the rows of A by a sequence of elementary row transformations of type 2, and similarly we may permute its columns. For any permutation results from some properly chosen sequence of interchanges. It is

Before continuing further with the study of rational equivalence we shall introduce the familiar properties of determinants in the language of matrix theory and shall also define some important special types of matrices. We

then discuss another result used for the types of proofs mentioned above.

shall

5.

Determinants. Let

B

be the square matrix

(14)

The corresponding symbol

..... (15)

D

bi

RECTANGULAR MATRICES called a t-rowed determinant or determinant of order

is

sum

of the

t!

27 t.

It is defined as the

terms of the form

(-l)*^*,...^,,

(16)

where the sequence of subscripts ii, t and the permutation 1*1, of 1, 2, .

.

.

.

,

.

.

it

,

.

.

.

,

it

ranges over all permutations may be carried into 1,2,...,

1)* is unique interchanges. That the sign ( son's First Course in the Theory of Equations, and

proved in L. E. Dickshall assume this result as well as all the consequent properties of determinants derived there. The determinant D will be spoken of here as the determinant of the matrix

t

by

B

i

and we

shall indicate this

is

we

by writing

D-

(17)

|fi|

D

equals determinant 5). Nonsquare matrices A do not have determinants, but their square submatrices have determinants called the (read

A

a square matrix of n > t rows, the complementary submatrix of any t-rowed square submatrix B is an (n t) -rowed square matrix whose determinant and that of B are minors of A called complementary

minors of A.

If

is

minors. In particular, every element a,-/ of a matrix A defines a one-rowed square submatrix of A whose determinant is the element itself. Thus we have seen that the elements of a matrix may be regarded either as its one-rowed

square submatrices or as its one-rowed minors. We now pass to a statement of some of the most important results on determinants.

The

result

on the interchange of rows and columns of determinants men-

may now be stated as Abe a square matrix. Then

tioned in Section 3

LEMMA

2.

Let '

(18)

|A'|

=

|A|.

The next three properties of determinants are those frequently used in the computation of determinants, and we shall state them now in the language we have just introduced.

LEMMA

3.

Let

B

be the matrix obtained

from a square matrix

mentary transformation of type 1 Then |B| |A|. LEMMA 4. Let B be the matrix obtained from a square matrix .

mentary transformation of type

LEMMA

5.

Let

B

by an

ele-

Then

|

B = A |

|

A.

by an

ele-

. |

from a square matrix A by an ele3 defined for a scalar a. Then |B| =a |A|.

be the matrix obtained

mentary transformation of'type The reader will recall that to obtain

2.

A

=

Lemma

3

may

be used in a simple fashion

INTRODUCTION TO ALGEBRAIC THEORIES

28

LEMMA nant

6.

If a square matrix has two equal rows or columns,

determi-

its

is zero.

Another

LEMMA

result of this type is

// a square matrix has a zero row or column,

7.

its

determinant is

zero.

Finally,

LEMMA

we have 8.

(column) of

C

Let A, B,

C

is the

sum

other rows (columns) of

A

row (column) of and that of B while all are the same as the corresponding rows (col-

of the ith

B

row

be n-rowed square matrices such that the ith

and

C

umns) of A. Then (19)

|C|

There

are, of course,

=

+

|A|

|B|.

many other properties of determinants, and of these

we shall use only very few. Those we shall use are, of course, also well known to the reader. Of particular importance is that result which might be used to define determinants by an induction on order and which does yield the actual process ordinarily used in the expansion of a determinant.

be an n-rowed square matrix A = (o
We

let

A

(20)

|

A = |

aikCki

=

c ik a ki

(i,

j,

=

1,

.

.

.

,

n)

.

Thus, the determinant of A is obtainable as the sum of the products of the elements a/ in any row (column) of A by their cofactors c/i, that is, the properly signed and labeled minors

The

result (20) is of

and

will

Let

B

(

l)

<4

"

J

'd t-/.

fundamental importance in our theory of matrices

be applied presently together with the following parallel result. be the matrix obtained from a square matrix A by replacing the tth row of A by its qth row. Then B has two equal rows and by Lemma 6

B =0. We expand B as above according to the elements of its ith row and obtain as its vanishing determinant the sum of the products of all elements in the qih row of A by the cofactors of the elements in the ith row |

|

of A.

Combining umns we have

this result with the corresponding property

a ik ckq

(21)

*~1

=

c 8k a k j

about

col-

=

k=l (i

T* q, s

^ j;

i, j, q,

8

=

1,

.

.

.

,

n)

.

RECTANGULAR MATRICES The equations

(20)

square matrix

A

and (21) exhibit certain relations between the arbitrary and the matrix we define as adj

(22)

These relations

29

will

(22) the adjoint of

A =

have important

A

and

see that

(i,

later consequences.

A=

if

(an)

is

j

=

.

1,

.

.

,

n)

.

We call the matrix

an n-rowed square matrix

adjoint is the n-rowed square matrix with the cofactor of the element which appears in the jth row and ith column of A as the element in its own tth row and jth column. Clearly, if A = then adj A = 0.

its

EXERCISES the adjoint of each of the matrices

1.

Compute

2.

Expand the determinants below and

ma

8:

32-1

3

2

1

1

a)

0-1 1 1

-3 -1 -1

3 1

003

3

-1 -1

verify the following instances of

4

-1

1

-3

1

1

-1

1

234

Lem-

-1 -1 1

0-1

3 1

1

234

-1

1

234

Special matrices. There are certain square matrices which have speforms but which occur so frequently in the theory of matrices that they have been given special names. The most general of these is the triangular 6.

cial

matrix, that is, a square matrix having the property that either all its elements to the right or all to the left of its diagonal are zero. Thus a square

matrix

A =

that an

=

(a,-/)

is

triangular

for all j

<

i.

if it is

true that either

It is clear that

A

is

=

a,,

triangular

we have The determinant of a triangular matrix

if

for all j

> i or A is 7

and only

if

triangular; and, moreover,

Theorem .

.

.

a nn of

The

We A

its

result

assume

induction first

1.

is the

product ana22

diagonal elements.

above

is

clearly true

if

n =

1

so that

A =

(an),

|

A = \

an.

1 and complete our true for square matrices of order n expanding \A according to the elements of its first row or

it

by

\

column

in the respective cases above. = (a,-/) is called a diagonal matrix matrix

A

if it is

a square matrix,

INTRODUCTION TO ALGEBRAIC THEORIES

30

and a/

=

that

determinant

Clearly, a diagonal matrix A is triangular so the product of its diagonal elements. the diagonal elements of a diagonal matrix are equal, we call the

its

If all

^ j.

for all i

is

matrix a scalar matrix and have \A = ajl4 The scalar matrix for which an = 1 is called the n-rowed identity matrix and will usually be designated by 7. If there be some question as to the order of I or if we are discussing \

several identity matrices of different orders, we shall indicate the order by a subscript and thus shall write either 7 n or I as is convenient for the n-

rowed identity matrix.

Any

scalar matrix

may

be indicated by

of,

(23)

where a

We

= an

is

the

common

value of the diagonal elements of the matrix.

shall discuss the implications of this notation later,

It is natural to call any m by n matrix all of whose elements are zeros a zero matrix. In any discussion of matrices we shall use the notation to represent not only the number zero but any zero matrix. The reader will

find that this usage will cause neither difficulty nor confusion.

We shall frequently feel it desirable to

consider square matrices of either

of the forms

Al

A A.

where A! is a square matrix. Then and the reader should verify the

(24) implies that

A

4 is necessarily square, fact that the Laplace expansion of de-

terminants implies that |A|

-

|A

= |

-|A 4 |.

|Ai|

The property above and that of Theorem 1 are special instances of a more general situation. We let A be a square matrix and partition it as in = t and the submatrices An all square matrices. Then the La(6) with s place expansion clearly implies that if all the A/ are zero matrices for either all i > j or all i <j, then |A| = |An| |A|. Evidently Theorem 1 is the case where the A, are one-rowed square matrices and the result con.

.

.

sidered in (24) the case where t = 2. In connection with the discussion just completed we shall define a notation which is quite useful. Let be a square matrix partitioned as in (6)

A

and suppose that

s

=

t}

the

An are

all

square matrices, and every

A,-/

=

RECTANGULAR MATRICES

31

composed of zero matrices and matrices Ai = An which are what we may call its diagonal blocks, and we shall indicate this

for i 7*

Then

j.

A

is

by writing

A =

(25)

diag{Ai,...,A,}.

of A is the product of the determinants of its submatrices Ai, At. In closing we note the following result which we referred to at the close of Section 4.

As above, the determinant .

LEMMA

9.

.

.

,

Every nonzero

m

by n matrix

A

is rationally equivalent to

a

matrix

(26)

/I

0\

\o

or

I is an identity matrix. For by elementary transformations of type

where

a pq

7*

1

we may carry any element

A into the element 6u of a matrix B which is rationally equivalent

of

1 elementary transformation of type 3 defined for a = frji we = 1. We then apply replace B by a rationally equivalent matrix C with c\\ = of 2 with row transformations c c r \ to replace C by elementary type for the rationally equivalent matrix D = (d< ) such that du = 1, d r \ =

to A.

By an

?

r c

> =

1,

and then use elementary column transformations of type 2 with dir

to replace

an

m

1

row. Clearly,

A

and

Now Ai

D

by the matrix

by n

1 matrix, and I\ is the identity matrix of one are rationally equivalent. Moreover, either AI = and we have (26) for / = /i, or our proof shows that AI is rationally equivalent to a matrix is

A

(

But t

(29)

then,

by Lemma

1,

A

is

rationally equivalent to a matrix

INTRODUCTION TO ALGEBRAIC THEORIES

32

After finitely

We

shall

such steps we obtain

many

show

later that the

number

(26).

of rows in the matrix I of (26)

is

uniquely determined by A.

EXERCISES Carry the following matrices into rationally equivalent matrices of the

1.

form

(26)

3

/

a)

10

5

\-l -1 -

2

1

2\

i

iy

/I

1

2\

(2

3 2

5] 3/

4\

211

1

I

6)

O/

\1

2023 0000 o

(1i

Apply elementary row transformations only

2.

arid carry

each of the following

matrices into a matrix of the form (26)

10

10^ 22-50 -21-52

00

ly

3. Apply elementary column transformations only and carry each of the following matrices into a matrix of the form (26).

a)

-x

2

3

/

3-2\

2

1

,

-27

4

\5

/! 6) \

J

/

.

c)

Show

4.

that

if

3

1

V-l

2

4

-1\ 5/

d)

/O

1

VO

5

2\ 1

3J

the determinant of a square matrix A is not zero then A can be by elementary row* transformations alone. Hint:

carried into the identity matrix

carry

A

^

preserved by elementary transformations. Some element must not be zero, and by row transformations we may a matrix with ones on the diagonal and zeros below and then into /.

The property \A\ in the first

column

into

of

is

A

The largest order of any nonvanishing minor of a rectangular matrix A is called the rank of A. The result of (20) states that every (t + l)-rowed minor of A is a sum of nu7.

* e.g.,

Rational equivalence of rectangular matrices.

Not every matrix may be take

A =

(11).

carried into the

form

(26)

by row transformations

only,

RECTANGULAR MATRICES merical multiples of its Crowed minors, and the former. We thus clearly have

LEMMA most

is at

minors of

the latter are

A vanish.

l)-rowed minors of

all

Then

zero so are

the

A

rank of

r.

We may also LEMMA

+

10. Let all (r

if

33

state this result as

A have a nonzero r-rowed minor A vanish. Then r is the rank of A.

+

l)-rowed

of the zero matrix

and that

11. Let

Note that we are assigning zero as the rank

and

let all (r

the rank of any nonzero matrix is at least 1. The problem of computing the rank of a matrix

A would seem from our and lemmas to involve as a minimum requirement the computation of at least one r-rowed minor of A and all (r + l)-rowed minors. The number of determinants to be computed would then normally be rather large, and the computations themselves generally quite complicated. Howdefinition

problem may be tremendously simplified by the application of elementary transformations. We are thus led to study the effect of such transformations on the rank of a matrix. Let then A result from the application of an elementary row transformation of either type 1 or type 3 to A. By Lemmas 3 and 5 every Crowed minor of A is the product by a nonzero scalar of a uniquely corresponding Crowed minor of A, and it follows that A and Ao have the same rank. If Ao results when we add to the ith row of A the product by c 7^ of its 0th row and B is a Crowed square submatrix of A, the correspondingly placed submatrix B of A is equal to B if no row of B is a part of the ith row of A. If, however, a row erf B is in the ith row of A and a row of B is in the 0th row of B, then by Lemma 2.4 we have B = B If, finally, a row of B is in the ith row of A but no row is in the 0th row of A, then by Lemma 8 Bo = B + c C where C is a Crowed square matrix all but one of whose rows coincide with those of B, and this remaining row is obtained by ever, the

.

|

|

I

1

|

|

|

I

1

\

,

B in the ith row of A by the correspondingly columned elements in its 0th row. But then it is easy to see that C is a minor of A as well as of AO. If A has rank r we put t = r + 1 and see of A that |B = |C| =0, Bo = Of or every (r + 1) -rowed minor |B in A, and our proof shows the Also there exists an r-rowed minor B 5* = B or B = B + c C in existence of a corresponding minor B =0 implies that |C| = -cr \B\ ^ 0, and A has a Ao. But then |B nonzero r-rowed minor |C|, A and A have the same rank. We observe, finally, that if an elementary row transformation be applied to the transpose A' of A to obtain Ai and the corresponding column transformation be applied to A to obtain Ao, then AJ = A\. By the above

replacing the elements of

|

\

.

|

|

|

|

|

|

|

1

|

|

|

l

|

1

|

|

\

\

INTRODUCTION TO ALGEBRAIC THEORIES

34

proof A' and AI have the same rank, by Lemma 2 A and A! have the same minors and hence the same rank, so that A\ and A( = AQ have the same rank. Hence, A and A have the same rank. Thus, any two rationally equivalent matrices have the same rank. Conversely, let the rank r of two by n matrices

m

A

and

B

be the same

9 to carry A into a rationally equivalent matrix (26). It is clear that the rank of the matrix in (26) is the number of rows in the matrix /. By the above proof A and this matrix have the same rank, I = I r

and use

Lemma

,

A

is

rationally equivalent to

<

(o' Similarly,

I)

B is rationally equivalent to

what we regard as the

Theorem

2.

Two

(30)

and

to A.

We have thus proved

principal result of this chapter.

m by n matrices are rationally equivalent if and only if

same rank, have also the consequent COROLLARY. Every by n matrix of rank

they have the

We

m

m by n matrix is

r is rationally equivalent to

an

(SO).

A matrix is called nonsingular if it is a square matrix and its determinant not zero. But then Theorem 2 implies, as in Ex. 4 of Section 6, Theorem

3. Every u-rowed nonsingular matrix is rationally equivalent to n-rowed identity matrix. In closing let us observe a result of the application to a matrix of either

the

row transformations only or column transformations only. We shall prove Theorem 4. Every m by n matrix of rank r > may be carried into a matrix of the forms

(31)

respectively,

where

(H

,

0),

by a sequence of elementary row or column transformations only,

G is an T-rowed matrix, H is an T-columned matrix,

have rank

For

A

and

both

G

and

H

r.

equivalent to (30) transformations. Clearly, we is

transformations and then

all

by a sequence

may

row and column applying all the row

of elementary

obtain (30) by

first

the column transformations. If

we then apply

the inverses of the column transformations in reverse order to (30), we obtain the result of the application of the row transformations alone to A.

But column transformations applied

to (30) clearly carry this matrix into

RECTANGULAR MATRICES

35

a matrix of the form given by the first matrix of (31). Moreover, it is evident that the rank of this matrix is that of (?, G has rank r. The result for column transformations is obtained similarly.

EXERCISES 1.

Compute the rank r of the following matrices by using elementary transformabut

tions to carry each into a matrix with all

rows

r

(or

columns) of zeros and an

obvious r-rowed nonzero minor.

a)

/I

1

1

5

3\ 2

\1

5

-I/

6)

(

/' c)

/2

4

3

4 16

4

1

3-2

1 (

\1

-12

-

-11

14

2. Carry the first of each of the following pairs of matrices into the second by elementary transformations. Hint: If necessary carry A and B into the form (30) and then apply the inverses of those transformations which carry B into (30) to carry (30) into B.

A =

/2

(l \2 /I

c)

_

3\

/I

'

n 6)A =

-1

A =

2 (

\3

-2

-

/2

i\

-221, -4

I/

-2 -4 -6

2

\1

1\ 1

3/

J5=(60 /I

,

3 1

1

B=ll VO

0,

CHAPTER

III

EQUIVALENCE OF MATRICES AND OF FORMS 1. Multiplication of matrices. If xi, related by a system of linear equations .

Xi

(1)

this

system was said in Section

Xi to the

ping

y,-.

We

m

call the

=

.

.

,

xm and

t/i,

.

.

.

atMi

(i

1.9 to define a linear

by n matrix

y n are variables

,

A =

=

1,

.

.

.

m)

,

,

mapping carrying the map-

(a^) the matrix of the

(1).

Suppose now that 21, second linear mapping

.

.

.

zq

,

are variables related to

y\,

.

.

.

y n by a

,

q

yi

(2)

with n by q matrix stitute (2) in (1)

B =

Xi

m by q matrix C =

=

and

(CM),

c ik

(4)

ik z k

third linear

(3)

with

^b

-

2*c ik z k it is

linear

and

(2),

=

1,

Then,

.

.

.

.

,

n)

,

we sub-

if

mapping

(i

=

1,

.

.

.

m)

,

,

by substitution that

easily verified

_ (i

The

(j

carrying the y; to the z k

(bj k ),

we obtain a

=

=

1,

.

.

.

,

ra;

k

=

1,

.

.

.

,

q)

.

mapping (3) is usually called the product of the mappings (1) and we shall also write C = AB and call the matrix C the product

of the matrix

A by the matrix

B.

have now defined the product AB of an m by n matrix A and an n by q matrix B to be a certain m by q matrix C. Moreover, we have defined*C so that the element dk in its ith row and fcth column is obtained

We

36

EQUIVALENCE OF MATRICES AND OF FORMS as the

sum dk =

+

an&i*

+

.

.

+

.

o>i n b n k

37

of the products of the

elements ay in the ith row (5)

of Ay

by the corresponding elements

?>,*

in the fcth

column

61* 62*

(6)

of B.

Thus we have stated what we

for multiplying matrices. Observe that if either

Moreover,

if

A

is

an

A

or

B

is

shall

speak of as the row by column rule

a zero matrix the product then we have

AB

is also.

m by n matrix, Im A

(7)

= AI n = A

,

where 7 r represents the r-rowed identity matrix defined for every r as in Section 2.6. Observe also that I m is the matrix of the linear transformation Xi = yi for i = 1, w, and thus in this case the product of (1) by (2) is immediately (2) hence (7) is trivially true. We have not defined and shall not define the product AB of two matrices in which the number of columns in A is not the same as the number of rows in B. Then, evidently, the fact that AB is defined need not imply that BA is defined. But when both are defined, they are generally not equal and may not even be matrices of the same size. This latter fact is clearly so if, for example, A is m by n, B is n by m, and m^n. If A and B are n-rowed square matrices, we shall say that A and B are commutative if AB = BA. Note the examples of noncommutative square .

.

.

,

;

matrices in the exercises below. Finally, let us observe the following

Theorem

1.

The transpose of a product

of two matrices is the product of

their transposes in reverse order.

In symbols we state this result as (8)

Here trix,

(AB)'

=

B'A'

.

A is an m by n matrix, B is an n by q matrix, (AB)' is a q by in mawhich we state is the product of the q by n matrix B' and the n by m

INTRODUCTION TO ALGEBRAIC THEORIES

38 matrix

A

We

f .

leave the direct application of the

row by column

rule to

prove this result as an exercise for the reader.

of

EXERCISES 1. Compute (3) and hence the product C = AB for the following linear changes variables (mappings) and afterward compute C by the row by column rule. I

I

Ixi

=

Us = 2.

Compute the

where the

a)

latter

2y l

2/2

+ -

32/2

Vl ==

-ISai

-2/s

[2/1=

92/3

1 2/a

following matrix products

product

/4

3

2\

3

2

1

\2

1

is

~~~

^"2

"2*1

=

+

*i

i~

"^"8

26z 2

+

13* 8

2z 2

-

s3

AB. Compute

also

BA

in the cases

defined.

/-I -2 -3^ 3

1

-I/ \~1 -2

4^

-

1

2

"I/"

3illi

-

*

^t

t

A

f\

i

,v

ci;

| |

9 j/9 ^ n*

ioo 1

-

o

Let the symbol EH represent the three-rowed square matrix with unity in the row and jth column and zeros elsewhere. Verify by explicit computation that EijEjk = Eik and that if j ?* g then EijE ok = 0. 3.

ith

2.

The

associative law. It

is

important to know that matrix multiplica-

tion has the property

(AB}C = A(BC)

(9)

for every

mby n matrix A,

n by q matrix B,

q

by

s

matrix C. This result

known as the associative law for matrix multiplication and it may be shown as a consequence that no matter how we group the factors in forming a product A\ At the result is the same. In particular, the powers A of any square matrix are unique. We shall assume these two consequences of

is

6

.

.

.

EQUIVALENCE OF MATRICES AND OF FORMS (9)

39

without further proof and refer the reader to treatises on the founda-

tions of mathematics for general discussions of such questions. = (a,-/), = (ft/*), C = (c k i), where in all To prove (9) we write

A

cases is

i

=

1,

.

.

.

,

m; j =

1,

.

B

.

.

,

n; k

clear that the element in the ith

=

1,

.

row and

.

.

Ith

=

I

q;

,

1,

.

column of

Then

it

G = (AB)C

is

.

.

,

s.

gn

(10)

while that in the same position in

H

= A(BC)

is

hu

(ii)

y

=

i

Each of these expressions is a sum of nq terms which are respectively of the form (dijbjk^Cki and a^bjkCki). But those terms in the respective sums with the same sets of subscripts are equal, since we have already assumed that the elements of our matrices satisfy the associative law a(bc) = (ab)c. hu for all i and Z, G = H, and (9) is proved. Hence, gu

EXERCISES Compute

/2 o)

A =

(AB)C and A(BC)

the products

-1

\0

3\

12,

3

in the following cases.

-1 2

B

=

I/

~3\

/

/

2

-1

1

^-a.! c)

3.

A(l

2

-1

A =

Products by diagonal and scalar matrices. Let

matrix and

B be a diagonal matrix,

(a/) be

an

m by n

and designate the

ith diagonal element is ra-rowed so our definition of product implies that if

B

B by &<. Then that BA is defined,

of

3),

then

,

'

(12)

BA =

(btftf) (i

=

1,

.

.

.

,

m\j =

1,

.

.

.

,

n)

;

INTRODUCTION TO ALGEBRAIC THEORIES

40 while

if

B is n-rowed,

then

AB =

(13)

(aijbj)

=

(i

1,

.

.

.

,

ra; j

=

1,

.

.

.

n)

,

.

Thus the product of a matrix A by a diagonal matrix B on the left is obtained as the result of multiplying the rows of A in turn by the corresponding diagonal elements of B; the product of A by a diagonal matrix on the right

is

the result of multiplying the columns of

A

in turn

by the

corre-

sponding diagonal elements of B. Now, let m = n, A be a square matrix. Then from (12) and (13) we see that

AB = BA

if

and only

(14)

if

(&<

As an immediate consequence

-

bj)av

=

(i,

of the case bi

=

.

.

.

=

bn

j

=

1,

we have

.

.

.

n)

,

.

the very

simple

Theorem

Every n-rowed scalar matrix

2.

is

commutative with

all

n-rowed

square matrices.

We

next see that, if i 7* j and & 5^ This gives the result we shall state as

Theorem all distinct.

the

3.

&/,

then (14) implies that a,

=

0.

Let the diagonal elements of an n-rowed diagonal matrix B be the only n-rowed square matrices commutative with B are

Then

n-rowed diagonal matrices. prove the converse of Theorem 2

We may now

inspiration of the

name

a result which

the

is

scalar matrix.

Theorem 4. The only n-rowed square matrices which are commutative with every n-rowed square matrix are the scalar matrices. For

let

(15)

B =

(ba)

(i,j,

= l,...,n)

B is commutative with every n-rowed square matrix We shall select A in various ways to obtain our theorem. First, we let E

and suppose that

3

A. be

jth row and column and zeros elsewhere and put BEj = EjB. Equations (12) and (13) imply that the jth row of EjB is the same as that of B and the jth column of BEj is the same as that of 5, while all other columns of BEj are zero. Thus if i ^ j, the elements in the ith column of EjB must be zero. Since 6,-< is in the for j j* i, and 5 is a diagonal matrix. If D ith column, we have 6/ = is the matrix with 1 in its first row and jth column and zeros elsewhere, the the diagonal matrix with unity in

its

;

EQUIVALENCE OF MATRICES AND OF FORMS

41

product BDj has bu in its first row and jth column and is equal to the matrix DjB which has 6/,-in this same place. Hence, fry, = bn = 6 for j = 2, n, and B is the scalar matrix 6/ n Let us now observe that if A is any m by n matrix and a is any scalar, .

.

.

.

,

then (a! m )A

(16)

= A(al n)

m

by n matrix whose element in the ith row and jth column is the product by a of the corresponding element of A. This is then a type of

is

an

product

aA = Aa

(17)

Chapter I for sequences, and we shall call such a product the scalar product of a by A. However, we have defined (17) as the instances (16) of our matrix product (4).

like that defined in

1.

the products

Compute

row by column

rule

EXERCISES AB and BA by the 0\

71 a)

A =

-2 \0

A =

,

37

0\

71 6)

use of (12) and (13) as well as the

if

-1 \0

B =

,

07

Ov **

_ ~

2

\0 2.

Find

all

\0

1

o

o

,

B

such that

0\

/I

4 =

o

17

three-rowed square matrices

o)

1

0\

73

A -

0\

0-1

/ 1

(2000 -2/

d)

-1

/O

02 01 00-2 or

-1

b)

A

BA = AB\i

INTRODUCTION TO ALGEBRAIC THEORIES

42 3.

Prove by direct multiplication that

4.

Let

5.

Show

matrix 6.

A

w

i

if

2

=

1

BA

and

wAB if

B of Ex. 4 has the property B = al and that the A = 7. Obtain similar results for the matrices of Ex. 3. 3

that the matrix

has the property

3

BAB if ic

Ha c

AB

be a primitive cube root of unity. Prove that

Compute

where

BA =

-d\ c)'

/O

n

Hi

and d are any ordinary complex numbers,

-1\ o)' c

and 3 are

their conjugates.

4. Elementary transformation matrices. We shall show that the matrix which is the result of the application of any elementary row (column) transformation to an m by n matrix A is a corresponding product EA (the product AN) where E is a uniquely determined square matrix. We might of course give a formula for each E and verify the statement, but it is simpler to describe E and to obtain our results by a device which is a consequence

of the following

Theorem 5. Let A be an m by n matrix, B be an n by q matrix so that C = AB is an m by q matrix. Apply an elementary row (column) transformation to A (to B) resulting in what we shall designate by Ao(by B ), and then the same elementary transformation to C resulting in Co (in C ). Then (0)

(0)

(18)

Co

= AB

,

C<>

= AB<>

.

For proof we see that

if we replace a^ by a,,- in the right members of (4) Thus we obtain the result of an elementary row transformation get c,*. 1 AB on of type by applying it to A. Our definitions also imply that for elementary row transformations of type 3 the result stated as (18) follows

we

from (19)

;!

;'1 (i

=

1,

.

.

.

,

m; k =

1,

.

.

.

,

q)

.

EQUIVALENCE OF MATRICES AND OF FORMS we

Finally,

see that for type 2 they follow

n

/

2} (a*,

(20)

+ ca j)b = t

3k

I

n

^a^b/^ |

\y-i

y-i

from

\

n

/

+

43

c

I

\

^^A* /

1

=

c ik

+

cc 9k

\y-i

/

(i

=

1,

.

.

.

,

n; k

=

1,

.

.

.

,

q)

,

and we have proved the first equation in (18). The corresponding column C (0) = AB (Q) has an obvious parallel proof or may be thought of as obtained being by the process of transposition. It is surely unnecessary to

result

supply further

details.

We now write A = IA where / is the ra-rowed identity matrix and apply Theorem 5 to obtain A = /<>A, in which 7 is the matrix called E above. Then we see that to apply any elementary row transformation to A we simply multiply A on the left by either EH, P;/(c), or R<(a). Here we define EH

to be the matrix obtained by interchanging the ith and jth rows of by adding c times the jth row of I to its Oh row, Ri(a) by multiply-

I, P*,(c)

ing the -ith row of / by a ? 0. We shall call EH, P,-(c), and Ri(a) elementary transformation matrices of types 1, 2, and 3, respectively. Observe that

Eh =

(21)

E,<

= EH

,

E En = i3

/

,

if we now assume that EH is n-rowed, the product AE^ is the result an elementary column transformation of type 1 on A. Similarly,

so that, of

(22)

(PH(C)]'

=

P,,(c)

,

P(-c)P w (c) = P(c)P(-c) =

/

,

and if P,-(c) is n-rowed, then APa(c) is the result of an elementary column transformation of type 2 on A. Finally, (23)

[Ri(a)Y

=

Rt(a)

,

R^a^R^a) = E

1

i

(a)^ i (a~

)

=

/

,

and if Ri(a) is n-rowed, then ARi(a) is the result of an elementary column transformation of type 3 on A. Thus the elementary column transformations give rise to exactly the same set of elementary transformation matrices as were obtained from the row transformations. We shall now interpret the results of Section 2.7 in terms of elementary transformation matrices. First of all, we may interpret Theorem 2.2 as the following

INTRODUCTION TO ALGEBRAIC THEORIES

44

LEMMA

Let

1.

A

and

B

transformation matrices PI,

B = if

and only

if

A

B

and

be .

.

m .

(?!

,

,

by n matrices. Then there exist elementary P 8 Qi, Qt such that ,

.

.

.

,

.

P.)A(Qi

,

.

.

.

t)

have the same rank.

A

Theorem 2.3 is the case of Lemma l where = PI P,Qi matrix, and consequently B v

.

LEMMA 2.

Q

.

Qt.

.

Every nonsingular matrix

is

is

the n-rowed identity

Thus we obtain

a product of elementary transforma-

tion matrices.

We shall close the results with an important consequence of Theorem 2.4. Theorem

6.

The rank

of a product of two matrices does not exceed the rank

of either factor.

For,

by Theorem

2.4, if

the rank of

A

is r,

mentary transformations carrying A into an r rows are all zero. By Theorem 5, tom

m

tions to

rank of

m if

we apply these transforma-

C = AB, we

the bottom result

there exists a sequence of eleby n matrix A Q whose bot-

C

is

on the

obtain a rationally equivalent matrix Co = A Q B. Then r rows of the w-rowed matrix C are all zero, and the

m

C and is at most r, as desired. The corresponding between the ranks of C and B is obtained similarly.

the rank of relation

EXERCISES 1.

Express the following as products of elementary transformation matrices.

^

0)

2.

2

l

Find the elementary transformation jjrtatjafes corresponding to the elementary

row transformations used in Ex. 2 of Sectfoi^fcfrand carry the matrices cise into the form (2.30) by matrix multiplication.

of that exer-

The determinant

of a product. In the theory of determinants it is the shown that symbol for the product of two determinants may be computed as the row by column product of the symbols for its factors. In our 6.

present terminology this result may be stated as Theorem 7. The determinant of a product of two square matrices product of the determinants of the factors, that is, (24)

|AB|

= |A|-

is the

|B|.

The usual proof in determinant theory of the result is quite complicated, and it is interesting to note that it is possible to derive the theorem as a

EQUIVALENCE OF MATRICES AND OF FORMS

45

simple consequence of our theorems which were obtained independently and which we should have wished to derive even had Theorem 7 been as-

sumed. We shall, therefore, give such a derivation. We thus let A and B be n-rowed square matrices and see that Theorem 6 states that if A = then AB = 0. Hence, let A be nonsingular so that, by Lemma 2, |

|

\

\

A = PL..P., where the Pi are elementary transformation matrices. From our definiwe see that, if E is an n-rowed elementary transformation matrix of 1, 1, or a, respectively. Thus, if G is an type 1, 2, or 3, then \E\ = n-rowed square matrix and <7 = EG, then Lemmas 2.3, 2.4, and 2.5 imply = -\G\, G|,a|G |, respectively, and hence |G = \E\ |G|. that |(?

tions

|

|

|

It follows clearly that,

if

Ei,

.

.

.

,

E

matrices, then EiO\ = \E t sult first to A to obtain \A\ = |Pi| ...

|M_i

.

.

\AB\ = |Pi. ..P,| = 6.

any elementary transformation

are

t

.

.

.

.

\

|Pi|

.

.

.

|P.

|

\Ei\

|G|.

|P| and then

=

\B\

\A\

designate

B

as desired.

|J8|

A is said to have an

Nonsingular matrices. An n-rowed square matrix if there exists a matrix B such that AB = BA

= 7 is the n-rowed an n-rowed square matrix which we shall

inverse

identity matrix. Clearly,

We apply this reto A B to obtain

is

by A* and thus write 1

AA~ = A- A = l

(25)

1

I

.

Moreover, we have

Theorem

8.

A

square ?>8j^m^A has an inverse if and only

singular.

^

if

A

is

non-

we apply Theorem 7 to obtain \A JA- = |/| = 1, A ^ 0. The converse may be shown to follow from (21), (22), (23), and Lemma 2; but we shall prove instead the result that if A 5^ then A" 1 is For if

|

1

(25) holds,

!

\

|

|

\

uniquely determined as the matrix (26)

A-*

This formula follows from the matrix equation (27)

A(adj A)

=

(adj

A) A = |A|

I

l multiplication by the scalar \A\~ and we observe that (27) is the inis terpretation of (2.20) and (2,21) in terms of matrix product, where adj our symbol for the adjoint matrix defined in (2.22).

by

,

A

INTRODUCTION TO ALGEBRAIC THEORIES

46

unique by showing that if either AB = / or BA = / 1 necessarily the matrix A" of (26). This is clear since in either

We now prove A~~ B

then

is

^

case \A\

IB =

A~

0,

l

l

B, and similarly

if

We note also that, if A

BA = and

1

For (AB)(B- lA~ l ) lar we have

l

/.

=

B-+A-*

= A(BB~ )A~ = A A" = 1

l

l

(A-O'^A')-

(29) /'

A n =

=

= (AA- )' = (A-yA',

q

if

mapping

(1)

the product (3)

is

with

.

/.

A

if

Finally,

is

nonsingu-

1 .

1

1

I

linear

1

B are nonsingular,

(AB)-*

(28)

For

A" = A^I = A~ (AB) = (A~ A)B =

of (26) exists,

(A- )' is the inverse of A'. n has an inverse mapping

m=

the identical mapping, that

with

(2)

C = AB

is, if

is

the

identity matrix. But this is then possible if and only if A 5^ 0, that is, shall (1) is what we called a nonsingular linear mapping in Section 1.9. |

|

We

use this concept later in studying the equivalence of forms.

EXERCISES 1.

Show

has rank

Then the

1.

that

if

Hint:

first

n

A By

1

an n-rowed square matrix of rank n 1 ?* = 0, PAQ(Q~ 1 adj A) (27) we have A(adj A)

is

rows of Q"1

A

adj

must be

2. Use the result above and (28) to prove that 2 and A ^ 0. and adj (adj A) = A if n |

3. 4.

Use Ex.

1

Compute

and

(27) to

zero, adj

A

0,

then adj

=

has rank

1.

n~2 A A) = A

adj (adj

|

|

\

show that

|adj

A|

= lA]^

the inverses of the following matrices

1 .

by the use

A

for

of (26).

if

n > 2

EQUIVALENCE OF MATRICES AND OF FORMS A

Let

5.

-1

by

47

(d) above and B be the matrix of (e). Compute C and verify that (AE)C = I by direct multiplication.

be the matrix of

(28)

=

7. Equivalence of rectangular matrices. Our considerations thus far have been devised as relatively simple steps toward a goal which we may now

We

attain.

first

DEFINITION. exist

make the Two m by n

nonsingular matrices

matrices

P and Q

A and B

PAQ = B

(30)

Observe that

P

are called equivalent if there

such that

.

and Q are necessarily square matrices

of

m and n rows,

respectively. By Lemma 2 both P and Q are products of elementary transformation matrices and therefore A and B are equivalent if and only if A and B are rationally equivalent. The reader should notice that the definition of

rational equivalence

to be regarded here as simply another

form of the above and, while the previous definition is more useful for proofs, that above is the one which has always been given in previous expositions of matrix theory. We may now apply Lemma 1 and have the principal result of the present chapter. is

definition of equivalence given

Theorem the

9.

Two

m

by n matrices are equivalent

if

and only

if they

have

same rank.

We

emphasize in closing that, if A and B are equivalent, the proof of 2.2 shows that the elements of P and Q in (30) may be taken to be rational functions, with rational coefficients, of the elements of A and B.

Theorem

EXERCISES 1.

P and Q for each of the matrices A of Ex. 1 of Section 2.6 PAQ has the form (2.30). Hint: If A is m by n, we may obtain P by ap-

Compute matrices

such that

plying those elementary row transformations used in that exercise to I m and simi-

(The details of an instance of this method are given in the example at the end of Section 8.)

larly for Q.

2.

that the product AB of any three-rowed square matrices A and B of not zero. Hint: There exist matrices P and Q such that A = PAQ has the

Show

rank 2

form

is

(2.30) for r

the same rank as 3.

illustrative

= 2. Then, if AB = 0, we have A*B* = where B Q B and may be shown to have two rows with elements

Compute the ranks

into a simpler matrix

of

A, B,

AB

QrlB has all zero.

Carry A B into B Q = BQ by

for the following matrices. Hint:

A Q = PA by row transformations

alone,

INTRODUCTION TO ALGEBRAIC THEORIES

48

column transformations alone, and thus compute the rank stead of that of

a)

of AoB<>

= P(AE)Q

in-

AB.

A=

2

3

4

B

,

B

4^

1-213

1-1 0-2

5-83 (3-52 8. Bilinear

forms. As

5/

we indicated at the close of Chapter I, the problem two forms of the same

of determining the conditions for the equivalence of

restricted type customarily modified by the imposition of corresponding restrictions on the linear mappings which are allowed. We now precede is

the introduction of those restrictions which are linear forms

made

for the case of bi-

by the presentation of certain notations which will

simplify our

discussion.

The one-rowed matrices x'

(31)

=

(xi,

.

.

.

,

x m)

y'

,

=

(yi,

.

.

.

,

y n)

have one-columned matrices x and y as their respective transposes. A be the m by n matrix of the system of equations (1) and see that system may be expressed as either of the matrix equations

let

x

(32)

= Ay

x'

,

=

y'A'

We

have called (1) a nonsingular linear mapping singular. But then the solution of (1) for yi, .

xi,

.

.

.

,

xn

is

.

if .

,

m=

= A-

1

x

,

y'

=

z'(A')-

1

We

A

tation (34)

.

A

is

non-

= x'(A~y

of (32) for y in terms of x (or y' in terms of x'). and variables Xi and y, and shall by n matrices

m

n and

y n as linear forms in

the solution

y

(33)

.

We this

x

=

P'u

shall again consider

now

introduce the no-

EQUIVALENCE OF MATRICES AND OF FORMS for a nonsingular linear

=

mapping carrying the

Xi to

new

49

variables Uk, for

i,

r m, so that the transpose P of P is a nonsingular m-rowed 1 = Um). Similarly, we write (u\, square matrix and u

fc

1,

.

.

.

,

.

.

.

,

= Q

y

(35)

for a nonsingular n-rowed square matrix return to the study of bilinear forms.

A

bilinear

scalar which

form /

=

=

Zziauj//, for i

may be regarded

Q and

v'

1,

,

.

.

.

=

(v\ t

.

.

m and j ~

as a one-rowed square matrix

.

,

1,

We now

v n ).

.

and

.

is

.

,

n, is

a

then the

matrix product

/

(36)

=

x'Ay

.

(31), and we call the m by n matrix A the matrix rankle rank of/. Also let g = x'By be a bilinear form in #1, xm m n B. Then with matrix we shall that and ?/i, and are yn / by say g

Here x and y are given by

of/, its

.

.

.

.

.

.

,

,

there exist nonsingular linear mappings (34) and (35) such um and Vi, v n into which / is that the matrix of the form in ui,

equivalent

if

.

carried

by these mappings /

B = PAQ

=

is

B.

.

But

.

.

,

=

(u'P)A(Qv)

.

.

,

(34) holds, then x'

if

u'(PAQ)v

=

u'P and

,

A

and are equivalent. Thus, two bilinear forms f and g are equivalent if and only if their matrices are equivalent. By Theorem 9 we see that two bilinear forms are equivalent if and only if they have the same rank. It follows also that every bilinear form of rank r is equivalent to so that

the form (37)

zit/i

+

.

.

+xy r

.

r

.

These results complete the study of the equivalence of bilinear forms.

ILLUSTRATIVE EXAMPLE

We shall find nonsingular linear mappings

into a form of the type (37).

The matrix f

of

/

2-3 -1

W6

(34)

is

1^

5

3

and

W

(35)

which carry the form

INTRODUCTION TO ALGEBRAIC THEORIES

50

We interchange the first and second new second row, add

6 times the

which evidently has rank the

first

row by

1,

2.

rows of A, add twice the new

new

first row to the row to the third row, and obtain

first

We then add the second row to the third row, multiply

the second row by

0-5\

/I

PA=

and obtain

J,

o

i

\o

o

-y o/

The matrix P is obtained by performing the transformations above on the threerowed identity matrix, and hence /

P-f-* \

We

continue and carry

times the

first

PA

column and

into

V

PAQ

1

-1 -I -4

of the

0\

o

.

I/

form

(2.30) f or r

times the second column of

PA

=

2

by adding

five

to its third column.

Then

5\

/I

Q =

1

f

I I

We

verify

by

xi

Z2 Z8

(34)

= - Jtt2 + Uz = -Ui - ftt2 ~ = ^3

-

17

\0

The corresponding linear mappings

V

and

(35) are given respectively (

4W3

Vi 2/2

,

I i 2/3

= = =

+

5^3

30t;8

+

vi

by

t>2

^3

direct substitution that

(-6vi

-

3i; 2

as desired.

EXERCISES Use the method above to

find nonsingular linear following bilinear forms into forms of the type (37). 1.

o) 2x
+ 3x# - x&i 2

2x22/2

mappings which carry the

EQUIVALENCE OF MATRICES AND OF FORMS c)

d)

+ 3xi2/ ~ + 5x + 2x y + x y + 3x - 2x yi 2xiyi Xiy + 3xi2/ + - X + 2X32/4 + 4X42/1 2xiyi

2

22/i

Zi2/a 8

2

2

zi2/4

2

2

51

3 2/i

s

2

32/3

+

X 4t/2

OJ42/3

+ 5X42/4

Use the method above to find a nonsingular linear mapping on Xi, X2, x8 such that it and the identity mapping on 2/1, y2 y* carry the following forms into forms 2.

,

of the type (37). a)

c)

Xii/i

d)

3

e)

-

4xi2/ 2

+

-

Zi2/ 8

x 22/i

+xy 2

2

-

2x42/2

Find a nonsingular linear mapping on 2/1, 2/2, 2/3 such that it and the identical xi, x 2 x3 carry the forms of Ex. 2 into forms of the type (37). Hint: The matrices A of the forms of Ex. 2 are nonsingular so that the corresponding matrices P have the property PA = I. Then P = A" 1 AQ = / has the unique solution 3.

mapping on

,

,

Q = 4.

P.

Use elementary row transformations as above

matrices of Section 5.

6,

Ex.

to

compute the inverses

of the

4.

Use elementary column transformations

to

compute the inverses

of the fol-

lowing matrices.

-4

1

-1\

-1301 10 2-3 3

1

O

-1

I

Congruence of square matrices. There are some important problems regarding special types of bilinear forms as well as the theory of equivalence of quadratic forms which arise when we restrict the linear mappings we use. 9.

We let m =

n so that the matrices A of forms/ = x'Ay are square matrices. = P' Then/ and g and (35) are called cogredient mappings if Q (34) are clearly equivalent under cogredient mappings if and only if

Then

.

B = PAP'

(38)

We

shall call

A

satisfying (38).

and

B

congruent

if

.

there exists a nonsingular matrix

P

INTRODUCTION TO ALGEBRAIC THEORIES

52

We

not study the complicated question as to the conditions that two arbitrary square matrices be congruent but shall restrict our attention shall

to two special cases. Before passing to this study we observe that are congruent if and only if A imply that A and

B

Lemma 2 and Section 7 may be carried into B by

a sequence of operations each of which consists of an elementary row transformation followed by the corresponding column transformation. Thus = P = P, PI, where the P* are elementary transformation matrices, B = P ... ... ... and so deforth as 2 (P!APDP 2 P. P. P.' P,', PjAPJ .

.

.

.

We

sired.

.

.

on a matrix A as cogredient elethe three types and shall use them in our study

shall speak of such operations

mentary transformations of

of the congruence of matrices.

Skew matrices and skew bilinear forms. A square matrix A is called A. If B = PAP' is congruent to symmetric if A' = A, and skew if A' = 10.

A

then B'

skew If

if

PA'P',

B

is

A

is

skew.

and only

A =

=

an

=

a>a

if

symmetric

and only

if

if

A

is

symmetric,

skew matrix, then an = an for all and consequently every diagonal element of A

(an) is a

i

and

j.

is zero.

B

is

Hence

We use

this result in the proof of

Theorem the

10.

same rank

r.

Two n-rowed skew Moreover

r is

and only if they and every skew matrix is

matrices are congruent if

an even

integer 2t,

thus congruent to a matrix

-It

/O

0\

It

(39)

.

O/

\0

A =

= PAP'

for every P and our result is trivial, or some an T* 0. We may interchange the ith row and first row, the ^'th and second row and thus also the corresponding columns by cogredient elementary transformations of type 1. We thus obtain a skew matrix H = (/&,-) con= ^22 = 0. Multiply ^12, An gruent to A and with a,- = hiz j^ 0, hzi = the first row and column of H by h^ and obtain a skew matrix C = (c -,) = 1, en = c 22 = 0. We now apply 1, c 2 i congruent to A and with Ci 2 =

For either

t

a sequence of cogredient elementary transformations of type 2 where we add c/i times the second row of C to its jth row as well as c, 2 times the first row of C to its jth row for j = 3, n, and thus obtain the skew .

.

.

,

matrix (40)

Ac

=

\ '

A,)

E_(0 *

-1\

\1

OJ

'

EQUIVALENCE OF MATRICES AND OF FORMS The matrix Ao

is

congruent to A,

A

is

i

53

skew matrix of n

necessarily a

2

2 rows rows, and any cogredient elementary transformation on the last n and columns of A induces corresponding transformations on AI, carrying it to a congruent skew matrix H\ and carrying Ao to a congruent skew

matrix

(E

H

VO It follows that, after

a

number

finite

we may

of such steps,

replace

A

by

a congruent skew matrix

G =

(41)

with each trix of

Ek =

diag

{JEi,

.

.

.

,

E

t,

0,

.

.

.

,

0}

G and A have rank 2t. If B also is a skew maB is congruent to (41) and to A, both A and B are con-

E. Clearly,

rank 2, then

gruent to (39). If A is a skew matrix, the corresponding bilinear form x'Ay is a skew bilinear form. Hence, two such forms are equivalent under cogredient nonsingular linear mappings if and only if they have the same rank. Moreover, if

/

is

a skew bilinear form of rank 2t

it is

mappings to

x^yi)

singular linear

(xiyz

equivalent under cogredient non-

+

.

.

.

+

EXERCISES Use a method analogous to that of the exercises of Section 8 to find cogredient linear mappings carrying the following skew forms to forms of the type above. a) b) c)

+

80:22/4

-

Symmetric matrices and quadratic forms. The theory of symmetric is considerably more extensive and complicated than that of skew matrices, and we shall obtain only some of its most elementary results. Our 11.

matrices

principal conclusion

Theorem of the

11.

may

be stated as

Every symmetric matrix

A is congruent to

a diagonal matrix

same rank as A.

We may evidently assume that A = A' =^ 0, and we shall prove first that A is congruent to a symmetric matrix H = (hij) with some diagonal element ha ^ 0. This is true for A = H if some diagonal element of A is not zero. Otherwise there is some a
INTRODUCTION TO ALGEBRAIC THEORIES

54

A

the jth column of

to its iih column,

ha

=

a,-*

+a

=

;

as de-

2a,- j^

permute the rows and corresponding columns of H to obtain a congruent symmetric matrix C with en = ha 7* 0. Then we add ~~cTiCki times the first row to its ifcth row, follow with the corresponding column transformation, and obtain a symmetric matrix

We now

sired.

/On (42)

\

Aj

\0

1 rows. As is a symmetric matrix with n Theorem 10 we carry out a finite number of such steps, and it is clear that we ultimately obtain a diagonal matrix. It is a matrix equivalent to A and must have the same rank. The result above may be applied to obtain a corresponding result on

congruent to A. Clearly, A\

in the proof of

symmetric bilinear forms of rank by a symmetric matrix A of rank

r,

that

is,

Theorem

r.

lent under cogredient transformations to a (43)

aiXitfi

The f(xi,

.

.

bilinear forms

+

.

.

.

+

/

= x'Ay

defined

11 then states that /is equiva-

form a rx ryr

.

Theorem 11 may also be applied to quadratic forms/ = As we saw in Section 1.7, / is the one-rowed square matrix

results of .

,

oj n ).

product

/

(44)

= x'Ax =

u-i symmetric matrix A. We call the uniquely determined symmetric matrix A the matrix of f and its rank the rank of f. Now in Section 1.9 we defined the equivalence of any quadratic form / and any second quadratic

for a

form g = y'By. We may then use the notations developed above and see that / and g are equivalent if and only if A and B are congruent. For if our nonsingular linear mapping is represented by the matrix equation x = P'u, then x' = u'P is a consequence, and/ = u'(PAP')u,J and g are equivalent if and only if B = PAP'. Thus Theorem 11 states that every quadratic form of rank r is equivalent to

ap*

(45)

The form

+

.

.

.

+ a x* r

.

(45) is of course to be regarded as a

ar

matrix diag

{ai,

.

form

.

x r with nonsingular matrix diag

in XL,

.

.

,

.

.

,

,

0,

.

.

.

,

0}.

However,

form

it

{ai,

x n with be regarded as a a r j. We shall

in xi,

may .

.

.

,

.

.

.

,

EQUIVALENCE OF MATRICES AND OF FORMS

55

a quadratic form / = x'Ax in xi, x n with nonsingular matrix A a nonsingular form, and we have shown that every quadratic form of rank r in n variables may be written as a nonsingular form in r variables whose matrix call

is

.

.

.

,

a diagonal matrix.

EXERCISES What

1.

is

A

the symmetric matrix

+ 2xiX 3x x + x\ 2xix 8x3X4 + x\ - 3x^2 + 2xiX - 3xJ x\

a) 3x1 6) c)

of the following quadratic forms?

+

0:1X2

3

4

2

-

2

4

Find a nonsingular matrix P with rational elements for each of the following A such that PAP' is a diagonal matrix. Determine P by writing A =

2.

matrices

IAI' and by applying cogredient elementary transformations.

2 e)

3

7

6

00-2-3

6

15

,

I

2

'-3-41 1

~5

1

-"0023 -l

-2 -1 -3 -1 -3 0\

-

-4 -5

-

5\

1

1

1

14/

/

,J

*>

1

3

3

2

1

2

21-1

1

1

\-l -1

-

1

O/

Write the symmetric bilinear forms whose matrices are those of (a), (6), (c), Ex. 2 and use the cogredient linear mappings obtained from that exercise to obtain equivalent forms with diagonal matrices. 3.

and

(d) of

4.

Apply the process

5.

Which

of the matrices of

bers as elements of 6.

linear

of

of Ex. 3 to (e), (/), (g),

and

(h) of

Ex. 2 are congruent

if

Ex. 2 for quadratic forms.

we

allow any complex

num-

Pf

= xf x\ are not equivalent under that the forms / = xf x\ and g the possible signs of values with Hint: real coefficients. Consider mappings

Show

/ and

of g.

+

INTRODUCTION TO ALGEBRAIC THEORIES

56

Nonmodular fields. In our discussion of the congruence and the equivalence of two matrices A and B the elements of the transformation matrices P and Q have thus far always been rational functions, with rational coefficients, of the elements of A and B. While we have mentioned this fact before, it has not, until now, been necessary to emphasize it. But the reader will observe that we have not, as yet, given conditions that two symmetric matrices be congruent, and our reason is that it is not possible to do so without some statement as to the nature of the quantities which we allow 12.

as elements of the transformation matrices P. algebraic concept which is one of the subject the concept of a field.

A

We

shall thus introduce

most fundamental concepts

an

of our

complex numbers is a set F of at least two distinct complex and a/c are in F for every such that a + &, ab, a fc, fields in of such F. c 7* are, Examples then, the set of all real numa, 6, of all the set of all rational functions and the set complex numbers, bers, with rational coefficients of any fixed complex number c. field of

numbers

If

F

is

a,

.

fe,

any

.

.

,

field of

K

= F(x) of all rational complex numbers, the set F is a mathematical system having prop-

functions in x with coefficients in

with respect to rational operations, just like those of F. Now it is true that even if one were interested only in the study of matrices whose

erties,

elements are ordinary complex numbers there would be a stage of this study where one would be forced to consider also matrices whose elements are rational functions of x.

Thus we

shall find it desirable to define the concept

K

of a field in such a general way as to include systems like the field defined shall do so and shall assume henceforth that what we called con-

above.

We

stants in Chapter

The

I and scalars

thereafter are elements of

we have already mentioned

fields

all

a fixed field F.

contain the complex number

unity and are closed with respect to rational operations. But it is clearly possible to obtain every rational number by the application to unity of a finite number of rational operations. Thus all our fields contain the field of all rational called

called nonmodular fields. The fields be defined in Chapter VI. We now make the fol-

numbers and are what are

modular fields

lowing brief DEFINITION.

will

A

set of elements F is said to form a nonmodular field if F contains the set of all rational numbers and is closed with respect to rational operations such that the following properties hold: I.

II.

III.

+ b) + c = a + (b + c) a(b + c) = ab + ac ab = ba a + b = b + a (a

for every a, b, c of F.

,

;

,

(ab)c

=

a(bc)

;

EQUIVALENCE OF MATRICES AND OF FORMS The difference a

F

tion x in

57

a solu-

6 is always defined in elementary algebra to be

of the equation

+b=

x

(46)

and the quotient a/6 to be a solution y yb

(47)

a

F of the equation*

in

=

a

,

.

Thus our hypothesis that F is closed with respect to rational operations should be interpreted to mean that any two elements a and b of F determine b and a unique product ab in F such that (46) has a a unique sum a in F and solution (47) has a solution in F if b j 0. In the author's Modern Higher Algebra it is shown that the solutions of (46) and (47) are unique.

+

In fact,

be concluded that the rational numbers

may

it

and

have the

1

properties

a

(48)

=

+

=

al

a

aO

,

=

0,

F and that there exists a unique solution x = aoix -}- a ~ and a unique solution y = 6" of yb = 1 for 6^0. Then the solutions = ab~ of (46) and (47) are uniquely determined by z = a + ( b), y

for every a of

1

l

.

We

also see that the rational

1=0, and a

1

a,

(

= a)

thus

1 (

6)

(

1

+

number

=

l)a

a

=

=

0,

a

+

=

ab for every a and b of a

a.

Hence

a

1

defined so that

1 is

l)a = also true that

whereas a.

It is

field

(

1

+

+ +

1)

(

1

a

(a) =

F.

EXERCISES 1. Let a, 6, and c range over the set of all rational numbers and F consist of all matrices of the following types. Prove that F is a field. (Use the definition of addition of matrices in (52).)

a

2.

Show

N

/a

^(b

that

-2b\

a)

if a, 6, c,

'~

'

r

"-

/a

x

b

.,

b

and d range over all rational numbers and i 2 form a quasi-field which is not a

set of all matrices of the following kind

/a

+ bi

\c

di

3(c

=

l,

the

field.

-)

a

Note that in view of III the property II implies that (b c)a = ba ca, and the existence of a solution of (46) is equivalent to that of b x = a, of (47) to that of by = a. But there are mathematical systems called quasi-fMs in which the law ab = ba *

+

+

+

does not hold, and for these systems the properties just mentioned must be additional assumptions.

made

as

INTRODUCTION TO ALGEBRAIC THEORIES

58

13. Summary of results. The theory completed thus far on polynomials with constant coefficients and matrices with scalar elements may now be clarified by restating our principal results in terms of the concept of a field.

We

observe

first

that

if

and

f(x)

g(x) are nonzero polynomials in x with

F then they have a greatest common divisor d(x) with and d(x) = a(x)f(x) + b(x)g(x) for polynomials a(x), b(x)

coefficients in a field coefficients in F,

with coefficients in F.

We next assume that A and B are two m by n matrices with elements in F and say that A and B are equivalent in F if there exist nonsingular matrices P and Q with elements in F such that PAQ = B. Then A and B a

field

are equivalent in

F if and only if they have the same rank.

Moreover, corre-

spondingly, two bilinear forms with coefficients in F are equivalent in F if and only if they have the same rank. Since the rank of a matrix (and of a

corresponding bilinear form) is defined without reference to the nature of the field F containing its elements, the particular F chosen to contain the

elements of the matrices

is

relatively

unimportant for the theory.

A and B are square matrices with elements in a field F, then we call A and B congruent in F if there exists a nonsingular matrix P with elements in F such that PAP = B. Similarly, we say that the bilinear forms x'Ay and x'By are equivalent in F under cogredient transformations* if A and B are congruent in F. When A = -A the matrix A is skew, and every matrix B congruent in F to A is skew, two skew matrices with elements in F are congruent in F if and only if they have the same rank. Hence, the precise nature of F is again unimportant. Let A = A' be a symmetric matrix with elements in F so that any matrix B congruent in F to A also is a symmetric matrix with elements in F. If

f

1

Then two corresponding quadratic forms x'Ax and x Bx f

are equivalent in

and only if A and B are congruent in F. Moreover, we have shown that every symmetric matrix of rank r and elements in F is congruent in F to a diagonal matrix diag (a a a r 0, in F and 0} with a* ^ that correspondingly every quadratic form x'Ax is equivalent in F to

F

if

,

.

.

.

,

,

.

.

.

,

The problem

of finding necessary and sufficient conditions for two quadforms with coefficients in a field F to be equivalent in F is one involving the nature of F in a fundamental way, and no simple solution of this problem exists for F an arbitrary field. In fact, we can obtain results only ratic

after rather complete specialization of F,

vary as *

F

we change our assumptions on

We leave

and these

results

may

be seen to

F.

to the reader the explicit formulation of the definitions of equivalence in linear

two forms, of two bilinear forms, and of two bilinear forms under cogredient mappings, where all the forms considered have elements in F. of

EQUIVALENCE OF MATRICES AND OF FORMS

59

The simplest Theorem 12.

conditions are those given in Let F be a field with the property that for every a of F there exists a quantity b such that b 2 = a. Then two symmetric matrices with eleare congruent in F if and only if they have the same rank. = diag ^{ai, = A' of rank r is congruent to ar , 0, For every , = a 6? for in F. for and a, Then if = diag {&rS 7* 6< , 0} >

ments in

F

A

A

.

.

67

.

^

.

PA

1 ,

0,

.

.

.

,

0},

P'

F

also congruent in

=

.

-

B=

B' has rank r, then 5 is 0} and hence to A. The converse follows

diag [I r , 0}. If also

to diag {/ r

.

P

,

from Theorem 2.2. We then have the obvious consequences.

COROLLARY

I.

Two symmetric

num-

matrices whose elements are complex

bers are congruent in the field of all complex the same rank.

numbers

if

and only

if they

have

COROLLARY II. Let F be the field of either Theorem 12 or CoroUary I. Then two quadratic forms with coefficients in F are equivalent in F if and only if they have the same rank. Hence every such form of rank r is equivalent in

F

to

(49)

x?

+

.

.

.

+ x?

.

There is one other result on symmetric matrices which will be seen to have evident interest when we proof involves the computation of the product of two matrices

14. Addition of matrices.

over an arbitrary state

it.

Its

field

which have been partitioned into two-rowed square matrices whose elements are rectangular matrices. If these matrices were one-rowed square matrices, that is to say in F, we should have the formula

But

it is

also true that

the partitioning of any

if

A

B is

and

carried out so

that the products in (51) have meaning and if we define the sum of two matrices appropriately, then (51) will still hold. Thus (51) will have major

importance as a formula for representing matrix computations. m and j We now let A = (ay) and B = (6
.

.

.

(52)

,

n, so that

A

and

B

are

S = A

m by n matrices.

+B =

(ay)

SH

,

(i

=

Then we

= an 1,

.

.

.

.

,

=

1,

define

+ &/ .

,m;j =

1,

.

.

.

,n)

.

INTRODUCTION TO ALGEBRAIC THEORIES

60

We have thus defined addition for any two matrices of the same shape such A + B is the matrix whose elements are the sums of correspondingly placed elements in A and B.

that

The elements If

C =

(bij

of our matrices are in a field F,

+ dj).

also

A+B = B + A,

(53)

We observe also that A + (~1-A) = 0. Now

C =

let

(cjk)

6,-,-)

(A+B) + C = A +

m

the

is

if

by n

(B

+

zero matrix, then

C)

.

A+

=

A,

be any n by q matrix. Then

(A

(54)

For

+ by = 6/ + a/. + c*/ = an + (a
and a^

an m by n matrix, we have Hence we have the properties

(dj) is

+ B)C = AC + BC

.

this equation is clearly a consequence of the corresponding property

of F, that

is,

of

(an

(55)

+

= a^k

&
+ bi,Cjk

We

have thug seen that addition of matrices has the properties (53) alfor addition of the elements of our matrices and that the assumed ways law (54), which we call the distributive law for matrix addition and multiplication, also holds. Clearly

D

if

+ B) = DA + DB

D(A

(56)

Observe, however, that if n rices, then A B\ and \A |

A

and

DA

is

defined, then

we have

similarly

if

a matrix such that

is

B are

+

\

equal, then \A\

>

and

1

A

B

and

.

are n-rowed square mat-

+ \B\ are usually not equal. For example, + \B\ = 2|A| while |A + B\ = |2A| =

Let us now apply our definitions to derive (51). We let A = (a;/) be an mbyn matrix, B = (&,-*) be an n by q matrix, and A\ be an s by t matrix, t. Then so that AI = (a*/) but now with i = 1, s and j = 1, .

.

.

,

.

.

.

,

(51) has meaning only if B\ has t rows, and we thus assume that Bi is a matrix of t rows and g columns. Our partitioning is now completely det columns, AS has m s termined and necessarily A* has s rows and n

rows and

and

q

t

columns,

g columns,

A B

m

4

has

8

has n

t columns, #2 has rows* and n rows and g columns, J5 4 has n

s t

t t

rows rows

EQUIVALENCE OF MATRICES AND OF FORMS and

The element in the ith row and

g columns.

q

fcth

61

column of AB

may

clearly be expressed as

(i

But

this equation is equivalent to the

A = (A D2 )

(57)

where we define Di,

Di

(58)

=

.

.

g

.

,

+

and

s 1,

.

.

.

Z>2,

s ,

may

+

1,

JE?i,

2

1,

.

.

.

=

k

ro;

,

1,

.

.

.

,

q)

matrix equation given by

(^}

AB =

,

DJE,

+ Drf*

,

#2 by

D =

,

Moreover, we

B=

,

=

2 ,

Ei

-

(fit,

B.)

E = 2

,

(B,,

B

4)

obtain (51) from (57) by simply using the ranges 1, 2, for i separately, as well as 1, 2, g and

.

.

.

,

m

.

q for j separately. In matrix language

.

we have used

.

,

(58)

and

computed

as the result of partition of matrices of matrices in (59) to give (51).

and then have used

(57)

and addition

We shall now apply the process above to prove the following theorem on symmetric matrices mentioned above. Theorem 13. Let Ai and BI be r-rowed nonsingular symmetric matrices with elements in F, and A and B be the corresponding n-rowed symmetric matrices

<> of rank

Ho'S). r.

Then

A

and

B

Ho'

are congruent in

F

if

and only

if

AI and BI are

congruent in F.

For if AI and BI are congruent in F there exists a nonsingular matrix Pi such that PiAiP( = BI. Then P = diag {Pi, I n - r } is nonsingular, and com-

INTRODUCTION TO ALGEBRAIC THEORIES

62

putation by the use of (51) gives PAP' a nonsingular matrix P we may write I

Pi

\p*

where Pi

=

B. Conversely,

p *}

p*)'

an r-rowed square matrix, and we

is

p *\

shall

have

PA p,.p(Af( Af't \_(P l A

l

P(

J-^A^

~MO

P'J'

P'*

PAP = B for 7

if

P^ PtA

must be nonsingular since \Bi\ = and A l are congruent in F. A! l |PJ |PJ| The result above thus states that, if / and g are quadratic forms with coefficients in F so that / and g are equivalent only if they have the same rank r, then / may be written as a nonsingular form / in r variables, g may be written as a nonsingular form g Q in r variables, and finally the original forms / and g are equivalent in F if and only if / and g Q are equivalent in F.

B

But then |

PA

1

1

1

P(

5^ 0.

|

and Hence

J

P B

l

ORAL EXERCISES 1.

Computed

+ Bif

a)

A

B= 2.

Verify that (A

+ B)' =

A'

+

B' for any

m by n matrices A

and B.

Show that every n-rowed square matrix A is expressible uniquely as the sum C with B = B', symmetric matrix B and a skew matrix C. Hint: Put A == B (7 = 0', compute A', and solve. 3.

+

of a

Real quadratic forms. We shall close our study of symmetric matand hence of quadratic forms with coefficients in F as well by consider= x'Ax ing the case where F is the field of all real numbers. Let then / = a x xf + have rank r so that we may take / + arxl for real a^ ^ 0. We now call the number of positive a the index i of / and prove 15.

rices

Theorem

14.

Two

the field of all real

same index.

.

quadratic forms with real coefficients are equivalent in if and only if they have both the same rank and the

numbers

EQUIVALENCE OF MATRICES AND OF FORMS

63

*

For proof we observe, first, that by Section 14 there is no loss of generality we assume that/ = x'Ax where A is a nonsingular diagonal matrix, that = n. Moreover, there is clearly no loss of generality if we take A = is, r d d r for positive d. Then there exist real diag {di, dt+i,

if

.

.

.

1

{PT with

P7

>

>

t

1

1

.

}

and

1

(61)

r

t

+

(x\

.

.

elements

+

.

-

*?)

1.

Thus, /

is

.

.

.

,

.

.

,

F

equivalent in

to

+ ...+*).

(* +1

it is equivalent in F to (61) and = n and index s so that g is equiva-

the same rank and index as/,

Now, if 0has

hence to /. Conversely,

F

\

,

such that p* = diy and if P is the nonsingular matrix diag then PAP is the matrix diag {1, 1, -1, -1}

elements

lent in

.

.

.

t,

,

^

numbers p

have rank r

let g

to

(*?+...+

(62)

- (J +l +

*2)

.

.

.

+3

.

propose to show that s = t. There is clearly no loss of generality if we assume that s ^ t and show that if s > t we arrive at a contradiction.

We

Hence, let s > t. Our hypothesis that the form / defined by (61) and the form g defined by (62) are equivalent in the real field implies that there exist real numbers d^ such that if we substitute the linear forms

in .

.

/ .

= f(x

.

l9

+ yj).

.

.

Put

,

dnyi

=

=

x2

resulting

.

t

.

.

These are

linear

t

numbers

The remaining n numbers

certain 0,

(ttf +1

.

.

+

.

,

.

0,

.

+d

.

.

in

=

=

xt

and

+

.

.

.

.

,

y, +1

+ =

.

.

.

.

.

.

=

1,

.

.

+ yj) =

n)

,

(yj +1

=

yn

.

,

+

in (63)

v9

not

all

zero

(t

in s

and

>

t

=

1,

.

.

.

,

*)

.

unknowns, and there

satisfying these equations.

equations of (63) then determine the values of x, as = t = 1, n, and we have the result h

t

+

Uj for j

w l+1

(y\

(i

+ cky. =

.

.

homogeneous equations v\,

yn

equations

AMI

(64)

exist real

+

x n), we obtain as a result

Xi

and consider the

/(O,

=

Xi

(63)

,

.

+ ul) ^

.

.

0,

,

tO =

.

t>f

.

.

+

,

.

.

.

+

0J

>

0.

But

clearly

ft

=

a contradiction.

We have now shown that two quadratic forms with real coefficients and the same rank are equivalent in the field of all complex numbers but that, their indices are distinct, they are inequivalent in the field of all real

if

numbers. We shall next study in some detail the important special case t = r of our discussion.

INTRODUCTION TO ALGEBRAIC THEORIES

64

A

A

symmetric matrix

are called semidefinite of rank r

A

if

is

.

.

Thus /

is

semidefinite

+ xj). We call A and/ definite

.

x'Ax

a matrix

\ <>

in F.

F to

congruent in

air

for a 5^

=

and the corresponding quadratic form /

;

=

if r

+

equivalent to a form a(x\

if it is

n, that

A

is,

is

both semidefinite

and nonsingular.

F is

If

the field of

positive or take a tive

if

and only

numbers, we may take a = 1 and call A and / and call A and / negative. Then A and / are nega-

all real

=

1

A

if

and

/ are

Thus we may and

positive.

shall re-

our attention to positive symmetric matrices and positive quadratic forms without loss of generality. If f(xi, x n ) is any real quadratic form, we have seen that there exists a nonsingular transformation (63) with real d^ such that / = y\ strict

.

.

.

,

+

+

we put

if

y t

= d

and only if the

=

t

<

dr =

d,

.

=

0, yi+i

.

>

iff

is

.

+

,

Ci,

.

.

.

are

cn

,

numbers and

real

any

l,/(ci,

all zero.

.

.

.

,

cn )

t

=

Now if < r, we have/ < < 0. Conversely, if /(ci,

y\

for y\

t

.

+

.

.

.

+

/(ci,

j/J,

.

.

.

,

.

.

,

=

<

cn)

...

then

0,

= d\ + = and y/

cn)

.

=

+

.

.

= 1 and all other have n, then we put y r+ \ c n not all zero such that /(ci, c n ) = 0. Hence, if /(ci, for all real c* not all zero, the form/ is positive definite. Conversely, If

0.

cn )

are

c

For otherwise / =

r.

If

in (63), there exist unique solutions y, = dj of the resultof linear equations, and the dj may readily be seen to be all zero

Xi

ing system if

++!/?)

(y\+i

!/f

r

<

.

=

.

.

+

.

,

+

=

.

cn) d\ y\ 2/ n /(ci, positive definite, we have / for all dj not all zero and hence for all c not all zero. d% .

.

.

.

.

.

,

,

.

,

+

We

>

have proved

Theorem

A

x n ) is positive semidefinite for all real Ci, is positive definite if and only . cn ) > , for all real ci not all zero. if f (ci, As a consequence of this result we shall prove

if

and only .

15.

if f (ci,

real quadratic form f(xi,

.

.

.

cn )

,

.

.

.

,

^

.

Theorem

16.

Every principal submatrix of a positive semidefinite matrix submatrix of a positive definite matrix

is positive semidefinite, every principal is positive definite.

For a principal submatrix B of a symmetric matrix A is defined as any im th rows m-rowed symmetric submatrix whose rows are in the tith, of A and whose corresponding columns are in the corresponding columns of A. Put XQ = (x^, z m ) so that g = x Q Bx Q is the quadratic form with B as matrix, and we obtain g from / by putting Xj = in / for j 9^ i*. for all values of the x ik and for all z = a, then g ^ Clearly, if / <> .

.

.

,

f

.

.

.

,

,

EQUIVALENCE OF MATRICES AND OF FORMS hence

B

A

is positive definite positive semidefinite by Theorem 15. If = for x not all and hence for the then singular, zero, / = g ik

is

and B is Xj above

65

all

zero

and

for the x ik not all zero, a contradiction.

The converse of Theorem 16 is also true, and we refer the reader to the author's Modern Higher Algebra for its proof. We shall use the result just obtained to prove

Theorem Then AA' For we

is

m

A be an by n matrix of rank r and with real elements. a positive semidefinite real symmetric matrix of rank r.

17. Let

may

write

A-- pP (I' A (o

where

P

o)

>

00' QQ

Q are nonsingular matrices of m and n rows, respectively. a positive definite symmetric matrix, and we partition QQ' so an r-rowed principal submatrix of QQ'. By Theorem 16 the ma-

and

Then QQ' that Qi

<>\o Q

is

is

trix Qi is positive definite,

is

congruent to the positive semidefinite matrix

C

of rank r and hence has

the property of our theorem.

EXERCISE What tion 11?

are the ranks

and

indices of the real

symmetric matrices of Ex.

2,

Sec-

CHAPTER

IV

LINEAR SPACES 1.

Linear spaces over a

The

field.

U =

(1)

(d,

Vn

set .

.

.

of all sequences

Cn)

,

may be thought of as a geometric n-dimensional space. We assume the laws of combination of such sequences of Section 1.8 and call u a point or vector, of Vn We suppose also that the quantities Ci are in a fixed field F and call c the ith coordinate of u, the quantities Ci, c n the coordinates of u. The entire set V n will then be called the n-dimensional linear space .

.

.

.

,

over F.

The

(u

(2)

a(bu)

(3)

=

for all a, 6 in

by

O.is

+

+w=

v)

(o6)w

(a

,

+

u

be easily seen to imply that

(v

+ w)

+ V)u =

+ bu

aw

+v=v+u

u

,

+

a(w

,

= aw

v)

+ aw

F and all vectors w, v, w of Fn The vector which we designate .

that vector

all

u =

(

Ci,

.

.

+ = .

w =

(5)

Note that the

first

whose coordinates are

of

w

(4)

where

F may

properties of a field

1

,

of (5)

is

u+(u)

u,

cn ).

,

zero,

=

and we have

Q,

Then u = u

u

,

the quantity

of F,

=

1

u

.

and the second zero

is

the

We

shall use the properties just noted somewhat later in an abstract definition of the mathematical concept of linear space, and we leave

zero vector.

the verification of the properties

(2), (3), (4),

and

(5) of

Vn to the reader.

Linear subspaces. A subset L of V n is called a linear subspace of V n if bv is in L for every a and b of F, every u and v of L. Then it is clear that L contains all linear combinations 2.

au

+

u =

(6)

for

a in F, and w^ in L.

aiUi

+

.

.

.

+ amum

,

LINEAR SPACES

67

We observe that the set of all linear combinations

m

ber

of given vectors, ui, to this definition. If now

.

.

um

,

any

finite

num-

a linear subspace L of Vn according we shall say that u\, Um

is

so defined, shall write

L and

span the space

.

L

(6) of

is

.

.

.

,

L-lm,...,!!*}.

(7)

It is clear that, if e,- is the vector whose jth coordinate is unity and whose other coordinates are zero, then ei, e n span Vn The space spanned by the zero vector consists of the zero vector alone .

and may be

.

.

.

,

L =

and designated by

called the zero space

{0}.

In what

fol-

our attention to the nonzero subspaces L of Vn and, for the time being, we shall indicate, when we call L a linear space over F that L is a linear subspace over F of some V n over F. lows

we

shall restrict

,

}

Linear independence. Our definition of a linear space L which is a V n implies that every subspace L contains the zero vector. If Oum. Hence the zero vector of {MI, u^, then = Oui

3.

subspace of

L = L is expressible .

ui,

.

.

.

,

.

.

+

,

(6) in at least this one way. u m are linearly independent in F or that ui, .

Vn over F), if

linearly independent vectors (of (6).

.

.

.

ai

shall say that

shall say that

um are a

,

set of

no other such expres-

is

and only

For

is unique.

cial case

= .

.

aiUi

+

if the

u =

+

(am

.

.

.

+

.

,

.

.

.

,

u

expression of every

L =

of

{ui,

this property clearly implies linear 0.

.

.

if ui,

Conversely, am um = biui

+

+

b m )um a<

DEFINITION.

,

LetL-

&< {ui,

pendent in F. Then we shall this

.

they are linearly dependent in F. Um are now seen to be linearly independent in

A set of vectors Ui,

u

.

.

we if

We .

,

+

is

there

.

um are linearly independent if it Thus, Ui, if and only if true that a linear combination ami (J^um = = = a 2 = ... am 0. If Ui, Um are not linearly independent in F, form

in the

sion of

.

+

.

.

.

form

in the

= .

.

.

,

.

.

.

.

um

call Ui,

.

.

.

u m in }

,

the

form

F

(6)

independence as the spe-

um are linearly independent and + 6mum then = (ai - bi)ui + ,

We now make the

& as desired.

over

}

.

,

=

a

0,

.

.

.

.

F andui,

u m a basis

,

.

.

.

,

over

um

F

be linearly inde-

of

L and indicate

by writing

(8)

L =

UiF

+

Vn = e\F + L spanned by

.

.

.

+

+ u mF

.

eJF. But we may actually show a finite number of vectors of Vn has a that every subspace basis in the above sense. Observe, first, that the definition of linear indeIt is evident that

.

.

.

INTRODUCTION TO ALGEBRAIC THEORIES

68

m=

=

=

and thus that u 5^ 0. ur be linearly independent vectors of Vn and u ^ be urj u are linearly independent in F or another vector. Then either u\ + arur + a Qu = for a* not all zero. If a - 0, then aiUi + a>iUi + = ar = 0, a contradiction. But then + OrUr = 0, from which a\ = l l u r }. It follows that, u = ( a Oi)ui + + ( a^ an )ur is in [u^ if ui, ... Mm are any m distinct nonzero vectors, we may choose some largest number r of vectors in this set which are linearly independent in F and we will then have the property that all remaining vectors in the set are pendence in case

Then

let ui,

.

.

.

that au

1 is

.

.

a

,

.

}

.

if

only

.

.

,

.

.

.

.

.

.

.

.

.

.

.

.

,

|

F of these r. We state this result as

linear combinations with coefficients in

m

1. Let L be spanned by distinct nonzero vectors Ui, has a basis consisting of certain r of these vectors, 1 < r < m.

Theorem

L

Then

.

.

.

,

um

.

EXERCISES Determine which of the following

1.

subspace they span. Hint: It u\

and

=

=

6)

Ul

=

c)

tii

=

*

d) u,

=

ui

=

tii

=

)

/)

2.

of the

To

see

if ui,

dependent we

HZ are linearly

u^

(1, 3,

-3)

(3, 1, 2)

,

(-1, -1, (1,

1)

,

-2, -1,

(1, 1, 1,

(1,

,

-1,

3)

-1) 1,

,

,

-1)

w2

=

u,

=

u,

=

u,

=

u,

=

u2 =

,

(2, 5,

-2)

,

u*

= =

(4, 1, 3)

,

m

(3, 2, 1)

,

7/3

(2,

-1,

(2, 2, 2,

=

6)

,

u =

-2)

,

u3 =

1,

(1, 1, 1, 0)

,

3

=

u,

(1, 1, 6)

(-1, -1,

0)

(7, 3, 9)

-1, -3,

(0,

(1, 2, 3, 4)

-1,

(5,

5,

1)

-3)

that the space L = {MI, w2 , ^3} spanned by the following sets of vectors Hint: In every case one of the vectors, say ui, has first coordinate not zero, x 2 ui = (0, 6 2 c 2 ), u 3 contains u* XsUi = (0, 63, c*). Some linear combina-

Show

is 7s.

and

form a basis

+ yui and solve for x and y.

xu\

a) MI

sets of three vectors

easy to see whether some two of the vectors, say

Ui are linearly independent.

write uz

>

is

L

,

two quantities has the form (0, 0, d) and L contains e 3 = (0, 0, 1). = Fs. easy to show then that L contains e 2 = (0, 1, 0) and e\ = (1, 0, 0), L

tion of these is

a) ui

3.

=

6)

m-

c)

I*

-

(1,

-2,

3)

,

u2 =

(0, 1, 8)

t*2

-

,

(0, 3, 2)

u,

=

,

(2, 3, 1)

(1,

-3,

(0, 2, 1)

u3 = (-1,

,

6) ,

,

u*

=

11,

(1,

3, 2)

-1, 23)

(1, 5, 4)

Determine whether or not the spaces spanned by the following

wi, Ut coincide with those

spanned by

the corresponding

It

vi,

v2

.

sets of vectors

Hint:

If

Li

=

LINEAR SPACES =

Lu

{tfi,

+ #2^2, a)

t>2

02}

=

there

,

must

exist solutions xi,

+ #4^2 such

^3^1

m=(3, -1,2,1),

U!

=

(1,2,

=

u,

(1, 4, 6, 1)

c)

in

=

(1,

-1,

2,

v,

d)

2,

-3)

=

(3,

-3,

Vl

/)

6,

=

Wl

(1, 0, 1, in

(3,

-2)

=

1, 1)

,

-2,

4,

=

0.

4,

(6, 0, 4, 1)

-6)

n=

,

-9)

(4,

-4,

8,

(2,

-2,

0, 6)

,

-1,1,0),

(2,

t*=(-l, -1, -1,1)

,

=

11,

^

#2X3

(7, 2, 10, 3)

(2, 1, 0, 1)

=

u,

-3,

,

,

=

*=

-2, 1,2),

,

(2,

-

,

-2,

(2,

-9)

ti,

=(1, -2,0,1),

=

x3 ou of the equations

(1,2,3,4),

=

u,

i-(l, -1,0,3),

in

t> 2

-13, -4),

,

i(-l, e)

=

u2

-1,2), in=(l,

a? 2 ,

that the determinant x\x

tn=(7, -11, -6, 1), 6)

69

(0,1,

-8)

-1,2),

*=

,

(1, 1, 0, 0)

4. The row and column spaces of a matrix* We shall obtain the principal theorems on the elementary properties of linear spaces by connecting this theory with certain properties of matrices which we have already derived.

Let us consider a set of

m vectors,

of

=

Ui

(9)

(aa,

.

.

.

,

a in )

(i

=

.

1,

.

.

,

rn)

,

V n over F. Then we may regard w as being the tth row of the correspondum as being m by n matrix A = (a
ing

y

.

.

.

,

]

row space of A. Thus every m by n matrix defines a linear subspace of V nj every subspace of V n spanned by m vectors defines a corresponding m by n matrix. If P = (pki) is any q by m matrix, the product PA is a q by n matrix.

what we

shall call the

The jth coordinate

of the vector

Wk =

(10) is pkiQit

umn

of

+

.

.

.

+ pkmOmh

PA. Hence

the

PklUl

that

Wi

is,

row of

+

.

.

.

+ fcth row and jth colcombination of the rows

the element in the

PA

is that linear

A whose coefficients form the kth row of P. We have now shown that every row of PA is in the row space of A. It follows that the row space of PA is contained in that of A. If P is nonsingu-

of

INTRODUCTION TO ALGEBRAIC THEORIES

70

then the result just derived implies that the row space of A = P~ l (PA) is contained in the row space of PA and therefore that these two linear spaces are the same. Thus we have lar,

of

P

LEMMA

1.

Let

PA

A

coincide.

and

an m-rowed nonsingular matrix. Then

be

the

row spates

we used the matrix product equivalent of Theorem 2.4, and we shall now state this

In the proof of Theorem 3.6 the elementary transformation theorem as the useful

LEMMA 2. Let Abeanmbyn matrix of rank r. Then there exist nonsingular matrices P and Q of m and n rows, respectively, such that

(\

PA =

(11)

AQ =

,

(H

0)

,

G and H have rank r, G is an r by n matrix, H is an m by r matrix. We use (11) and note that the rows of G differ from those of PA only in

where

zero rows.

Then the rows

of

G

By Lemma

span the row space of PA.

1

we have

LEMMA

We

3.

The row spaces

G

of

A

and

coincide.

shall use this result in the proof of

The r rows of G form a basis of the row space of A. Any r + 1 vectors of the row space of A are linearly dependent in F. v r Our definition of G For we may designate the rows of G by v\, implies that there is no loss of generality if we permute its rows in any de-

Theorem

2.

.

+

+

b rv r sired fashion. Thus, if b\v\ may assume for convenience that 61 9* 0. .

.

.

=

.

.

.

,

for bi in

F

not

The determinant

we

all zero,

of the r-rowed

square matrix

P = (%)

(12)

,

P,

=

.

(fc,

.

.

,

&,)

,

P = 2

(0, 7,-x)

clearly 61, and hence P is nonsingular. Then PG is r-rowed and of rank r. But this is impossible since biv\ + is the first row of PG. + b rv r Hence the rows of G are linearly independent in F, they span the row space of G and of A, they are a basis of the row space of A. r + 1, so + bkrvr for k = 1, Assume, now, that Wk = bkiVi + = that Wk are any r + 1 vectors of the row space L + vr F of A. v\F + Define B = (bki) and obtain Wk as the fcth row of the r + 1 by n matrix BG. By Theorem 3.6 the rank of BG is at most r, and by Lemma 2 there is

.

.

.

.

.

.

.

+

1,

such that the

.

.

.

+ l)-rowed matrix D = (d for g, k = 1, + (r l)st row of D(BG) is the zero vector. But then

exists a nonsingular (r

r

.

,

.

g k)

.

.

.

,

LINEAR SPACES dr+i, iWi

+

matrix

lar

.

.

D

.

+ d +i, r+iWr+i r

and cannot

all

=

71

the dr +i tk form a be zero, the vectors 101,

row

0,

.

.

.

,

of the nonsinguwr+i are linearly

dependent in F. This proves Theorem 2. We now apply Theorem 1 to obtain Theorem 3. The matrix G of Lemma 2 may be taken to be a submatrix of A. The integer r of Theorem 1 is in fact the rank of the by n matrix whose ith row is Ui. For let A be an m by n matrix whose ith row is Ui and let r be the integer

m

Theorem 1, the rank of A be s. After a permutation of the rows of A, if u r are a basis of the row space of A. necessary, we may assume that ui, Then u k = b k \ui + + b kr u r for b ki in F, and k = r + 1, m. The

of

.

matrix

P

given

,

.

.

.

.

,

by

D-

(B nonsingular, and

is

.

.

.

.

it is

clear that

if

G =

(14)

Ur then

PA

is

given by (11). It follows that s is the rank of G, 2 to obtain a nonsingular r-rowed matrix

we apply Lemma that the rth

drr u r

row

of

DG =

0,

the rth row of

=

D

s

<

r.

D=

not zero, dr iUi

is

<

If s

such

(d gk )

+

.

.

r

+

.

u r are linearly indecontrary to our hypothesis that w 1; pendent. This completes our proof. We may now obtain the principal result on linear subspaces of F. Theorem 4. Every linear subspace L over F of V n over F has a basis. Any two bases of L have the same number r < n of vectorsj and we shall call r the .

.

.

,

order of

For

L

over F.

Vn =

+

+

+

e n F, and by Theorem 2 any n 1 vectors of eiF are linearly dependent in F. Thus any linear subspace L over F of n contains at most n linearly independent vectors. It follows that there .

.

.

Vn

V

maximum number r < n of linearly independent vectors HI, ur in L, and that w, u\, u are linearly dependent in F for every M of L. u }, L = UiF + By the proof of Theorem 1 the vector u is in \Ui, + urF. But if also L = ViF + + v,F, then Theorem 2 implies that s < r and similarly that r < s, r = s is unique. exists

a

.

.

.

.

,

r

.

.

.

.

.

.

.

.

.

,

r

.

.

,

INTRODUCTION TO ALGEBRAIC THEORIES

72

In closing this section we note that the rows of the transpose A* of A by the columns of A and are, indeed, their transposes. Thus we shall call the row space of A' the column space of A. It is

are uniquely determined

Vm We

call the order of the row and column spaces and column ranks of A. By Theorem 3 the rank A and A have the same rank and we have proved The row and column ranks of a matrix are equal to its rank.

a linear subspace of

.

of A, respectively, the row of is its row rank. Also

A

Theorem 5.

f

EXERCISES 1.

Solve Ex.

1

and 2

of Section 3

by the use

of elementary transformations to

compute the rank of the matrices whose rows are the given vectors. 2.

Form the four-rowed matrices whose rows are the 3. Show thus that LI = [HI, i^} = L2 = {vi,

Section

vectors v2 ]

if

u\, u^, v\, v 2

and only

if

of Ex. 3,

the ranks

A are equal to the order of the subspace Li, that the rank of the matrices formed from the first two rows of each A.

of the corresponding matrices

3.

Find a basis

of the

row space

is,

of each of the following matrices, the basis to

consist actually of rows of the corresponding matrix.

2301

10 20

1-2 2-4

2-3-1

1

2-3-1

0-11

Let

A

3

04-12 212-2

1

-1001

4.

1

-2-1

11

4-7

c)

-2 -1 -1

12-1 35102 11 3-6-6 47036 3

1

230-1

5100 1234

1

7

4

-15 -16

be a rectangular matrix of the form

Mi Ui where A\

is

nonsingular.

Show

that then there exists a nonsingular matrix

P

such

that

PA Give also a simple form of Ai.

for P. Hint:

Mi

A,\

VO

A,)

Show

that the rows of A* are in the row space

LINEAR SPACES 5.

of

73

Let the matrix of Ex. 4 be either symmetric or skew. Show that the choice

P then implies that

Show 6.

also that,

if

the order of A\

is

the rank of A, the matrix ^5

=

0.

The concept of equivalence. In discussing the properties of mathemati-

cal systems such as fields

and

linear spaces over

F

it

becomes desirable

quite frequently to identify in some fashion those systems behaving exactly the same with respect to the given set of definitive properties under conshall call such systems equivalent and shall now proceed to sideration.

We

define this concept in terms of that of function. Let G and (?' be two systems and define a single-valued function to G'.

In elementary mathematics

the independent variable

ever, it

on

more convenient

is

G to G

and

f

G

f

it is

customary to

call

G

/ on

G

the range of

the range of the dependent variable. How/ is a function

in general situations to say that

or that / is a correspondence on

G to G'.

Then / is given by

g->g'=f(g)

(15)

(read g corresponds to g'} such that every element g of G determines a unique corresponding element g' of (?'. In elementary algebra and analysis the sys-

tems G and G' are usually taken to be the field of all real or all complex numbers and (15) is then given by a formula y = /Or). But the basic idea there is that given above of a correspondence (15) on G to (?'. This concept may be seen to be sufficiently general as to permit its extension in many directions.

Suppose now that

f

a correspondence such that every element g of G is the corresponding element f(g) of one and only one g of G. Then we call (15) a one-to-one correspondence on G to G'. It is clear that (15) then (15) is

r

defines a second one-to-one correspondence

M=

(16)

which

is

now on G

ence between

G

to G, and we may thus call (15) a one-to-one correspondand G' and indicate this by writing f

g+

(17)

Note, however, that,

and

0'-<7,

if

G and

>
same system, the functions (15) Thus we may let G be the field of all real

G' are the

(16) are, in general, distinct.

INTRODUCTION TO ALGEBRAIC THEORIES

74

numbers and (15) be the function x 2x, so that (16) is the function x \x. Of course, if G and G' are distinct it is not particularly important whether we use (15) or (16) to define our correspondence.

We

proceed to use the concept just given in constructing the fundamental definition of this section, that of equivalence. Let us consider two mathematical systems (?, G' of the same kind such as two fields or two linear spaces over a fixed field F. These systems consist of sets of elements #, A, closed with respect to certain operations. (Thus, for example, we might have g + h in G for every g and h in G and also g' + h' in G' for every g' and h' in G'.) We then call G and G' equivalent if there exists a one-to-one correspondence between them which is preserved under the operations of their definition. We now see that we have defined two fields F and F' to be equivalent if there exists a one-to-one correspondence (15) between them such that (g + h)' = g' + h', (gh)' = g'h' for every g and h of F. Let us then pass to the second case which we require for our further discussion of .

.

.

linear spaces.

Let F be a fixed field and V and au are unique elements of

consist of a set of elements such that

V

for every

u and

we shall call V a general linear space over F. and there is a one-to-one correspondence u <

If

v of

7

V and

u

+v

a of F. Then

a second* such space UQ between V and V such is

that (u

+

0)0

=u

<>

+

^o

=

(au)

,

au

V and V

V

for every u and v of and a of F, then we shall say that lent over F. have thus introduced two instances of

We

what

is

o

are equiva-

a very im-

portant concept in all algebra. The reader should observe that under our definition every mathematical system G is equivalent to itself and that if G is equivalent to a system G',

then G'

is

equivalent to G. Finally,

if

G'

is

equivalent to G", then

G

is

equivalent to G".

EXERCISES 1.

Verify the statement that the field of

cients of the

complex number

V2

is

all

rational functions with rational coeffi-

equivalent to the

field of all

matrices

'-CD for rational *

We

a and 6 under the correspondence

V

A

<

>

a

+

use the notation Vo instead of to avoid confusion in the consequent usage as well as for the transpose of u.

of u' for the arbitrary vector of

V

LINEAR SPACES 2.

75

Verify the statement that the field of complex numbers matrices

is

equivalent to the

field of

-b\ (a \b

a and

for real 3.

a)

6.

Verify the statement that the set of a field equivalent to F.

all

scalar matrices with elements in a field

F forms

4. Verify the statement that the mathematical system consisting of all two-rowed square matrices with elements in F and defined with respect to addition and multiplication is equivalent to the set of all matrices

fa n

ai 2

a

an

a,

a*

O22

021

under the correspondence indicated by the notation. 6.

Linear spaces of

We

finite order.

shall restrict all further

study of

V F

to be a linear spaces to linear spaces of order n over F. Then we define is equivalent over to linear space of order n over a given field F if n over F. Clearly, our definition implies that every two linear spaces of the

F

V

same order n over F are equivalent over F. Our definition also implies that, if V is a linear space of order n over F, then the properties (2), (3), (4), and (5) hold for every u, v, w, of V and a, b in F. Moreover, every quantity of V is uniquely expressible in the form (18)

Citfi

where the equivalence between CiVi

(19)

+

.

.

.

+

.

.

.

+

Cn t>n

V and V n is

+ Cn V n

<

>

,

given by

(ft,

.

.

.

,

Cn)

.

= ua and u v to be in V for every u, v of V and shown very easily that, if (2), (3), (4), and (5) hold be may and every u of V is uniquely expressible in the form (18) for d in F, then V is equivalent over F to V n However, we prefer instead to define V by its equivalence to Vn This preference then requires the (somewhat trivial)

+

Conversely, define au

a of F. Then

it

.

.

proof of

Theorem over

F

to

V

6.

Every linear subspace

L

of order r over

F

of

Vn is equivalent

r.

Thus we

term linear subspace L of order r over F by L is indeed what we have called a linear space of order r over F

justify the use of the

proving that

INTRODUCTION TO ALGEBRAIC THEORIES

76

contained in the space of

L =

uiF

+

.

.

.

Vn r

U =

(20)

for

For proof we merely observe that every vector

.

+ u F is uniquely expressible in the form

d

in F.

Thus u

in

L

+

CiUi

.

.

.

+ CrU

r

uniquely determines the

d

F and

in

conversely.

It follows that

w->(ci, ...,
(21)

V and V and it is trivial to verify L and V We have now seen that every linear space L of order n over F may be regarded as a linear subspace of a space M of order m over F for any m > n. Moreover, L = M if and only if m = n.

is

a one-to-one correspondence between

that

n,

it

defines

r

an equivalence of

r.

Theorem 3 should now be interpreted for arbitrary and we have a result which we state as Theorem 7. Let L = UiF + + unF and Vi, .

F for

there exist quantities a,- in Vi

and

the coefficient

matrix

=

.

.

.

.

,

vm

L

be in

so that

which

anUi

A=

.

linear spaces of order

+

(aij)

.

.

.

+a

in

un

,

Then

is defined.

the

number

of the

vk

which are linearly independent in F is the rank of the matrix A. Moreover, = n and A is nonsingular. v m form a basis of L over F if and only if Vi, .

.

.

m

,

EXERCISES 1.

finite

Verify the statement that the following sets of matrices are linear spaces of order over F and find a basis for each. a) b) c)

d) 2.

The set of all m by n matrices with elements in F. The set of all mbyn matrices whose elements not in the The set of all n-rowed scalar matrices. The set of all n-rowed diagonal matrices.

first

Find bases for the following linear spaces of polynomials with x of degree at most three.

row are

zero.

coefficients in F.

a) All polynomials in 6)

All polynomials in independent variables x

c)

(in x and y together). All polynomials in x =

x and

y.

d) All polynomials in e)

t*

+

t

and y

=

J

8

and y and degree at most two

+

2

and degree at most two

in

_ ^2, with

F the

field of all rational

numbers.

All polynomials in a primitive cube root of unity with rational numbers.

F

the

field of all

LINEAR SPACES

77

the field of all rational 1) with /) All polynomials in w = u(i = and i* = v? that 2. Hint: Prove are a basis. 1, w, i, 1,

F

+

numbers

m

The polynomials

g)

of (/)

but with

3. Let A = diag {1, 1, 2}. three-rowed diagonal matrices.

Show

4.

rices

Show

AB form

that 7, A, B,

numbers.

field of all real

that 7, A, A* form a basis of the set of

a basis of the set of

all

all

two-rowed square mat-

if

Show

5.

if

that,

A =

/O

0\

-1 (0

01,

\0 then

F the

A

A,

7,

2 ,

A

AB,

5,

I/

B AB A J5 2 form 2

2

2 ,

2

a basis of the set of

,

,

three-rowed

all

square matrices. vm } and L 2 = Addition of linear subspaces. If LI = (vi, w q ) are linear subspaces over F of a space L of order n over F, {wi, w q ] of L will be called the sum of vm w\, the subspace Lo = {wi, , 7.

.

.

.

.

.

L 2 and

Li and

.

.

only vector which

L 2 are

is

in

In this case the order of

then Lo

For

show

= v^

it is

v

if

only

,

=

.

.

.

clear that aiVi

+

L 2 Thus v ^ .

that the vectors

{Li,Li}

-

t\-

not form a basis of

.

.

L

is

the

sum

.

.

L 2 and in fact

and

2

.

.

.

.

.

.

Conversely,

L if

and

.

.

.

q

q

.

and Wj spanning .

.

of the orders of LI

.

implies that the a*

L

the zero vector, we shall say sum and write

of their

+ vmF, L = wiF + + w F, w F. + and +bw = + OmVm + Jwi + a\v\ + = + (bq)w is in both LI + amvm (-bi)wi + LI

.

.

.

L 2 is

+ L,

L!

= viF + v F m + + WiF +

if

that,

+

.

complementary subspaces Lo

shall

.

both LI and

(23)

and

.

,

,

Lo=

that LI and

we

.

be designated generally by

will

(22) If the

.

,

6,-

.

.

.

.

q

q

if

q

are not all zero

and therefore

are linearly dependent in F and do = 0, then the v> and w, necessarily t>

do form a basis of Lo, and Lo has order m + If LI and Lo are linear subspaces of L and

if

L

contains LI,

we may ask

INTRODUCTION TO ALGEBRAIC THEORIES

78

whether a linear subspace L 2 of L exists such that L = LI + L 2 The existence of such a space is clearly a corollary of Theorem 8. Let LI of order over F be a linear subspace of L of order n .

m

Then

over F.

there exists

L2

a linear subspace

of

L

L2

such that LI and

are

complementary subspaces of L.

The result above may be proved by the method we used to prove Theovm u\, u n in rem 1, where we apply this method to the set u let L = uiF + F. us a matrix + n However, give, instead, proof using i,

We put L = Vn

theory. vectors

vi,

matrix

Q

.

.

.

,

let

,

vm of LI.

nonsingular.

.

,

,

.

.

.

,

,

G be the mbyn matrix whose rows are the basal

GQ

such that the columns of

is

.

Then G has rank m, and there exists a nonsingular

GQ = where ft

.

Then

are a permutation of those of

(ft

ft)

(?,

,

the matrix

ft

is

nonsingular,

and

A =

AoQ""

1

is

obtained by permuting the columns of A$.

But then

A = nonsingular, the rows of A span V n and the rows of H span the space L 2 which we have been seeking. Moreover, it is clear that the rows of are certain of the vectors e which we defined in Section 2.

is

,

H

EXERCISES

m

1. Let LI be the row space of each of the by n matrices of Section 4, Ex. 3. Use the method above to find a basis of the corresponding V n consisting of a basis of

Li and of a complementary space

L

2.

Let the following vectors U{ span

2.

to Li

and f

%=

,-.(!, -1,1,1),

.= (1,2,1,0), fin

c)

Li, v

span

Li.

Find a complement in

{

Li,

L

to La.

i*

(4, 3, 1, 1) (1, 0, 2,

(3,

-2,

%=

,

-1) -1)

,

,

2,

-2,

1, 2)

u,-(l, -1,0,

,

u3

.-(!, -1,1,0),

-(1,2, 0,0),

.* = = /, = * \

(2,

,

*s

1)

-(4, -1,4,0)

=

-3,

3, 2)

(0, 1, 2,

-1)

(-5,

-4,

(4,

3,

,%

,

*-

in

,

2)

,

= =

(1, 0, 0, 1)

(!, 4, 2,

-3)

(2, 1, 6,

-3)

(-2,

-2,

1,

1)

2}

LINEAR SPACES 8.

79

of linear equations. The set of all linear forms in x\, F is a linear space

Systems

with coefficients in

L =

(24)

of order

n over

The

F.

(25)

=

fi

.

+ x nF

.

.

members

left

fi(xi,

+

xiF

.

.

.

,

=

xn)

+

d

.

.

+

.

a in x n

of a system

a

(26)

of if

m

t

+

iXi

.

.

.

+a

n unknowns, m by n matrix

linear equations in r is the rank of the

by Theorem 7 that F and the remaining m

see

in

xn

=

c

(i

are such forms

A =

(a,-/)

=

1,

and are

.

.

.

,

in L.

m)

,

Then,

we

of coefficients of (26),

certain r of the forms / are linearly independent in r forms are linear combinations of these r.

We may assume without loss of generality that the equations (26) have been labeled so that /i, fr are linearly independent in F, and .

(27)

.

.

,

=

/*

6*1/1

+

.

+

.

.

b krfr

(k

=

r

(i

ui,

.

.

.

u r are

,

linearly independent in F,

uk =

(29)

the system (26)

that/i(di,

(30)

.

.

.

,

m)

A =

(28)

If

1,

Then

for b k j in F.

where

+

.

.

.

,

is

dn)

Ck

+

.

.

.

+

Ci.

Then

fk(di,

.

.

.

1,

.

.

.

1,

.

.

.

,

w)

,

m)

,

and

b kr Ur

(k

consistent, there exist quantities

= =

bkiUi

=

=

di,

r

.

.

+ .

,

,

d n in

F such

1,

.

(27) implies that

,

dn )

=

bklCi

+

.

.

.

+ (fc

-

r

+

.

.

,

m)

,

INTRODUCTION TO ALGEBRAIC THEORIES

80

Define the augmented matrix matrix

A*

of the system (26) to be the

m by n

u*

A*

(31)

u

(OH,

,

ain

(i

and

see that (29)

and

ul

(32)

so that the rank of

rank

(30)

A*

is

c

,

=

1,

.

.

.

1,

.

.

.

,

m)

,

,

m)

,

imply that

= at

+

6*11*

most

.

.

.

+b

kr u* r

But A* has

r.

(k

A

=

r

+

A*

as a submatrix;

has

r.

Conversely,

if

A * has the same rank r as A

and we choose

wi,

.

.

.

ur

,

to

u* are clearly linearly independent. be linearly independent, then u* We then have (29) and may apply elementary row transformations of type 1 to A* which add b kr u*) to ul for k r + 1, m. (b k iU* + These replace the submatrix A of A * by .

t

.

m, (S)-

(33)

.

.

.

.

,

+

.

.

.

,

o UT

A*

and replace

by

(G

(34)

\0

Cl \ 1

C,/

r)-rowed and one-columned matrix C 2 has c/bo = c* bkrCr) as its elements. But, clearly, if any c* 5^ 0, the has a nonzero (r l)-rowed minor. This is impossible if A* is

where the (m (ftjfcici

+

.

.

matrix A* of rank r.

.

+

+

We now see that the system (26) is consistent if and only if A* has the same rank r as A. Moreover, we have already shown that, if A* does have the same rank as A, then m r of the equations (26) may be regarded as

LINEAR SPACES

81

linear combinations of the remaining r equations and are satisfied by the solutions of these equations. It thus remains to show that any system of r

equations in

x

=

(xi,

.

.

xi,

.

.

.

.

x n with matrix of rank r has solutions.

,

x n ) and see that such a system

,

may

We may write

be regarded as a matrix

equation

=

Gx'

(35)

Before solving (35)

LEMMA 4.

Let

G

t/

v

,

=

.

(ci,

.

.

,

cr )

.

we prove be

an

n matrix

r by

G=

(36)

of rank

Then

r.

0)Q

(I F

for a nonsingular n-rowed matrix Q. For Lemma 2 states that G = (H 0)Qi, where Qi is an r by r matrix of rank r. Then singular and

Q2 = Q 2 Qi.

diag {H, 7 n _ r },

The system (37)

n-rowed and non-

is

H is nonsingular,

H

(7 r

0)Q 2 = (H

(35)

may now

(I T

0)t/'

But then y = xQ'

=

Thus we have

0).

(36) for

so

is

Q =

be written as y

t/,

=

=

xQ'

( yi ,

..., yn).

a nonsingular linear transformation and the t/ are x n Evidently, (37) has the linearly independent linear forms in Xi, solution yi = c for i = 1, r; the solution of (35) is then given by z = y(Q')~ l for yi = Ci(i = 1, r) and 2/ r +i, 2/n arbitrary. Obis

.

.

.

.

.

serve that,

if

.

.

.

,

,

.

.

-

,

we choose the notation

of the x

-

,

G =

so that

Gi an r-rowed nonsingular matrix, then

(38)

Q

where FI and X\ have

Q'

so that

=

(!

r

columns.

^J,

From xQ'

we obtain

this

= (X G(+Xt G' 1

i

(Gi,

62) with

INTRODUCTION TO ALGEBRAIC THEORIES

82

and our solution of

(35) is given

- (Y -

X

(39)

l

But then we have solved

by l

for xi,

.

.

.

,

For exercises on linear equations we the

X,(

x r as linear functions of

Xr+i,

.

.

.

,

xn

.

refer the reader to the First Course in

Theory of Equations.

9.

The system of equations a linear mapping was expressed in (3.32) as a matrix equation y'A'. Let us interchange the roles of m and n, A and A.' in this equaThen we see that a linear mapping may be expressed as a matrix Linear mappings and linear transformations.

(3.1) of

x'

=

tion.

equation

= uA,

v

(40)

A

where

is

an

m by n matrix and u =

(41)

(pi,

.

.

.

,

ym)

v

,

=

(xi,

.

.

.

,

xw)

.

Clearly, u is a vector of Vm over F v is a vector of V n over F, and (40) may be regarded as a correspondence u > uA defined by A whereby every u of Vm determines a unique vector uA of F n We now proceed to formulate ,

.

this concept

more

abstractly. be linear spaces of respective orders and n over Let L and consider a correspondence on L to M. Designate the correspondence

symbol

M

5, so that

m

S

is

F and by the

the function

u*us

S: (read in

us

to u upper S) wherein every vector u of Suppose also that

u goes

M

.

(au

(42)

for every

+ 6tto) 5 =

au8

L determines a unique

+ bu

a and 6 of F, u and U Q of L. Then we shall call S a linear mapping L on the space and describe (42) as the property that S is

M

of the space linear.

we

Then a

linear

(43)

L=

M

= viF + um F and L and but fixed bases mapping S uniquely determines u$ in M, and hence

Suppose now that so that

u\F

+

.

.

.

+

M

are given not only the spaces

uf

=

anVi

+

.

.

.

+ ain vn

(i

=

.

.

1,

.

.

.

+

v n F, as well.

.

,

m)

,

LINEAR SPACES

83

an in F. Thus S determines also an m by n matrix A = (a ). But, conversely, if A is an m by n matrix and we define uf by (43) for the given elements an of A, then the property that S is linear uniquely determines the mapping S. This is true since every u of L is uniquely expressible in the form

for

7

u =

(44)

for

2/<

in

F and

yiUi

+

.

.

.

+ ymum

,

(42) implies that

us

(45)

It follows that to every linear

and M

mapping S

of

L on

M and 0wen bases of L

w

there corresponds a unique by n matrix A and conversely. shall call A the matrix of S with respect to the given bases of L and M. ,

We now

We

observe that

where

-

But v

then,

= u s in

1

M

= we assume temporarily that L = Vm and (40) and (41), we see that S is the linear mapping if

u - us

(46)

and put

= uA

A. Thus every linear mapping which is a change of be regarded as a linear mapping of the space Vm

for the given matrix

variable as in (3.1) on the space Vn

Vn

may

.

Let us next observe the effect on the matrix defined by a linear mapping of a change of bases of the linear spaces. Define new bases of L and

M

respectively,

by

4

0)

(47)

= i-i

y-i

,

INTRODUCTION TO ALGEBRAIC THEORIES

84 SB

for k

1,

.

.

.

,

m

and

nonsingular and, as

I

=

we saw

1,

.

.

.

,

n.

in (3.33),

Then P = (pki) and Q = (qu) are we may also write the second set of

equations of (47) in the form

(48)

v,

= 1-1

where

=

JB

= Q" We 1

(r/j)

.

wW

.

apply the linearity of

Substituting (43) and (48),

S

to (47)

and obtain

we have

(49)

where b k = Spkidarji- Hence the matrix B S with respect to our new bases is given by i

B = PAQr

(50)

=

(bki)

of the linear

mapping

1 .

and Q" 1 are arbitrary nonsingular matrices of m and n rows, respectively, we see that changes of basis in L and replace A by an equivalent matrix. Thus any two equivalent m by n matrices define the same mapping of L on If L and are the same space we shall henceforth call a linear mapping S of L on L a linear transformation of L. Since we are now considering only a single space, the only possible meaning of the Ui and v,- in (43) can be that of a fixed basis u\, u n of L of order n over F and of a second basis v n of L. Let us restrict our attention to the case where v = u^ v\, Then we define the matrix A of a linear transformation $ on L with respect to a fixed basis ui, u n of L to be the matrix A determined by (43) with Ui = Vi. We have defined thereby a one-to-one correspondence between the set of all n-rowed square matrices with elements in F and the set of all linear transformations on L of order n over F. If L = F n such a Since

P

M

M

M

.

.

.

.

.

.

.

,

,

.

.

.

,

,

correspondence

is

given

by u

us = uA

.

we should and do call S a nonsingular linear transformation if A is = u8A~ we see that a nonnonsingular. Since we may then solve for u Clearly,

1

)

singular linear transformation defines a one-to-one correspondence of

and

itself.

L

LINEAR SPACES

We now

A

observe the effect on

85

of a change of basis of L.

We

use (47)

= v+ and i4 = *40) so that we have P = Q. Hence a change of basis* of L with matrix P replaces the matrix A of a linear trans-

but note that ut

0)

,

formation by

B = PAP-

(51)

now

1 .

clear that in order to

study those properties of a linear transnot depend on the basis of L over F we need only study those properties of square matrices A which are unchanged when we It is

formation on pass to

L which do

PAP~ We l

shall call

.

A

two matrices

and

B

P

and shall obtain necessary for a nonsingular matrix in our next chapter. similar and be tions that

similar

and

if

(51) holds

sufficient condi-

B

A

EXERCISES Let S be the linear mapping (46) of 73 on A. Find the vectors of 7 4 into which (-2,

1.

rices

mapped by

F4

defined for the following mat-

3, 4), (1, 0, 0), (0, 1, 0) of

F3

are

S.

a)

-3

1

I

A =

\-l

A =

c)

1\

2-6-1

I

/2

3

1

21

-I/

-1

2

-2

3-2

\1

1

b)

A =

/-2 -1

I

3

d)

A =

-1 -I/

0\

2

-3/

4)

\

-5\

4

2

0\

/-2

0-10

I

\-l

1

1

01 I/

Show

that the linear transformations (46) of V* defined for the following matare nonsingular and find their inverse transformations. Apply both S and to the vectors of Ex. 1.

2.

rices

S" 1

A

/-4 a)

A = V

/S

-2

6)

-

-4x?

2x1

+

+

A

=

117

2zi

uf

wj

0> .

+ 40:1X2 -

Hxl = -6x^2

Observe that a change of bases

we put

6)

u =

d) 3x1

*

5

for the matrices of Ex. 2

of all vectors (points) tions.

5\

20

and let C be one or the other of the curves whose coordinates satisfy the following equa(x\, x%, x$) Find the equation of the curves C s into which each S carries each C.

Define

3.

3

3

(47) of

L

-

-

18x2X3

+

1

L when by a nonsingu-

defines a linear transformation of

Thus we may regard a change

lar linear transformation.

10xix 8

of basis as being induced

INTRODUCTION TO ALGEBRAIC THEORIES

86

Orthogonal linear transformations. The final topic of our study of linear spaces will be a brief introduction to those linear transformations permitted in what is called Euclidean geometry. Let then Vn be the n-dimen10.

c n ) over a field F. sional linear space of vectors u = (ci, the norm of u (square of the length of u) to be the value f(u) = /(ci, .

.

We

*

,

of the quadratic

define .

.

,

cn)

form

...,^-^ + ...+4.

/fe,

(52)

We

.

propose to study those linear transformations

S on V n which

are said

to be length preserving and define this concept as the property that f(u) 8 f(u ) for every u of n Such transformations S will be called orthogonal. us = uA for an n-rowed define S matrix A.

V

We may

=

.

by

Then,

square

= us (us )' = uAAV. Write B = AA' - (ft,,) = = 2c?. Put c p = 1, c/ = for j ^ p and and see that/(w ) 2Ci6i,-c/, /(w) 5 have f(u) = /(w ) only if 6 = 1 for every i. Then take c p c q = 1, all = /(w) only if other c/ = 0, from which f(u) = 2, f(us ) = 2 + 26 b pq = for a p 5^ g, B = / is the identity matrix. We call matrices A clearly, f(u)

=

uu', f(u s

s

)

pfl

satisfying

AA' =

(53)

orthogonal matrices

matrix

I

and have shown that S

is

orthogonal

if

and only

if its

is an orthogonal matrix. have seen that S determines

A uniquely only in terms of a fixed Euclidean geometry the only changes of basis allowed are those obtained by an orthogonal linear transformation, that is, those

We

basis of

Fn Now in .

which the matrix

for

P of

(51) is orthogonal.

But then

PP = 1

7,

P'

= P-

P'P = /, so that if S is a linear transformation with orthogonal matrix and we replace A by PAP"" 1 = B, then BB' and

B

is

(PAP')(PA'P')

- PAA'P' =

I

1 ,

A

,

also orthogonal.

EXERCISES 1.

2. lar.

3.

What

are the possible values of the determinant of

Let I be the identity matrix,

Show

that (/

Show

+ A)""^/

A)

an orthogonal matrix?

A be a skew matrix such that / + A is nonsinguis

orthogonal.

that every orthogonal two-rowed matrix /

V

a

(b

=1

A

has the form

LINEAR SPACES where a

=

such that 0?i

a

2

2

s(s

+

s*

+

2

AA' 4.

*

2

1/2

)~

6

,

=

2

Z(s

+

J

2

2

)-*/

7* 0.

Hint: The result

that

s

t*

+ #12= 1 so + 6 = (s + 2

J

2

=

+

2

)(s

J

2

1

=

range over all quantities in F A is a diagonal matrix. Now

t

is trivial if

an are

t

an,

)"

and

,

87

of the

form above, while, conversely, = + a are derived from 6,022

The values 021 =

1.

7.

The equations

h are x

=

for rotation of axes in a real Euclidean plane through an angle sin h, y z sin ft t/ 3/0 cos h. Show that the corresponding

=

z cos h

+

orthogonal and that every real orthogonal two-rowed matrix matrix of a rotation or its product by the matrix

matrix

is

Evo of a reflection x 5.

A

Find a

put du

=

XQ y

yQ

,

real orthogonal

PAP'

such that

=

=

is

is

either the

-i

.

matrix

P for each

of the following

a diagonal matrix. Hint:

Compute

symmetric matrices

PAP = D = 1

(d*,-)

and

0. 1N

\

M

i

a)

6)

OJ

/3

4>

(4

-3J

\

x

C>

A (l

l

\ l)

j\

/3 (2

Orthogonal spaces. We shall call two vectors u and v of V n orthog= 0. Then, if A is is, in a geometric sense, perpendicular) if uv' any orthogonal matrix and we define a linear transformation S of Vn by us = uA, we have 11.

onal (that

us = wA

tr

,

8

wA

wW =

,

uAA't;'

=u

f

=

=

0. Thus orthogonal transformations on V n preserve orthogonality of vectors of V n If L = viF v m F is a linear subspace of F, we define the set to the be set of all vectors w in Vn such that tw' = for every v of L. 0(L) if

and only

if

uv'

.

+

Then 0(L) in

Vn to

is

.

.

+

.

a linear subspace of

L. For, clearly,

have 0(01^

+

bw 2 )'

=

Vn which we shall call the space orthogonal

w 2 are = 0, fawj

Wi and

if

atwj

+

0(L) and a and 6 are in F, we ^i + ^2 is in 0(L). We now

in

prove

Theorem 9. Let L be a linear m. of 0(L) is n In fact we shall prove Theorem 10. Let L be the row that

G=

(I m

subspace of order

m of Vn

.

TVien the order

space of the m by n matrix G of ran/c m so 0)Q for a nonsingular n-rowed matrix Q. Then O(L) is the = (0 In-mXQ')" 1 o/ rank n m.

row space of H For proof we

first

note that the elements of

GH'

are the products

t^toj

INTRODUCTION TO ALGEBRAIC THEORIES

88

of the rows (I m 0)[(0

G by

of

Vi

the transposes of the rows Wj of H.

/n-m)], and, clearly,

GH' =

then

Let then

0.

+ y F of order q over F so that 0(L) contains the Evidently H has rank n m, and we must have g > n .

.

q

But

is

Q

is

nonsingular.

yiF

+

of

H.

We let HO be

m.

by n matrix whose kth row is y*, and we have GH'Q = 0)Q#Q. The rank of the n by q matrix

g since

f

row space

the g (I m

GH =

0(L) =

=

0,

But

m nonzero rows, and D must have rank Di = 0, D has at most n = n n m. This that proves q ra, the row space of H is 0(L). q Note that the row space of H is the set of all solutions x xn) (xi,

so that

<

.

.

.

,

of the

homogeneous

The sum of the

linear

orders of

system Gx = 1

L and 0(L)

is

0.

n,

and

it is

natural to ask whether

or not they are complementary in V n that is, whether V n = L 0(L). This is not true in general, since if F is the field of all complex numbers and

+

,

L =

=

= (1, i), then vv = 1 + i2 = 0. Hence 0(L) is contained in L and 0(L) = L. However, we may prove Theorem 11. Let F be a field whose quantities are real numbers. Then V n = L + 0(L). For by Theorem 9 it suffices to prove that the only vector w in L and 0(L) is the zero vector. Hence let w be in both L and 0(L) so that w = dG, dm ) has elements in F and G is an m by n matrix of where d = (di, while also Gw = GG'd By rank m whose row space is L. Then Gw' = Theorem 3.17 the matrix GG' has rank m and is nonsingular, GG'd' = as desired. only if d = 0, d = 0, w = i

vF,

2

.

.

f

v

1,

.

,

f

f

.

7

EXERCISE Let

L

be the space over the

field of all real

numbers spanned by the following

vectors u*. Find a basis of the space 0(L) in the corresponding a)

in-

6) Ul

-

c)

ui

-

d)

in-

=

(1,2,

-1,0),

(1, 0, 1, 1) (1,

-1,

(1, 2,

,

2, 1)

-1)

,

,

u,

-

in

=

u,

=

^-

Vn

.

(0, 1, 2, 1)

(0, 1, 0, 1) (2,

-1,

f-l,

1,

,

2, 3)

0)

,

,

u3

=

u,

=

u3

=

(-1, (1,

2, 1, 0)

-2,

(3, 3, 3)

4, 0)

CHAPTER V POLYNOMIALS WITH MATRIC COEFFICIENTS Matrices with polynomial elements. Let

1.

F be a field and designate by

Fix]

(1)

(read:

F

bracket x) the set of

all

polynomials in x with coefficients in F.

We shall consider m by n matrices with elements in F[x] and define elementary transformations of three types on such matrices as in Section 2.4. As we stated in that section, we assume that in the elementary transformations of type 2 the quantities c are permitted to be any quantities of F[x\. But those of type 3 are restricted so that the quantity a in F[x] shall have an inverse in F[x]. Then a ^ must be a constant polynomial, that is, a may

be any nonzero quantity of F. We now let A and B be by n matrices with elements in F[x] and call A and B equivalent in F[x] if there exists a sequence of elementary transformations carrying A into B. The field F(x) of all rational functions of x with coefficients in F contains Flx] and it is thus clear that if A and B are equiva-

m

}

lent in F[x] they are also equivalent in F(x).

are equivalent in F[x] only

if

Hence we

A and B We may then

see that

they have the same rank.

prove

LEMMA lent

1

in F[x]

.

Every nonzero matrix

A of rank r with elements in F[x] is equiva-

to

1 -

(S where GI vides

=

diag

(fi,

.

.

.

,

fr }

X)

for monic polynomials

fi

=

fi(x)

such that

fi

di-

fi+i.

For the elements of all matrices equivalent in Fix] to A are polynomials and in the set of all such polynomials there is a nonzero polynomial

in x, /i

=

/i(#) of lowest degree.

Using elementary transformations of types 3

and 1, we may assume that f\ is monic and is the element in the first row and column of a matrix C = (c ) equivalent in F[x] to A. By the Division ;

89

INTRODUCTION TO ALGEBRAIC THEORIES

90

= qifi Algorithm for polynomials we may write CH F[x] and r of degree less than the degree of f\. But if first

row

with

Ti

of

C

to its ith row,

we

see that every

is

D

du

and

for g<

we add

q>

r< in

times the

pass to a matrix equivalent in F[x] to

A

column. Our definition of /i have now shown A equivalent we Moreover, = (da) with dn = for i 7* 1, du = f\. Similarly,

as the element in its

thus implies that r< in F[x] to a matrix

we

+r

I'th

row

arid first

zero.

is

by /i and hence

divisible

that

A

is

equivalent in

F[x] to a matrix

(3)

Vo

where

may

A

2

w

has

1

rows and n

apply the same process to

A

ultimately show that

such that

every / =

the set of

all

is

A

columns. Then either

After a finite

2.

number

A2 =

all

monic and

is

we we our lemma 0,

or

of such steps

equivalent in F[x] to a matrix (2) of

/<(x) is

elements of

1

a polynomial of least degree in

matrices equivalent in F[x] to

(4)

Write /i+i

= fiSi

+

ti,

where

s<

and

ti

are in F[x] and the degree of

ti is

less

than the degree of /i. Then we add the first row of A i to its second row so that the submatrix in the first two rows and columns of the result is

ft

(

(5)

\fi

We

then add

a*

times the

first

column to the second column

to obtain

a matrix equivalent in F[x] to Ai and with corresponding submatrix //,-

(6)

Our

\f< definition of /t thus implies that

We

=

/ divides />i as described. observe now that the elements of every <-rowed minor of a matrix ti

0,

with elements in F[x] are polynomials in

A

z, so that these minors are also

POLYNOMIALS WITH MATRIC COEFFICIENTS

91

By Section 2.7 if B is obtained from A by an elementary then transformation, every Crowed minor of B is either a Crowed minor of minor of A by a quantity a of F, or the sum the of a 2-rowed A, product polynomials in

x.

Crowed minors of A and/ is a polynomial of F[x]. If d in F[x] then divides every Crowed minor of A, it also divides every 2-rowed minor of all m by n matrices B equivalent in F[x] to A. But A is also equivalent in F[x] to B and therefore the Crowed minors of equivalent matrices have the same common divisors. We may state this result as LEMMA 2. Let Abe an m by n matrix with elements in F[x] and d t be the greatest common divisor of all i-rowed minors of A. Then d t is also the greatest common divisor of the i-rowed minors of every matrix B equivalent in F[x] to A. Every (k + l)-rowed minor Mk+i of A may be expanded according to a row and is then a linear combination, with coefficients in F[x], of fc-rowed minors of A. Hence dk divides every Mk+i so that dk divides dk+i. We ob-

MI + fMz where MI and Afa

are

serve also that in (2) the only nonzero fc-rowed minors are the fc-rowed

minors |diag

We

\fi

we

divides /,+

.

.

.

.

.

.

,

|

=

thus have d k

/i

.

.

.

fk,

whence

--A.

(7)

customary to relabel the polynomials / and thus to write fr = gi, = g r We call g the jth invariant factor of A and see that if we /r_i 02, /i = 1 we have the formula define d It is

t

=

>

3

gf

(8)

Moreover,

now

0, is

divisible

by

0i,

.

.

w If,

.

,

r,

then

A

is

1

visors d k

to (2)

=

1,

and

.

.

.

,

r

see that

1. if

A

=

1,

i

r)

.

We

apply elehas invariant

equivalent in F[x] to

(o then,

(j

0/+i for j

mentary transformations of type factors

=

-*i

2).

*>

equivalent in F[z] to 4, it has the same greatest common diand hence the same g, of (8), while, if the converse holds, B is is

equivalent in F[x] to (9) and to A.

We have

proved

INTRODUCTION TO ALGEBRAIC THEORIES

92

Theorem F[x]

m by n matrices with elements in F[x] are equivalent in if they have the same invariant factors. Every m by n matrix

Two

1.

if and only

of rank r with invariant factors gi,

g r is equivalent in F[x] to (9). As in our theory of the equivalence of matrices on a field we may obtain a theory of equivalence in F[x] using matrix products instead of elementary transformations.

P

both

We

.

.

and P- have elements if

P

to be an elementary matrix

in F[x}. Then,

the quantities a and 6 are in F[x], ab

But

,

thus define a matrix

1

quantities of F.

.

=

=

/ |

1

P has elements in F[x]

a

if

=

\P\ and b

so that a

1,

and

so does adj P.

=

\P~

if

l

\,

6 are nonzero

Hence

so will

P- = PI" adj P if |P is in F. Thus we have proved that a square matrix P with polynomial elements is elementary if and only if its determinant 1

1

|

|

is, in F) and not zero. observe that, in particular, the determinant of any elementary

a constant (that

is

We now

A

and B are square matrices with elements in F[x] and are equivalent in F[x], their determinants differ only by a factor in F. Moreover, if \A and \B\ are monic polynomials, then the equivalence of A and B in F[x] implies that \A - \B\ and, in fact, transformation matrix

is

in F.

Hence,

if

\

\

when A

is

determinant

is

that

It is

the product g\ gn clear now that a square matrix

and only

if

a nonsingular matrix with

if

P

.

is

.

.

0i,

.

.

.

,

gn

as invariant factors

its

.

P with elements in F[x] is elementary

equivalent in F[x] to the identity matrix,

and thus the

invariant factors of P are all unity. We may now redefine equivalence. We call two m by n matrices A and B with elements in F[x] equivalent in F[x] if there exist elementary matrices P and Q such that PAQ = B. Then we again have the result that A and B are equivalent in F[x] if and only if they have the same invariant factors. For under our first definition P and Q are equiva-

and hence may be expressed as products of elementary transformation matrices. But, if PO and Q are elementary transformation matrices, the products P&A, AQo are the matrices resulting from lent in F[x] to identity matrices

the application of the corresponding elementary transformations to A. Hence, PAQ must have the same invariant factors as A. The converse is

proved similarly, and we have the result desired. In closing let us note a rather simple polynomial property of invariant factors. The invariant factors of a matrix A with elements in F[x] and rank r are certain

=

i .

.

.

1, ,

r.

.

.

.

,

r

monic polynomials 1.

Let us then

If

g k (x)

call

=

1,

Qi(x)

such that Qi+i(x) divides gi(x) for

then g&x)

those gt(x)

^

1

=

1

for

larger j

=

k

+

1,

the nontrivial invariant factors

POLYNOMIALS WITH MATRIC COEFFICIENTS of

A

=

the remaining g^x)

}

an integer

exists

g i+ i(x)

=

.

.

=

.

=

g r (x)

Thus

the trivial invariant factors of A.

1

such that gi(x) has positive degree for

t

i

93

=

1,

there

...,,

1.

EXERCISES 1. Express the following matrices as polynomials in x whose coefficients are matrices with constant elements.

a)

I

x3

/x 2

x

d)

2

\x 2

+x +x -

+

3x 2

-

x2

x x

+

x2

1

2x

1

3x

2x 2

-

x3

1

-

x2

+ 4x -

2

+ 1\ +x + 2/

1

2. Let A be an m by n matrix whose elements are in F[x]. Describe a process by means of which we may use elementary row transformations involving only the fth and kth rows of A to replace A by a matrix with the g.c.d. of an and a*,- in its ith row and jth column. Hint: Use the g.c.d. process of Section 1.6 with/ = an,

Q

=

a>kj>

3.

form

Use elementary transformations to carry the following matrices into the (9).

\ a)

(x \Q

x

+

l)

\

/x 2

\

/x(x-l) b)

x(x

+

c)

l)j

+ x-2

\

x

V

2

+ 2*

-

3/

Describe a process for reducing a matrix A with elements in F[x] to an equivaHow, then, may we use the process of Ex. 3 to carry this preliminary diagonal matrix into the' form (9)? 4.

lent diagonal matrix.

5.

Reduce the matrices

of Ex. 1 to the

form

(9)

by the use

of elementary trans-

formations. 6.

Determine the invariant factors

of the matrices of

Ex.

1

by the use

of (8).

INTRODUCTION TO ALGEBRAIC THEORIES

94

Use elementary transformations to reduce the following matrices

7.

form

(9).

+2

x 2.

Elementary

-x2

divisors.

g\(x)

where

Ci,

.

.

of a matrix

.

,

c,

Let

=

x

+

~x 2

1

K be the field of all complex numbers so that

(x

-

ci)

ei

.

.

.

(x

e

c,)

,

are the distinct complex roots of the

first

invariant factor

A

with elements in K[x], Since 0+i(x) divides 0(x), that every g<(x) divides 0i(x), and thus n-(r\

C\C\\ v^iuy

&%{)

Here .

.

.

to the

,

r is the r.

We

number

(r {*'

/,Vtil ^i)

frc v-

of invariant factors of A,

shall call the rs

cyVi* /

e\j

=

TV

^ e^ e^

1

it is

.

.

for

i

i,

^

.

clear

r"i ,

rj

=

.

2,

polynomials

the elementary divisors of A. Those for which e^ nontrivial elementary divisors of

A.

>

will

be called the

POLYNOMIALS WITH MATRIC COEFFICIENTS

95

The invariant factors of A clearly determine its elementary divisors Cj where r is the uniquely as certain rs powers // of linear functions x rank of A, and s is the number of distinct roots of the invariant factors

A

of A. Conversely, the elementary divisors of uniquely determine its invariant factors. In fact, let us consider a set of q polynomials each a power with positive integral exponent of a monic linear factor with a complex

The

root.

distinct roots in our set

polynomials have the form the

(z

tfyen

c/)

n *>

be labeled

for

n^ >

Ci,

.

.

.

and our

c,

,

For each

0.

c,-

let

tj

+

HH =

^

n polynomials by adjoining t tj polynomials (x c,) / with Let us then order the t exponents n, to be integers e^ satisfying t and ^ ^ Ctj ^ 0. Define gi(x) as in (10) for i = 1,

ts

0. 02j

.

.

.

.

.

.

,

obtain a set of polynomials gi(x) such that g%+i(x) divides g^(x) for i 2 1, the Qi(x) are the nontrivial invariant factors of a matrix .

.

be

^

exactly

#ij

may

number of hkj in our set, t be the maximum tj. Then, clearly, q = ti t tSj and our set of polynomials may be extended to a set of

+

.

hkj

=

.

,

1,

A

whose nontrivial elementary divisors are the given hkj. If A has rank r, we have r ^ t, and we adjoin (r t)s new trivial elementary divisors // to obtain the complete set of r invariant factors 0,-(z) of A. It is now evident that two by n matrices with elements in K[x] are equivalent in K[x] if and only if they have the same elementary divisors.

m

The matrix

has prescribed invariant factors and hence prescribed it is desirable to obtain a matrix of a form

(9)

elementary divisors. However,

exhibiting the elementary divisors explicitly.

We shall do this.

Let us prove

first

Theorem

f s be monic polynomials of F[x] which are rela2. Let f i, in Then the pairs. only nontrivial invariant factor of the matrix tively prime fs f B } is its determinant g = f i A = diag {fi, .

The

.

.

.

.

,

,

.

,

result is trivial for s

A =

=

1.

=

If s

2,

.

.

.

the g.c.d. of the elements f\ and

=

l,/i/2 is the only nontrivial invariant factor of 2 is equivalent in F[x] to diag (fif 2 2, and 1J. Assume, then, in to that A,_i = diag {/i, is 5,_i = diag {0_i, F[x] equivalent ,/,_i}

/2 of

2

diag {/i,/2J

is

unity, d\

A

A

,

.

!,...,!}, where

0._i

.

=

.

/i

.

.

.

Then

/,-i.

A =

diag

...,/,}

{/i,

is

equiv-

alent in F[x] to diag {0 f _i, / 1, diag 1}. But 0,_i is prime to / in to is equivalent to is F[x] diag {g, 1}. Hence {
.

.

,

A

.

.

.

,

and our theorem

is

proved.

We see now that if gi(x)

is

defined

by

(10) for distinct

complex numbers

the corresponding elementary divisors /, /* are relatively prime in pairs. By Theorem 2 the matrix Ai = diag {/, ...,/} is equivalent .

Cjj

in F[x] to diag {0 t

-,

!,...,!}. But then

A =

.

.

,

diag {^i,

.

.

.

,

A

t }

is

equiv-

INTRODUCTION TO ALGEBRAIC THEORIES

96

alent in F[x] to diag [g^ variant factors of A are 0i, .

we have proved Theorem 3. Let

^

tegers ni

Ci,

Then

0.

.

.

.

.

.

.

,

g tj

,

.

.

fi

as

its

.

.

.

We

(ft-

,

and hence the nontrivial inexamine the form of A to see that 1},

,

numbers and fi=

c r be complex

n

(x

Ci)

i/or in-

matrix

the

A = has the

1,

diag

{fi,

.

.

,f r j

.

elementary divisors.

EXERCISES The

1.

What

are a)

following polynomials are the nontrivial invariant factors of a matrix. nontrivial elementary divisors?

its

+ 2x* + x\ + z + 2x* +

x* + x + x*, x x* + x, x 2x* + x* + x, 2x + 1), z 2z + x, x(x I) (x 4z + 5z - 2, x* z 7z + 2, 5s + 9z

x6

V)

2

2

c)

d)

2.

(*

The

-

3

2

8

2

e)

x*

5

6

(x

l)^,

-

2

2

I)

(x

,

3-1

,

2

3

2

2

-

-

x

1),

a;

2

-

3z

+2

1

following polynomials are the nontrivial elementary divisors of a matrix is six. What are its invariant factors?

whose rank a) b) c)

(x (x

-

(x

/) x, 3.

form

(*

2)',

(x

+

-

-

(x

2),

(x

1),

(x

1)',

(x

- 1),

(x

(*-3),

(x-3),

d) x, e)

(x

1)',

-

1),

+

-

1),

(x

2),

x,

(*-3),

-

2),

(x

-

x*,

2

I)

(x

,

(x

+

(x

3),

-

z>

(x

4),

(x +

x',

1)

x

-

*',

x'

1)S

x*

x,

x,

+

1),

x,

**,

- 1), (x - 1)*, (x

1)2,

+

5)

Find elementary transformations which carry the following matrices into the (9).

/(x

o)(

-

/x 3

\

1)

x-2 x

\

-0) I/

(0 \0

x

\0

/x a c)

\

6)(0x + l \

(x-l) x

+

I/

0)

+ 2/

POLYNOMIALS WITH MATRIC COEFFICIENTS 3.

97

Matric polynomials. Let the elements a*, of an m by n matrix A be and let s be a positive integer not less than the degree of any of the Then every a# has s as a virtual degree and we may write

in F[x] a,-/.

(11)

Oif

a$

for

in F. Define

Ak =

(12)

(a^) and obtain an expression of

f(x)

m

= A Qx>

+

.

.

.

A

in the

form

+ A.

by n matrices A k Thus f(x) is a polynomial in x of virtual degree m 6y n matrix coefficients Ak and virtual leading coefficient AQ> Moreover, we say that/(x) has degree s and leading coefficient Ao if ^o ^ 0. In order to be able to multiply as well as to add our matrices we shall

for s

.

with

henceforth restrict our attention to n-rowed square matrices with elements in F[x] and thus to the set of all polynomials in x with coefficients n-rowed

square matrices having elements in F. Let us

rowed matric polynomials. nomial f(x) ly

is

If all the

the zero polynomial,

A k in

call

these polynomials n-

(11) are zero matrices, the poly-

and we again designate

by 0. Evident-

it

we have

LEMMA

The degree of

3.

f (x)

+

g(x) is not greater than the degree of

f (x)

or g(x).

LEMMA

4. Let f (x) have degree n and leading coefficient Ao, g(x) have deand leading coefficient B such that AoB 5^ 0. Then the degree of f (x)g(x) is m + n and the leading coefficient of f (x)g(x) is AoB

gree

m

.

in Chapter I we use Lemma 4 in the derivation of the Division Algorithm for matric polynomials which we state as

As

Theorem degrees s

4.

and

t

Let

f (x)

and g(x)

be n-rowed matric polynomials of respective

such that the leading

coefficient of g(x) is nonsingular.

there exist unique polynomials q(x), Q(x), r(x),

have virtual degree (13)

1

t

f (x)

=

and

q(x)g(x)

Moreover, if s < t, then q(x) t. Q(x) have degree s

While the proof

is

Then

R(x) such that r(x) and R(x)

very

+ r(x) = =

much

Q(x)

=

g(x)Q(x)

0,

+ R(x)

while if s

the same as that in

^

.

t,

then q(x)

Theorem

and

1.1, let

us

and J?o be give it in some detail. We assume first that s ^ t and let A the respective leading coefficients of /(#) and g(x). Then B^ 1 exists, and if q\(x)g(x) has virtual deq^x) = A^B^x'"' the polynomial fi(x) = f(x)

^

INTRODUCTION TO ALGEBRAIC THEORIES

98

1. This implies a finite process by means of which we begin with i * t and leading coefficient a polynomial /i(x) of virtual degree s 1 i and then form /i+i(x) = fi(x) q i+ i(x)g(x) of virtual degree s

gree 5

A^

for <7t+i(x) = A^jB^x*""*""'. 1. //(x) of virtual degree t q(x)

-

0, r(x)

= /(x)

leading coefficient

if s

A B^

1

Q

<

The process terminates when we obtain an Thus we have the first equation of (13) with t and t, and otherwise with q(x) of degree s

and r(x) the //(x) above.

=

If also /(x)

q$(x)g(x}

+

^

q(x) 0, the degree of this polynomial is h jg 0, and its C 0. Also C Bo 5^ since B is nonsingular. But leading coefficient is = r(x) r (x) is t then by Lemma 4 the degree of [qo(x) ft, g(x)]0(x) r (x) for #o(#)

^

+

a contradiction. This proves the uniqueness of g(x) and r(z). The existence and uniqueness of Q(x) and R(x) is proved in exactly the same way except that we begin by forming /(x)

whereas

its

virtual degree

is

t

1,

Let us regard the first equation of (13) as the right division of f(x) by g(x), the second as the left division of f(x) by g(x). Then we shall speak correspondingly of q(x) and r(x) as right quotient and remainder, of Q(x) and 12 (x) as left quotient and remainder. If r(x) = 0, we have /(#) = q(x)g(x), and 0(x) is a ngrfa divisor of /(x). Similarly, we call (/(x) a left divisor of 0(x)

if

It is natural

/(x)

now

=

gr(x)Q(x), so that J?(x)

=

in (13).

Remainder Theorem for matric polyusual form is ambiguous since, for ex-

to try to prove a

nomials. However, the theorem in

ample, if C is an n-rowed square matrix and/(x) the polynomial /(C) might mean any one of A Q C 2

= A CA

x2

=

x 2A

= xA

x,

2

CAoC, and these matrices might all be different. Thus we must first define what we shall mean by/(<7). We shall do this and obtain a Remainder Theorem which we ,

,

state as

Let f(x) be an n-rowed square matric polynomial (12), C be ann-rowed square matrix with elements in F. Define fn(C) (read: f right of C),

Theorem

and fL (C) (14)

5.

(read: f

left

of C) by

f R (C)

= A

f L (C)

= CAo +0-^1

C-

+ A^*- + 1

.

.

and (15)

Then the right and left remainders on and fi/C), respectively.

+

.

.

.

+CA_ + A. 1

division of f (x) by xl

.

C

are fn(C)

POLYNOMIALS WITH MATRIC COEFFICIENTS To make our proof we use Theorem

99

as in the case of polynomials with coefficients in a

C and have }(x) = q(x)g(x) + = B has elements in F. We then 1 and r(x) r(x) where q(x) has degree s wish to draw our conclusion from /(C) = qR (C)(C C) + B. This statement is correct, but let us examine it more closely. We write q(x) = 4 with g(x)

field

Cox*~

*(*)

+

l

=

.

.

.

C,_i

-

q(x)(xl

= Then,

+

=

xl

+

C._!x)

and have

C)

+ da-' +

(Co*

.

.

.

-

(CoC*-'

+

.

.

.

+

C_!C)

.

D is any n-rowed square matrix with elements in F, we have

if

=

h R (D)

CoZ>

+

-

= C

(Ci

-

CoC)!)-

1

+

.

.

.

+

-

(C_i

C._ 2 C)D

- C_i

while

q*(D)(DI

C)

D-

+

(CiD-

and these matrices are equal tative.

They

are equal

/(C) =

hR (C)

theorem

is

if

1

-

CoD-'C)

+

.

if and only = and thus C, f(x)

in general*

D =

+B = qR (C)(C -

C)

+B

=

.

if

.

D and C are commu-

h(x)

+B

implies that of our

The second part

B.

proved similarly.

As a consequence

of the result just proved for matric polynomials which we state as

we have

the Factor Theorem

C as a right divisor if Theorem 6. The matric polynomial f (x) has xl C as a left divisor if and only if f/;(C) = 0. and only if f(C) = 0; it has xl For Theorem 5 implies that, if /#(C) = 0, then in (12) the polynomial r(x)

=

=

0, f(x)

q(x)(xl

have seen that/fi (C)

=

-

Conversely,

C).

fe(C)(CJ

-

C)

=

0.

if

The

=

-

C), we q(x)(xl results on the left follow

f(x)

similarly.

Our principal use of the result above is precisely what is usually called C as a factor, then the trivial part of Theorem 5, that is, if /(re) has x C is a root of f(x). However, it is nontrivial that /(C) = and follows only from the study above where we showed that if D is any square matrix such that DC = CD, then h(x) = q(x)(xl - C) implies that h R (D) = qR (D)(D *

E.g.,

D'

-

if

C).

q(x)

-

x so that h(x)

- DC * D - CD

unless

=

DC =

x8

-

CD.

Cx, then h R (D)

= D2 - CD, q M (D)(D -

C)

-

INTRODUCTION TO ALGEBRAIC THEORIES

100

EXERCISES 1.

Express the following matrices as polynomials /(x) and g(x) with matric

cients

and compute

2z 4

-

q(x), Q(x), r(x),

x*

R(x) of

+ 2 -x + x 8

1

X

(1+ 0*2

4 x

/v.2

2.

Use /(#)

by

of Ex. l(c)

/O

a)C=(0 \2

4.

The

and

substitution 1

find /ft(C) and/z,(C)

__ O'rS iJU

t

3

as well as

coeffi-

(13).

y?

3a.2

T

2^2

by the use

-

ff JU

1

Q/2

_l

\jJ(/

|"

2

x i

x

2

3

5

of the division process

if

0\

/O

l) O/

6)C=(l \0

characteristic matrix

2

0\

/I c)

I/

and function.

2

0\

(7=12-1 I/

\0

If f(x) is

a matric polynomial shall call/(x) a

n-rowed scalar matrix coefficients A^, then we scalar polynomial Thus A k = a k l for the a^ in F, and (12) with

(16)

/(x)

=

(a<&

+ ...+ a.)I

,

the n-rowed identity matrix. We call f(x) monic if a = 1. If now g(x) is also a scalar polynomial, the quotients q(x) and Q(x) in (13) are the same scalar polynomials and also r(x) = R(x) is scalar. For obvi-

where /

is

ously this case of Theorem 4 is now the result of multiplying nomials of Theorem 1.1 by the n-rowed identity matrix.

all

the poly-

POLYNOMIALS WITH MATRIC COEFFICIENTS A

101

any n-rowed square matrix, the polynomials //?(A) and/i,(A) are equal for every scalar polynomial /(x), and we shall designate their common value by If

is

/(A)

(17)

= aoA

+

.

.

+ a,_iA + aj

.

.

or the equation /(x) = has 0. By Theorem 6 the matrix A is a root of /(x) if and A as either a right- or a left-hand factor.

We now say that either the polynomial /(x) as a root

=

if

/(A) only if /(x) has xl

We

A

A

matrix xl

shall call the

terminant \xl nomial

|

A

the characteristic matrix of A, the de-

the characteristic determinant of A, the scalar poly-

f(x)

(18)

=

\xl

-

A\

I

the characteristic function of A, and the corresponding equation /(x) = A to obtain the characteristic equation of A. We now apply (3.27) to xl (19)

(xl

-

A)[adj (xl

-

A)]

=

[adj (xl

-

A)](xl

-

A)

= |x/- A Then

the elements of adj (xl

A) are the

/.

cof actors of the elements of

A) is a matric polynomial A, and adj (xl By the argument above we have Theorem 7. Every square matrix is a root of its

xl

The g.c.d.

|

(in general, nonscalar).

characteristic equation.

A) is clearly the polynomial d n -i(x) defined f or xl A and d n (x)= \xl A \. But then adj (x/ A) =d n _i(x)B(x), where B(x) is an n-rowed square matrix with elements in F[x\. Hence B(x) A were defined in (8), is a matric polynomial. The invariant factors of xl = = and by (19) \xl (xl A)B(x)d n _i(x). By the gi(x)d-i(x)I A\I uniqueness of quotient in Theorem 4 we have of the elements of adj (xl

g(x)

(20)

=

0i(x)7

=

(xl

-

A)J5(x)

.

Hence, clearly, g(A) = 0. Observe also that the g.c.d. of the elements of B(x) is unity so that if B(x) = Q(x)q(x) for a monic scalar polynomial = 1. q(x), then q(x) We now define the minimum function of a square matrix A to be the

Theorem trix of A.

A

The remark

just

8. Let gi(x) be the first invariant factor of the characteristic

ma-

monic scalar polynomial of made above then implies

Then g(x)

=

least degree

gi(x)I is the

with

as a root.

minimum function

of A.

INTRODUCTION TO ALGEBRAIC THEORIES

102

For if h(x)

is

the

minimum function of A we may write g(x) =

r(x) for scalar polynomials h(x)

and

+

h(x)q(x)

r(x) such that the degree of r(x)

is less

= 0,and0(A) = Osothatr(A) = 0,r(z) = 0. Hence g(x) = h(x)q(x), and since g(x) and h(x) are monic so is q(x). By Theorem 6 we have h(x) = (xl A)Q(x), and by (20) we have g(x) = = (xl (x/ 4)5(z). The uniqueness in Theorem 4 then A)Q(x)q(x) states that B(x) = Q(x)q(x), q(x) = 1, from which g(x) = h(x) as desired. We see now that xl A is a monic polynomial of degree n and is not = m = n in (9), and zero, r

than that of h(x). But&(A)

\

|

P(x)

(21)

(si

-

A)

.

=

Q(x)

diag

{jfi,

.

.

.

,

gn ]

and Q(x). But then, as we have already ob-

for elementary matrices P(x)

served in an earlier discussion,

c-

(22)

=

for c

|P (a:)

Theorem

and d |

9.

=

d

\xI-A\ \Q(x)\ in F.

=

...gn

gl

Hence cd

jPAe characteristic function of

=

and we have proved

1,

a square matrix

A is

/&#

product by I o/ tfta product of the invariant factors of the characteristic matrix of A. This result implies that \xl A\ is the product of g\(x) by divisors gi(x) of g\(x}. It follows that

F

is

A in any field K conwe have already seen that if F is

every root of \xl

But

a root of

in fact

\

taining g\(x). A are the field of all complex numbers, the elementary divisors of xl Then whose is the are the c/)*w product c, polynomials (x \xl A\. distinct roots of g\(x) as well as of teristic roots

In closing this section we note that

+ aa"- + 1

(x

\A\

.

= (-l) nan

.

.

They

. \

we

if

are called the charac-

write f(x)

+ a*) /, then/(0) = -A |

It follows that,

-

A"*

(23)

A

xl |

of A.

= -o^ (A^ l

if

\A

\

^

0,

+ M- +

7 \

=

/

=

\xl

A\

n

/, so that

(-l) |A

|

then

2

.

=

.

.

+ an-!

/)

,

A A~ = A- A. Moreover, if \A\ =0, then ~ A~~ does not exist. If, then, A 7* and gi(x) = x m + bixm + + m the polynomial gf(a:) = g\(x)I can be the minimum function of A only if ~ b m = 0. Since A 9* 0, we have m > 1, and G = A m + m~ + + and hence

it is

obvious that

l

1

l

l

.

l

6m _i/ (24)

is

a nonzero matrix with the property

AG = GA =

.

M

.

fc

.

2

.

.

.

,

POLYNOMIALS WITH MATRIC COEFFICIENTS

103

EXERCISES 1.

When

2.

What, then, are the minimum functions

the

is

minimum

/2

.

>

(l 3.

A =

Let

respectively.

3\

{^4i,

that

/O

,.

6)

-2J

diag

Show

function of a matrix linear?

f(x)

is

f(x)I t any t, then/m+nCA) k tion that A = diag [Af, A%\.

A

Let

multiple of g\(x)

.

.

a)

and

functions of A, A\,

/o

0\

l)

(o

6J

A 2 are square matrices of m in F[x]

let

A*

and we

Hint: Prove

and n rows

define first

6.

Compute

7.

It

by

=

the least

is

common

is

nonsingular and

A = z

0.

the characteristic functions of the following matrices.

+

+

property that di is the matrices of Ex. 6.

5. Similarity of

A

(x)

induc-

,

,

Prove that g(x)

be shown that the characteristic function f(x) = x n n~* n l)*atX ( l) a n of an n-rowed square matrix

matrices

t

g(x)I m^ n gi(x)I m and Qi(x)I n be the

may

(

f

gi(x).

Apply Ex. 4 in the case where A\

+

3\

(4

diag {fm(Ai),fn (A 2 )}.

5.

.

/2

any polynomial

have the form of Ex. 3 and

minimum

respective

e>

(6

=

for

4.

1\

A^} where 4i and if

of the following matrices?

sum

a\x

A

n~ l

+

has the

of all i-rowed principal minors of A. Verify this for the

square matrices.

We

have defined two n-rowed square

B with elements in a field F to be similar in F if there exists matrix P with elements in F such that

and

a nonsingular

PAP- = B 1

.

The principal result on the similarity of square matrices is then given by Theorem 10. Two matrices are similar in F if and only if their characteristic

For

But

matrices have the same invariant factors. if

PAP- = 1

B,

P has elements in F,

then \P\

- A)P~ == xPIP~ - B = xl - B. A is in F, P is elementary. Hence xl

P(xl

^

l

l

104

INTRODUCTION TO ALGEBRAIC THEORIES

and xl

B

Conversely,

and have the same invariant

are equivalent in F[x] let

A and xl

xl

-

P(x)[xl

(25)

A]Q(x)

=

Q(x).

We

and

for elementary matrices P(x)

P = PL (B)

(26)

as in

Theorem 5 and have

(27)

P(x)

=

(xl

-

+P

B)P*(x)

factors.

B have the same invariant factors, so that

-B

xl

define

Q = Qa (B)

,

= Qo()(x7 -

Q(x)

,

+

B)

Q

.

Then

-

P(x)[(xl

P

We now [P(z)]-

=

A)]Q(x) (xl

-

(xl

-

Q

4)

-

B)P(x)(xI

(z)(z7

-

+P

B)

- A) Q =

xl

-

(xl

-

use (25) and the fact that P(x) and Q(x) are elementary to write

=

1

C(x), Q(x)~

1

=

D(x) for matrix polynomials C(x) and D(x)

such that

(J -

(28)

=

A)Q(x)

But then from

P

(27) .

(xl

C(x)(a;I

and

-

-

B)

P

,

(28)

A) =

(s/

-

J3)[Z)(a;)

-

P*(x)(xl

-

A)]

and thus (x/

(29)

R=

-

J5)

-P

-

(si

=P

Q =

A)

(x7

-

-

+

(x)C(x) D(x)Q Q (x) Pt(x)(xI-A)Q Q (x). By Lemma 4 the degree in x of the right member of (29) is at least two unless R(x) = 0. But the degree in x of the left member of (29) is at most one,

where

R(x)

=

fl(a?)

0,

P

(30) It follows that

PAQ =

^

(xl

B,

A)

P7Q =

-

Q =

-B

xl

.

Q = P- PAP" = B 1

1

7,

,

A

Observe that the degree of xl j

is \

as desired.

n and hence that

.

(31)

.

.

g (x) t

HI

n

if

gree of the ith nontrivial invariant factor gt(x) the property

|

is

the de-

A =

xl

|

implies that

+n + 2

.

.

.

+n = t

n

,

tti

^

n2

^

.

.

.

^ n = t

.

Obviously, this is an important restriction on the possible degrees of the invariant factors of the characteristic matrix of an n-rowed square matrix.

POLYNOMIALS WITH MATRIC COEFFICIENTS

105

EXERCISES What

1.

are

all

of square matrices

possible types of invariant factors of the characteristic matrices

having

1, 2, 3,

or 4 rows?

2.

Give the possible elementary divisors of such matrices.

3.

Use the proof

of

Theorem 10

to

show that

if

AI,

A^

and Bz are n-rowed

Bi,

+

+

A 2 and E\x B2 square matrices such that A\ and B\ are nonsingular, then A\x and Q with are equivalent in F[x] if and only if there exist nonsingular matrices elements in

F

BT^

B

such that

PA& =

Bi and

PA Q = B2 2

.

Hint: Take

P A = -Ar ^, 1

in (25).

Show that the hypothesis that A\ is nonsingular in Ex. 3 is essential by proving

4.

that Aix

/ and B\x

J are equivalent hi

yet

F[x],

B

P

and Q do not

exist, if

l

matrices with prescribed invariant factors. If g\(x), are the nontrivial invariant factors of a matrix xl A and n is g t (x) the degree of 0(z), then by Theorem 1 the n-rowed square matrix 6. Characteristic

.

.

.

,

B =

diag {Bi,

.

.

.

B

,

t ]

will be similar in F to A if Bi is an n-rowed square matrix such that the only nontrivial invariant factor of the characteristic matrix of Bi is g>(x). B = diag {xl ni BI, B is equivalent in xl nt For then xl .

F[x] to diag {G i, f

clude that xl

B

.

.

t ]

,

=

diag {#, !,...,!}, and we conhas the same invariant factors as xl A Thus the problem

...,(?}, where Gi

.

A

of constructing an n-rowed square matrix whose characteristic matrix has prescribed invariant factors is completely solved by the result we state as

Theorem

9.

Let g(x)

=

xn

(bix*-

1

010 00 000

+

.

.

.

+ bn

)

and

1

(32)

bn Then g(x)I

b n _i b n

is both the characteristic

and

the

the only nontrivial invariant factor of xl

minimum function

of A, g(x) is

A.

For x

-1 x

...

-1

...

(33)

...

x

-1

62

x

61

INTRODUCTION TO ALGEBRAIC THEORIES

106

& n of (33) is an (n The complementary submatrix of the element 1)1 and its derowed square triangular matrix with diagonal elements all ~ terminant is (-I)"-1 Thus the cofactor of -6n is (-l) n+ 1 (-l) n 1 = 1 and hence dn -\(x) = 1. It remains to prove that dn (x) = \xl A\ = g(x). A = x bi. This is true if n = 1, since then A = A\ = (61), and \xl 1 rows, so that Let it be true for matrices A n _i of the form (33) and of n 1 n~2 = .

\

A n-i\

\xl

first

bn

=

z""

+

(bix

.

+ &n-i) is the cofactor of the element

.

.

row and column of (33). We now expand (33) according to n~ l n~ 2 column and obtain \xl + + 6n-i)] (b\x A\ = x[x

x in the

first

.

its

.

.

g(x) as desired. This proves our theorem.

The whose

A with complex number elements have prescribed elementary divisors has a see that the argument preceding Theorem 9

construction of square matrices characteristic matrices

simple solution, and we shall reduces the solution to the proof of Theorem 10. Let c be a complex number, c

be the n-rowed square matrix

1

c

(34)

A

1

000 000

c

1

c

A is (x c) n Then the only nontrivial invariant factor of xl A is a triangular matrix with diagonal elements all x c, For xl n The c) complementary minor of the element in the \xl A\ = (x A is a triangular matrix with diagonal nth row and first column of xl n elements all unity, dn-i(x) = 1, and dn (x) = (x c) is the only nontrivial .

.

invariant factor of A.

n are positive inc are complex numbers and ni, Thus if Ci, we construct matrices Aj of the form (34) for c = c, and with rc A ] then has n rows, and its charrows. The matrix A = diag {Ai, B }, where Bi = xl ni Ai is A = diag {Bi, acteristic matrix xl c n But equivalent in F[x] to diag {/, !,...,!} such that / = (x then xl A is equivalent in F[x] to diag {/i, ...,/,!,...,!}, and by Theorem 3 the nontrivial elementary divisors of xl A are /i, ...,/* as .

.

.

,

.

t

.

.

,

t

tegers,

;

.

.

.

t

,

.

.

.

,

t

t-)

desired.

.

POLYNOMIALS WITH MATRIC COEFFICIENTS

107

EXERCISES invariant factors and elementary divisors of the characteristic

Compute the

1.

matrices of the following matrices.

-6

-5 -19\

2

2

5

1

-2

0-5

1

3-12

2.

B =

diag {Bi,

.

.

.

,

B

similar in

t]

F

1,

to each of the matrices of

respectively,

Solve Ex. 2 with the characteristic function of Bi mentary divisor of A, Bi of the form (34). 3.

7.

Additional topics. There are

matrices other than those to

9^

where Bi has the form (32), and the characteristic function the ith nontrivial invariant factor of A.

Ex. is

Find a matrix

1

now

many important

we have

discussed,

of

Bi

the ith nontrivial ele-

topics of the theory of

and we leave

their exposition

more advanced texts. Let us mention some of these topics here, however. The quantities of the field K of all complex numbers have the form c

where

R

is

jugate of c

the

field of all real

=

a

+

(a, b

bi

in R, i2

=

1)

,

numbers, a subfield of K. The complex con-

is

c

=

a

bi

,

> c defines a and the correspondence c < self-equivalence or automorphism This of K, a fact verified in Section 6.9. automorphism of K leaves the

elements of

then

may

its

subfield

call it

R

unaltered, that

an automorphism over

jR.

is,

a

=

a for every real

a.

We

INTRODUCTION TO ALGEBRAIC THEORIES

108

If A is any m by n matrix with elements a a in K, we define A to be the It is then m by n matrix whose element in its ith row and jth column is a,-/.

a simple matter to verify that

Z5 = IS

(J)'

,

=A

R=

7 ,

()-*

,

WS

for every A, B, and nonsingular C. Moreover, then (JHB)' = now define a matrix to be Hermitian if JF = A, skew-Hermitian

We A if JF = A. Two matrices A and B are said to be conjunctive in K if there exists a nonsingular matrix P with elements in K such that 7

.

The results of this theory are almost exactly the same as those of the theory of congruent matrices, and it is, in fact, possible to obtain a general theory including both of the theories above as special cases.

Two symmetric matrices A and B with elements in a field F are said to be orthogonally equivalent in F if there exists an orthogonal matrix P with elements in F such that PAP' = B. But PP' = P'P = / so that B = PAP~ l is both similar and congruent to A. Analogously, we call a matrix P with complex elements such that PP 7 = P 7 ? = /, a unitary matrix. Then we say that two Hermitian matrices A and B are unitary equivalent if PAP7 #, where P is a unitary matrix. Both of these concepts may also be shown to be special cases of a more general concept. Finally, let us mention the topic of the equivalence and congruence of pairs of matrices. Let A, B C, D be matrices of the same numbers of rows and columns. Then we call the pairs A, B and C, B equivalent* pairs if there exist nonsingular square matrices P and Q such that simultaneously PAQ = C and PBQ = D. Similarly, if A, B, C, D are n-rowed square y

matrices,

we f

A, B and C, D congruent pairs D for a nonsingular matrix P.

call

C and PBP =

if

simultaneously

PAP' =

References to treatments of the topics mentioned above as well as others be found in the final bibliographical section of Chapter VI. We shall not state any of the results here. will

*

In this connection see Exs. 3 and 4 of Section

5.

CHAPTER

VI

FUNDAMENTAL CONCEPTS 1. Groups. These pages were written in order to bridge the gap between the intuitive function-theoretic study of algebra, as presented in the usual course on the theory of equations, and the abstract approach of the author's

Modern Higher

Algebra. The objective of our exposition has now been atFor our study of matrices with constant elements led us naturally to introduce the concepts of field, linear space, correspondence, and equivalence, and we are ready now to begin the study of abstract algebra. Howtained.

ever, we believe it desirable to precede the serious study of material such as that of the first two chapters of the Modern Higher Algebra by a brief

We

discussion of this subject matter, without proofs (or exercises). shall give this discussion here and shall therewith not only leave our readers with an acquaintance with the basic concepts of algebraic theory but with a

knowledge of how these concepts

may lead into those branches of mathematics called the Theory of Numbers and the Theory of Algebraic Numbers. Our first new concept is that of a set G of elements closed with respect to a single operation, and we wish to define the concept that G forms a group with respect to this operation. It should be clear that if we do not state the nature either of the elements of G or of the operation, it will not matter if we indicate the operation as multiplication. If we wish later to consider special sets of elements with specified operations we shall then replace "product" in our definition make the

A

by the operation

G

set DEFINITION. of elements a, b, c, respect to multiplication if for every a, b, c of

I.

II.

III.

The product ab

The

is

.

.

.

desired.

is said to

Thus we

shall

form a group with

G

in G;

associative law

a (be)

=

(ab)c holds;

G of the equations

There exist solutions x and y in

ax

=

b

ya = b

,

.

The reader is already familiar with the groups (with respect to ordinary multiplication) of all nonzero rational numbers, all nonzero real numbers, 109

INTRODUCTION TO ALGEBRAIC THEORIES

110

and, indeed,

groups

G

all

nonzero elements of any

such that for every a and 6 of

IV. The products ab

Such groups are

=

ba

all

examples of

.

called commutative or abelian groups.

An

example of a

the group, with respect to matrix muln-rowed square matrices with elements in a nonsingular

nondbelian (noncommutative) group tiplication, of all

These are have

field.

G we

is

field.

Every group G contains a unique element such that for every a of G ae

(1)

Moreover, every element a of

Then the

=

=

ea

G has a

aar 1

(2)

=

x

=

ar l b

.

1 unique inverse a" in

ar l a

solutions of the equations of

(3)

a

e called its identity element ,

=

e

G

such that

.

Axiom

III are the unique elements

,

A set H of elements of a group G is called a subgroup of G if the

product

any two elements of H is in H, H contains the identity element of G and the inverse element h~ l of every h of H. Then H forms a group with respect to the same operation as does G. The equivalence of two groups is defined as an instance of the general definition of equivalence which we gave in Section 4.5. The concept of equivalence of two mathematical systems of the same kind as well as the of

concept of subsystem (e.g., subgroup of a group, subfield of a field, linear subspace over F of a linear space over F) are two concepts of evident funda-

mental importance which are given in algebraic theory whenever any new mathematical system is defined.

The number

of elements in a group

G

is

number is number n, and

called its order. This

and we call G an infinite group; or it is a a finite group of order n. For finite groups we have the important result which we shall state without proof. * either infinity,

we

call

finite

G

LEMMA

1.

Let

H

be

a subgroup of a

finite

group G. Then

the order of

H

divides the order of G.

A

simple example of a finite abelian group is the set of all nth roots of unity. The reader may verify that an example of a finite nonabelian group *

The proof

is

given in Chapter

VI

of

my

Modern Higher

Algebra.

FUNDAMENTAL CONCEPTS

111

given by the quaternion group of order 8 whose elements are the tworowed matrices with complex elements,

is

'T

f

(4)

set of all

-1\

/O

BD

-A,

-i,

[AB, The

0\

/

A

Mo-;)'

-(i

o)'

-AB.

-B,

powers a

(5)

=

of an element a of a group

e,

G

or 1 a2 cr2

a,

,

,

.

,

.

.

forms a subgroup of

G

which we

shall desig-

nate by (6)

[a]

and

shall call the cyclic group generated by a. Its order is called the order of

can be shown that either

the element

a and

and a has

infinite order, or

distinct

it

a has

all

order

finite

the powers

ra,

and

[a]

(5) are distinct

consists of the

m

powers

(7)

e, a,

a2

a'TO 1

.

.

.

,

,

1

m

the identity element of [a], a m = e. Then the order of a is the least integer t such that a* = e. Moreover, it can be shown that a* = e if

where

e is

and only

if

m divides

since

m is

n = mq, a n =

LEMMA

t.

m

of an element of a finite group G divides the order of G, the order of the subgroup [a], and we may apply Lemma 1. Thus

The order

2.

(a

m

q )

=

Let e 66

eq

2/ie

=

e.

We

therefore have

identity element of a group

an

(8)

=

G

o/ order n. Tften

e

/or et;en/ a of G. 2.

Additive groups. In any field and in the set of all n-rowed square matThus we have said that the set of all nonzero

rices there are two operations.

field and the set of all nonsingular n-rowed square matrices form multiplicative groups. But the elements of any field, the set of all m by n matrices with elements in a field, the elements of any linear space, all form additive groups, that is, groups with respect to the operation of addition as defined for each of these mathematical systems. The reader will observe that the axioms for an additive abelian group G are those axioms

elements of a

INTRODUCTION TO ALGEBRAIC THEORIES

112

which we gave in Section 3.12 for a field. Additive groups are normally assumed to be abelian, that is, the use of addition to designate the operation with respect to which a group G is defined is usually taken to

for addition

connote the fact that G is abelian. The identity element of an additive group such that a element, that is, the element verse with respect to addition of a

a

+

=

a)

(

=

+a

a)

(

Thus

0.

its zero

usually called

is

=

+

=

a

+

The

a.

in-

a and is such that designated as the solutions of the additive formulais

tion

a

(9)

+x=

of the equations of our group

z

(10)

When G b

a.

is

abelian,

Thus we

= (-a)

b

Axiom

+

a

=

6

+

b

,

III are

=

y

6,

we have x

+

y

,

(-a).

y and designate their

common

value by

define the operation of subtraction in terms of that of addi-

tion.

In a cyclic additive group (11)

0, a,

where, clearly, define

a

ra)

(

m

if

is

=

any (m

[a]

the elements are always designated

-a, 2-

a,

-(2

a),

positive integer a).

Here

m

.

.

.

(m

m

,

a)

a does not

by

=

m

mean

(

a),

and we

the product of a

but means the sum a a with m sumgroup of order m, the elements of [a] are 0, a, 2a, (m 1) a, and m is least positive integer such that the sum of m summands all equal to a is zero. However, if [a] is infinite, then it may be seen that n a = q a for any integers n and q if and only if n and q are

by the

mands. .

.

.

positive integer If [a] is

a

+

.

.

.

+

finite

,

equal. 3.

Rings.

The set consisting of all n-rowed square matrices with elements

ring.

F is an instance of certain type of mathematical system called a Many other systems which are known to the reader are rings and we

shall

make

in a field

the

A

ring is an additive abelian group of at least two distinct elements such that, for every a, b, c, of R,

DEFINITION.

I.

The product ab

is

in

R;

II.

The

associative law a(bc)

=

(ab)c holds;

III.

The

distributive laws

+

c)

a(b

=

ab

+ ac,

(b

+

c)a

= ba

+

ca hold.

FUNDAMENTAL CONCEPTS We leave

113

to the reader the explicit formulation of the definitions of sab-

ring and equivalence of rings. They may be found in the first chapter of the Modern Higher Algebra. The reader should also verify that all nonmodular

are rings, the set of all ordinary integers is a ring. zero element of a ring R is its identity element with respect to addition. Observe that by making the hypothesis that R contains at least two fields

The

elements we exclude the mathematical system consisting of zero alone from the systems we have called rings. Rings may now be seen to be mathematical systems R whose elements

have

all the ordinary properties of numbers except that possibly the prodab ucts and ba might be different elements of R, the equations ax = b of

ya

=

ea

=

b might not have solutions in R if a ^ 0, b are in R. A ring may also contain divisors of zero, that is, elements a 9* 0, c ^ such that ac = 0. In particular, the ring of all n-rowed square matrices has already been seen to have such elements as well as the other properties just mentioned. A ring is said to possess a unity element e if e in R has the property

ae

=

a for every a of R. The element

ordinary number

1

and

element of the set of

is

e

then has the properties of the

usually designated

by that symbol. The unity

n-rowed square matrices is the n-rowed identity matrix, and the unity element was always the number 1 in the other rings we have studied. However, the set of all two-rowed square matrices of the form all

/O

r\

\o

o;

(12)

with

may easily be seen to be a ring without a unity element. In nonzero elements of this ring are divisors of zero. A ring R is said to be commutative if ab = ba for every a and 6 of R. The ring of all integers is a commutative ring, the ring of all n-rowed square matr rational

fact, all

rices

with elements in a

field

F

4.

Abstract fields. If

R

any

is

is

a noncommutative ring.

ring,

we

shall designate

by

R* * all nonzero elements of R. Then we shall call R a division ring if R* is a multiplicative group. This occurs clearly if and only if the equations ax = 6, ya = b have solutions in R* for every a and 6 of R*. The set of all

the set of

n-rowed square matrices

is

not a division

ring.

However,

let c

and d range

INTRODUCTION TO ALGEBRAIC THEORIES

114 over

all

Then

complex numbers, 5 and d be the complex conjugate of Q of all two-rowed matrices

A =

(13)

and

d.

*

ft

c

\a is

c

the set

a noncommutative division ring. The reader should verify

A ^

in particular that every

=

and \A\

or d j

c 7*

order 4 over the

this, noting nonsingular since A 9^ implies that dd > 0. The ring Q is a linear space of

is

cc

+

numbers and

field of all real

has the matrices

it

I,A,BjAB

of (4) as a basis over that field. It is usually called the ring of real quaternions.

Until the present we have restricted the term "field" to mean a field containing the field of all rational numbers. We now define fields in general.

DEFINITION.

A

field is

a ring

F

such that

F*

is

a multiplicative abelian

group.

The

identity element of the multiplicative group F* is then the unity 1 of F. The whole set F is an additive group with identity element

element 0,

and

generates an additive cyclic subgroup [1]. If this cyclic group has may be shown to be equivalent to the set of all ordinary

1

infinite order, it

But F

is closed with respect to rational operations, and [1] then of F equivalent to the field of all rational numbers. We a subfield generates call all such fields nonmodular fields. The group [1] might, however, be a finite group. Its elements are then

integers.

the sums 1

(14)

where p 1

+1+

is .

prime, and fields

.

.

.

.

.

p

,

-

1

,

we have the property that the sum with p summands is zero. It is easy to show that p is a a with a follows that if a is in F, then the sum a

it

F

+

1

is

equal to the product (1

+ + + + 1)0 = 0. We .

modular fields of

the characteristic of

all

+1+ may

characteristic p. It

subfields of a field

in fact, every subfield of

ment

0, 1, 2,

the order of this group, and

p summands such

=

F

.

.

F and, the unity ele-

the same as that of

is

F contains the subfield

call

easily be shown that

generated by

y

F

under rational operations. commutative ring with a unity element and withIntegral domains. out divisors of zero is called an integral domain. Any field forms a somewhat of

A

5.

example of an integral domain. Less trivial examples are the set x q ] of all polynomials in F[x] of all polynomials in x, the set F[XI, in a field . both . x and coefficients (in F, the set of all ordinary 1, cases) , q

trivial

.

.

.

.

,

FUNDAMENTAL CONCEPTS The

integers.

set of all integers

may be extended

115

to the field of all rational

numbers by adjoining quotients a/6, 6/^0. In a similar fashion we adjoin in J to imbed any integral domain J in a field. quotients a/6 for a and b ^ When we studied polynomials in Chapter I we studied questions about divisibility and greatest common divisor. We may also study such questions about arbitrary integral domains. Let us then formulate such a study. Let J be an integral domain and a and 6 be in J. Then we say that a is divisible by

a

=

b (or that b divides

u

If

be.

Thus u is a

in

J

divides

unit of

its

a)

if

there exists an element c in

unity element

J if it has an inverse

1,

then u

The

in J.

is

J such that

called a unit of J.

inverse of a unit

is

clearly

also a unit.

Two quantities b and 6 Then

b

and

6

are said to be associated

are associated

and only

if

6

if

=

if

each divides the other.

bu for a unit

u.

Moreover,

b divides a so does every associate of b. Every unit of J divides every a of J. Thus we are led to one of the most important problems about an inteif

gral domain, that of determining its units. quantity p of an integral domain J is called a prime or irreducible quanis not a unit of J and the only divisors of tity of J if p p in J are units and

A

^

associates of p. of J is an a

Every associate of a prime is a prime. which is neither a prime nor a unit of

^

to ask whether or not every composite a of

a

(15)

for a finite

whenever

number

also

a

=

of primes

qi

.

.

.

=

pi

p of

.

J.

qa for primes

some

.

.

J may be

It is natural

then

written in the form

pr

We may #,-,

A composite quantity J.

also ask

then necessarily

if it is

s

=

r

true that

and the

qi

When

these properties hold we may call J a unique factorization integral domain. The reader is familiar with the fact that the set of all ordinary integers is such an integral domain. This

are associates of the p/ in

order.

fact, as well as the Xij

.

.

.

,

corresponding property for the set of all polynomials in x n with coefficients in a field F are derived in Chapter II of the

Modern Higher Algebra. The problem of determining a

author's

g.c.d. (greatest

common

divisor) of

two

elements a and b of a unique factorization domain is solvable in terms of the factorization of a and 6. However, we saw that in the case of the set F[x]

may be found by a Euclidean process. Let us then formulate the problem regarding g.c.d. 's. We define a g.c.d. of two elements a and b not both zero of J to be a common divisor d of a and b such that every common divisor of a and 6 divides d. Then all g.c.d. s of a and b are associates. We call a and b relatively prime if their only common divisors are units of J,

the g.c.d.

;

INTRODUCTION TO ALGEBRAIC THEORIES

116

is, they have the unity element of J as a g.c.d. We now see that one of the questions regarding an integral domain J is the question as to whether every a and b of J have a g.c.d. Moreover, we must ask whether there exist

that

x and y in

J

such that

=

d is

d

ax

+

by

common divisor and hence a g.c.d. of a and b; and finally whether or not may be found by the use of a Euclidean Division Algorithm. a

M

of a ring R is called an Ideals and residue class rings. A subset and a of R. contains g R if h, ag, ga, for every g and h of Then either consists of zero alone and will be called the zero ideal of R, or may be seen to be a subring of R with the property that the products 6.

ideal of

M

am,

M

M

M

ma of any element m of M and any element a of 1? are in M. H is any set of elements of a ring J?, we may designate by {H\

If

the set

sums of elements of the form xmy for x and y in #, m show that {H} is an ideal. If H consists of finitely m of jR, we write {H} = {mi, m/}, and if H many elements mi, consists of only one element m of R we write consisting of all finite in H. It is easy to .

.

.

,

.

t

.

.

,

y

M=

(16)

{m}

most important type of an ideal is called a principal ideal. It consists of all finite sums of elements of the form amb = {m} consists of all for a and 6 in R. When J? is a commutative ring, am for a in R. products for the corresponding ideal. This

M

The

ring

rived from

R

itself is

an

ideal of

R

the fact that in the case

called the unit ideal. This

where R has

a unity

term

de-

is

quantity R =

{

1

}

.

Evidently {0} is the zero ideal. be an ideal of R and define Let

M

o

(17)

s

6

(M)

a congruent b modulo M) if a b is in M. We may then define for every a of R. We put into the shall call a residue class g of class every b in R such that a = 6 (M). Clearly a = b (M) if and only if b 33 a (Af). Moreover, if a c in Af, then (a 6 is in and b 6) = = a in M. 6 c is It follows that c) (6 (a and b are the same resig due class) if and only if b is in g. (read:

M M

what we

+

Let us now define the sum and product of residue (18)

g

+b=

a

+b

,

g

b

= a-

classes

b

.

by

FUNDAMENTAL CONCEPTS may be = 06. aifri

verified readily that

It

if

a\

=

our definitions of

It follows that

=b

g, 61

,

117

then ai

+

b\

sum and product

=

a

+ b,

of residue

M

classes are unique. Then it is easy to show that if is not R the set of all the residue classes forms a ring with respect to the operations just defined. We call this ring the residue class or difference ring (read: R minus

R M M = R the residue classes are the zero and we have not called set a M an integral domain, we the When the residue ring R ideal M a prime ideal of R. We Ma ideal of R R M M has only a a These concepts coincide the case where R M). When

all

this

class,

ring.

class

call

is

divisorless

call

is

if

in

field.

finite

number of elements since it may be shown that any integral domain with a finite number of elements is a field. This coincidence occurs in most of the topics of mathematics (in particular the Theory of Algebraic Numbers) where ideals are studied.

7.

The

ring of ordinary integers.

which we

The set

shall designate henceforth

and we

gral domain,

by

of all ordinary integers is a ring

E. It

is

easily seen to be

an

inte-

prove that

it

has the property of unique factori-

that the units of

E

are those ordinary integers u such 1 and 1 are the only units of E.

shall

zation.

We

observe

that uv

=

1

first

for

an integer

But then

v.

Thus the primes of E are the ordinary positive prime integers 2, 3, 5, etc., and their associates 5, etc. Every integer a is associated with 3, 2, its

absolute value

^0. We

a |

\

note

now

that

if

b is

any

integer not zero,

the multiples (19)

0,

-|6|,2|&|, -2|6|,...

|6|,

are clearly a set of integers one of which exceeds* any given integer a. Then let (g 1) |6| be the least multiple of |6| which exceeds a so that - g\b\ = r such that < r < \b\. put 1)|6| > a, a g\b\
+ +

We

= giib > Qj q = g otherwise, and have g\b\ =
q

.

|

|

|

\

have thus proved the Division Algorithm for E, a result we state as Theorem 1. Let a and b ^ be integers. Then there exist unique 6 a = bq + r. q and r such that

0
We now

1

1

leave for the reader the application of the Euclidean process,

which we used to prove Theorem *

integers

,

We use the concept of

1.5, to

our present case. The process yields

magnitude of integers throughout our study of the ring E.

INTRODUCTION TO ALGEBRAIC THEORIES

118

Theorem and b such

Let

2.

f

and g

d

=

and

g.

(20)

a and

is

positive divisor of both f

there exist integers a

+ bg

af

Then d

is the

g.c.d.

of f

prime

to g.

unique positive

g.

The result above implies Theorem 3. Let f, g, h be

integers such that

Then f divides h. For by Theorem 2 we have af + bg gh

Then

be nonzero integers.

that

= /g,

A = (ah then have

We

Theorem

+

bq)f

is

divisible

=

1,

afh

divides

f

gh and

+ fy/A = h.

is

But by hypothesis

by /.

Let p be a prime divisor of gh. Then p divides g or h. For if p does not divide gr, the g.c.d. of p and g is either 1 or an associate of p. The latter is impossible, and therefore p is prime to g.

We

also

4.

have

Theorem

Let

5.

m

be

an

Then

integer.

the set of integers

prime

to

m

is

closed with respect to multiplication.

For let a and b be prime to m and d be the g.c.d. of ab and m. If a6 is not prime to m we have d > 1, and by Theorem 3 if d is prime to a it divides 6. But then a divisor c > 1 of d divides a or b as well as m contrary to hypothesis.

We may now conclude our proof of what mental Theorem of Arithmetic. Theorem

Every composite integer a

6.

a

(21)

=

is

sometimes called the Funda-

is expressible

in the form

pi...p r

uniquely apart from the order of the positive prime factors pi, For if a = 6c, every divisor of b or of c is a divisor of a. If a .

has divisors b such that

it

1

<

b

<

|a|,

and there

.

.

,

is

pr

.

composite,

exists a least divisor

But then pi is a positive prime, a = p\Oz for \a^\ < \a\. If Oz is a prime, we write a 2 = pz with p 2 a positive prime and have (21) for r = 2. Otherwise a* is composite and has a prime divisor p% by the proof above, a 2 = p 2a 3 and a = pip 2 a 3 f r a s| < |aa| After a finite number of

Pi

>

1 of a.

.

l

>

stages the sequence of decreasing positive integers |a| .

.

must terminate, and we have

.

primes qi

.

.

forj

.

gi, g..

=

1,

(21). If also

a

=

qi

.

.

|a 2 .

q,

|

>

|as|

>

for positive

pr = uniquely determined by a, and p\ = Then either we may arrange the q* so that gi pi, or pi ^ g/ s. But if the divisor pi of qi q8 is not equal to gi, it does .

.

.

.

.

.

,

,

g, the sign

is

.

.

.

.

.

.

FUNDAMENTAL CONCEPTS

119

not divide qi and by Theorem 4 must divide q z q 8 By our hypothesis it does not divide # 2 and must divide g 3 qa This finite process leads to .

.

.

.

.

.

.

.

a contradiction. Thus pi = gi, p2 ... p r = ?*... ?, and the proof just completed may be repeated, and we may take p 2 = q*. Proceeding simi-

we ultimately obtain

larly,

r

=

=

the p

s,

qi for

an appropriate ordering*

of the q^

The

8.

ideals of the ring of integers. Let

E of all integers and m be

M be a nonzero ideal of the M M

the least positive integer in Then contains every element qm of the principal ideal {m}. If h is in M, we may use Theorem 1 to write h < r < m. But mq and h are r where mq set

M M, that every element of M in

mq =

/i

r is in

.

+

Our

.

m implies that r =

definition of

Theorem The residue

classes of

E

modulo {m} are now the

(22)

For

0, 1,

a

if

is

Then a

any

r is in

integer,

{m}

a

;

.

.

.

defined for is

m>

1

the class

is

the class

m

is 1.

1 of all

,

m-

I

,

m a positive integer,

classes

.

we have a = mq + r for r = 0, 1, r. Thus the elements of the residue

.

=

Eelement

and thus

We

in {m}. have proved 7. TTie ideals of E are principal ideals {m} is

,

m

1.

class ring

{m}

are given by (22). Then of all integers divisible integers

.

.

E

{m}

is

a ring whose zero

by m and whose unity element

whose remainder

Theorem

in

1

on division by

is an integer prime to m, the elements of the residue class a are prime to m. For by Theorem 2 there exist integers c and d such that

a

If

ac

(23) If 6 is in a,

ac

+ md

=

then b 1,

=

a

+

mq, be

and therefore

6

+ md =

1

+ m(d

and

m

.

qc)

=

ac

+ m(qc +

classes a in a abelian form multiplicative group. If m is a composite integer cd where

E >

c

d

qc)

=

c

=

{m} defined for a prime

to

m

m>

d,

are relatively prime.

and Theorem 7 implies Theorem 8. The residue

all

1,

>

d

1,

then

But a

m>

c,

1,

and d are both not the zero class. But C'd = cd = m = Q, E {m} has divisors of zero and is not an integral domain. If m is a prime, then * We may order the p so that pi ^ p 2 ^ ^ p and similarly assume that ^ ^ 7.. Then we obtain r = 5, p, = & for i = 1, ^ r. 02

and

c

{

.

.

.

.

.

.

r

.

.

.

,

INTRODUCTION TO* ALGEBRAIC THEORIES

120

m is

prime to w, and Theorem 8 states that E {w} is a proved Theorem 9. An ideal of E is a prime ideal if and only ifM. = {p} for is a divisorless ideal. a positive prime p, We observe now that a = 6 (M) for = {m} means that a b = mq, b is divisible by m. Thus it is customary in the Theory of Numthat is, a

every a not in

We have

field.

M

M

M

bers to write

a

a

(24)

b

(mod m)

a congruent 6 modulo m) if a 6 is divisible by m. But then a = 6 + das well as g == c and if we also have d, we will have g + c 6 d. Hence if (24) and (read:

c 3=

(25)

hold,

=

6,

c

=

d (mod m)

we have

+cs6+d

a

(26)

Thus the

rules (26) for

tions of addition

(mod m)

=

ac

,

6d (mod m)

.

combining congruences are equivalent to the

and multiplication

in

E

defini-

{m}.

We next state the number-theoretic consequence of Theorem 8 and Lemma 2

which

Theorem

m>

Theorem and which we state as number of positive integers not greater than m. Then if a is prime to m we have

called Euler's

is

10. Let f (m) be the

and prime

to

For /(m)

rem

s

af

(27)

8.

Our

is

1

(mod m)

.

clearly the order of the multiplicative

result then follows

from

Lemma

We next have the

Fermat Theorem.

Theorem

pbea

11. Let

prime. Then

ap

(28)

group defined in Theo-

2.

=

a (mod p)

for every integer a.

For (28) holds if a is divisible by p. Otherwise a is prime to p, and a is 1 and by one of the residue classes 1,2,..., p 1. Thus f(p) = p 1 l p = a a Theorem 10 aP~ 1 is divisible by p, a(o^~ is also di1) visible

The *

by

p.

ring

This

E

field is

{p} defined

by a

positive prime

equivalent to the subfield generated

of characteristic p.

by

its

p

is

a field*

P

whose

unity quantity of any

field

FUNDAMENTAL CONCEPTS P*

121

1. The elements p of P* are the distinct roots of the equation I and are not all roots of any equation of lower degree. Then it may be shown that P* is a cyclic " r p 2 are multiplicative group [r] where r is an integer such that 1, r, rf a complete set of nonzero residue classes modulo {p Such an integer r is

nonzero elements form an abelian group

of order

~~ xp l

=

.

,

}

called a primitive root

Theorem integer t

modulo

p be a prime

12. Let

t

For p

=

.

,

then have

of the

form 4n

+

Then

!

there exists

an

such that

(29)

t*

We

p.

.

.

1

r -i, t*

=

-

4n,

2

+1a

(mod

p)

.

and we let r be a primitive root modulo

- (P + 1)(P - 1), ft = r^y* I since r is

1

(

+

!)(

-

1)

=

p,

t

=

rn.

in the field

Then

E-

=

as desired. However, primitive, ^ + 1 There is a number of other results on congruences which are corollaries of theorems on rings and fields. However, we shall not mention them here. {p}.

is

9. Quadratic extensions of a field. If a linear space u\F u n F over F,

+

.

.

.

F

is

a subfield of a field

we say

that

K

is

a

K which

field of degree

n over F. The theory of linear spaces of Chapter IV implies that Ui may be taken to be any nonzero element of K. Hence we may take Ui to be the unity element 1 of F. Then if n = 1, the field K is F. We call K a quad= 2, 3, 4, or 5. ratic, cubic, quartic, or quintic field over F according as n Let n = 2 so that K has a basis u\ = 1, u 2 over F. The quantities of K are then uniquely expressible in the form fc = c\ + c 2 u 2 for ci and c 2 in F, and fc is in F k = fc 1 + Ow 2 if and only if c 2 = 0. Clearly, if k is in F, then 1, fc do not form a basis of X over F. We now say that a quantity u in K generates K over F if 1, u are a basis of K over F. Then u generates K over F if and only if u is not in F. For if 1, u are linearly dependent in F we for a 2 7* 0, u= have ai + a zu = o^ a\ is in F. The elements k of a quadratic field have the property that 1, fc, fc2 are 2 = for c ci, c 2 not all zero and linearly dependent in F, cofc + cjc + c 2 = -c^ 1 is in F, fc is a root = in F. If c 0, then Ci cannot be zero, and k 2 with coefficients in F. If fc is not in F, of the monic polynomial (x fc) then Co T^ 0, fc is a root of a monic polynomial of degree two. Thus evgry ,

)

l

,

element

fc

of a quadratic field

(30)

with (31)

f(x, T(fc)

and N(k)

fc)

=

a root of an equation

is

x2

-

T(k)x

in F. In particular, u*

-

bu

+ N(k)

if

=

u generates

+c=

K

over

F we have

INTRODUCTION TO ALGEBRAIC THEORIES

122

and we propose to find the value of T(K) and N(k) as polyand the coordinates fci and fc 2 in F of k = fci + fc2W. Define a correspondence S on K to X by

for b

and

c in F,

nomials in

b, c

=

k

(32)

fci

+ to -

fc

=

s

+ k us

ki

2

,

in F where us is in K. Then (32) is a one-to-one corres and itself if and only if u generates K over F. If fc = spondence 8 in F have we k + fco = (fci + fcs) + k$ + k^u fcs + kiu for fca and ki kfi s = 5 and we have fci + fcs + (fca + fcOu (fc 2 + fcOw, so that (fc + fc )

for all

and

fci

of

fc 2

K

,

,

(33)

(fc

Also

fcfco

=

fcifcs

+

while

u,

(fci&4

ks

kH

=

+

)

fc 2 fc 4

z equation x

if

(u

s

bx

=

2

)

+

bu s

=

c

distinct roots in a field

c,

5

=

that

is,

over

us

or

u

6

of

K

(fcifc 4

of the quadratic

is 6,

.

K

F

of

fc.

In either case

F

unaltered and

K.

K were any field of degree n over F and F

a root in

is

> the identity correspondence fc < of the elements leaving

defines a self-equivalence of is called an automorphism over If

fc 2 fc 4

(fcifcs

of the roots

us = u

S is

2

But the quadratic equation can have only two

0.

(35)

In the former case

.

)*.

K, the sum

$

+ kj

fcifcs

(fcfco)

and only

ks

u = + kjc^u + + c) + + (fcifo + k^k^u3 + kJd(u8 But then

(34) if

=

s

fc

if

S and T were automorphisms

define ST as the result fc then k s > (fc s ) r It is easy to

K, we would

>

k ST

=

"

8

2

of applythat the set of all (fc

)

first k>k and show is a group G with respect to the operation just automorphisms over F of defined. In case G has order equal to the degree n of K over F it is called the Galois group of K over F, and that branch of algebra called the Galois Theory is concerned with relative properties of K and G. In our present s 2 case u s = (u s ) s = (b u) = b (b u) = u so that S is the identity = = w u if and only if 2w 6, which is not possible automorphism. But b since u is not in F unless K is a modular field in which u + u = 0. Hence if is a nonmodular quadratic field over F, the automorphism group of K over F is the cyclic group [S] of order 2 and is the Galois group of K.

s

ing

.

K

*

K

We u)]

=

(36)

see k\ +

now

that

fcifc 2 6

+

if

fc

=

u).

fc|u(6

T(fc)

+

fci

=

fc

+

fc 2

u,

5 fc

,

fcfc^

=

w2 =

c.

then

But bu

N(k)

=

(fci

+

Hence

kk s

,

fc 2 u)[fci

if

-f

fc 2

(6

FUNDAMENTAL CONCEPTS

123

we have

=

T(k)

(37)

+kb

2fci

t

and the polynomial of

(30) is

(38)

/(*,

=

fc)

The function T(k) is called the Moreover, we may show that

+

T(ajc

(39)

a 2 fc

=

)

for every ai and a 2 of F a fc s =

+

(aifc

2

where u

now assume

satisfies (31).

a 2 r(fc

+

-

ks)

+ ^Jc + =

)

=

+ fakj)

,

.

is

called the

N(kk Q ) = N(k)

,

T(aifc

=

(hkj!

kk Q (kko) s

k\c

and N(k)

s

a 2 fc

desired. Similarly,* N(kk Q ) 2 if fc is in F, then JV(Jfc) = fc

Let us

fc)(x

k\

and fc and fc of K. For

+

ajc

)

-

(x

trace of k,

+

aiT(fc)

=

N(k)

,

ai(fc

kk Q k s k$

norm

of

fc.

N(k Q )

+ asfco) = (ifc + a + + ks + 02(^0 + kfi) as 2 fc )

)

=

s

(kk )(k Q k$).

Note that

.

that the field

Then

K

is

K is nonmodular so that K by the root u

also generated

= F

+

uF

%b of the

equation

z2

(40)

=

a

(a in

F)

,

2 = & 2 /4 = a = (w u2 bu c 6 2 /4. Let us then assume with6/2) out loss of generality that u is a root of (40) so that in (31) we have 6 = 0, a. Then (37) has the simplified form given by c =

T(k)

(41)

Now if a = The in F.

d? for

F and w

not in

fc 2

+

+

if

For

if

(x )x, fc(w)

ring F[u] of all 2 equation x

F

+ d^O, K now u

is

=

,

N(k)

=

d^O.

=

d2 (u ,

k\

-

k\a

+ d) (u

.

d)

=

0,

whereas u

is

impossible in a field. of all consist polynomials in u with coefficients

This

is

any polynomial in F[x], we may write k(x) = ki(x ) + fci(a) + ki(a)u. Thus every nonmodular quadratic field is the polynomials with coefficients in F in an algebraic root u of an

k(x)

=

2*i

d in F, we have u2

quantities of

2

and

=

2

is

a where a

is

in F, a is not the square root of any quantity of F, is a field, it is actually the field F(u) of all

nonmodular. Since

K

u with coefficients in F. the nonmodular field F and the equation x 2 defined. For we may take

rational functions in

Conversely, given, then

K

if

is

"(?;)

<

*

The

trace function

cative function.

is

=

a in

F

are

" (;

)

thus called a linear function and the norm function a multipli-

INTRODUCTION TO ALGEBRAIC THEORIES

124

identify F with the set of all two-rowed scalar matrices with elements F (so as to make K contain F). Then every polynomial in u has the form = k = 0. if and only if ki = k = ki + k*u and N(k) = k\ - k\a = 2 2 = then we a to But For otherwise 2 7^ 0, (fti/if ) contrary hypothesis. k for of take K = F + uF and have fc~ = (fc? 2 u) kla)' every

and

in

fc

1

fc

l

K. Hence

K

is

the field

1

F(u). That

K

is that of F. unity element of over a nonmodular field fields

K

We

K

F

^

fc

nonmodular is evident since the have thus constructed all quadratic is

in terms of equations x 2

=

a for a in

2

F, a 7^ d for any d of F. Observe in closing that

such that

fc

7^

is

in F.

if

But

K=

F(u), then a root of

v is

z2

(43)

=

b2 a

K

F(v) for every v

=

bu

.

Thus we may replace the defining quantity a in F by any multiple 62a for b 7^ in F. It is also shown easily that if K is defined by a and K by a then K and KQ are fields equivalent over F if and only if a = 62a. ,

10. Integers of quadratic fields.

The Theory

of Algebraic

Numbers

is

concerned principally with the integral domain consisting of the elements of degree n over the field of all rational called algebraic integers in a field numbers. We shall discuss somewhat briefly the case n = 2. be a quadratic field over the rational field so that is Let, then, 2 generated by root u of u = a where a is rational and not a rational square. By the use of (43) we may multiply a by an integer and hence take a inte= c2d where d has no square factor and c and d are ordinary gral. Write a

K

K

integers. If ic field is

K

we take 6 =

generated by

c" 1 in (43) we replace a by d. Hence every quadrata root u of the quadratic equation

x2

(44)

=

a

=

pi

.

.

.

pr

,

where the p< are distinct positive primes and r > I for a > 0, while if 1 we interpret (44) as the case a negative and r = 0. a = The quantities k of K have the form k = k\ + k^u where fci and k% are if the coefficients ordinary rational numbers. We call k an integer of of if and only if of are k Thus is an T(k) N(k) (30) integers. integer shall determine and are both We all integers ordinary integers. 2ki k\ k\a

K

K

y

of

K stating our final results as Theorem

13.

The integers

containing the ring

E

of

all

a quadratic field 'Kform an integral domain J ordinary integers. Then J consists of all linear of

combinations (45)

Ci

+cw 2

FUNDAMENTAL CONCEPTS for Ci and 02 in E, where

w =

u

if

=

=

2 (mod 4) or a

3

(mod

4) but

w = l+

(46)

i/

a

125

= 1 (mod 4). Note that a ^

a

(mod I.

A/1

for

bo, bi,

Then

b 2 in

_ ^1 ,,

E and 6

=

2

__ &2

-

7

A/2

7

7

fv v

>

factor.

__ -

61, b 2

00

60,

common denominator of fci and

Now

.

We write

1

00

the positive least

the g.c.d. of

1 is

a has no square

4) since

2fci is

that b 2 divides

an

fc 2 .

integer, 60 divides 2bi,

p were an odd prime 2 61. But then p would divide b?, b\a. Since a has no square factors this is possible only if p divides 62, a contradiction. Hence 6 is a power of 2. If b > 4 divides 2bi, then 2 divides bi, 4 divides b? and b|a, and thus 2 divides 6 2 We have a contradiction and have proved that 6 = 1, 2. If 6 = 2 and 61 is even, then 4 divides b\a, and hence 2

k%a factor of 6 k\

b|a), so

bJ7 (6?

,

If

b|a.

b\

it would divide 2bi only if it divided and p 2 would divide 6? b\a as well as ,

-

divides 6 2 contrary to the definition of 6 Similarly, if 6 2 were even, then 4 would divide 6f, a contradiction. Hence 61 = 2wi -f 1, 62 = 2?w 2 1 for .

+ +m

= 4[mf m>i ra 2 and 6f a(^ 2 l and b\a 2 )] ordinary integers a is divisible by 4 if and only if a = 1 (mod 4). Thus we have proved 1 that J consists of the elements (45) with w = u if a s= 2, 3 (mod 4). But

m

if

a

and

2w

=

1

6 2 in

(mod

4),

6

=

,

+

,

then we have shown that either fc

1,'or in either case

= mi

+mu+w 2

for

w

fc

=

61

in (46).

+

+

b 2u with

b,

However, w =

fc has the form (45) with Ci and c 2 in E. remains to show that J is an integral domain. The elements of J are in the field K, and thus it suffices to show that fc A, kh are in J for every But the sum of fc and h of the form (45) is clearly of that fc and h of J.

1,

and

It

+

form, the product

is

of the

w = u

form

then

ger m, T(w)

(45)

if

w2

is

of that form.

But

this condition holds since

ii

w = a + Qw, while otherwise v? = a = 4m + 1 for an inte= J + i = 1, #(tiO = i(l ~ a) = -m, ty2 - w - m = 0, 2

(47)

This completes the proof.

w*

= m

+w

.

INTRODUCTION TO ALGEBRAIC THEORIES

126

The N(kh)

units of

=

J

=

1 for h also in J. Then an ordinary integer which divides unity,

are elements k such that kh

=

N(K)N(h)

1,

N(k)

is

N(k)=l.

(48)

s s 1. But k is in Conversely, if (48) holds, k has the property kk = 1 or 8 = s 1 = = Ar or tf Hence fc* and J when k is in J since T(k ) ) (*). r(*) N(k 5 = fc fc-i. Thus (48) is a necessary and sufficient condition that k be a

unit of /.

a

If

s

2,

3

4) so that

(mod

(49)

c\

However, 1

if

a

so that

=

1

(mod

=

4N(k)

4),

=

fc

Ci

+

-cia=

then (48)

is

equivalent to

1.

(4m

= c\ + l)c| =

=

4.

then (48) becomes N(k)

-

+ 4cic + c\

4c?

c 2 u,

2

+ CiC 4.

=

elm

2

But

this is

equivalent to (2ci

(50)

+c

2 2)

-

c|a

We may

determine the units of J completely and simply in case a is 4 for For both (49) and (50) have the form x\ + x\g = 1, negative. = 4 for # a and is and and this > 0, 2 possible ordinary integers x\ g = = 1. Now a has no square factors, and hence g ^ 4, 0, c\ only if #2 1, the only possible remaining cases are gr = 1, 2, 3. If g = 2 we have x\ + 1 1 only ^ #2 = 0. Hence we have proved that the units of J are 1, 2^1

a < let a

for every

Now is

save only a = 3. 1, 1 so that (49) becomes

zero, the other

or

is 1

1,

(51)

4,

u,

1, u,

In the remaining case a

and

if

c2

^

=

3

we must have

=

we

Then

c2

c2

The

1,

units of

J form a

negative this group

=

1,

w,

u2

=

=

1

1,

2ci

or

1

(52)

s -w, w

1,

a

=

Then one

of ci

and

c2

finite

.

+

c2

=

while c 2

-w s

,

multiplicative group,

is

1.

use (50) and have (2ci

= gives c\ for CL Clearly, the units of J are

of signs.

+ ci =

c\

and the units of J are

1

=

+c

2 2)

+ 3cl =

with any choice 1 gives

.

and we have shown that

group.

+ 2u has norm 9 -

or 1

4w2 = 9

-

=

if

a

is

1. Hence h is h for s 7* t, we may take a unit of J, and so is A for every integer L If h* t > 8 and have A'""* = 1. But we may regard u as the ordinary positive V2

If

a

2,

then h

3

1

=

9

8

FUNDAMENTAL CONCEPTS >

and have h

J

units of

is

1

5,

an

ft

"*

>

infinite

5*~8

>

Hence the

1.

group. It

may

127

multiplicative group of the

similarly be shown to be infinite for

every positive a.

We shall not study the units of quadratic fields further but shall pass on to

some

results

on primes and prime

ideals in

two

special cases.

Gauss numbers. The complex numbers of the form x + yi with raand y are called the Gauss complex numbers, and those for which x and y are integers are called the Gauss integers. Then the Gauss complex numbers are the elements of a quadratic field K of our study with 11.

tional x

u-

-1,

and the Gauss integers comprise its integral domain J. We have deteru of J and shall now study its divisibility properties. mined the units 1, Our first result is the Division Algorithm which we state as Theorem 14. Let f and g ^ be in J. Then there exist elements h and r in J such that f

(53)

=

gh

+r

< N(r) < N(g). and For fg- 1 is in K, fg~\ = k\ + k^u with rational fci and fc 2 Every rational number t lies in an interval s < t < s + 1 for an ordinary integer s. If then \t s < t < s + \ then (<-)< i while ifs + < and Hence there exist such that h% (s + 1) i. ordinary integers h\ .

<J<s+l

|

Put sg

S2

ai^fci-fti,

(54) ft

=

=

gh

hi

+

+ hju,

r.

s

=

Si

Then N(s)

=

fe 2

-ft2,

+ s u, r = si + s\ < 2

=

|*i|<J,

|a|
l = h sg so that fg~ = J, tf (r) N(s)N(g)

+ <

/

=

+

gh N(g) as de-

s,

sired.

We observe that the quotient h and the remainder r need not be unique in our present case. For example, if / = 2 u and g = 1 u, we have = = = l with 2. N(l) Ar(-u) = 1. Then/ =l-g N(g) Division the of a ggc.d. existence We shall use the Algorithm to prove

+

+ 2-0-u

+

Our proof will be different and simpler than that we gave in the case of polynomials and indicated in the case of integers but has the defect of being merely existential and not constructive. We first prove Theorem 15. Every ideal of J is a principal ideal.

M

M

are positive integers, and For the norms of the nonzero elements of in such that N(m) < N(f) for every / of M. By there exists an m 7*

M

INTRODUCTION

128

TO,

Theorem 14 we have / = mh + r so is r = f /, m and mh are in

M

M

ALGEBRAIC THEORIES and

for h

r in

wA, and

,

it

J and

<

N(m). But must be zero.

N(r)

follows that r

= {m}. Thus/ = mh, The above result then implies Theorem 16. Let f and g 6e nonzero elements of J. Then there exist b and

c

in J such that

=

d

(55)

+

bf

eg

a common divisor of f and g. TTms d is a g.c.d. of f and g. For the set of all elements of the form xf + yg with x and y in J is an = {d} d in has the form (55) ideal of J. By Theorem 15 we have and divides / = 1 / + 00, and g = The above result may now be seen to imply that if / divides gh and is prime to g, then / divides h, and also if p is a prime of J dividing g h, then p divides g or h. Moreover, if / is a composite integer of J, then / = g h for nonunit g and h, N(g) < N(f). Then if p is a divisor of/ of least positive norm it is a prime divisor of /, and we continue the proof of Theorem 6 is

M

M

M

,

0/+lginM.

to obtain

Theorem

17.

Every composite Gauss integer

=

f

(56)

pi

.

.

.

is expressible

as a product

pr

of primes pi which are determined uniquely by

f

apart from their order and

unit multipliers.

We observe that Theorem 17 implies that an ideal M of J is a prime ideal

M

= {d} for a prime d of J. (and, in fact, a divisorless ideal) if and only if Let us then determine the prime quantities d = di d*u of J. We see first s = s = d zu. For if d that if d is a prime of J, so is d d\ gh with N(g) ^ 1, s s s s N(h) * 1, we have d = g h for N(g ) = N(g), N(h ) = N(h), and d is

+

composite.

We now prove 18. A positive prime

p of E is either a prime of J or the product a prime of J. Every prime d of J is either associated with a positive prime of E or arises from the factorization in J of a positive s prime p = dd of E which is composite in J.

Theorem

N(d)

= dds

,

where d

is

a positive prime of E and is composite in J, then p = dk for N(d) > 1, N(k) > 1, N(p) = p* = N(d)N(k). But then p = N(d). lid = = 1, h is a (h) gh with N(g) > 1, then N(d) = p = N(g)N(h) so that

For

if

p

is

N

unit,

d

is

a prime. Conversely,

positive integer of

let

d be a prime of J. Then

E and is either a prime or is composite.

have at most two prime factors

in E, c

= pp Q

c

But

= N(d) c

=

for positive primes

is a dd s can

p and p

FUNDAMENTAL CONCEPTS

129

assume that p is associated with d and po with ds so that PQ PQ is associated with d and with p. Since p and po are both in E, we = p2 have PQ = p. But p and p are positive and must be equal, N(d) Therefore d is associated with the prime p of E which is prime in J.

of E.

We may

=

.

We now clearly complete our study of the primes of J by proving Theorem 19. A positive prime p of E is a prime of J if and only if p has the

form

4m +

To prove have

t

=

2s

3.

we observe

this result

+

1, t*

=

4s

2

+ 4s +

first

=

1

that

4s(s

+

an odd integer of E we + !. One of s and s + 1

is

if

!)

2 (mod 4) (mod 8). If t is even, we have t = 2 55 4 of Thus sum is a two to and t (mod 8). squares congruent 0, 1, 2, 4, 0, or 5 modulo 8 while 4n + 3 is congruent 3 or 7 modulo 8. It follows that 2 p = 4n + 3 7* x* + y We now assume that p = gh for g and h in J and 2 = = nor h were a unit, we would have p A'Xp) N(g)N(h). If neither have N(g} > 1, and both of these integers would be divisors of p 2 But 2 2 = 4n + 3 then]V(g) = N(h) = p = x + y which is impossible. Hence, p

is

even,

t

2

=

+1=

8r

1

.

gr

.

,

is

J

1 = (l + w)(l w)is composite in = 4n + 1 is composite in J. We know

prime in J. We note that 2= 1 and that it remains to show that p

+

by Theorem 12 that there exists an integer b in E such that b + 1 is divisible u = p(fci + fc 2tO, and 1 == u, then 6 by p. If p divides b + u or 6 pfc 2 which is impossible. But a prime p of J cannot divide the product 2 u, u) = b + 1 without dividing one of its factors 6 + u b (b + u)(b Hence p is not a prime of /. This completes the proof. We use the result above to derive an interesting theorem of the Theory of Numbers. We call a positive integer c a sum of two squares if c = x2 + y 2 for x and y in E. Then we have Theorem 20. Write c = f2g where f and g are positive integers and g has no square factors. Then cisa sum of two squares if and only if no prime factor of g has the form 4n + 3. = di For if c = x 2 + y 2 = (x + yu)(x yu), we may write x + yu d r for primes d in J, c = N(di) N(d r). Then N(di) = p is a prime of E if and only if p 7^ 4n + 3 and otherwise N(di) p?. Thus the prime factors of c of the form 4n + 3 occur to even powers and are not factors of g. p r for positive primes p< of Snotof the form 4n + Conversely, if g = pi = for d r), we have d< in J, g = tf (di) N(d r ) = #(di N(di) p< 3, 2 2 = = = = f or x + i/w in J. z + t/ d r) and c JV(fc) N(fdi Note in closing that a positive prime p of the form 4n + 3 divides x* + y2 if and only if p divides both a: and y. For p is a prime of J and divides yu. Then (# + yu)(x yu) if and only if p divides either x + yu or x 2

,

}

.

.

.

.

.

.

.

.

.

.

.

.

.

ifc

.

.

.

.

.

INTRODUCTION TO ALGEBRAIC THEORIES

130

k zu), x = pfci, y = p& 2 for integers ki and p(ki follows, then, that if x, y, z are ordinary integers such that

x

yu

=

z2

(57)

+

=

2 2/

z2

fc 2

of E. It

,

= 4n +

3 of z divides both x and y. Then let x y, z have g.c.d. unity. It follows that the odd prime divisors of z have the form 4n + 1. We may show readily also that x and y cannot both be even or be odd and that z must be odd.*

every prime divisor p

An

12.

integral

domain with nonprincipal

We

ideals.

shall close

position with a discussion of some properties of the ring 5. Since 5 = 3 (mod defined by a = u* = the field

K

J have

y

y

+ k^u for k\ and

J

our ex-

of integers of

4), the

elements

E of all integers.

Oban integer of E which is a divisor in J of k\ + fc 2 w, then 6 must divide both k\ and fc 2 For k\ + k^u = b(hi + h^u), k\ = bhi, fc 2 =

of

the form k\

serve that

if

in the set

fc 2

6 is

.

bhz.

We now prove

Theorem

22.

The elements

of which are associated. For if k is a composite of

3, 7, 1

+ 2u,

J we have

k

=

2u are primes of J no two

1

gh,

N(k)

=

N(g)N(h) for ordi-

nary integral proper divisors N(g) and N(h) of N(k). The norms of the integers of our theorem are 9, 49, 21, 21, respectively, and the only positive proper divisors of these norms are

N(g)

=

g\

+ 5gl > 0, g\ + 5gl

impossible since g\ The units of J are 1,

is

^ 1,

We see now that 21 =

=

3, 7.

3, 7.

Thus

and

clearly

7

=

(1

if

Evidently g 2

2, 2.

3

But

3, 7, 1

+ 2u

g

=

gi

+

* 0, g\ <

y

I

g*u, 1.

we have

But^l

=

2u are primes of

1

J.

no two of them are associated. + 2w)(l 2w), and we have factored

21 into prime factors in J in two distinct ways. Moreover, the principal ideal {3} of J defined for the prime 3 is not a prime ideal. For 3 does not divide 1

+ 2w and 1

the residue class

2u in J yet does divide their product, and therefore 2u as divisors of ring J {3} contains 1 + 2u and 1

zero.

The

ring

J

We let M be

contains nonprincipal ideals one of which we shall exhibit. the ideal of J consisting of all elements of J of the form

3*

(58) If this ideal

d of 3 and *

1

were a principal ideal

+ 2u.

For further

40-42.

+ y(l + 2u) {d}, there

would

(x,

exist

a

y in J)

common

Since these are nonassociated primes, d

.

divisor

must be a unit

results see L. E. Dickson's Introduction to the Theory of

Number8 pp. 1

FUNDAMENTAL CONCEPTS 1

or

-1

of J,

and

7

=

216

+

+ 2u)7c

divide

7,

(1

\d}

= =

a contradiction.

J and hence

Then

{!}. (1

+

1

=

36

-

2u)[fc(l

+ (1 + + 7c],

2u)c for b and c in J, But 1 2w does not

2u)

We now proceed to

131

M

prove that

+ is

a

divisorless

a prime ideal of J. We have shown that is not a principal ideal and does not contain Since contains 3 but not 1 it cannot contain 2. For otherwise 3 2 =

ideal of

is

M

M

would be

M. Let

in

c

E

be an integer of

M so that

in

M contains 3g contains 3q = the ordinary integers in M are by The ideal M contains 3 and + 2u and so contains =

r

Since

0, 1, 2.

c

it

divisible

=

c

3<j

+

r

1.

1

where

=

0.

Hence

w2 =

hQ

+ h* in

r,

r

3.

1

wi

(59)

If

/i

is

in

M

E

and

in

M. By

,

=

then

ft

3

wz

,

=

/&

+

= Zu -

Aau for

the proof above

h

(60)

=

ft

(1

+ 2u) =

and

ft

ft 2

+ ^2 =

ftiWi

ft 2

m E,h 3fti

+ w

-

w

1

.

ft 2

for hi in E,

2

M

We

have thus proved that consists of all quantities of the form (60) for hi and ft 2 ordinary integers. Thus we may call wi, w 2 a basis of over E. Note that 1 has a basis 1, u over E in this sense. It may be shown that every ideal of J has a basis of two elements over E. Every integer of / has the form k = ki + k^u = ki + fc 2w 2 + fo. Write = 3c + r for c in E and r = 0, 1, 2. Then k = cwi + fc 2w 2 + r = fci + fc 2

M

{

r

}

(M), the elements of

We

have proved that

J J

M are the residue M equivalent to E

classes 0, 1, 2 such that 3

is

{

3}

and

is

a

field,

=

0.

M

is

a divisorless ideal of J.

This completes our discussion of ideals and of quadratic fields. We shall conclude our text with the following brief bibliographical summary.

Let us begin with references to standard topics on matrices not covered

The theory of orthogonal and unitary equivalence of symmetric matrices is contained with generalizations in Chapter of the Modern Higher Algebra and is further generalized and connected with

in our introductory exposition.

V

the theory of equivalence of pairs of matrices in the author's paper entitled 'Symmetric and Alternate Matrices in an Arbitrary Field," in Transactions of the American Mathematical Society, XLIII (1938), 386-436. See also pages 74-76 and Chapter VI of L. E. Dickson's Modern Algebraic Theories, and '

Chapter VI of

J.

M. H. Wedderburn's

Lectures on Matrices.

V

Both

of these

texts as well as Chapters III, IV, and of the Modern Higher Algebra inof all the material of our course, clude, Chapters II-V. For a discussion

132

INTRODUCTION TO ALGEBRAIC THEORIES

without details but with complete references of many other topics on maMacDuffee, The Theory of Matrices ("Ergebnisse der Mathematik und ihrer Grenzgebiete," Vol. II, No. 5 [pp. 110]). The theory of rings as given here is contained in the detailed discussion of Chapters I and II of the Modern Higher Algebra, and the theory of ideals in Chapter XI. See also the much more extensive treatment in Van der Waerden's Moderne Algebra. The units of the ring of integers of a quadratic field are discussed on page 233 of R. Fricke's Algebra, Volume III, and its ideals on pages 106-10 of H. Hecke's Theorie der algebrdischen Zahlen. We close with a reference to the only recent book in English on algebraic number theory, H. Weyl's Algebraic Theory of Numbers (Princeton, 1940). trices see C. C.

INDEX Abelian group, 110 Addition of matrices, 59 Additive group, 111 Adjoint matrix, 29 rank of, 46 Algebraic integers, 124 Associated quantities, 115 Associative law, 38 matrix, 80

Augmented

Automorphism,

107, 122

Basis, 67

Bibliography, 131 Bilinear form, 14, 48

matrix of, 49 rank of, 49 skew, 53 symmetric, 54 types of, 14 Characteristic

:

Complex numbers, 75 field of,

Composite quantity, 115 Congruent: matrices, 51 quantities, 116 Conjunctive matrices, 108 Constant, 1, 19

Coordinate, 66 Correspondence, 73 Definite symmetric matrix, 64

Degree

t-rowed, 27

Diag {Ai,...,

of a field, 114

Diagonal

matrix, 101 Closure, 8 Coefficient, 2, 97

Cogredient elementary transformations, 52 mappings, 51 :

elements, 23 matrix, 29 of a matrix, 23 Difference, 57 Difference ring, 117 Distributive law, 60

:

of a matrix, 20

rank, 72 space, 72

Divisibility, 115

Division, right,

left,

98

Division algorithm for: Gauss numbers, 127 integers, 117 matric polynomials, 97 polynomials, 4 Division ring, 113 Divisors of zero, 113

:

group, 110 matrices, 37 ring, 113

Complementary

:

blocks, 31

Cofactor, 28

Commutative

of:

a polynomial, 2, 7, 97 a term, 6 zero polynomial, 2 Dependent vectors, 67 Determinant, 26 order of, 27 of a product, 44

equation, 101

Column

56

of Gauss, 127

:

minor, 27

Element

spaces, 77

submatrix, 21 Complex conjugate, 107

:

identity, 110 inverse, 110

133

INTRODUCTION TO ALGEBRAIC THEORIES

134 Element

order of a subgroup of, 110 subgroup of, 110 zero element of, 112

continued

unity, 113 zero, 112, 113

Groups, equivalence

Elementary: divisors, 94 matrix, 92

of:

Ideal, 116 divisorless, 117

prime, 117 principal, 116 unit, 116 zero, 116

bilinear forms, 49

Identity:

forms, 17 groups, 110

element, 110

linear spaces, 74

matrix, 30 Independent vectors, 67

matrices, 47, 89, 92

Integers:

quadratic forms, 59 Euclid's process, 10 Euler's theorem, 120

algebraic, 124

congruent, 120 ordinary, 117 Integral domains, 114

Factor theorem, 5, 99 Fermat theorem, 120 Field, 56, 114 characteristic of, 114 of

Integral operations, 1

Invariant factors, 91 Inverse element, 110 :

complex numbers, 56

degree of, 121 generating quantity

Forms,

7, 13; see also

110

Homogeneous polynomial, 7

Elementary transformations, 24, 25 cogredient, 52 matrices of, 43 Equations, systems of, 19, 79 Equivalence, 73, 74 Equivalence

of,

of,

121

Bilinear forms

Function, 73

Irreducible quantities, 115

Leading

characteristic, 101

minimum, 101 Fundamental Theorem

mapping, 46 matrix, 45

coefficient, 3,

97

97 Leading form, 8 Left division, 98 virtual, 3,

of Arithmetic, 118

Galois group, 122

Length preserving transformation,

Gauss integers, 127 Gauss numbers, 127

Linear:

General linear space, 74 Greatest common divisor, 9 of Gauss numbers, 128 of integers, 118 of polynomials, 9 process, 10 Group, 109 abelian, 110 additive, 111 commutative, 110 cyclic, 111 order of a, 110

combination, 15 dependence, 67 form, 15

independence, 67 space, 66, 74

subspace, 66, 71 Linear change of variables, 38 Linear mappings, 17, 82 cogredient, 51 inverse of, 17, 46 matrix of, 36, 83 nonsingular, 17

product

of,

36

INDEX rows

20 30 skew, 52

Linear space, 66, 71, 74 basis of, 67 order of, 71

skew-Hermitian, 108 square, 20

orthogonal, 86 see

of,

scalar,

Linear transformations, 84

Mappings;

135

Linear mappings

Matrices: of, 59 commutative, 37

addition

symmetric, 52, 53, 59, 64 transpose of, 22 triangular, 29 unitary, 108 zero, 30

congruent, 51

Minimum

congruent pairs of, 108 conjunctive, 108 equivalent, 47, 89, 92

Minors, 27

equivalent pairs

of,

function, 101

Monic polynomial,

3,

100

Multiple roots, 5

108 form, 13

orthogonal, 86

n-ary

orthogonally equivalent, 108

7i-dimensional space, 66

products

of,

Nonsingular

36

rationally equivalent, 25,

34, 47

similar, 85, 103

unitary equivalent, 108

Matrix

characteristic, 101

characteristic function of a, 101 of coefficients, 19

20

of,

diagonal

of,

of,

mapping, 84 matrix, 34

Norm Norm

adjoint of, 29 augmented, 80 of a bilinear form, 49

columns

:

linear transformation, 84

quadratic form, 55 in a field, 123

:

determinant diagonal, 29

q-ic

of a vector, 86

Order of: a group, 110 a group element, 111 a linear space, 71 Orthogonal:

27

matrices, 86

subspaces, 87

23

transformations, 86

diagonal elements

of,

23

vectors, 87

elementary, 92 of an elementary transformation, 43 elements of, 20 equal, 21

Hermitian, 108 identity, 30 invariant factors inverse of a

:

associated, 5

6

constant, 1 of,

91

function

degree

of, 2, 7,

97

divisibility of, 5

mapping, 36, 83

minimum

Polynomials

coefficients of,

45

of,

Point, 66

of,

101

equal, 2 factors of, 5

partitioning of, 21

g.c.d. of, 9 homogeneous, 7

principal diagonal of, 23

identically equal, 6

nonsingular, 34

rank

of,

32

rectangular, 19

monic, 3, 100 13

n-ic,

INTRODUCTION TO ALGEBRAIC THEORIES

136

Polynomials continued products of, 3

Rational: equivalence, 25 functions, 8

g-ary, 13

rationally irreducible, 12 relatively prime, 11

roots of, 5 scalar, 100 in several variables,

6

virtual degree of, 2, 6, 97 zero, 1 Positive form, 64

Prime to a polynomial, 11 Prime quantity, 115 Primitive root, 121 Principal diagonal, 23

Quadratic

field,

121

integers of, 124

Quadratic form, 54 definite, 64 index of, 62 negative, 64 nonsingular, 55 real, 62 Quadratic forms, equivalent, 59 Quantities: associated, 115

composite, 115 congruent, 6, 11 irreducible, 115 prime, 115 relatively prime, 115

Quartic field, 121 Quartic form, 13 Quasi-field, 57

Quaternary form, 13 Quaternions, 114 Quinary form, 13 Quotient, 57 right, left, 98

Rank

of:

an adjoint matrix, 46 a a a a a

bilinear form, 49

matrix, 32 product, 44 quadratic form, 54 row space, 72

operations, 8 Real:

quadratic form, 62 quaternions, 114 symmetric matrix, 64 Reflection, 87

Relatively prime: polynomials, 11 quantities, 115

Remainder

:

98 theorem, 4, 98 Residue classes, 116 Right division, 98 Ring, 112 commutative, 113 difference, 117 division, 113 residue class, 117 Roots, 5 multiple, 5 Rotation of axes, 87 Row, 69 rank, 72 space, 69, 72 right, left,

Row by

column

rule,

37

Scalar:

matrix, 30 polynomial, 100 product, 16, 41 Scalars, 19 Self-equivalence, 107 Semidefinite forms, matrices, 64

Sequence: elements zero, 16

of,

16

Similar matrices, 85, 103 Skew forms, 53 Skew matrices, 52

Space; see Linear space Spanning a space, 67 Subfield, subgroup, 110 Submatrix, 21 complementary, 21

INDEX

137

Subring, 113

Unit

Subspaces, 66, 75, 77 complementary, 77

Units, 115

sum

of,

116

Unity element, 113

77

Variables, change of, 38

Subsystems, 110 Subtraction, 112

Vectors, 66

Symmetric bilinear forms, 54 Symmetric matrices, 52, 53 congruence

ideal,

of,

59

linearly independent, 67

norm zero,

definiteness of, 64

of,

86

orthogonal, 87

66

Virtual degree, 2, 6, 97 Virtual leading coefficient,

Ternary forms, 13

Zero:

Trace, 123

Transformations, 84

divisors of, 113

Transpose, 22 of a product, 37 of a sum, 62

element, 112, 113 ideal, 116

Unary form, 13 Unique factorization,

matrix, 30

115, 118, 127

polynomial, 1 sequence, 16 space, 67

3,

97