3.5. LINEAR ALGEBRA OVER Z Notes

convention, we will use additive notation for the group operation. In particular, the sth power of an element x will be written as sx, and the order of an element x is the smallest natural number s such that sx D 0. The subgroup generated by a subset S of an abelian group G is

ZS WD fn1x1 C C nd xd W d 0; ni 2 Z; and xi 2 Sg:

The subgroup generated by a family A1; : : : As of subgroups is A1 C C As D fa1 C C as W ai 2 Ai for all ig.

A group is said to be finitely generated if it is generated by a finite

subset. A finite group is, of course, finitely generated. Zn is infinite, but finitely generated, while Q is not finitely generated.

In the next section (Section 3.6), we will obtain a definitive structure

theorem and classification of finitely generated abelian groups. The key to this theorem is the following observation. Let G be a finitely generated abelian group and let fx1; : : : ; xng be a generating subset for G of minimum cardinality. We obtain a homomorphism from Zn to G given by ' W .a1; : : : ; an/ 7! Pi ai xi . The kernel N of ' is a subgroup of Zn, and G Š Zn=N . Conversely, for any subgroup N of Zn, Zn=N is a finitely generated abelian group.

Therefore, to understand finitely generated abelian groups, we must

understand subgroups of Zn. The study of subgroups of Zn involves linear algebra over Z.

The theory presented in this section and the next is a special case of

the structure theory for finitely generated modules over a principal ideal domain, which is discussed in sections 8.4 and 8.5, beginning on page

i

i

i

“bookmt” — 2006/8/8 — 12:58 — page 186 — #198

i

186

3. PRODUCTS OF GROUPS 368. The reader or instructor who needs to save time may therefore prefer to omit some of the proofs in Sections 3.5 and 3.6 in the expectation of treating the general case in detail.

We define linear independence in abelian groups as for vector spaces: a

subset S of an abelian group G is linearly independent over Z if whenever x1; : : : ; xn are distinct elements of S and r1; : : : ; rn are elements of Z, if

r1x1 C r2x2 C C rnxn D 0;

then ri D 0 for all i.

A basis for G is a linearly independent set S with ZS D G. A free

abelian group is an abelian group with a basis. Zn is a free abelian group with the basis f Oe1; : : : ; Oeng, where Oej is the sequence with j –entry equal to 1 and all other entries equal to 0. We call this the standard basis of Zn.

An abelian group need not be free. For example, in a finite abelian

group G, no non-empty subset of G is linearly independent; in fact, if n is the order of G, and x 2 G, then nx D 0, so fxg is linearly dependent.

We have the following elementary results on direct products of abelian

groups and freeness.

Proposition 3.5.1. Let G be an abelian group with subgroups A1; : : : As such that G D A1C CAs. Then the following conditions are equivalent:

(a)

.a1; : : : ; as/ 7! a1 C C as is an isomorphism of A1 As onto G.

(b)

Each element g 2 G can be expressed as a sum x D a1C Cas, with ai 2 Ai for all i, in exactly one way.

(c)

If 0 D a1 C C as, with ai 2 Ai for all i, then ai D 0 for all i .

Proof. This can be obtained from results about direct products for general (not necessarily abelian) groups, but the proof for abelian groups is very direct. The map in part (a) is a homomorphism, because the groups are abelian. (Check this.) By hypothesis the homomorphism is surjective, so (a) is equivalent to the injectivity of the map. But (b) also states that the map is injective, and (c) states that the kernel of the map is trivial. So all three assertions are equivalent.

n

Proposition 3.5.2. Let G be an abelian group and let x1; : : : ; xn be distinct nonzero elements of G. The following conditions are equivalent:

(a)

The set B D fx1; : : : ; xng is a basis of G.

(b)

The map

.r1; : : : ; rn/ 7! r1x1 C r2x2 C C rnxn

i

i

i

“bookmt” — 2006/8/8 — 12:58 — page 187 — #199

i

3.5. LINEAR ALGEBRA OVER Z

187

is a group isomorphism from Zn to G.

(c)

For each i , the map r 7! rxi is injective, and

G D Zx1 Zx2 Zxn:

Proof. It is easy to see that the map in (b) is a group homomorphism. The set B is linearly independent if, and only if, the map is injective, and B generates G if, and only if the map is surjective. This shows the equivalence of (a) and (b). We leave it as an exercise to show that (a) and (c) are equivalent.

n

Let S be a subset of Zn. Since Zn is a subset of the Q–vector space

Qn, it makes sense to consider linear independence of S over Z or over Q. It is easy to check that a subset of Zn is linearly independent over Z if, and only if, it is linearly independent over Q (Exercise 3.5.4). Consequently, a linearly independent subset of Zn has at most n elements, and if n ¤ m, then the abelian groups Zn and Zm are nonisomorphic (Exercise 3.5.5).

Lemma 3.5.3. A basis of a free abelian group is a minimal generating set.

Proof. Suppose B is a basis of a free abelian group G and B0 is a proper subset. Let b 2 B n B0. If b were contained in the subgroup generated by B0, then b could be expressed as a Z–linear combination of elements of B0, contradicting the linear independence of B. Therefore b 62 ZB0, and B0 does not generate G.

n

Lemma 3.5.4. Any basis of a finitely generated free abelian group is finite.

Proof. Suppose that G is a free abelian group with a (possibly infinite) basis B and a finite generating set S . Each element of S is a Z–linear combination of finitely many elements of B. Since S is finite, it is contained in the subgroup geneated by a finite subset B0 of B. But then G D ZS ZB0. So B0 generates G. It follows from the previous lemma that B0 D B.

n

Proposition 3.5.5. Any two bases of a finitely generated free abelian group have the same cardinality.

i

i

i

“bookmt” — 2006/8/8 — 12:58 — page 188 — #200

i

188

3. PRODUCTS OF GROUPS

Proof. Let G be a finitely generated free abelian group. By the previous lemma, any basis of G is finite. If G has a basis with n elements, then G Š Zn, by Proposition 3.5.2. Since Zn and Zm are nonisomorphic if m ¤ n, G cannot have bases of different cardinalities.

n

Definition 3.5.6. The rank of a finitely generated free abelian group is the cardinality of any basis.

Proposition 3.5.7. Every subgroup of Zn can be generated by no more than n elements.

Proof. The proof goes by induction on n. We know that every subgroup of Z is cyclic (Proposition 2.2.21), so this takes care of the base case n D 1. Suppose that n > 1 and that the assertion holds for subgroups of Zk for k < n. Let F be the subgroup of Zn generated by f Oe1; : : : ; Oen 1g; thus, F is a free abelian group of rank n

1.

Let N be a subgoup of Zn. By the induction hypothesis, N 0 D N \ F

has a generating set with no more than n

1 elements. Let ˛n denote the

nth co-ordinate function on Zn. Then ˛n is a group homomorphism from Zn to Z, and ˛n.N / is a subgroup of Z. If ˛n.N / D f0g, then N D N 0, so N is generated by no more than n

1 elements. Otherwise, there is a

d > 0 such that ˛n.N / D d Z. Choose y 2 N such that ˛n.y/ D d . For every x 2 N , ˛n.x/ D kd for some k 2 Z. Therefore, ˛n.x

ky/ D 0,

so x

ky 2 N 0. Thus we have x D ky C .x

ky/ 2 Zy C N 0. Since N 0

is generated by no more than n

1 elements, N is generated by no more

than n elements.

n

Corollary 3.5.8. Every subgroup of a finitely generated abelian group is finitely generated.

Proof. Let G be a finitely generated abelian group, with a generating set fx1; : : : ; xng. Define homomorphism from Zn onto G by '.Pi ri Oei / D

P

i ri xi . Let A be a subgroup of G and let N D ' 1.A/. According to the

previous lemma, N has a generating set X with no more than n elements. Then '.X / is a generating set for A with no more than n elements.

n

We know that if N is an s dimensional subspace of the vector space

Kn, then there is a basis fv1; : : : ; vng of Kn such that fv1; : : : ; vsg is a basis of N . For subgroups of Zn, the analogous statement is the following:

i

i

i

“bookmt” — 2006/8/8 — 12:58 — page 189 — #201

i

3.5. LINEAR ALGEBRA OVER Z

189

If N is a nonzero subgroup of Zn, then there exist

a basis fv1; : : : ; vng of Zn, s 1, and nonzero elements d1; d2; : : : ; ds of Z, with di divid

ing dj if i j

such that fd1v1; : : : ; dsvsg is a basis of N . In particular, N is free.

The key to this is the following statement about diagonalization of

rectangular matrices over Z. Say that a (not necessarily square) matrix A D .ai;j / is diagonal if ai;j D 0 unless i D j . If A is m–by–n and k D minfm; ng, write A D diag.d1; d2; : : : ; dk/ if A is diagonal and ai;i D di for 1 i k.

Proposition 3.5.9. Let A be an m–by–n matrix over Z. Then there exist invertible matrices P 2 Matm.Z/ and Q 2 Matn.Z/ such that PAQ D diag.d1; d2; : : : ; ds; 0; : : : ; 0/, where the d 0s are positive and d

i

i divides dj

for i j .

The matrix PAQ D diag.d1; d2; : : : ; ds; 0; : : : ; 0/, where di divides

dj for i j is called the Smith normal form of A.5

Diagonalization of the matrix A is accomplished by a version of Gauss

ian elimination (row and column reduction). Let us review the elementary row and column operations of Gaussian elimination, and their implementation by pre– or post–mulitplication by elementary invertible matrices.

The first type of elementary row operation replaces some row ai of

A by that row plus an integer multiple of another row aj , leaving all other rows unchanged. The operation of replacing ai by ai Cˇaj is implemented by multiplication on the left by the m–by-m matrix E C ˇEi;j , where E is the m–by-m identity matrix, and Ei;j is the matrix unit with a 1 in the .i; j / position. E CˇEi;j is invertible in Matm.Z/ with inverse E ˇEi;j .

For example, for m D 4,

21 0 0 03

0 1 0 ˇ

E C ˇE

6

7

2;4 D 6

:

0 0 1

07

4

5

0 0 0

1

The second type of elementary row operation interchanges two rows.

The operation of interchanging the i –th and j –th rows is implemented by multiplication on the left by the m–by-m permutation matrix Pi;j corresponding to the transposition .i; j /. Pi;j is its own inverse.

5A Mathematica notebook SmithNormalForm.nb with a program for computing

Smith normal form of integer matrices is available on my web page.

i

i

i

“bookmt” — 2006/8/8 — 12:58 — page 190 — #202

i

190

3. PRODUCTS OF GROUPS

For example, for m D 4,

21 0 0 03

0 0 0 1

P

6

7

2;4 D 6

:

0 0 1 07

4

5

0 1 0 0

The third type of elementary row operation replaces some row ai with

ai . This operation is it’s own inverse, and is implemented by left multi

plication by the diagonal matrix with 1’s on the diagonal except for a

1

in the .i; i / position.

Elementary column operations are analogous to elementary row oper

ations. They are implemented by right multiplication by invertible n–by–n matrices.

We say that two matrices are row–equivalent if one is transformed

into the other by a sequence of elementary row operations; likewise, two matrices are column–equivalent if one is transformed into the other by a sequence of elementary column operations. Two matrices are equivalent if one is transformed into the other by a sequence of elementary row and column operations.

In the following discussion, when we say that a is smaller than b, we

mean that jaj jbj; when we say that a is strictly smaller than b, we mean that jaj < jbj.

Lemma 3.5.10. Suppose that A has nonzero entry ˛ in the .1; 1/ position.

(a)

If there is a element ˇ in the first row or column that is not divisible by ˛, then A is equivalent to a matrix with smaller .1; 1/ entry.

(b)

If ˛ divides all entries in the first row and column, then A is equivalent to a matrix with .1; 1/ entry equal to ˛ and all other entries in the first row and column equal to zero.

Proof. Suppose that A has an entry ˇ is in the first column, in the .i; 1/ position and that ˇ is not divisible by ˛. Write ˇ D ˛q C r where 0 < r < j˛j. A row operation of type 1, ai ! ai

qa1 produces a matrix with r

in the .i; 1/ position. Then transposing rows 1 and i yields a matrix with r in the .1; 1/ position. The case that A has an entry in the first row that is not divisible by ˛ is handled similarly, with column operations rather than row operations.

If ˛ divides all the entries in the first row and column, then row and

column operations of type 1 can be used to replace the nonzero entries by zeros.

n

i

i

i

“bookmt” — 2006/8/8 — 12:58 — page 191 — #203

i

3.5. LINEAR ALGEBRA OVER Z

191

Proof of Proposition 3.5.9. If A is the zero matrix, there is nothing to

do. Otherwise, we proceed as follows:

Step 1. There is a nonzero entry of minimum size. By row and column

permutations, we can put this entry of minimum size in the .1; 1/ position. Denote the .1; 1/ entry of the matrix by ˛. According to Lemma if there is a nonzero entry in the first row or column which is not divisible by ˛, then A is equivalent to a matrix whose nonzero entry of least degree is strictly smaller than ˛. If necessary, move the entry of minimum size to the .1; 1/ position by row and column permutations.

Since the size of the .1; 1/ entry cannot be reduced indefinitely, after

some number of row or column operations which reduce the size of the .1; 1/ entry, we have to reach a matrix whose .1; 1/ entry divides all other entries in the first row and column. Then by row and column operations of the first type, we obtain a block diagonal matrix

2

0

0 3

60

7

6 :

7 :

6 :

B0 7

4 :

5

0

Step 2. We wish to obtain such a block diagonal matrix as in Step 1

in which the .1; 1/ entry divides all the other matrix entries. If no longer has minimum size among nonzero entries, then apply row and column interchanges to move an entry of minimum size to the .1; 1/ position. If is of minimum size, but some entry of B0 is not divisible by , replace the first row of the large matrix by the sum of the first row and the row containing the offending entry. This gives a matrix with in the .1; 1/ position and at least one entry not divisible by in the first row. In either case, repeating Step 1 will give a new block diagonal matrix whose .1; 1/ entry is smaller than .

Again, the size of the .1; 1/ entry cannot be reduced indefinitely, so

after some number of repetitions, we obtain a block diagonal matrix

2d

3

1

0

0

6 0

7

6

7 :

6 :

:

B 7

4 :

5

0

whose .1; 1/ entry d1 divides all the other matrix entries.

Step 3. By an appropriate inductive hypothesis, B is equivalent to a

diagonal matrix diag.d2; : : : ; dr ; 0; : : : ; 0/, with di dividing dj if 2 i j . The row and column operations effecting this equivalence do not change the first row or first column of the larger matrix, nor do they change the divisibility of all entries by d1. Thus A is equivalent to a diagonal matrix

i

i

i

“bookmt” — 2006/8/8 — 12:58 — page 192 — #204

i

192

3. PRODUCTS OF GROUPS

with the required divisibility properties. The nonzero diagonal entries can be made positive by row operations of type 3.

n

Example 3.5.11. (Greatest common divisor of several integers.) The diagonalization procedure of Proposition 3.5.9 provides a means of computing the greatest common divisor d of several nonzero integers a1; : : : ; an as well as integers t1; : : : ; tn such that d D t1a1 C tnan. Let A denote the row matrix A D .a1; : : : ; an/. By Propsition 3.5.9, there exist an invertible matrix P 2 Mat1.Z/ and an invertible matrix Q 2 Matn.Z/ such that PAQ is a diagonal 1–by–n matrix, PAQ D .d; 0; : : : ; 0/, with d 0. P is just multiplication by ˙1, so we can absorb it into Q, giving AQ D .d; 0; : : : ; 0/. Let .t1; : : : ; tn/ denote the entries of the first column of Q. Then we have d D t1a1 C tnan, and d is in the subgroup of Z generated by a1; : : : ; an. On the other hand, let .b1; : : : ; bn/ denote the entries of the first row of Q 1. Then A D .d; 0; : : : ; 0/Q 1 imples that ai D dbi for 1 i n. Therefore, d is nonzero, and is a common divisor of a1; : : : ; an. It follows that d is the greatest common divisor of a1; : : : ; an.

Lemma 3.5.12. Let .v1; : : : ; vn/ be a sequence of n elements of Zn. Let P D Œv1; : : : ; vn be the n–by–n matrix whose j th column is vj . The following conditions are equivalent:

(a)

fv1; : : : ; vng is an basis of Zn.

(b)

fv1; : : : ; vng generates Zn.

(c)

P is invertible in Matn.Z/.

Proof. Condition (a) trivially implies condition (b). If (b) holds, then each standard basis element Oej is in Zfv1; : : : ; vng,

X

Oej D

ai;j vi :

(3.5.1)

i

Let A D .ai;j /. The n equations 3.5.1 are equivalent to the single matrix equation E D PA, where E is the n–by–n identity matrix. Thus, P is invertible with inverse A 2 Matn.Z/.

If P is invertible with inverse A 2 Matn.Z/, then E D PA implies

that each standard basis element Oej is in Zfv1; : : : ; vng, so fv1; : : : ; vng generates Zn. Moreover, ker.P / D f0g means that fv1; : : : ; vng is linearly independent.

n

We can now combine Proposition 3.5.9 and Lemma 3.5.12 to obtain

our main result about bases of subgroups of Zn.

i

i

i

“bookmt” — 2006/8/8 — 12:58 — page 193 — #205

i

3.5. LINEAR ALGEBRA OVER Z

193

Theorem 3.5.13. If N is a subgroup of Zn, then N is a free abelian group of rank s n. Moreover, there exists a basis fv1; : : : ; vng of Zn, and there exist positive integers d1; d2; : : : ; ds, such that di divides dj if i j and fd1v1; : : : ; dsvsg is a basis of N .

Proof. If N D f0g, there is nothing to do, so assume N is not the trivial subgroup. We know from Proposition 3.5.7 that N is generated by no more than n elements. Let fx1; : : : ; xsg be a generating set for N of minimum cardinality. Let A denotes the n–by–s matrix whose columns are x1; : : : ; xs. According to Proposition 3.5.9, there exist invertible matrices P 2 Matn.Z/ and Q 2 Mats.Z/ such that A0 D PAQ is diagonal,

A0 D PAQ D diag.d1; d2; : : : ; ds/:

We will see below that all the dj are necessarily nonzero. Again, according to Proposition 3.5.9, P and Q can be chosen so that the di ’s are positive and di divides dj whenever i j . We rewrite the equation relating A0 and A as

AQ D P 1A0:

(3.5.2)

Let fv1; : : : ; vng denote the columns of P 1, and fw1; : : : ; wsg the columns of AQ.

According to Lemma 3.5.12, fv1; : : : ; vng is a basis of Zn. Moreover,

since Q is invertible in Mats.Z/, it follows that fw1; : : : ; wsg generates N . (See Exercise 3.5.7.) Since s is the minimum cardinality of a generating set for N , we have wj ¤ 0 for all j .

We can rewrite Equation (3.5.2) as

Œw1; : : : ; ws D Œv1; : : : ; vnA0 D Œd1v1; : : : ; dsvs:

Since the wj ’s are all nonzero, the dj ’s are all nonzero. But then, since fv1; : : : ; vsg is linearly independent, it follows that fd1v1; : : : ; dsvsg is linearly independent. Thus fw1; : : : ; wsg D fd1v1; : : : ; dsvsg is a basis of N .

n

Exercises 3.5

3.5.1. Consider Z as a subgroup of Q. Show that Z is not complemented; that is, there is no subgroup N of Q such that Q D Z N .

3.5.2. Show that Q is not a free abelian group.

3.5.3. Show that conditions (a) and (c) in Proposition 3.5.2 are equivalent.

3.5.4. Show that A subset of Zn is linearly independent over Z if, and only if, it is linearly independent over Q.

i

i </body></html>

Home