Friday, June 02, 2006

Group Theory: Lagrange's Theorem

In today's blog, I review the proof for Lagrange's Theorem. The theorem is named after Joseph-Louis Lagrange who first stated it. The first complete proof came 30 years later.

In today's blog, I also use the concept of order, subgroup, and coset. The concept of the coset was first proposed by Evariste Galois. The term "coset" was coined by G. A. Miller in 1910.

The content of today's blog is taken from Joseph A. Gallian's Contemporary Abstract Algebra.

Definition 1: Order of a Group

The number of elements of a group.

NOTE: If you need to review the definition of the group, see here.

Definition 2: Subgroup

If H is a subset of a group G and H is a group itself under the operation of G, then H is a subgroup of G.

Definition 3: Coset of H in G

Let G be a group and H a subgroup of G. For any a ∈ G, the set aH { ah : h ∈ H } is called the left coset of H in G containing a. The set Ha { ha : h ∈ H } is called the right coset of H in G containing a.

NOTE: An important idea behind the coset is that it is a distinct partition of elements (see Lemma 2 below). From the property of closure, we know that if two values are elements of a group, then their product (by this, I mean the result of the group operation) is also an element of the group.

From this, we know that the set of cosets can be divided up as follows: a1H, a2H, ..., arH where r is a positive integer and where for each coset i ≠ j → aiH ∩ ajH = ∅ [See Lagrange's Theorem below to see how this partitioning can be used]

Example 1 Coset: Z9

Let G = Z9 = { 0, 1, 2, 3, 4, 5, 6, 7, 8 } with operation '+'

NOTE: Z9 is the set of integers modulo 9 [See here for a review of modular arithmetic]

Let H = { 0, 3, 6 } with operation '+'

We can see that H is a subgroup of G

The left coset in this case is a+H (note it would aH is the operation were '*')

Here are the cosets:

0 + H = { 0, 3, 6 } = 3 + H = 6 + H
1 + H = { 1, 4, 7 } = 4 + H = 7 + H
2 + H = {2, 5, 8} = 5 + H = 8 + H

We can see that all cosets are either equal or distinct. I present a proof of this in Lemma 2 below.

Example 2: Even integers

Let Z be the set of integers

Then 2Z is a left coset which includes { ..., 0, 2, 4 , 6, ... }

Lemma 1: aH = H if and only if a ∈ H

Proof:

(1) Assume aH = H

(2) Then, a = ae ∈ aH = H

(3) Assume a ∈ H

(4) aH ⊆ H since h ∈ H → ah ∈ H [By property of closure, see here if needed]

(5) H ⊆ aH since:

(a) Let h be any element of H.

(b) a-1 ∈ H since a ∈ H [By the inverse property, see here if needed]

(c) a-1H ∈ H [By property of closure, see here if needed]

(d) So h = eh = (aa-1)h = a(a-1h) [By identity property, inverse property, and associative property, see here if needed]

(e) But a(a-1h) ∈ aH so that from (#5d), h ∈ aH.

(6) So H = aH since H ⊆ aH and aH ⊆ H.

QED

Lemma 2: if aH, bH are two cosets, then aH = bH or aH ∩ bH = ∅

Proof:

(1) Assume that aH ∩ bH ≠ ∅

(2) Let x ∈ aH ∩ bH since aH ∩ bH ≠ ∅

(3) Then there exists h1, h2 such that:

x = ah1
x= bh2

Since x is found in both aH and bH by assumption.

(4) Thus, a = xh1-1 = (bh2)h1-1

(5) From this, aH = [(bh2)h1-1]H = b(h2h1-1H) = bH [By Lemma 1 above]

QED

Theorem: Lagrange's Theorem

If G is a finite group and H is a subgroup of G, then the order of H divides the order of G.

Proof:

(1) Let a1H, a2H, ..., arH denote the distinct left cosets of H in G. [See Definition 3 above for details on left cosets of H in G.]

NOTE: If two cosets are equal then we only count them once.

(2) For each a ∈ G, we have aH = aiH for some i by our construction in step #1.

(3) a ∈ aH since:

a = ae and ae ∈ aH since H is a subgroup. [See Definition 2 above for details on subgroups]

(4) Thus, each member of G belongs to one of the cosets aiH [from step #2 and step #3.]

(5) G = a1H ∪ a2H ∪ ... ∪ arH [This follows directly from step #4]

(6) From Lemma 2 above, we know aiH = ajH or aiH ∩ ajH = ∅ and since each ai is distinct, we get:

order(G) = order(a1H) + order(a2H) + ... + order(arH)

(7) Since order(aiH) = order(H) for each i (by the definition of cosets, see definition 3 above, we have:

order (G) = r*order(H)

QED

10 comments :

Akash said...

Hi Larry,

It was wonderful going thru ur blog. You really have maintained it in an impeccable manner - i must say. Further, you have gone thru the troubles of providing links for some concepts which others might need and again it is a wonderful act and i really appreciate it. The world needs more math afficiandos like you.

Thanks for your beautiful explanations. Again I add thanks for your selfless service to humanity....Hope you create a book out of your blogs.

Tom said...

Hi Larry,

On your page about the proof of Lagrange theorem at

http://mathrefresher.blogspot.com/2006/06/group-theory-lagranges-theorem.html

can you explain how step 5 in Lemma 2 follows from Lemma 1? I'm not sure I understood.

Larry Freeman said...

Hi Tom,

I'll try to break it down step by step. I hope that this makes the step clear.

In Lemma 2, step #3 says that:
x = bh_2
x = ah_1

Since x=ah_1, we know that:
a = x(h_1)^(-1)

Since x=bh_2, we know that:
x(h_1)^(-1) = (bh_2)(h_1)^(-1)

Since a = x(h_1)^(-1), it follows that:
a = (bh_2)(h_1)^(-1)

Since a=(bh_2)(h_1)^(-1), it follows that:
aH=[(bh_2)(h_1)^(-1)]H

We further note that:
[(bh_2)(h_1)^(-1)]H = b[(h_2)(h_1)^(-1)H]

Now, we know that h_1,h_2 are elements of H [from step #3]

Since h_1 ∈ H, it follows that (h_1)^(-1) ∈ H. [Since closure is a property of groups]

Since (h_1)^(-1) ∈ H and h_2 ∈ H, it follows that (h_2)(h_1)^(-1) ∈ H

That's all we need to use Lemma 1 above. Since (h_2)(h_1)^(-1) ∈ H,
[(h_2)(h_1)^(-1)]H = H

Since [(h_2)(h_1)^(-1)]H = H, it follows that:
b[(h_2)(h_1)^(-1)]H = bH

Tom said...

Thank you, that made it clear!

Manohar Kuse said...

Very well exlained. This note on lagrange theorem in group theory helped me more than my textbook.
Thanks!!!

paaji said...

GOD !!!

novita said...

hi,
thanks for your explanation,,
the first time i read the proof in the book contemporary abstract algebra,n when i read your explanation i understand about the proof but i still confused about steps 6 order(G)= order(a1(H))+....order(ar(H))if we sum like that so relation with your example before o(G)=o(0(H))+o(1(H))...+o(8(H))=3+3+3+3+3+3+3+3=24.it is wrong,because o(G)=9
and then steps 7 o(G)= r.o(H) relation with example r=8 so o(G)=8.3=24.
please explain that i need that in this week..

Larry Freeman said...

Hi Novita,

Can you provide more details on your example. I'm not clear how you are getting to O(G)=9.

Are you sure that you are following this assumption:

From this, we know that the set of cosets can be divided up as follows: a1H, a2H, ..., arH where r is a positive integer and where for each coset i ≠ j → aiH ∩ ajH = ∅

-Larry

Pawan Seerwani said...

This post helped me a lot..!!
Thanks and keep writing..! :) :)

Pawan Seerwani said...
This comment has been removed by a blog administrator.