Archive for January, 2009

Finitely generated free abelian groups

31 January, 2009

An abelian group A is called freely generated if it is generated by S\subset A such that f=\sum_{s\in S}k_s s=0 (such an expression is called a relation in S) holds for for a finite sum f of elements of S iff k_s=0 for all s\in S (such a relation is called trivial).

Note a direct analogy between a free generating set and a basis of a vectorspace (here of course the coefficients are integers, not field elements.) Indeed, each a\in A has a unique expression a=\sum_{s\in S}k_s s as a sum of the generators with appropriate integer coefficients; if there were two such expressions a=\sum_{s\in S}k_s s=\sum_{s\in S}k'_s s then 0=\sum_{s\in S}(k_s-k'_s) s would be a nontrivial relation in S, contradiction.
Freely generated groups are also called free. Finitely generated (f.g., for short) free abelian groups are quite close in their behavour to finite-dimensional vectorspaces, although there are important differences, too.
The first important property of f.g. free abelian groups is the following:

Let A be freely generated by a set S and also by a set S'. Then |S|=|S'|.

You can compare it to the well-known fact that two bases of a vectorspaces have the same cardinality. The proof is similar, too, albeit with a twist stemming from the fact that not all nonzero integers have multiplicative inverses.
Each s'\in S' can be written as s'=\sum_{s\in S} k_s(s') s, for k_s(s')\in\mathbb{Z}. Group all the latter in an |S'|\times |S| matrix Q, with entries Q_{s',s}=k_s(s'). Without loss in generatlity we may assume that |S|\leq |S'|. If |S|<|S'| then there exists a nonzero vector v\in \mathbb{Q}^{|S'|}\cap Ker(Q^T), i.e. vQ=0. Clearing denominators in the entries of v, we may assume that they are all integer. Then \sum_{t\in S'}v_t t=0 is a nontrivial relation among elements of S', a contradiction establishing the claimed property.

Thus we see that the number of generators in a free generating sets is an invariant of A. It is called the rank of A and denoted rk(A). This notion is parallel to the notion of the dimension of a vectorspace, for obvious reasons.
The next question is to study subgroups of free abelian groups. Namely, the following holds.

A subgroup H of a f.g. free abelian group A is free, and
rk(H)\leq rk(A).

Let A be freely generated by S=\{s_1,\dots,s_n\} (so n=rk(A)).
We proceed by induction on n. When n=1, we already proved this as a corollary to 1st Isomorphism Theorem.
So we can consider now H_1=H\cap\langle s_1,\dots,s_{n-1}\rangle. By induction, H_1 is f.g., i.e. H_1 is freely generated by h_1=\sum_{j=1}^{n-1} k_{1,j} s_j,\dots,h_{m-1}=\sum_{j=1}^{n-1} k_{m-1,j} s_j. Then m\leq n, otherwise, arguing as in the previous proof, we can find a nontrivial relation between s_1,\dots,s_{n-1}. This settles the 2nd claim of the theorem.

If H_1=H then we are done. So now let us consider expressions h=\sum_{j=1}^n k_j(h) s_j for each h\in H, and define r to be the minimal positive k_n(h), with the minimum taken over all h\in H. Note that each k_n(h) is divisible by r. Let an h_m\in H satisfy k_n(h_m)=r.
We claim that H is f.g. by h_1,\dots, h_m. First, we observe that there are no nontrivial relations between the latter elements. Indeed, if there was one, say \sum_j \ell_j h_j=0, then \ell_m\neq 0 by induction assumption, and so \ell_m h_m\in \langle s_1,\dots,s_{n-1}\rangle. But the latter gives a nontrivial relation between s_j‘s, as \ell_m h_m=\ell_m \sum_j k_j(h_m) s_j, a contradiction.
It remains to show that every h\in H can be written as h=\sum_j \ell_j(h) h_j. Consider x=h-\frac{k_n(h)}{r}h_m. Then x\in H_1, and so h=x+\frac{k_n(h)}{r}h_m=\sum_{j=1}^{m-1}\ell_j(x) h_j + \frac{k_n(h)}{r}h_m, as required.


Properties of homomorphisms of abelian groups

29 January, 2009

Let \phi: B\to A be a homomorphism of abelian groups (B,+) and (A,+) (we denoted operations in both groups by the same symbol – these are different operations, but no confusion will arise; you will always see from the context in which group we work; same for 0s in these groups).

The image of \phi is the set Im(\phi)=\{\phi(b)\mid b\in B\};
the kernel of \phi is the set Ker(\phi)=\{b\in B\mid \phi(b)=0\}.

It is easy to check (check this!) using the definition of homomorphism that sets just defined are subgroups: Im(\phi)\leq A and Ker(\phi)\leq B.

Note that image and kernel are concepts parallel to the concepts of the image and kernel of a linear map between vectorspaces; in particular such linear maps provide homomorphisms between additive groups of the corresponding vectorspaces.

Cosets and quotient, a.k.a. factor, groups .

Let H\leq B. Given b\in B, the set b+H:=\{b+h\mid h\in H\} is called the coset of b in B.
For any x,y\in B the following holds: either x+H=y+H, or x+H\cap y+H=\emptyset. (Indeed, if x-y\in H, then we have the former, as H is closed under addition, otherwise the latter – check this.) Thus we have a partition of B into cosets of H.

A fancy way of saying the latter is to say that being in the same coset of H defines an equivalence relation on B.
As an example, consider B=\mathbb{Z} and a positive integer m. Then the cosets of H=m\mathbb{Z} in B are the sets of integers of the form n+mk, with k,n\in\mathbb{Z}. Then n_1+mk_1 and n_2+mk_2 are in the same coset of H iff n_1-n_2+m(k_1-k_2)\in H, i.e. when m divides n_1-n_2. Recalling the procedure of division with reminder, is easy to see that the cosets are x+H, where x=0,1,\dots, m-1.

The set of cosets of H in B has a natural structure of group defined on it.

The quotient group B/H=(\{b+H\mid b\in B\},+_{B/H}) has the set of cosets of H in B as the set of elements; the addition is defined by (x+H)+_{B/H}(y+H):=(x+y)+H.

In a way, we can identify the operation +_{B/H} with the + in B.
The former is the same as the latter taken “modulo H“.
So we still need to check that this way one ideed has an abelian group. Commutativity and associativity in B/H is immediate from the associativity and commutativity in B. Then, 0_{B/H}=H (note that H=0+H is a coset of H in B, just any other coset), and -(x+H) is -x+H.
Continuing the above example B=\mathbb{Z}, H=m\mathbb{Z} we have B/H isomorphic to \mathbb{Z}_m. This is in fact not suprising, and is implied by the following general theorem.

1st Isomorphism Theorem.

Let \phi: B\to A be a homorphism of abelian groups. Then we can identify Im(\phi) with certain quotient group of B. Namely Im(\phi)\cong B/Ker(\phi). Specifically, the latter isomorphism is given by b+Ker(\phi)\mapsto\phi(b).

The proof of this is left as an easy exercise (that you should do!). The (rather unfortunate) name (1st…) comes from the fact that there are more similar results in group theory (sometimes also the already mentioned facts that Ker and Im are subgroups is included as its part).
It follows that every H\leq B is the kernel of the homomorphism B\to B/H. What distinguishes such homomorphisms from the general ones is that they are surjective, i.e. the target of the mapping equals its image.
(Thus there is a 1-1 correspondence between the surjective homomorphisms from B and subgroups of B.)

A question to think about: what are the groups B/H in the cases when H=B, and H={0}?

Armed with the 1st isomorpshism theorem, we can easily give a proof of our claim about cyclic groups. Namely, let A=\langle s\rangle be a cyclic group. Consider a homomorphism \phi:\mathbb{Z}\to A defined by \phi(n)=ns.
Trivially, \phi is surjective. Let m the minimal positive integer such that ms=0, provided that such an integer exists. We claim that if m does not exist then \phi is an isomorphism, and otherwise Ker(\phi)=\langle m\rangle. Of course, if ks=0 for a negative k, then -ks=0, too, so there is no loss in generality in assuming m\ge 0, if it exists. Thus in the case of no such m we indeed have an isomorphism. In the case when such an m exists it is obvious that m\mathbb{Z}=Ker(\phi) (check this!). Thus, by the 1st isomorphism theorem, A\cong \mathbb{Z}/m\mathbb{Z}, completing the proof of the claim.

Sometimes, although not always, a subgroup isomorphic to B/H is readily found inside B. This is for instance always the case when B is the additive group of a finite-dimensional vectorspace, and H the additive group of a subspace. Then B=A\oplus H, as is known from linear algebra.
(A fancy way to say the latter is to say that B is a split extension of H.)
You are encouraged to show that this is indeed not true in general (Hint: consider B=\mathbb{Z}_4 and \mathbb{Z}_2\cong H=2B\le B.) (Such extensions are called non-split.)

Abelian groups

28 January, 2009

Here is the 1st in the series of posts for the Algbera I course I teach now.

An abelian group is a pair (A,+), where A is a set and a binary operation + on A that is

  • associative, i.e. x+(y+z)=(x+y)+z for all x,y,z\in A,
    and thus we can drop brackets x+(y+z)=x+y+z without introducing any ambiguity;
  • commitative, i.e. y+x=x+y for all x,y\in A,
  • there exists 0=0_A\in A, a special element satisfying x+0=x for all x\in A. It must not be confused with the integer number 0, as in general it has nothing to do with 0_A, although it shares similar properties (integers w.r.t. addition are an example of an abelian group, and there these two things are indeed the same). Elements like 0_A are called neutral w.r.t. the operation in question.
  • for any x\in A there exists x'\in A such that x+x'=0. We denote x' by -x. We usually abbreviate x+(-y) as x-y, etc.

Note that these axioms are essentially the axioms of a vector space that “forgot everything about the field”. The following is also very helpful, although might look evident at first sight.
(But it is not! Later, in ring theory, when we see zero-divisors, we will see that the intuition of “cancelling” may fail you!)

The equation a+x=b for any given a,b\in A has unique solution x=b-a.
Thus we can cancel: x+y=x+z iff y=z, for all x,y,z\in A.

First examples of abelian groups

  1. Integers w.r.t. addition as the operation \mathbb{Z}=(\mathbb{Z},+)
  2. Vector spaces w.r.t. addition of vectors as the operation (such a group is called the additive group of the vector space)
  3. additive groups of fields, e.g. the real numbers w.r.t. addition
  4. Integers modulo m w.r.t. addition \mod m, i.e.

The size of a group A is usually called order, and denote |A|. So |\mathbb{Z}|=\infty, while |\mathbb{Z}_m|=m.

New abelian groups from old: direct products,, a.k.a. direct sums

Given two abelian groups (A,+_A) and (B,+_B), define the group
A\oplus B=(A\times B,+), the direct sum of A and B, where the operation + is component-wise:
(a,b)+(a',b')=(a+_A a',b+_B b').

Similarly, one can define direct sums of an arbitarty number of abelian groups. E.g. the additive groups of n-dimensional vector spaces over a field F can be viewed as direct sums of n copies of the additive group of F.

The next important concept is of homomorphism and isomorphism of abelian groups.

Given two groups (A,+_A) and (B,+_B), a function \phi:B\to A satisfying \phi(b+_B b')=\phi(b)+_A\phi(b') is called a homomorphism from B to A.

When \phi:B\to A is a bijection, then it is called isomorphism, and one writes (A,+_A)\cong (B,+_B), or just A\cong B.

From the point of view of abstract algebra, two isomorphic groups are hardly distinguishable, although of course they can appear in different disguises.
An example of nontrivial isomorphism is \mathbb{Z}_6\cong \mathbb{Z}_2\oplus\mathbb{Z}_3.
(To see the isomorphism, set \phi(1)=(1,1) and try extending it by additivity, i.e. compute \phi(1+1), etc. Eventually you arrive at an isomorphism \phi:\mathbb{Z}_6\to\mathbb{Z}_2\oplus\mathbb{Z}_3.
Interestingly, \mathbb{Z}_4\not\cong \mathbb{Z}_2\oplus\mathbb{Z}_2. Can you prove this?)


A subgroup B of A is a subset of A=(A,+) that is closed under the addition in A. (Notation: B\le A or B\leq A, the latter does not exlcude B=A.)
This means that for any x,y\in B also -x,x+y\in B, and immediately implies 0\in B.

Examples of subgroups:

  1. additive group (U,+) of a subspace U of a vectorspace V is a subgroup of (V,+); in shorthand, (U,+)\leq (V,+);
  2. for any two positive integers m,n, one has \mathbb{Z}_m\leq\mathbb{Z}_{mn}; (this is indeed not immediate, but note that n\in\mathbb{Z}_{nm} generates a subgroup n\mathbb{Z}_{nm}\cong \mathbb{Z}_m.)
  3. m\mathbb{Z}\leq \mathbb{Z}, e.g. for m=2 we have that the set of all even integers form a subgroup in the integers.
  4. for a prime number p, define \mathbb{Z}[\frac{1}{p}]=\{\frac{m}{p^k}\mid m,k\in\mathbb{Z}, k\geq 0\}.

Generating sets, etc.
First, a bit of terminology: any abelian group A is a \mathbb{Z}-module, i.e. in a sense A relates to \mathbb{Z} in a way similar to the way a vectorspace over a field F relates to F. More precisely, this means that for any a\in A, n\in\mathbb{Z}, the product na is well-defined, as follows:

  1. if n=0 then na=0_A,
  2. if n<0 then na=(-n)(-a),
  3. if n>0 then na={a+\dots+a}, the sum of n copies of a.

Note that, in contrast to vectorspace/field relationship, it can perfectly happen that na=0_A while neither n=0 nor a=0_A, e.g. na=0_A for any a\in A=\mathbb{Z}_n.

Let S\subseteq A. Define \langle S\rangle, the subgroup generated by S, to be \langle S\rangle=\cap_{S\subseteq B\leq A} B, i.e. the intersection of all the subgroups of A containing S.

One can prove that \langle S\rangle=\{\sum_{s\in S} k_s s\mid k_s\in\mathbb{Z}, \text{and only finitely many } k_s\neq 0\}. (Note that in algebra infinite sums are, normally speaking, not allowed, as we don’t have a notion of convergence.)

Cyclic subgroups. These are subgroups generated by just one element, s\in A, i.e. one should take S=\{s\} and denote \langle S\rangle=\langle s\rangle.
That is as simple as it gets as far as subgroups are concerned. We define the order of s to the be |\langle s\rangle|, the order of the cyclic subgroup it generates.
Similarly, groups generated by one element are called cyclic.
One can show the following classification of cyclic groups.

Either \langle s\rangle\cong\mathbb{Z} (and so |s|=\infty), or \langle s\rangle\cong\mathbb{Z}_m, for some m>0 (and so |s|=m).

We postpond a proof until we learned more about homomorphisms.

Every subgroup H of a cyclic group A=\langle s\rangle is cyclic.

Let H\leq A, and m the minimal positive integer such that ms\in H. Suppose that ks\in H. Without loss of generality, k\ge 0, as H is a subgroup and so -ks\in H. By the integer division with a remainder algorithm, one has k=nm+\ell, for 0\leq \ell\le m. On the other hand \ell s\in H, as \ell s=(k-nm)s=ks-nms\in H. By the choice of m, we have \ell =0, and so H=\langle ms\rangle.

Generally speaking, complete classification of abelian groups is out of question, but groups that are somehow similar to finite-dimensional vector spaces, finitely generated abelian groups, can be completely classified.

An abelian group A is called finitely generated if there exists S\subset A such that \langle S\rangle=A and |S|<\infty.

You might like think which of the following groups are finitely generated:

  1. the direct sum of a finite number of cyclic groups
  2. (\mathbb{Q},+)
  3. \mathbb{Z}[\frac{1}{p}], for a prime p

Finally, note that there are abelian groups that do not admit a countable generating set, leave alone finite. (Hint: to see this, prove first that a group with a countable generating set is countable.)