Tag Archives: group

SL(2,IR) is the commutator subgroup of GL(2,IR)

Here is a proof of the above fact.

Let N be the commutator subgroup of the general linear group GL(2,\mathbb R); i.e.,

N=\langle ABA^{-1}B^{-1}:A,B\in GL(2,\mathbb R)\rangle.

First, it is clear that N is contained in the special linear group SL(2,\mathbb R), since \det(ABA^{-1}B^{-1})=1 for any A,B\in GL(2,\mathbb R). Next, we claim that N contains all matrices

\begin{pmatrix} 1 & b\\ 0 & 1\end{pmatrix}.

This follows from noting that

\begin{pmatrix} 1 & b\\ 0 & 1\end{pmatrix}=\begin{pmatrix} 1 & b\\ 0 & b\end{pmatrix}\begin{pmatrix} 1 & 1\\ 0 & 1\end{pmatrix}\begin{pmatrix} 1 & b\\ 0 & b\end{pmatrix}^{-1}\begin{pmatrix} 1 & 1\\ 0 & 1\end{pmatrix}^{-1}.

By taking transposes, it also follows that N contains all matrices

\begin{pmatrix} 1 & 0\\ c & 1\end{pmatrix}.

Further, N contains all matrices

\begin{pmatrix} a & 0\\ 0 & 1/a\end{pmatrix}

since

\begin{pmatrix} a & 0\\ 0 & 1/a\end{pmatrix}=\begin{pmatrix} a & 0\\ 0 & 1\end{pmatrix}\begin{pmatrix} 0 & 1\\ 1 & 0\end{pmatrix}\begin{pmatrix} a & 0\\ 0 & 1\end{pmatrix}^{-1}\begin{pmatrix} 0 & 1\\ 1 & 0\end{pmatrix}^{-1}

for any a\neq 0.

Now let

\begin{pmatrix} a & b\\ c & d\end{pmatrix}\in SL(2,\mathbb R).

Then ad-bc=1. Using the above results,

\begin{pmatrix} a & b\\ c & d\end{pmatrix}=\begin{pmatrix} 1 & 0\\ c/a & 1\end{pmatrix}\begin{pmatrix} 1 & ab\\ 0 & 1\end{pmatrix}\begin{pmatrix} a & 0\\ 0 & 1/a\end{pmatrix}\in N

if a\neq 0, and

\begin{pmatrix} a & b\\ c & d\end{pmatrix}=\begin{pmatrix}0&1\\-1&0\end{pmatrix}\begin{pmatrix}1&-\frac{d}{b}\\ 0&1\end{pmatrix}\begin{pmatrix}1&0\\ ab&1\end{pmatrix}\begin{pmatrix}1/b&0\\ 0&b\end{pmatrix}\in N

if b\neq 0, and the latter since

\begin{aligned}\begin{pmatrix} 0 & -1\\ 1 & 0\end{pmatrix}=&\begin{pmatrix}x&y\\0&-x-y\end{pmatrix}\begin{pmatrix}-x-y&0\\ x&y\end{pmatrix}\begin{pmatrix}x&y\\0&-x-y\end{pmatrix}^{-1}\begin{pmatrix}-x-y&0\\ x&y\end{pmatrix}^{-1}\\ \in &N\end{aligned}

for any x,y,x+y\neq 0. Thus SL(2,\mathbb R)\subseteq N, i.e., N=SL(2,\mathbb R).

Advertisements

Leave a comment

Filed under Linear algebra

A nice group theory result

While working on some group theory problems today a friend and I came up with the following result.

Lemma. Let H be a normal subgroup of a finite group G such that \gcd(|H|,|G/H|)=1. If the order of g\in G divides |H|, then g\in H.

Proof. Let d be the order of g. Then the order d' of gH in G/H divides both d and |G/H|. But \gcd(d,|G/H|)=1. Hence d'=1, i.e., gH=H, i.e., g\in H. \square

Corollary 1. Let H be a normal subgroup of a finite group G such that \gcd(|H|,|G/H|)=1. If K\le G such that |K| divides |H|, then K\le H.

Proof. Apply the lemma to the elements of K. \square

Corollary 2. Let H be a normal subgroup of a finite group G such that \gcd(|H|,|G/H|)=1. Then H is the unique subgroup of G of order |H|.

Proof. Use Corollary 1. \square

Here is an example of the lemma in action.

Problem. Show that S_4 has no normal subgroup of order 8 or 3.

Solution. If H is a normal subgroup of S_4 of order 8, then \gcd(|H|,|S_4/H|)=1. Hence every element of order 2 or 4 in S_4 must lie in H. In particular, (1\ 2),(1\ 2\ 3\ 4)\in H. By a result in the previous post, H=S_4, a contradiction.

Likewise, if H is a normal subgroup of S_4 of order 3, then H must contain every 3-cycle; in particular, (1\ 2\ 3),(2\ 3\ 4)\in H. Hence (1\ 2\ 3)(2\ 3\ 4)=(1\ 2)(3\ 4)\in H. But this has order 2, and 2\nmid 3, a contradiction. \square

More generally, we can prove the following.

Corollary 3. S_n for n\ge 4 has no non-trivial proper normal subgroup H with \gcd(|H|,|S_n/H|)=1.

Proof. Suppose otherwise and let d divide |H|. Then H must contain all d-cycles. So if |H| is even then taking d=2 gives H=S_n. If |H| is odd, it contains the cycles \sigma=(1\ \cdots\ d) and \rho=(d\ \cdots\ 2\ n) for some 3\le d<n. Then \sigma\rho=(1\ 2\ n)\in H has order 3. So |H| contains all 3-cycles, i.e., A_n\le H. Since A_n\le S_n is maximal, either H=A_n or H=S_n, a contradiction. \square

Leave a comment

Filed under Algebra

Generating the symmetric group

It’s a fairly well-known fact that the symmetric group S_n can be generated by the transposition (1\ 2) and the ncycle (1\ \cdots\ n). One way to prove it is as follows.

  1. Show that the transpositions (a\ b) for a,b\in\{1,\dots,n\} generate S_n.
  2. Show that any transposition (a\ b) can be obtained from (1\ 2) and (1\ \cdots\ n).

We also need the following key lemma the proof of which is routine.

Lemma. \rho (a\ b)\rho^{-1}=(\rho(a)\ \rho(b)) for any \rho\in S_n and a,b\in\{1,\dots,n\}.

(1) is easily proven by the observation that any permutation of 1,\dots,n can be obtained by swapping two elements at a time. (2) is a bit more interesting.

We first use the lemma to observe that any transposition of the form (a\ a+1) can be obtained from (1\ 2) upon repeated conjugation by (1\ \cdots\ n). Now, since (a\ b)=(b\ a), WLOG let a<b. Using the lemma, conjugating (a\ a+1) by (a+1\ a+2) gives (a\ a+2), conjugating (a\ a+2) by (a+2\ a+3) gives (a\ a+3), etc. In this way we can eventually get (a\ b). So we are done by (1).

This argument shows that S_n can in fact be generated by (a\ a+1) and (1\ \cdots\ n) for any a.


Now let’s consider an arbitrary transposition \tau and an n-cycle \sigma in S_n. By relabeling 1,\dots,n, we can assume that \sigma=(1\ \cdots\ n) and \tau=(a\ b) for a<b. Note that \sigma^{-a+1}\tau\sigma^{a-1}=(1\ c) where c=b-a+1, so WLOG \tau=(1\ c). Then \sigma^k\tau\sigma^{-k}=(1+k\ c+k) for each k. In particular, taking k=c-1 gives \sigma^{c-1}\tau\sigma^{-c+1}=(c\ 2c-1)=:\rho. Then \rho\tau\rho^{-1}=(1\ 2c-1). Repeating this procedure produces (1\ c+k(c-1)) for k=0,1,2,\dots. Now \{c+k(c-1):k=0,1,\dots,n-1\} is a complete set of residues mod n if and only if \gcd(c-1,n)=1, i.e., \gcd(b-a,n)=1. So we’ve shown that

Theorem. Let \tau=(a\ b) be a transposition and \sigma=(c_1\ \cdots\ c_n) be an n-cycle in S_n. Then \tau and \sigma generate S_n if and only if \gcd(c_b-c_a,n)=1.

In particular, (a\ b) and (1\ \cdots\ n) generate S_n if and only if \gcd(b-a,n)=1.

Corollary. S_p is generated by any transposition and any p-cycle for p prime.

1 Comment

Filed under Algebra

Jordan-Hölder theorem

I am cramming for my algebra comprehensive exam so I will probably be posting stuff like this for a while.

A chain of subgroups \{e\}=H_0\triangleleft H_1\triangleleft\cdots\triangleleft H_n=G of a finite group G with H_{i+1}/H_i simple for all i is called a composition series of G. (The H_{i+1}/H_i are called composition factors.) The theorem in question states that every group has a composition series, and the composition factors in any two such series are unique up to reordering.

We can easily prove the first part of the theorem, that any finite group has a composition series, using the extreme principle. Let n\ge 0 be the largest integer for which there is a chain \{e\}=H_0\triangleleft H_1\triangleleft\cdots\triangleleft H_n=G of subgroups. (Such an n exists because there is trivially a chain with n=1, and our group is finite.) We claim that the composition factors in this case are simple. If not, WLOG H_{i+1}/H_i has a non-trivial normal subgroup \widetilde N. By correspondence, \widetilde N=N/H_i for some H_i\triangleleft N\triangleleft H_{i+1}. But then

\{e\}=H_0\triangleleft H_1\triangleleft\cdots\triangleleft H_i\triangleleft N\triangleleft H_{i+1}\cdots\triangleleft H_n=G

is a longer chain, a contradiction.

While the proof of the general theorem requires some non-trivial group theory (e.g. see here), we can easily prove the theorem for finite abelian groups using elementary number theory. For such a group, the orders of the composition factors must exactly be the prime factors—listed with multiplicity—of the order of the group. So the result follows immediately from the fundamental theorem of arithmetic.

Leave a comment

Filed under Algebra, Number theory

Permutation of digits by multiplication

Here is an expository write-up of this post.

The number N=142857 is interesting because of the following property

\begin{aligned}N&=142857\\ 2N&=285714\\ 3N&=428571\\ 4N&=571428\\ 5N&=714285\\ 6N&=857142\end{aligned}

and 7N=999999. The last equation means that

\displaystyle\frac 17=0.\overline{142857}.

So multiplying N by 1,2,3,4,5,6 simply permutes the digits of N. As elements of S_6 these permutations correspond to (using cycle notation)

\hbox{id}, (153)(264), (165432), (135)(246), (123456), (14)(25)(36)

respectively. We can read off the following from this list.

  • Since (165432) and (123456) are full-length cycles, 3 and 5 are primitive roots modulo 7.
  • 2 and 4 have order 3 modulo 7, while 6 has order 2.

In general, if p is an odd prime and b is a positive integer with order d modulo p, then 1/p will have period (b^d-1)/p of length d in base b. This follows simply from observing that if b^d-1=mp then

\displaystyle\frac 1p=\frac{m}{b^d-1}=\frac{m}{b^d}+\frac{m}{b^{2d}}+\frac{m}{b^{3d}}+\cdots.

Now let b>p be a primitive root modulo p. We shall work in base b. Then 1/p will have period L=(b^{p-1}-1)/p of length p-1. Since the periods of 1/p,2/p,\dots,(p-1)/p are L,2L,\dots,(p-1)L, all of length p-1, which are all powers of some permutation of the digits of L, and no two of which are congruent modulo b, it follows that the digits of L are all distinct. So we’ve shown the following.

Theorem. If p is an odd prime and b>p is a primitive root modulo p, then the base b expansion of 1/p has period of length p-1 with distinct digits.

Taking p=7, b=10 gives our previous example. So the prime 7 in base 10 is indeed very special, since it is the only prime less than 10 for which 10 is a primitive root.

1 Comment

Filed under Number theory