Search for notes by fellow students, in your own course and all over the country.
Browse our notes for titles which look like what you need, you can preview any of the notes via a sample of the contents. After you're happy these are the notes you're after simply pop them into your shopping cart.
Document Preview
Extracts from the notes are below, to see the PDF you'll receive please use the links above
Notes on Algebra
Donu Arapura
December 5, 2017
Contents
1 The idea of a group
1
...
3
8
2 The group of permutations
11
2
...
13
3 Rotations and reflections in the plane
15
3
...
17
4 Cyclic groups and dihedral groups
19
4
...
22
5 Finite sets, counting and group theory
24
5
...
28
6 More counting problems with groups
29
6
...
34
7 Kernels and quotients
36
7
...
39
8 Rings and modular arithmetic
40
8
...
43
9 Z∗p is cyclic
9
...
45
47
10 Matrices over Zp
49
10
...
50
11 The sign of a permutation
52
11
...
54
12 Determinants
56
12
...
59
1
13 The 3 dimensional rotation group
60
13
...
63
14 Finite subgroups of the rotation group
64
14
...
67
15 Quaternions
15
...
69
71
16 The Spin group
73
16
...
75
2
Chapter 1
The idea of a group
One of our goals in this class is to make precise the idea of symmetry, which is
important in math, other parts of science, and art
...
But what does this mean? One
way of expressing this is to a view a symmetry of a given shape as a motion
which takes the shape to itself
...
3
1
2
We want to describe all the symmetries, which are the motions (both rotations and flips) which takes the triangle to itself
...
We call this I, which stands for identity
...
We can rotate once counterclockwise
...
We can rotate once clockwise
R− : 1 → 3 → 2 → 1
...
In the limit, as the number of vertices go to infinity, we get the circle
...
We can use any rotation about the center,
or a reflection about a line through the center
...
) and two dimensional crystals is a repetetive pattern in the plane such
as the one drawn below
...
Then there are infinitely many symmetries
...
We
can also flip or reflect the pattern along vertical lines
...
This has translational symmetries as before, but no flipping symmetries
...
One might ask can we replace four by five, or some arbitrary number of, ducks and still get an infinitely repeating symmetric pattern
as above? The answer surprisingly is no
...
The study of symmetry leads to an algebraic structure
...
To simplify further, let us start with the limiting case where r → ∞
...
These can be
described precisely as follows
...
We
can see that if we translate by x and then by y, it is the same as translating by
x + y
...
Basic laws of algebra
have a natural meaning here: Translating by x and then by 0 is the same as
translating by x, or in symbols
x+0=x
( 0 is the identity)
Translating by x and then y is that same translating y and then x, or
x+y =y+x
(commutative law)
We can always translate back to where we started because
Given x, we can find y with x + y = 0
(existence of the inverse)
Finally, translating by three numbers x, y, z in succesion is the same as translating by x + y and then z, or x then y + z
...
Let Rθ : C → C be the rotation (counterclockwise) through an
angle θ ∈ [0, 2π) = {x ∈ R | 0 ≤ x < 2π} measured in radians
...
Now we define addition in
C as follows: given θ, φ ∈ C, let θ ⊕ φ be given by rotating θ by the additional
angle φ
...
At first it may seem like a strange operation, but notice that many familiar
rules apply:
5
Lemma 1
...
If θ ∈ C, then θ ⊕ 0 = θ
...
Since θ < 2π, θ ⊕ 0 = θ + 0 = θ
Lemma 1
...
If θ, φ ∈ C, then θ ⊕ φ = φ ⊕ θ
...
If we compare
(
φ+θ
φ⊕θ =
φ + θ − 2π
if φ + θ < 2π
if φ + θ ≥ 2π
we see that it is identical to θ ⊕ φ
...
3
...
Proof
...
We omit the proof for now, but the associative law
θ ⊕ (φ ⊕ ψ) = (θ ⊕ φ) ⊕ ψ
also holds
...
We have a name for such a thing
...
To
appreciate the power of this simple set of rules, let us extend a standard result
from highschool algebra
...
4
...
For any a, b ∈ A, there is exactly one solution to x + a = b
...
By the axioms, there exists an element that we denote by −a such that
a + (−a) = 0
...
Suppose that x is any solution to
x + a = b
...
In the future, we will just write b − a instead of b + (−a)
...
Given a set X,
6
a permutation of X is a one to one onto function f : X → X
...
The symmetries R+ etc
...
Here are some abstractly given permutations
of the set {1, 2, 3, 4}
...
It may be helpful to visualize these
2 ← 1
1 → 2
3 ← 2
2 → 3
,
=
f=
1 ← 3
3
→
1
4 ← 4
4 → 4
2 ← 1
1 → 2
1 ← 2
2 → 1
=
g=
4 ← 3
3 → 4
3 ← 4
4 → 3
Since the above notations are a bit cumbersome, we often write this in permutation notation as
1 2 3 4
1 2 3 4
f=
,g =
2 3 1 4
2 1 4 3
Note these are not matrices
...
A cycle of a permutation is a sequence of elements a → f (a) →
f (f (a))
...
To specify a permutation it is just enough to list
the cycles as in
f = (123)(4), g = (12)(34)
Cycles consisting of just one element are usually omitted, so we would write
f = (123)
...
Given two permutations f : X → X and g : X → X
...
In the examples above,
f ◦ g(1) = f (g(1)) = f (2) = 3, etc
...
More visually
3 ← 2 ← 1
2 ← 1 ← 2
fg =
=
4 ← 4 ← 3
1 ← 3 ← 4
7
3
2
4
1
←
←
←
←
1
2
3
4
Note that we use backword arrows because this is consistent with function composition
...
With a bit of practice, this can this read off directly from the permutation
symbols
1 2 3 4
1 2 3 4
1 2 3 4
=
2 3 1 4
2 1 4 3
3 2 4 1
We now return to our triangle example
...
The full multiplication table can be worked out with enough patience as
◦
I
F12
F13
F23
R+
R−
I
I
F12
F13
F23
R+
R−
F12
F12
I
R+
R−
F23
F13
F13
F13
R−
I
R+
F12
F23
F23
F23
R+
R−
I
F13
F12
R+
R+
F23
F13
F12
R−
I
R−
R−
F13
F23
F13
I
R+
One thing that can be observed from the table is that every element has an
inverse, i
...
an element which multiplies with it to give the identity
...
A group is a set with an multiplication, which is associative,
has an identity and such that every element has an inverse
...
Suffice it to say that we now have two new
examples of groups
...
1
...
Show that all the rotations preserving the square are given by I, R, R2 =
RR and R3
...
2
...
Write these out explicitly in cycle notation
...
The above 8 rotations and flips is a complete list of all the symmetries
of the square
...
Give an example of a
permutation of {1, 2, 3, 4} which is not a symmetry of the square
...
Determine the inverses of the rotations R, R2 = RR and R3
...
Determine the group of symmetries (rotations and flips) of a rectangle
which is not a square
...
Determine all the symmetries of a regular pentagon
...
7
...
)
(a) Given z = a + bi ∈ C, recall that z¯ = a − bi
...
(b) Let C be the set of complex numbers of the form a + bi, where
a2 + b2 = 1
...
Conclude that C is a group under multiplication
...
This is
another way to turn C into a group which is the same as the previous
group in an appropriate sense
...
Equivalently, if f (x1 ) = f (x2 ) then x1 = x2
...
An
important example of a function is the identity function idX : X → X defined
by idX (x) = x
...
If X is understood, we
write this as id
...
1
...
1
...
2
...
Proof
...
If g ◦ f (x1 ) = g ◦ f (x2 ),
g(f (x1 )) = g(f (x2 ))
...
This proves 1
...
Given z ∈ Z, we can find y ∈ Y
that g(y) = z because g is onto
...
This proves 2
...
such
= y
...
2
...
To be clear two functions are considered to be equal if they produce
equal outputs on the same input
...
3
...
11
Proof
...
We
define f −1 (y) = x
...
Lemma 2
...
Given a function f : X → Y , f ◦ idX = f and idY ◦ f = f
...
The first equation holds because f ◦ id(x) = f (id(x)) = f (x)
...
Now come to the key definition
...
5
...
The associative law: (x ∗ y) ∗ z = x ∗ (y ∗ z)
2
...
Existence of inverses: given x, there exists y such that x ∗ y = y ∗ x = e
We sometimes say that (G, ∗, e) is a group we want to specify the operation
and identity
...
We will see in the exercises that each x has exactly one inverse
...
It is also worth repeating what we said in the first chapter in this context
...
6
...
Given a set X, recall that a permutation of X is a one to one onto function f :
X → X
...
When X = {1, 2,
...
Putting
the previous lemmas, we get
Theorem 2
...
SX becomes a group under composition, with identity given by
id
...
Most of you have actually
encountered this before, although perhaps not by name, and in particular, you
probably already know is that:
Theorem 2
...
The number of elements of Sn is n! = 1 · 2 · 3 · · · n
...
For n = 3, we see that S3 has
6 elements, so it must coincide with the symmetry group of the triangle
...
This a pretty typical
...
Definition 2
...
Given a group (G, ∗, e), a subset S ⊆ G is called a subgroup
if e ∈ S, and x, y ∈ S implies x ∗ y, x−1 ∈ S (one says that S is closed under
these operations)
...
Proposition 2
...
A subgroup S ⊆ G of a group is also a group
...
The same laws of G hold for elements of
S
...
id =
1 2 3
...
For example,
1 2 3 4
f=
1 4 2 3
1 4 2 3
1 2 3 4
−1
f =
=
1 2 3 4
1 3 4 2
In cycle notation, we simply reverse the cycles
f = (243), f −1 = (342)
2
...
Let X be a nonempty set and let f : X → X be a function
...
(One direction is easy, and the other
will require you to be a bit creative
...
Let X be a nonempty set and let f : X → X be a function
...
(People who know some set theory will need to
invoke the axiom of choice
...
A permutation f ∈ Sn is a transposition, if it interchanges two numbers,
say i and j and fixes everything else, i
...
f (i) = j, f (j) = i, f (x) = x, i 6=
x 6= j, or f = (ij) in cycle notation
...
(b) Check (12)(34), (123), (1234) ∈ S4 are products of transpositions
...
4
...
In
other words, if x ∗ e0 = e0 ∗ x = x holds for all x, prove e0 = e
...
Given a group (G, ∗, e),
13
(a) Prove that every element x as exactly one inverse
...
(b) Prove that (x ∗ y)−1 = y −1 ∗ x−1
...
Given a group (G, ∗, e),
(a) Given y, z ∈ G, prove that there is exactly one x1 ∈ G satisfying
x1 ∗ y = z and exactly one x2 ∈ G satisfying y ∗ x2 = z
...
e
...
7
...
(If
you happen to know Lagrange’s theorem, don’t use it
...
)
8
...
(a) Prove that if H and K are both subgroups of a group G, then H ∩ K
is a subgroup
...
Let
a11 a12
...
...
If B is another n × n matrix, we can form
their product C = AB which is another n × n matrix with entries
X
cij = ai1 b1j + ai2 b2j +
...
has entries
(
1
δij =
0
...
if i = j
otherwise
Lemma 3
...
Matrix multiplication is associative and I is the identity for it,
i
...
AI = IA = A
...
Given matrices A, B, C, the ijth entries of A(BC) and (AB)C both work
out to
XX
aik bk` c`j
k
`
Also
aij =
X
aik δkj =
k
X
k
15
δik akj
An n × n matrix A is invertible if there exists an n × n matrix A−1 such that
AA = A−1 A = I
...
2
...
For 2 × 2 matrices there is a simple test for invertibility
...
3
...
In this case,
d −b
A−1 = (det(A))−1
−c a
Proof
...
Then an easy calculation gives
−c a
AB = BA = ∆I
...
Suppose that ∆ = 0 and A−1 exists
...
This implies that A = 0, and therefore
that 0 = AA−1 = I
...
Let us study an important subgroup of this
...
We denote the set of these by SO(2) (SO stands for
special orthogonal)
...
4
...
16
Proof
...
If we multiply two rotation matrices
cos θ − sin θ cos φ − sin φ
R(θ)R(φ) =
sin θ
cos θ
sin φ cos φ
"
#
cos θ cos φ − sin θ sin φ − cos θ sin φ − sin θ cos φ
=
sin θ cos φ + cos θ sin φ cos θ cos φ − sin θ sin φ
cos(θ + φ) − sin(θ + φ)
=
sin(θ + φ) cos(θ + φ)
= R(θ + φ)
Therefore SO(2) is closed under multiplication
...
Since the first
column is on the unit circle, it can be written as (cos θ, sin θ)T (the symbol
(−)T , read transpose, turns a row into a column)
...
This implies that the second column is ±(− sin θ, cos θ)T
...
This means that F (θ) is a reflection about the line
spanned by v1
...
5
...
Given a unit vector v ∈ R2 and A ∈ O(2), Av is also a unit vector
...
3
...
Let U T (2) be the set of upper triangular matrices
1 a
0 1
Show this forms a subgroup of GL2 (R)
...
Let U T (3) be the set of upper triangular matrices
1 a b
0 1 c
0 0 1
Show this forms a subgroup of GL3 (R)
...
Find a pair of nonzero orthogonal vectors v1 , v2 , F (θ)v1 = v1 and F (θ)v2 =
−v2
...
)
4
...
A matrix is called orthogonal if AT A = I = AAT (the second
equation is redundant but included for convenience)
...
(b) Prove that the set of n × n orthogonal matrices O(n) is a subgroup
of GLn (R)
...
5
...
6
...
Write P (σ) for the permutation
matrix corresponding to σ ∈ S3
...
What can you conclude about the set {I, F }?
7
...
Prove the same thing for GLn (R), where permutations matrices are defined the same way
...
)
18
Chapter 4
Cyclic groups and dihedral
groups
Consider the group Cn of rotational symmetries of a regular n-gon
...
, n
...
Rn−1 } ⊂ Sn
where I = id and
R = (123
...
We won’t need to multiply permutations
explicitly, we just use this rule: Rj Rk = Rj+k and if j + k ≥ n, we “wrap
around” to Rj+k−n
...
Definition 4
...
A finite group G is called cyclic if there exists an element
g ∈ G, called a generator, such that every element of G is a power of g
...
In particular:
Lemma 4
...
A cyclic group is abelian
...
g j g k = g j+k = g k g j
...
Let
Zn = {0, 1, 2
...
(
x+y
if x + y ∈ Zn
x⊕y =
x + y − n otherwise
19
This is usually called modular addition
...
Here is the table for n = 2
⊕
0
1
0
0
1
1
1
0
This is the simplest nonzero abelian group
...
We can see that µ2 = {1, −1} is a cyclic group under multiplication
...
2πik
2πik
µn = e2πik/n = cos
+ i sin
| k = 0, 1,
...
µn is generated by e2πi/n , so it is cyclic
...
If we associate k 7→ Rk or k 7→ e2πik/n and compare addition/multiplication tables, they will match
...
Definition 4
...
If (G, ∗, e) and (H, ◦, e0 ) are groups
...
A one to
one onto homomorphism is called an isomorphism
...
In symbols, we write G ∼
= H
...
The
function f : Z → µn defined by f (k) = e2πik/n is a homomorphism which is not
an isomorphism because it is not one to one
...
Theorem 4
...
A cyclic group of order n is isomorphic to Zn
...
Let G be the cyclic group in question with generator g
...
That is g n1 = g n2 for n1 > n2
...
Let us assume that n is the smallest such
number (this is called the order of g)
...
, g n−1 } and
that all the elements as written are distinct
...
n − 1} then g m1 6= g m2
...
So now the function f (i) = g i is easily seen to given an isomorphism from
Zn to G
...
We make
use of a result usually called the “division algorithm”
...
Theorem 4
...
Let x be an integer and n positive integer, then there exists a
unique pair of integers q, r satisfying
x = qn + r, 0 ≤ r < n
Proof
...
Suppose r ≥ n
...
This is a contradiction, therefore r < n
...
Then r0 ∈ R so r0 ≥ r
...
So r0 − r is divisible by n
...
But 0 is the only integer in this range divisible
by n is 0
...
We denote the number r given above by x mod n; mod is read “modulo” or
simply “mod”
...
Lemma 4
...
If x1 , x2 , n are integers with n > 0, then
(x1 + x2 ) mod n = (x1 mod n) ⊕ (x2 mod n)
Proof
...
Then xi = qi n + ri for appropriate qi
...
We see that
(
r1 + r2 = r1 ⊕ r2
if r1 + r2 < n
(x1 + x2 ) mod n =
r1 + r2 − n = r1 ⊕ r2 otherwise
This would imply that f (x) = x mod n gives a homomorphism from Z → Zn
if we already knew that Zn were a group
...
Lemma 4
...
Suppose that (G, ∗, e) is a group and f : G → H is an onto map
to another set H with an operation ∗ such that f (x ∗ y) = f (x) ∗ f (y)
...
In the future, we usually just write + for modular addition
...
There are 2n elements in total consisting
21
of n rotations and n flips
...
Let
R = (123
...
This generates a cyclic subgroup Cn ⊂ Dn
...
One can calculate that
FR =
1
n
2
n−1
...
1
1
2
2
3
...
n
1
= (1 n − 1)(2 n − 2)
...
n
1
F RF =
n − 1 n − 2
...
n
=
n 1
...
...
We will eventually see that the elements of Dn are given by
I, R, R2
...
So we say that these elements generate the group
...
) We have three basic relations
among the generators
F 2 = I, Rn = I, F RF = R−1
Everything else about Dn follows from this
...
For instance, let us check that (F R)2 = I
using only these relations
(F R)2 = (F RF )R = R−1 R = I
4
...
Determine all the generators of Z6 and Z8
...
Let Z∗7 = {1, 2, 3, 4, 5, 6} with an operation defined by x y = (x·y) mod 7
...
3
...
} is a cyclic
subgroup
...
The order of this
group is called the order of g
...
4
...
22
5
...
7
...
Let us say that an infinite group is cyclic if it isomorphic to Z
...
7
...
Let
d ∈ G be the smallest positive element
...
Conclude that G is cyclic
...
Let F, R ∈ Dn be as above
...
(b) Show that for any i, j > 0, (F Ri )(F Rj ) is a rotation
...
, n
...
Assuming the previous exercise, show that f : Dn → Z2 given by f (Ri ) =
0 and f (F Ri ) = 1 is a homomorphism
...
Let G ⊂ O(2) be the set of matrices
2πk
cos θ ± sin θ
|θ=
, k = 0, 1,
...
Use these facts to prove
that Dn is isomorphic to G
...
} be the set of natural numbers
...
So that [0] = ∅ is the empty set, and [n] = {0, 1,
...
A set X is called finite if there is a one to one onto function (also called a one
to one correspondence) f : [n] → X for some n ∈ N
...
Lemma 5
...
If X is finite and g : X → Y is a one to one correspondence,
then Y is finite and |Y | = |X|
...
By definition, we have a one to one correspondence f : [n] → X, where
n = |X|
...
Proposition 5
...
If a finite set X can be written as a union of two disjoint
subsets Y ∪ Z, then |X| = |Y | + |Z|
...
)
Proof
...
Define
h : [n + m] → X by
f (i)
if i < n
h(i) =
g(i − n) if i ≥ n
This is a one to one correspondence
...
Yn such that Yi and Yj are disjoint whenever i 6= j
...
3
...
Yn is a partition, then |X| = |Y1 | + |Y2 | +
...
24
Proof
...
Yn | = |Y1 | + |Y2 | + |Y3 ∪
...
= |Y1 | + |Y2 | +
...
4
...
The collection {f −1 (y)} forms a partition of X
...
5
...
Proof
...
Then
p−1 (y) = {(x, y) | x ∈ X}
and (x, y) → x gives a one to one correspondence to X
...
Given a subgroup H ⊂ G and g ∈ G, let gH = {gh | h ∈ H}
...
For example, when G = S3 and H = {I, (123), (321)}, the cosets
are
IH = (123)H = (321)H = H
and
(12)H = (13)H = (23)H = {(12), (13), (23)}
Thus the collection of distinct cosets gives a partition of S3 into rotations and
flips, and there are the same number of each
...
Lemma 5
...
If two cosets g1 H and g2 H have a nonempty intersection then
g1 H = g2 H
...
If g ∈ g1 H ∩ g2 H, we can write g = g1 h1 = g2 h2 with h1 , h2 ∈ H
...
If h ∈ H, then h1 h2 h ∈ H because H is a subgroup
...
This proves that g2 H ⊆ g1 H
...
Therefore these sets are
equal
...
7
...
Every element g ∈ G lies in the coset gH
...
By the previous lemma, the cosets are pairwise disjoint
...
8
...
Proof
...
Then f is onto
...
Then h1 = g −1 gh1 = g −1 gh2 = h2
...
Consequently |gH| = |H|
...
9 (Lagrange)
...
Proof
...
Given g ∈ G, the order of g is the smallest positive n such that g n = e
...
Therefore:
Corollary 5
...
The order of any element g ∈ G divides the order of G
...
11
...
Proof
...
By the previous corollary g ∈ G divides p
...
Therefore G is generated by g
...
Even if we require n < |G| then it
may still fail (exercise 9)
...
Theorem 5
...
If the order of a finite group G is divisible by a prime
number p, then G has an element of order p
Proof when p = 2
...
We can partition G into A = {g ∈
G | g 2 = e} and B = {g ∈ G | g 2 6= e}
...
Every element
g ∈ B satisfies g 6= g −1
...
Therefore |A| = |G| − |B| is even
...
It follows that A contains an element different from e,
and this must have order 2
...
Definition 5
...
Given i ∈ {1,
...
A
subgroup G ⊆ Sn is called transitive if for some i, Orb(i) = {1,
...
Definition 5
...
Given subgroup G ⊆ Sn and i ∈ {1,
...
15 (Orbit-Stabilizer theorem)
...
, n} then
|G| = | Orb(i)| · | Stab(i)|
In particular,
|G| = n| Stab(i)|
if G is transitive
...
We define a function f : G → Orb(i) by f (g) = g(i)
...
By definition if j ∈ Orb(i), there exists
g0 ∈ T
...
In one direction, if h ∈ Stab(i)
then g0 h(i) = j
...
Suppose g ∈ T
...
We see that h(i) = g0−1 g(i) = g0−1 (j) = i
...
This shows that
X
X
|G| =
|f −1 (j)| =
| Stab(i)| = | Orb(i)| · | Stab(i)|
j∈Orb(i)
j∈Orb(i)
Corollary 5
...
|Sn | = n!
Proof
...
When
n = 1, Sn consists of the identity so |S1 | = 1 = 1!
...
The group Sn+1 acts transitively
on {1,
...
We want to show that there is a one to one correspondence
between Stab(n + 1) and Sn
...
n
n+1
f (1) f (2)
...
Therefore
we have established the correspondence
...
Therefore
|Sn+1 | = (n + 1)| Stab(n + 1)| = (n + 1)(n!) = (n + 1)!
27
5
...
Given finite sets Y, Z
...
Recall
that the intersection Y ∩ Z = {x | x ∈ Y and x ∈ Z}
...
If B ⊆ A, prove that |A − B| = |A| − |B|, where A − B = {a | a ∈
A and a ∈
/ B}
...
3
...
Suppose that a 6 sided dice is rolled twice
...
Given a subset S of these outcomes, called
an event, the probability of S occurring is |S|/36
...
4
...
(a) Prove that the stablizer H of an element i is a subgroup of G
...
Is the stabilizer a normal subgroup?
5
...
We
can do much better
...
6
...
Choose two elements g1 , g2 from a finite group G
...
Determine all the transitive subgroups of S3
...
Let Zm1 × Zm2 ×
...
, an ) | ai ∈ Zmi } be the set of vectors
...
, an ) + (b1 ,
...
, an + bn ) with mod mi arithmetic in each slot
...
mn
...
, mn
...
10
...
28
Chapter 6
More counting problems
with groups
A polyhedron is a three dimensional version of a polygon
...
4
3
1
2
It is regular if all the triangles, called faces, are equilateral
...
Let us call the symmetry
group T
...
We can use the orbit-stabilizer theorem to calculate
the order of T
...
The stabilizer of 4 is the group of rotations keeping it fixed
...
It is easy to list the 9 remaining rotations
...
1: cube
We can rotate 180◦ about the line joining the midpoint of the edges 13 and 24
to get (13)(24)
...
1
...
This is usually called the alternating group A4
...
Let us start by writing down all the
obvious elements
...
We can rotate the cube
90◦ about the axis connecting the top and bottom faces to get
(1234)(5678)
More generally, we have 3 rotations of 90◦ , 180◦ , 270◦ fixing each pair of opposite
faces
...
There are 2 rotations, other than I, fixing each
diagonally opposite pair of vertices such as 1and 7 (the dotted line in picture)
...
For example
(254)(368)
is type B
...
This is the hardest
to visualize
...
Now do a 180◦ rotation about L
...
To see that this is a complete list, we use the orbit-stabilizer theorem
...
Therefore |C| = (8)(3) = 24
...
However, we can do better
...
One can see that any non-identity element of C must permute the
diagonal lines nontrivially
...
Since they both have order 24, we can conclude
that:
Lemma 6
...
The symmetry group C of a cube is isomorphic to S4
...
Question 6
...
How many dice are there?
Recall that a die (singular of dice) is gotten by labelling the faces of cube by
the numbers 1 through 6
...
Choose
some initial labelling, then there as many ways to relabel as there are permutations which is 6! = 720
...
From
this, one may expect that there are 720/24 = 30 possibilities
...
Question 6
...
How many cubes are there with 3 red faces and 3 blue?
Arguing as above, labelling the faces of the cube 1 through 6, there are
= 20 ways to pick 3 red faces
...
On the
other hand, dividing by the number of symmetries yields 20/24, which doesn’t
make sense
...
Let X be a
finte set of things such as relabellings of the cube, or colorings of a labelled
cube, and suppose that G is a finite set of permutations of X
...
This means
that each g ∈ G determines a permutation of X such that g1 g2 (x) = g1 (g2 (x))
for all gi ∈ G, x ∈ X
...
Given x ∈ X, its orbit
Orb(x) = {g(x) | g ∈ G}, and let X/G be the set of orbits
...
Given g ∈ G, let F ix(g) = {x ∈ X | g(x) = x} be the set of fixed points
...
5 (Burnside’s Formula)
...
Theorem 5
...
Let
S = {(x, g) ∈ X × G | g(x) = x}
Consider the map p : S → G given by p(x, g) = g
...
Therefore proposition 5
...
1)
g∈G
g∈G
Next consider the map q : S → X given by q(x, g) = x
...
Therefore proposition 5
...
, and group
terms of the last sum into these orbits
X
X
|S| =
| Stab(x)| +
| Stab(x)| +
...
Furthermore, for any x ∈ Orb(xi ), we have | Stab(x)| = | Stab(xi )|
...
= |G| · |X/G|
x∈Orb(x2 )
Combining this with equation (6
...
Let us say that the action of G on X is fixed point free if Fix(g) = ∅ unless
g is the identity
...
32
Corollary 6
...
If the action is fixed point free,
|X/G| = |X|/|G|
Coming back to question 6
...
Let X be the set of relabellings of the cube,
and G = C the symmetry group of the cube
...
The solution to question 6
...
So instead, let us consider the simpler question
...
7
...
Then
Fix(I) = X
has
4
2
= 6 elements
...
For a fixed point of g = (13)(24), the sides
adjacent to 13 and 24 would have to be the same color
...
Thus
|X/T | =
1
(6 + 2 + 2 + 2) = 1
12
Of course, this can be figured out directly
...
In practice, however, there a some tricks to simplify the sum
...
Since we
can rewrite this as g2 = h−1 g1 h, we can see that the relationship is symmetric
...
8
...
Example 6
...
In the dihedral group Dn , R is conjugate to R−1 because F RF =
F RF −1 = R−1
...
10
...
The relevance for counting problems is as follows
...
11
...
5, if g1 is
conjugate to g2 , then | Fix(g1 )| = | Fix(g2 )|
Proof
...
Then g2 · x = x
...
This means that hx ∈ Fix(g1 )
...
This has an inverse f −1 :
Fix(g1 ) → Fix(g2 ) given by f (y) = h−1 y
...
Therefore | Fix(g1 )| = | Fix(g2 )|
...
6
...
Calculate the order of the (rotational) symmetry group for the octrahedron
(which most people would call a diamond)
2
...
)
3
...
1
...
Repeat for the tetrahedron, octahedron and dodecahedron
...
How many ways are the color the sides of a tetrahedron with 2 red faces, 1
and blue and 1 green
...
)
5
...
4 using Burnside
...
How many ways are there to color the sides of a cube with 2 red faces and
4 blue? (Same instructions as above
...
Given a group G, and a subgroup H, show that G acts transitively on
G/H by g(γH) = gγH
...
8
...
(Hint: Use the action G on itself defined as in the previous
problem, and use this to construct a one to one homomorphism G → SG
...
Explain why the statement of example 6
...
35
Chapter 7
Kernels and quotients
Recall that homomorphism between groups f : G → Q is a map which preserves
the operation and identity (which we denote by · and e)
...
The failure to be one to one is easy to measure
...
1
...
Lemma 7
...
A homomorphism is one to one if and only if ker f = {e}
...
The kernel is a special kind of
subgroup
...
There it also called the kernel or
sometimes the null space
...
3
...
The operation h 7→ ghg −1 is called conjugation of h by g
...
Proposition 7
...
Suppose that f : G → Q is a homomorphism, then ker f is
a normal subgroup
...
Let h1 , h2 ∈ H and g ∈ G
...
Here are some examples
...
5
...
Example 7
...
In S3 , H = {I, (123), (321)} is a normal subgroup
...
We want to prove that every normal subgroup arises as the kernel of a homomorphism
...
Given subsets H1 , H2 ⊂ G
of a group, define their product by
H1 H2 = {h1 h2 | h1 ∈ H1 , h2 ∈ H2 }
36
Lemma 7
...
If H ⊆ G is normal, then the product of cosets satisfies (g1 H)(g2 H) =
(g1 g2 )H
...
By definition, (g1 H)(g2 H) = {g1 h1 g2 h2 | h1 , h2 ∈ H}
...
Therefore g1 h1 g2 h2 = g1 g2 h3 h2 ∈ (g1 g2 )H
...
For the reverse inclusion (g1 g2 )H ⊆ (g1 H)(g2 H), observe that if h ∈ H,
then g1 g2 h = (g1 e)(g2 h) ∈ (g1 H)(g2 H)
...
8
...
The map p(g) = gH is a homomorphism
with kernel H
...
By the previous lemma, (gH)(eH) = gH = (eH)(gH), (gH)(g −1 H) =
H = (g −1 H)(gH), and (g1 H)(g2 Hg3 H) = g1 g2 g3 H = (g1 Hg2 H)(g3 H)
...
Also p(g1 g2 ) = g1 g2 H = (g1 H)(g2 H) = p(g1 )(g2 ), so p is a
homomorphism
...
When H is normal, we refer to G/H as the quotient group
...
Lemma 7
...
Let f : G → H be a homomorphism with kernel K = ker f
...
In
particular, H is isomorphic to G/K if f is onto
...
The quotient construction can be
used to tie up some loose ends from earlier sections
...
This is a subgroup
...
The label “new” is temporary, and is there to distinguish it from
Znew
n
Zn = {0, 1,
...
Given an integer x, let x
¯ = x + nZ
...
We leave it as an exercise to show this is a one
to one correspondence, and that
x⊕y =x+y
where + on the right is addition in the quotient group
...
Recall, in fact, that we never fully completed the proof that the old Zn
was a group
...
For example, in the exercises, we will see that the dihedral group Dn
contains a cyclic subgroup Cn , which is normal and the quotient Dn /Cn is also
cyclic
...
This
is the full symmetry group of the circle which includes rotations and reflection
...
37
Proposition 7
...
SO(2) is a normal subgroup of O(2)
...
The first, which uses determinants, gets to the point
quickly
...
1)
...
We start with a standard result
...
11
...
Proof
...
It follows that SO(2) is the
kernel
...
Second Proof
...
This is true when A ∈ SO(2) because SO(2) is a subgroup
...
In fact we will show that for any reflection A
AR(θ)A−1 = R(−θ)
(7
...
Then an easy
0 −1
calculation shows that F R(θ)F −1 = F R(θ)F = R(−θ)
...
Then
cos φ
sin φ
A=
= F R(−φ)
sin φ − cos φ
So
AR(θ)A−1 = F R(−φ)R(θ)R(φ)F = R(−θ)
as claimed
...
What about the quotient O(2)/SO(2)
...
38
7
...
Prove lemma 7
...
2
...
3
...
9
...
Then that
f¯(gH) = f (g) is a well defined function which gives an isomorphism
G/K ∼
= f (G)
...
(a) Given a group G and a normal subgroup H
...
Show that the restriction of p gives a one to one correspondence
S → G/H
...
5
...
6
...
7
...
Is it normal?
8
...
What if f is not
onto?
9
...
(a) Prove that the center is an abelian normal subgroup
...
)
10
...
39
Chapter 8
Rings and modular
arithmetic
So far, we have been working with just one operation at a time
...
It is
useful to give a name to this sort of thing
...
1
...
2
...
Example 8
...
Let Z (respectively Q, R , C) be the set of integers (respectively
rational numbers, real numbers, complex numbers) with the usual operations
...
Example 8
...
The set Mnn (R) of n × n matrices over R with the usual matrix
operations forms a ring
...
We now focus on a new example
...
, n − 1}, where x = x + nZ
...
We will try to define multiplication the
same way by
ab = ab
However, we have to prove that this definition makes sense
...
Lemma 8
...
If a = a0 and b = b0 , then ab = a0 b0
Proof
...
Therefore
a0 = a + nx and b = b0 + ny for some x, y ∈ Z
...
Theorem 8
...
Zn is a commutative ring
...
The laws follow from the fact that Z is a commutative ring, the definition
of the operations in Zn , and the fact that the map Z → Zn is onto
...
To get a feeling for modular multiplication, lets write down the table for Z6
·
0
1
2
3
4
5
0
0
0
0
0
0
0
1
0
1
2
3
4
5
2
0
2
4
0
2
4
3
0
3
0
3
0
3
4
0
4
2
0
4
2
5
0
5
4
3
2
1
One curious fact is that some nonzero numbers, such as 2, can be multiplied by
other nonzero numbers to get 0
...
Lemma 8
...
An element m ∈ Zn is a zero divisor if m > 1 and m divides n
...
We have that n = mm0 for some 0 < m0 < n
...
Definition 8
...
An element x ∈ R of a ring is invertible if there exists an
element y such that xy = yx = 1
...
(When R is commutative, invertible elements are also called units
...
9
...
41
This will be proven in the exercises
...
For example, Mnn (R)∗ = GLn (R)
...
The greatest common divisor is exactly that, the common divisor greater
than or equal to all others (it exists since the set of common divisors is finite)
...
Lemma 8
...
If a, b are natural numbers then gcd(a, b) = gcd(b, a mod b)
Proof
...
Then the division algorithm gives a = qb + r for some
integer q
...
Therefore
gcd(b, r) is a common divisor of a and b, so that that gcd(b, r) ≤ gcd(a, b)
...
Therefore gcd(a, b) is a
common divisor of b and r, so gcd(a, b) ≤ gcd(b, r), which forces them to be
equal
...
For example
gcd(100, 40) = gcd(40, 20) = gcd(20, 0) = 20
...
The simplest
examples are the linear ones: given integers a, b, c, find all integers m, n such
that am + bn = c
...
11
...
Proof
...
We now prove the theorem for natural numbers a, b
by induction on the minimum min(a, b)
...
Since a = gcd(a, b) divides
c by assumption, (c/a, 0) gives a solution of am + bn = c
...
Suppose b ≤ a, and let r = r(a, b) = a mod b and
q = q(a, b) be given as in theorem 4
...
Then rm0 + bn0 = c has a solution since
min(r, b) = r < b = min(a, b) and gcd(b, r) = gcd(a, b) divides c
...
From the last proof, we can deduce:
Corollary 8
...
Given a, b ∈ Z, there exists m, n ∈ Z such that am + bn =
gcd(a, b)
...
13
...
Proof
...
12
...
Since have r(mm0 , n) = 1,
mm0 = 1
...
Definition 8
...
A ring is called a division ring if R∗ = R − {0}
...
For example Q, R and C are fields
...
The previous theorem implies the following:
Theorem 8
...
The ring Zn is a field if and only if n is prime
...
16 (Fermat’s little theorem)
...
Proof
...
Now suppose that p does not
divide n, then n ∈ Z∗p
...
So by Lagrange’s theorem,
n has order dividing p − 1
...
This implies that p divides np−1 − 1 (which is usually taken as the statement of
Fermat’s little theorem) and therefore np − n
...
17
Exercises
1
...
Prove that 0 · x = 0
...
)
2
...
Prove that (−1) · x = −x, where −x is the
additive inverse of x, that is (−x) + x = 0
...
The Gaussian integers Z[i] = {a + bi | a, b ∈ Z}, where i = −1
...
(b) Determine the group Z[i]∗ of invertible elements
...
Check that the Gaussian field Q[i] = {a + bi | a, b ∈ Q} is a field when
equipped with the usual operations
...
Prove that there are no zero divisors in a field, i
...
if xy = 0 then x = 0
or y = 0
...
If R1 and R2 are commutative rings, define R = R1 × R2 with operations
(a1 , a2 ) + (b1 , b2 ) = (a1 + b1 , a2 + b2 ) and (a1 , a2 ) · (b1 , b2 ) = (a1 b1 , a2 b2 )
...
Show that this has zero divisors
...
An element x of a commutative ring is nilpotent if xN = 0 for some integer
N ≥ 0
...
8
...
9
...
This sequence will eventually repeat itself
...
Obviously, short periods are
less useful, since the pattern shouldn’t be too predictable
...
(b) Explain why picking a nilpotent in Zn would be a really bad choice
...
+ a0
where n ∈ N is arbitrary and the coefficients an ,
...
Note that polynomials are often viewed as functions but it is important to really treat these as
expressions
...
We denote the set of these polynomials by K[x]
...
g
...
The highest power of x occurring with a nonzero coefficient is called the degree
...
+ a0
g = bn xn + bn1 xn−1 +
...
(a0 + b0 )
Multiplication is defined using the rules one learns in school
f g = (a0 b0 ) + (a1 b0 + a0 b1 )x + (a2 b0 + a1 b1 + a0 b2 )x2 +
...
1
...
Proof
...
Let f and g be as above
and
h = cn xn + cn−1 xn−1 +
...
The following is easy
to check and true by design
...
2
...
The lemma says that eva : K[x] → K is a ring homomorphism
...
Lemma 9
...
An element r ∈ K is a root of f ∈ K[x] if and only if x − a
divides f , i
...
If f = (x − r)g, then clearly f (r) = (r − r)g(r) = 0
...
Write f = an xn +
...
We want g =
bn−1 xn−1 +
...
This equation is equivalent to the
system
bn−1 = an
bn−2 − rbn−1 = an−1
...
, b0 , so there is no guarantee that we have a solution
...
), then
the new system will have n equations, and this would be consistent
...
− rb0 = an rn + an−1 rn−1 +
...
So we have eliminated the last equation
...
Theorem 9
...
If f ∈ K[x] polynomial of degree n, then it has at most n distinct
roots
...
, rn , then f = c(x − r1 )
...
Proof
...
Then f = (x − r1 )g by the previous
lemma
...
By induction on the
degree, we can assume that g has at most n − 1 roots
...
, rn are roots, f = c(x − r1 )
...
But clearly c
must equal the leading coefficient
...
Sometimes this is denoted by Fp to emphasize that its a field
...
Proposition 9
...
We can factor xp − x = x(x − 1)(x − 2)
...
By Fermat’s little theorem, 1
...
Therefore xp − x =
x(x − 1)(x − 2)
...
Corollary 9
...
(p − 1)! = −1
Proof
...
(x − (p − 1))
...
p!
Corollary 9
...
The binomial coefficients np = n!(p−n)!
are divisible by n when
1 < n < p
...
Substitue 1 + x into the above identity to obtain (1 + x)p − (1 + x) = 0
in Zp
...
Theorem 9
...
If p is prime, then Z∗p is cyclic
...
We won’t prove this in general, but to get some sense
of why this is true, let’s prove it when p = 2q + 1, where q is another prime
...
g
...
Then
Z∗p has order 2q
...
There is
only element of order 1, namely 1
...
An element of order q satisfies xq − 1 = 0, and be different
from 1
...
So to summarize there are no
more q + 1 elements of orders 1, 2, q
...
9
...
Given a field K and a positive integer n, let n = 1 +
...
K is
said to have positive characteristic if n = 0 for some positive n, otherwise
K is said to have characteristic 0
...
Prove that the
characteristic is a prime number
...
For any field, prove the binomial theorem
n
X
n m
(x + 1) =
x
m
m=0
n
(Recall
n+1
m
=
n
m
+
n+1
m
...
Let K be a field and s ∈ K
...
Show that this becomes a commutative ring if we define
addition and multiplication as the notation suggests:
√
√
√
(a + bi s) + (c + d s) = (a + c) + (b + d) s
√
√
√
(a + b s)(c + d s) = (ac + bds) + (ad + bc) s
√
4
...
If this equation
√
does
not
have
a
root,
then
prove
that
K[
s] is a field (Hint: (a + b s)(a −
√
b s) =? and when is it zero?)
...
When p is an odd prime, show that the map x 7→ x2 from Z∗p → Z∗p is not
onto
...
48
Chapter 10
Matrices over Zp
We can now combine everything we’ve learned to construct a new, and interesting, collection of finite groups
...
Then Zp is a field,
which means that we can perform all the usual operations in it, including division
...
For instance, we can consider vectors of length n with entries in Zp
...
This becomes an abelian group under vector addition:
(a1 ,
...
, bn ) = (a1 + b1 ,
...
One can also consider
matrices with entries in Zp
...
For example,
Theorem 10
...
Let A be an n × n matrix with entries
in a field K
...
A is not
invertible if and only if it can be taken to a matrix with a zero row
...
Let us denote the set of
invertible n × n matrices with entries in K by GLn (K)
...
When K = Zp , this is a finite group
...
Let us start with the 2 × 2 case
...
A ∈ GL2 (Zp ) will act on v ∈ Z2p
by matrix multiplication Av
...
2
...
Proof
...
This will satisfy Av = u
...
3
...
The condition Av = v means that the first column is v
...
4
...
From the last two lemmas and the orbit-stabilizer theorem, the order is
(p2 − 1)(p − 1)p
Corollary 10
...
GL2 (Z2 ) is isomorphic to S3
...
GL(Z2 ) acts on Z22 − {0} which has 3 elements
...
Since the order of GL(Z2 ) is 6, f has to be onto as well
...
For p = 3,
the order is 48 which is not the factorial of anything
...
Theorem 10
...
The order of GLn (Zp ) is (pn − 1)(pn − p)
...
We will apply the same strategy as before
...
]T
...
The stabilizer of v is the set of matrices of the form
1 x2 x3
...
...
Therefore A 7→ (B, x2 , x3 ,
...
It follows by induction on n that
| Stab(v)| = pn−1 |GLn−1 (Zp )|
= pn−1 (pn−1 − 1)
...
(pn − pn−1 )
10
...
A matrix over a field is called elementary if it can be obtained from I
by a single row operation
...
50
2
...
If E1 ,
...
E1 A = I,
then prove that A is invertible and that EN
...
3
...
, EN are elementary matrices such that EN
...
(Hint: show that ker A contains a
nonzero vector
...
Determine which of the following matrices over Z2 is invertible, and find
the inverse when it exists
...
Cauchy’s theorem would
imply that GL2 (Zp ) would have an element of
1 1
order p
...
0 1
6
...
Show that
this is onto, and use this to compute the order of the kernel (which is
usually denoted as SL2 (Zp ))
...
The order of SL2 (Z3 ) is 24, which might lead one to suspect it’s isomorphic
to S4
...
51
Chapter 11
The sign of a permutation
Theorem 11
...
Suppose n ≥ 2
...
(b) If the identity I = τ1
...
Before giving the proof, we need the following lemmas
...
2
...
, n} are mutually distinct elements
...
1)
(ac)(ab) = (ab)(bc)
(11
...
3)
(cd)(ab) = (ab)(cd)
(11
...
The first couple are obvious, the rest will be left as an exercise
...
3
...
τr , in Sn , is equal to another product of transpositions τ10
...
Proof
...
Use (11
...
4) to move transpositions containing n next to each other
...
1) and (11
...
In each of these moves, either r
stays the same or drops by 2
...
Here are a couple of examples when n = 4,
(43)(41)(24) = (41)(13)(24) = (41)(24)(13) = (24)(12)(13)
(34)(12)(34) = (34)(34)(12) = (12)
52
Proof of theorem 11
...
We prove both statements by induction on n
...
Now
suppose that (a) holds for Sn
...
If f (n + 1) = n + 1, then
f ∈ Stab(n + 1) which can be identified with Sn
...
Now suppose that j = f (n + 1) 6= n + 1
...
This implies that g is a product
of transpositions τ1 τ2
...
Therefore f = (n + 1 j)τ1 τ2
...
Suppose that (b) holds for Sn
...
τr
(11
...
By using these lemma 11
...
τr0 0
(11
...
If
exactly one of the τi0 ’s contains n + 1, then τ10
...
This can’t be the identity contradicting (11
...
Therefore
none of the τi0 ’s contains n + 1
...
6) can be viewed as an
equation in Sn
...
Corollary 11
...
If a permutation σ is expressible as a product of an even
(respectively odd) number of transpositions, then any decomposition of σ as a
product of transpositions has an even (respectively odd) number of transpositions
...
Write
σ = τ1
...
τr0 0
where τi , τj0 are transpositions
...
τ1−1 τ10
...
τ1 τ10
...
This is possible only if r and r0 have the same
parity
...
5
...
Define
(
1
if σ is even
sign(σ) =
−1 if σ is odd
Lemma 11
...
The map sign : Sn → {1, −1} is a homomorphism
...
Clearly sign(I) = 1 and sign(στ ) = sign(σ) sign(τ )
...
7
...
53
Observe that An is a subgroup, and in fact a normal subgroup, because it
equals ker(sign)
...
Therefore
Lemma 11
...
|An | = 12 n!
...
A more precise
analysis, which we omit, shows that these groups are in fact isomorphic
...
A function
f : X n → R is called symmetric if
f (x1 ,
...
, xj ,
...
, xj ,
...
xn )
and antisymmetric if
f (x1 ,
...
, xj ,
...
, xj ,
...
xn )
for all i 6= j
...
Clearly when f is antisymmetric,
f (x1 ,
...
, xσ(n) )
holds for any permutation
...
We define the symmetrization and antisymmetrization
operators by
1 X
f (xσ(1) ,
...
, xσ(n) )
n!
σ∈Sn
We’ll see in the exercises that these operators produce (anti)symmetric functions
...
9
Exercises
1
...
2
...
Prove that if σ ∈ Sn is odd, then so is σ −1
...
Prove that a cycle of length r is even if and only if r is odd
...
Prove that if G ⊆ Sn is a subgroup of odd order, then G ⊆ An
...
Prove that Sym(f ) (respectively Asym(f )) is symmetric (respectively antisymmetric), and furthermore that f = Sym(f ) (f = Asym(f )) if and
only if f symmetric ( antisymmetric)
...
If f is symmetric, prove that Asym(f ) = 0
...
Prove that
f (x1 ,
...
, xσ(n) )
holds for all σ ∈ An if and only if f is a sum of a symmetric and antisymmetric function
...
Given an
n × n matrix A = [aij ] over a field K, the determinant
X
det A =
sign(σ)a1σ(1)
...
There is also symmetric version, without sign(σ), called the permanent
...
The definition, we gave for the determinant, is not very
practical
...
Theorem 12
...
Given an n × n matrix A, the following properties hold
...
Then det C = det A + det B
...
(e) Let us write A = [v1 ,
...
are the columns
...
vτ (n) ) = sign(τ ) det(v1 ,
...
Item (a) is clear because all the terms δ1σ(1)
...
(b)
X
det B =
sign(σ)a1σ(1)
...
anσ(n)
σ∈Sn
=b
X
sign(σ)a1σ(1)
...
anσ(n)
σ∈Sn
= b det A
56
(c) Denote the ith columns of A, B, C by [α1 ,
...
] and [α1 + β1 ,
...
(ασ(i) + βσ(i) )
...
ασ(i)
...
βσ(i)
...
anσ(n) = aτ (1)τ σ(1)
...
In particular, setting τ = σ −1 gives
a1σ(1)
...
aσ−1 (n)n
Therefore
det AT =
X
sign(τ )aτ (1)1
...
aσ−1 (n)n
σ∈Sn
=
X
sign(σ)aσ−1 (1)1
...
Therefore
X
det(vτ (1) ,
...
anστ (n)
σ∈Sn
X
=
sign(στ ) sign(τ )a1στ (1)
...
anστ (n)
σ∈Sn
In the last sum, we can set η = στ , and sum over η ∈ Sn
...
vn )
...
2
...
By (b), det A = 0 · det A
...
This can be summarized as
Lemma 12
...
If A, E are both n × n with E elementary, then det(E) 6= 0 and
det(EA) = det(E) det(A)
...
Theorem 12
...
Given an n × n matrix A, the following statements are equivalent
(a) A is invertible
...
(c) Av = 0 implies v = 0
...
By theorem 10
...
In the first case det A 6= 0 by lemma 12
...
In the
second case, det A is proportional to det B = 0
...
If A is invertible and Av = 0, then v = A−1 Av = 0
...
Then det AT = det A = 0 by what was just proved
...
For simplicity, suppose that the first row is zero
...
, 0]T
...
This proves the equivalence of
(a) and (c)
...
5
...
Proof
...
3
...
An element λ ∈ K is an eigenvalue of A if there
exists a nonzero vector v ∈ K n , called an eigenvector, such that
Av = λv
or equivalently
(λI − A)v = 0
Theorem 12
...
The expression p(x) = det(xI − A) is a polynomial of degree
n, called the characteristic polynomial of A
...
Proof
...
(xδnσ(n) − anσ(n) )
σ∈Sn
is a polynomial of degree n
...
By theorem 12
...
58
Corollary 12
...
A has at most n distinct eigenvalues
...
8
Exercises
1
...
Check that det E =
−1 and det(EA) = − det A
...
Let E be obtained from I by multiplying a row by k ∈ K ∗
...
3
...
Check that det E = 1 and det(EA) = det A
...
Suppose that a square matrix A can be subdivided into blocks
B C
0 D
as indicated with B and D square
...
5
...
anσ(n)
σ∈Sn
Prove that Perm A = Perm AT
...
Calculate the cardinality of {A ∈ GLn (Zp ) | det A = 0}
...
Suppose that A is an n × n matrix with n eigenvalues λ1
...
e
...
(x −
λn )
...
λn and trace A = λ1 +
...
ann
...
r
θ
A bit more precisely, the transformation R = R(θ, r) has the line through r
as the axis, and the plane perpendicular to the line is rotated by the angle
θ in the direction given by the right hand rule (the direction that the fingers
of right hand point if the thumb points in the direction of r)
...
It is invertible with inverse R(−θ, r)
...
We will show that it is a subgroup, and in particular
that the product of two rotations is again a rotation
...
The trick is
characterize the matrices that arise from rotations
...
e
...
This is equivalent to AT A = I
...
1
...
60
Proof
...
We already saw in the exercises to chapter 3 that the set of orthogonal
matrices O(3) forms a subgroup of GL3 (R)
...
Lemma 13
...
SO(3) is a subgroup of O(3)
...
If A, B ∈ SO(3), then det(AB) = det(A) det(B) = 1 and det(A−1 ) =
1−1 = 1
...
Proposition 13
...
Every rotation matrix lies in SO(3)
...
Given a unit vector v3 = r as above, fix R = R(θ, r)
...
Therefore A =
[v1 v2 v3 ] is an orthogonal matrix
...
Then
R(v1 ) = cos θv1 + sin θv2
R(v2 ) = − sin θv1 + cos θv2
R(v3 ) = v3
and therefore
RA = AM
where
cos θ
M = sin θ
0
− sin θ
cos θ
0
0
0
1
Since M, A ∈ SO(3), it follows that R = AM A−1 ∈ SO(3)
...
In fact, I did find an expression with the help of a computer algebra
package:
2
a + cos(θ) − a2 cos(θ)
−c sin(θ) + ab − ab cos(θ)
ac − ac cos(θ) + b sin(θ)
ab − ab cos(θ) + c sin(θ)
−a sin(θ) + bc − bc cos(θ)
b2 + cos(θ) − b2 cos(θ)
2
2
2
2
−b sin(θ) + ac − ac cos(θ) bc − bc cos(θ) + a sin(θ) −b + b cos(θ) − a + a cos(θ) + 1
However, the formula is pretty horrendous and essentially useless
...
We want to prove that every matrix in SO(3) is a rotation
...
In general, a real matrix need not have any real
eigenvalues
...
Lemma 13
...
A 3 × 3 real matrix has a real eigenvalue
...
The characteristic polynomial p(λ) = λ3 +a2 λ2 +
...
Since λ3 grows faster than the other terms, p(λ) > 0 when λ 0, and p(λ) < 0
when λ 0
...
(This intuitive argument is justified by the
intermediate value theorem from analysis
...
5
...
Proof
...
Since a multiple of v will satisfy the same
conditions, we can assume that the square of the length v T v = x2 + y 2 + z 2 = 1
...
6
...
Proof
...
By the previous lemma, ±1 is an eigenvalue
...
First suppose that 1 is eigenvalue
...
We can assume that v3 is a unit vector
...
The vectors v1 and v2
form a basis for the plane v3⊥ perpendicular to v3
...
It follows that
RA = [Rv1 , Rv2 , Rv3 ] = [Rv1 , Rv2 , v3 ]
remains orthogonal
...
Thus we can write
R(v1 ) = av1 + bv2
R(v2 ) = cv1 + dv2
R(v3 ) = v3
The matrix
a b 0
A−1 RA = c d 0
0 0 1
a b
lies in SO(3)
...
It follows that R = R(θ, v3 )
...
Defining
A as above, we can see that
a b 0
A−1 RA = c d 0
0 0 −1
62
This time the upper 2 × 2 is block lies O(2) with determinant −1
...
This means that there is a nonzero vector v in the plane
v3⊥ such Rv = v
...
From the proof, we extract the following useful fact
...
7
...
If the matrix
is not the identity then the corresponding eigenvector is the axis of rotation
...
Let us summarize everything we’ve proved in one statement
...
8
...
13
...
Check that unlike SO(2), SO(3) is not abelian
...
)
2
...
Conclude that a normal subgroup of SO(3), different from {I}, is
infinite
...
Check that
cos θ
sin θ
0
− sin θ
cos θ
0
0
0
1
has 1, e±iθ as complex eigenvalues
...
4
...
Therefore we can view O(2) as a subgroup
of SO(3)
...
5
...
Prove that H1 ∼
= H2 if they are
conjugate
...
Prove that for any nonzero vector v ∈ R3 , the subgroup {g ∈ SO(3) |
gv = ±v} (respectively {g ∈ SO(3) | gv = v}) is conjugate, and therefore isomorphic, to O(2) (respectively SO(2))
...
)
63
Chapter 14
Finite subgroups of the
rotation group
At this point, it should it should come as no surprise that finite subgroups of
the O(2) are groups of a symmetries of a regular polygon
...
Theorem 14
...
A finite subgroup of SO(2) is cyclic, and a finite subgroup of
O(2) not contained in SO(2) is dihedral
...
We include the “degenerate” cases D1 ∼
= Z2 ,
and D2 ∼
= Z2 × Z2 (see exercises)
...
First suppose that G ⊂ SO(2) is finite
...
Let R ∈ G − {I} be the rotation with
the smallest possible θ
...
Since
φ ≥ θ, we can write φ = nθ + ψ, where n ≥ 0 is an integer and ψ ≥ 0
...
Since ψ is
the angle of SR−n , we must have ψ = 0
...
So G is
generated by R, and therefore cyclic
...
Then there
exists F ∈ G with det F = −1
...
G ∩ SO(2) is cyclic with generator R by the previous paragraph
...
We have that det F R = −1, so it is also a reflection
...
Together with the relations F 2 = I
and Rn , we see that G ∼
= Dn
...
Since O(2) ⊂ SO(3), we have
the above examples
...
Remarkably, the converse is also true
...
64
Theorem 14
...
Let G ⊂ SO(3) be a finite subgroup
...
The proof will be broken down into a series of lemmas
...
Then G acts on the sphere S of
radius one centered at the origin
...
Let P be the set of poles
...
It follows that P
is a finite set with even cardinality
...
So, we can partition P into a finite number, say n, of orbits
...
Lemma 14
...
X
n
1
1
=
1−
2 1−
|G|
| Stab(pi )|
i=1
(14
...
By Burnside’s formula
n=
1 X
| Fix(g)|
|G|
g∈G
As noted above | Fix(g)| = 2, when g 6= I
...
4
...
1)
...
Since |G| ≥ 2 and | Stab(pi )| ≥ 2, we must have
1
1≤2 1−
<2
|G|
and
n X
1
≤
1−
| Stab(pi )|
The only way for (14
...
65
Lemma 14
...
If n = 2, G is cyclic
...
Since Stab(pi ) ⊆ G, we have
1
1
1−
≤ 1−
| Stab(pi )|
|G|
(14
...
1) implies
1
1
1
2 1−
= 1−
+ 1−
|G|
| Stab(p1 )|
| Stab(p2 |
and this forces equality in (14
...
This implies that G =
Stab(p1 ) = Stab(p2 )
...
It follows
that g would have to be a rotation in the plane perpendicular to L
...
Therefore it is cyclic by theorem 14
...
We now turn to the case n = 3
...
(14
...
Lemma 14
...
The only integer solutions to the inequalities
2 ≤ n1 ≤ n2 ≤ n3
1
1
1
+
+
>1
n1
n2
n3
are as listed together with the corresponding orders of G
...
(b) (2, 3, 3) and |G| = 12
...
(d) (2, 3, 5) and |G| = 60
...
2, we need the following
Lemma 14
...
A subgroup G ⊂ SO(3) corresponding to the triple (2, 2, n) is
isomorphic to Dn
...
We will deal with n = 2 in the exercises, so let us assume that n > 2
...
This has order n
...
We must have
an element F ∈ G which takes p3 to −p3 , because otherwise we would have two
orbits with stabilizers of order n > 2 contradicting our assumptions
...
Let k = |K|
...
This forces k = 2n
...
This implies G ⊂ {g ∈ SO(3) | gp3 = ±p3 } ∼
= O(2) (by a previous exercise)
...
1 implies that G is dihedral
...
8
Exercises
1
...
Prove that this is abelian, and that the map f : Z2 × Z2 → D2 given by
f (1, 0) = F and f (0, 1) = R gives an isomorphism
...
2
...
Prove that D2 ∼
= G
...
Let G ⊂ SO(3) be a finite group and P be the set of poles
...
4
...
6
...
Let G ⊂ SO(3) be a subgroup corresponding to the triple (2, 2, 2) in the
sense of lemma 14
...
Prove that G ∼
= D2
...
Consider a regular tetrahedron inscribed in the unit sphere S
...
Show that the T action on P has three orbits, where one of them
has a stabilizer of order 2 and the remaining two have stabilizers of order
3
...
Determine the poles of the symmetry group of the cube, and determine
the orbits and stabilizers as in the previous exercise
...
This idea can be extended
to handle rotations in R3 , and this will be explained in the next chapter
...
The ring of quaternions is given by
H = {a + bi + cj + dk | a, b, c, d ∈ R}
where i, j, k are symbols
...
We define
0 = 0 + 0i + 0j + 0k
1 = 1 + 0i + 0j + 0k
(a + bi + cj + dk) + (a0 + b0 i + c0 j + d0 k) = (a + a0 ) + (b + b0 )i + (c + c0 )j + (d + d0 )k
(a + bi + cj + dk) · (a0 + b0 i + c0 j + d0 k) = (aa0 − bb0 − cc0 − dd0 ) + (ab0 + ba0 + cd0 − dc0 )i
+ (ac0 − bd0 + ca0 + db0 )j + (ad0 + bc0 − cb0 + da0 )k
To put it another way, multiplication is determined by the rules:
1 is the identity
i2 = j 2 = k 2 = −1
ij = −ji = k
jk = −kj = i
ki = −ik = j
...
1
...
69
Proof
...
In principle, associativity can be checked by a long and messy
calculation
...
We define a
map f : H → M22 (C) by
f (a + bi + cj + dk) = aI + bσi + cσj + dσk
a + di bi − c
=
bi + c a − di
(15
...
If
f (a + bi + cj + dk) = 0
then clearly a = b = c = d = 0 by (15
...
So f is one to one
...
2)
etc
...
Associativity of products is now automatic
...
We could have simply defined the set of quaternions to be the set of matrices
of the form (15
...
But this would hide the fact that quaternions should be
viewed as a generalization of complex numbers
...
We define the conjugate, norm and real
and imaginary parts of a quaternion by
a + bi + cj + dk = a − bi − cj − dk
p
|a + bi + cj + dk| = a2 + b2 + c2 + d2
Re(a + bi + cj + dk) = a
Im(a + bi + cj + dk) = bi + cj + dk
Let us say that a quaternion is imaginary if its real part is zero
Theorem 15
...
Let q ∈ H then
(a) q = q
...
70
(b) q1 + q2 = q2 + q1
...
(d) qq = |q|2
...
The first two statements are easy
...
Corollary 15
...
H forms a division ring
...
Lagrange proved that every positive integer is a sum of four squares of integers
...
Proposition 15
...
If x and y are both expressible as a sum of four squares of
integers, then the same is true of xy
...
By assumption, we can find two quaternions q1 and q2 with integer coefficients such that x = |q1 |2 and y = |q2 |2
...
By theorem 15
...
15
...
Check (15
...
2
...
2
...
Prove part (e) and (f)
...
Check that the set Q = {1, −1, i, −i, j, −j, k, −k} is a subgroup of H∗
which is not abelian and not isomorphic to D4
...
71
5
...
6
...
Check that T˜ ⊂ H∗ is a subgroup of order 24
...
7
...
Identifying vectors (a, b, c) ∈ R3
with imaginary quaternions ai + bj + ck, the scalar product is an R-valued
operation given by
hbi + cj + dk, ei + f j + gki = be + cf + dg
The vector product is an R3 -valued distributive operation satisfying
v × w = −w × v
i × j = k, j × k = i, k × i = j
...
We saw earlier a rotation can be represented by a 3 × 3 matrix in SO(3)
...
We will give an alternative based on the
ring of quaternions which makes this easy
...
2, we can see that this is a subgroup of H∗ , so it really is
a group
...
Usually this group is called Spin(3), but we won’t consider any
of the other groups in this series
...
1
...
Proof
...
Therefore
qvq = qvq = −qvq
This implies qvq is imaginary
...
The previous lemma allows us to define a transformation Rot(q) : R3 →
R3 by Rot(q) = qvq for q ∈ Spin
...
Lemma 16
...
Rot : Spin → GL3 (R) is a homomorphism
...
We have that Rot(q1 q2 ) = Rot(q1 ) Rot(q2 ) because Rot(q1 q2 )(v) = q1 q2 vq 2 q 1 =
Rot(q1 ) Rot(q2 )(v)
...
Lemma 16
...
Rot(q) is an orthogonal matrix
...
We use the standard characterization of orthogonal matrices that these
are exactly the square matrices for which |Av| = |v| for all vectors v
...
73
Lemma 16
...
Rot(q) ∈ SO(3)
...
There are a number of ways to see this
...
In terms of the vector cross products, right handed means that
the cross product of the first vector with the second vector is the third
...
The right handed basis i, j, k gets transformed to Rot(q)i, Rot(q)j, Rot(q)k
...
So this is
again right handed
...
5
...
Proof
...
It clearly satisfies |q| = 1
...
Theorem 16
...
For any unit vector r viewed as an imaginary quaternion,
Rot(cos(θ) + sin(θ)r)
is R(2θ, r)
...
Pick a right handed system orthonormal vectors v1 , v2 , v3 with v3 = r
...
Let
q = cos(θ) + sin(θ)r
...
We also find
Rot(q)v1 = (cos θ + sin θv3 )v1 (cos θ − sin θv3 )
= (cos2 θ − sin2 θ)v1 + (2 sin θ cos θ)v2
= cos(2θ)v1 + sin(2θ)v2
and
Rot(q)v2 = (cos θ + sin θv3 )v2 (cos θ − sin θv3 )
= − sin(2θ)v1 + cos(2θ)v2
which means that Rot(q) behaves like R(2θ, r)
...
7
...
Proof
...
The
kernel of Rot consists of {1, −1}
...
So in other words, a rotation can be represented by an element of Spin
uniquely up to a plus or minus sign
...
74
16
...
Suppose we rotate R3 counterclockwise once around the z axis by 90◦ , and
then around the x axis by 90◦
...
Determine it
...
Given a matrix A ∈ Mnn (C)
...
In other words
the ijth entry of A∗ is aji
...
) A matrix A
called unitary if A∗ A = I and special unitary if in addition det A = 1
...
3
...
1)
...
Prove that this gives an isomorphism Spin ∼
= SU (2)
...
Consider the quaternion group Q = {±1, ±i, ±j, ±k} studied in a previous
exercise
...
5
...
Show that the image T of T˜ in SO(3) has order 12, and that it consists
of the union of the set of matrices in exercise 5 and
π π
{R(θ, r) | θ ∈ { , }, r ∈ V }
6 3
6
...
Show that the T acts as the rotational symmetry group of the regular tetrahedron with vertices in V
...
Artin, Algebra
[2]
M
...
Weyl, Symmetry
76