exam Flashcards
inverse element of x
unique y∈G : xy=e=yx
y=x^(-1)
show that xy=e
inverse element properties
(a^(-1))^(-1) = a
(a1…an)^(-1) = an^(-1)…a1^(-1)
(a^n)^(-1) = a^(-n) = (a^(-1))^n
x^0=
e
a and b “congruent modulo N”
N|a-b
a≡bmodN
equivalence relation
[reflexivity]
a≡amodN
[symmetry]
a≡bmodN ⟺ b≡amodN
[transitivity]
a≡bmodN and b≡cmodN
⟹ a≡cmodN
residue class of a modulo N
amodN := {b∈Z| b≡amodN}
amodN=bmodN
⟺a≡bmodN
a=qN+r
⟹a≡rmodN
⟹amodN=rmodN
amodN
= a_
= {a+Nk|k∈Z}
a is a “unit modulo N”
∃b_ ∈ Z/NZ :
a_ * b_ = 1_
gcd(a,N) = 1
(Z/NZ)^X
subset of Z/NZ containing all units modulo N
Euler’s totient function
ρ(N) = #(Z/NZ)^X
Euler’s theorem
for all a_∈ (Z/NZ)^X,
(a_)^ρ(N) = 1_
Fermat’s little theorem
if p is prime,
(amodp)^p = amodp
subgroup H of G
H<=G
H is subset of G and group law and unit element are the same.
subgroup criterion
[H1]
e∈H
[H2]
x,y∈H ⟹ x*y ∈H
[H3]
x ∈H ⟹ x^(-1) ∈H
Lagrange
H is a subgroup of finite G
⟹
#H | #G
ord(x)
- minimum m>0 such that x^m=e
- no such m exists ⟹ ord(x)=∞
ord(x^(-1))
- ord(x) = ord(x^(-1))
- ord(x)<∞
⟹
<x>={x,x^2,...,x^ord(x)=e}
-
</x>
ord(x)<∞
<x> = {x , x^2, ..., x^(ord(x)) = e}
</x>
<x></x>
= ord(x)
G<∞
⟹ ord(x) < ∞ ⟹ ord(x)|#G
x^n=e
⟹ ord(x) | n
G “cyclic”
if G=<g> for some g∈G
g is then the "generator" of G</g>
ord(g) = #G
⟺ G is cyclic and generated by g
, for finite G
homomorphism
f:X->Y : f(xy) = f(x)f(y)
homorphism properties
- f(e1) = e2
- f(x^(-1)) = f(x)^(-1)
- f isomorphism ⟹ f^(-1) isomorphism
- g:G2->G3 homomorphism -> g∘f homomorphism
, for f:G1->G2
isomorphism
bijective homomorphism
isomorphism properties
- G1 abelian ⟺ G2 abelian
- ord(g1) = k ⟺ f(x) of order k
- # G1 = #G2
- the restriction of f to any H1<=G1 is an isomorphism
kernel of f
given homomorphism f:(X,ex)->(Y,ey)
ker(f) := {x∈X | f(x) = ey}
kernel properties
- ker(f) is subgroup of X
- f injective ⟺ ker(f) = {ex}
CHINESE REMAINDER THEOREM
- take N,M ∈ Z>0: Gcd(N,M)=1
- then the map f:Z/NMZ -> Z/NZ X Z/MZ : amodNM ↦ (amodN, amodM)
is a well-defined group isomorphism
ρ(n)
for n∈Z>0: n=p1^(e1) * … * pk^(ek) where pi prime.
ρ(n) = ∏ (pi-1)pi^(ei-1) = n∏ (1-1/pi)
* product taken over prime divisors of n
Euler’s totient function properties
φ(NM) = φ(N) * φ(M)
for all positive integers N,M with gcd(N,M) = 1
S↓(Σ)
Σ non-empty set
S↓(Σ) := set of all bijections from Σ to Σ
symmetric group on the set Σ
(S↓(Σ) , ∘ , idΣ)
Cayley’s theorem
every group G is isomorphic to a subgroup of S↓(G)
k-cycle properties
δ = (i1 … ik) ∈S↓(n)
- every δ can be written as a product δ = δ1* … * δr where δi are pairwise disjoint cycles of length >=2
(unique aside from order of δi)
- δ^(-1) = (ik … i1)
- ord(δ) = k
- δ1, … , δr pairwise disjoint ⟹ (δ1 … δr)^n = δ1^n … δr^n
- δ1, … , δr pairwise disjoint with lengths Li>=2 ⟹ ord(δ1 … δr) = lcm(L1,…,Lr)
- every permutation can be written as a product of transpositions
sign of permutation
ε(δ) := ∏{1<=i<j<=n} (δ(i)-δ(j))/(i-j)
= (-1)^(ΣLi-1)
= +- 1
ρ ∘ ( a1 … al) ∘ ρ^(-1)
= (ρ(a1) … ρ(al))
for any ρ∈S↓(n) and any l-cycle (a1 … al) ∈S↓(n)
S↓(n)
= n!
if a permutation can be written as a product of transpositions as 𝓣1…𝓣L and γ1…γk
⟹ L = Kmod2
alternating group
for n>=1
A↓(n) is the subgroup of S↓(n) consisting of all even permutations
elements of A↓(n) for n>=2
(n!)/2
A↓(n) for n>=3
the elements of A↓(n) can be written as products of 3-cycles
inner product
<u,v> = u1v1 * … * unvn
norm
||u|| = √ (<u,u>)
distance
d(u,v) = √ (<u-v, u-v>)
O(R^n, <.,.>)
the set of all linear maps φ satisfying <v,w> = <φ(u), φ(v)>
linear maps in O(R^n, <.,.>) preserve
[norm]
||φ(u)|| = ||u||
[distance]
||φ(u) - φ(v)|| = ||u-v||
[angle θ]
cosθ =
( √ (<φ(u) , φ(v)>) ) /
(||φ(u)||||φ(v)||)
*linear maps preserving inner product are invertible
orthogonal group
O(n) = {A∈ GLn(R) | A^(T)A = I}
special orthogonal group
SO(n) = {A∈ GLn(R) | A^(T)A = I and det(A) = 1}
isometry on R^n
a map φ: R^n -> R^n with the property d(u,v) = d(φ(u),φ(v))
* does not have to be linear!
isometry properties
- an isometry mapping 0∈R^n to 0 is linear
- the linear isometries on R^n are the elements of O(R^n, <.,.>) = O(n)
- every isometry can be written as a composition of a translation and a linear isometry
- isometries are invertible
the symmetry group of F⊆R^n
the subgroup in the group of all isometries formed by the isometries on R^n which map F to F.
aφ(F)
infinite dihedral group
D↓(∞) := the symmetry group of a circle
D↓(∞) properties
- D↓(∞) isomorphic to O(2)
- subset of all rotations R⊂D↓(∞) is isomorphic to SO(2)
- if δ∈D↓(∞) is any reflection then D↓(∞) = R U δ*R
- taking δ the reflection across x-axis, we have δρδ = ρ^(-1) , ∀ρ∈R
n-th dihedral group
D↓(n) := the symmetry group of Fn
D↓(n) properties
- D↓(n) contains the rotation ρ by an angle 2π/n and the reflection δ in the y-axis
- every element of D↓(n) can be written in a unique way as ρ^k or δρ^k for some 0<=k<n
- D↓(n) has 2n elements
- D↓(n) abelian ⟺ n=2
- ord(ρ) =n and ord(δρ^k) = 2
⟹ ρ^n = δ^2 = id
⟹ δρδ = ρ^(-1) - the subgroup R↓(n) of D↓(n) consisting of all rotations is isomorphic to Z/nZ
λ↓(a)
ρ↓(b)
g↦ag
g↦gb
conjugation by a
the bijective map γ↓(a) : G->G : g↦aga^(-1)
properties of γ↓(a)
- γ↓(a) isomorphism
- γ↓(a) γ↓(b) = γ↓(ab)
- inverse of γ↓(a) is γ↓(a^(-1))
- H<=G ⟹ γ↓(H) = aHa^(-1) also subgroup, and H≅aHa^(-1)
x,y conjugate
∃ γ↓(a) conjugation for some a:
γ↓(a) (x) = y
conjugacy class of x∈G
the subset of G
C↓(x) = {y∈G |∃a∈G : γ↓(a) (x) = y}
conjugacy class properties
- x conjugate to itself
- x∈C↓(y) ⟹ y∈C↓(x)
- x∈C↓(y) and y∈C↓(z) ⟹ x∈C↓(z)
- every group is a disjoint union of conjugacy classes
conjugate of a cycle (a1 … ak) by ρ∈S↓(n)
= ρ(a1 … ak)ρ^(-1) = (ρ(a1) … ρ(ak))
cycle type of δ
δ = δ1…δk
with Li length of δi L1<=…<=Lk
including elements i: δi=I as 1-cycles
the sequence [L1, … , Lk]
C↓[L1,…,Lk]
conjugacy class of permutations of cycle type [L1,…,Lk]
S↓(n) = U C↓[L1,…,Lk]
= U C↓(δ) with δ being the permutations in S↓(n) with pairwise distinct cycle types
centraliser of a
N(a) := {g∈G | φ↓(g) (a) = a }
= {g∈G | ga = ag}
- G finite ⟹ #G = #C↓(a) * #N(a)
left coset of H in G
any subset of the form gH for g∈G
G/H
:= {gH : g∈G}
the set consisting of all left-cosets
index of H in G
[G:H] := #G(G/H)
number of disjoint left cosets of H in G
if not finite then [G:H] = ∞
group action
a map G X X -> X : (g,x) ↦ gx satisfying
[A1] ex=x , ∀x∈X
[A2] (gh)x = g(hx) , ∀g,h∈G, ∀x∈X
stabiliser of x in G
G↓(x) := {g∈G : gx=x} ⊆ G
orbit of x under G
Gx := {gx: g∈G} ⊆ X
“faithful” action
if for every distinct pair g,h∈G, ∃x∈X:
gx ≠ hx
“transitive” action
if for every distinct pair x1,x2∈X, ∃g∈G:
g*x1 = x2
⟺ Gx=x for all x
x∈X “fix point” of G
if Gx = {x}
i.e. gx=x, ∀g∈G
set of all fix points in G
X^(G) := {x∈X: gx=x, ∀g∈G}
“fix point free” action
X^(G) = ∅
orbit-stabiliser theorem
for any G-set X and any x∈X one has #Gx = [G:G↓(x)]
sylow p-group in G
subgroup H⊆G with #H = p^n
*for a prime number p that divides the order go G
#G = mp^n , n>=1 gcd(p,m)=1
n↓(p) (G)
number of pairwise disjoint slow p-groups in G
sylow theorem
- # G = p^n * mn>=1, gcd(p,m) =1
- a subgroup H with #H = p^n is a sylow p-group.
number of pairwise distinct sylow p-groups in G
n↓(p) (G) ≡ 1modp
n↓(p) (G) | m
cauchy theorem
if G is a finite group and if p is a prime number dividing the order of G, then there exists a g∈G such that ord(g) = p
“normal” subgroup H
H = aHa^(-1) , ∀a∈G
denoted H◁G
properties of normal subgroup
right-coset of H in G
set of form Hg for some g∈G
inverse L:G->G mapping left cosets to right cosets and vice versa.
L(gH) = Hg^(-1)
L(Hg) = g^(-1) H
index [G:H]
number of left cosets = number of right cosets
[G:H] = 2
⟹ H<=G is normal
canonical homomorphism
π : G -> G/H
the surjective homomorphism
g↦gH
ker(π)
= H
G “simple”
G ≠ {e} and {e},G are only normal subgroups of G
CRITERION VIII.1.2
- H◁G
- to construct homomorphism
φ:G/H->G’
to some arb. group G’ - ## find homomorphism ψ:G->G’ : H⊂ker(ψ)
homomorphism theorem
ψ : G->G’ is a group homomorphism
⟹
H:=Ker(ψ) is a normal subgroup of G and G/H ≅ ψ(G) <= G’
ψ surjective ⟹ G/H ≅ G’
first isomorphism theorem
take arbitrary subgroup H<=G and normal subgroup N◁ G then
- HN = {hn | h∈H and n∈N} is a subgroup of G
- N is a normal subgroup of HN
- H∩N is a normal subgroup of H
- H/(H∩N)≅HN/N
second isomorphism theorem
N◁ G
- every normal subgroup in G/N has the form H/N, with H a normal subgroup in G containing N
- if N proper subgroup of some normal subgroup H in G, then (G/N)/(H/N)≅G/H
G “finitely generated”
there exists finitely many elements g1,…,gn∈G with the property:
g= (g↓(i1))^(+-1) … (g↓(it))^(+-1)
∀g∈G can be written in this form with indices 1<=ij<=n
*it is allowed that ik=il, i.e. any gi can be used multiple times
G generated by g1,…,gn
if G finitely generated and we write G=<g1,…,gn>
finitely generated abelian group
- a group (G,.,e) is abelian if ab=ba for all a,b∈G.
- it is finitely generated if there are x1,…,xn∈G : ∀x∈G can be written as x = xi1 ^(+-1) … xim^(+-1) with ij∈{1,…,n}
free abelian group
STRUCTURE THEOREM
- finitely generated abelian group A
- there is unique integer r>=0 and unique (possible empty) finite sequence (d1,…,dm), di>1: dm|dm-1|…|d1
- A ≅ Z^r x Z/d1Z x … x Z/dmZ
- r := rank
- d1,…,dm := elementary divisors of A
torsion subgroup of A
Ator = {a∈A | ord(a) < ∞}
rank Z^n / H
= n-k
k := rank of H
