exam Flashcards
(108 cards)
1
Q
inverse element of x
A
unique y∈G : xy=e=yx
y=x^(-1)
show that xy=e
2
Q
inverse element properties
A
(a^(-1))^(-1) = a
(a1…an)^(-1) = an^(-1)…a1^(-1)
(a^n)^(-1) = a^(-n) = (a^(-1))^n
3
Q
x^0=
A
e
4
Q
a and b “congruent modulo N”
A
N|a-b
a≡bmodN
5
Q
equivalence relation
A
[reflexivity]
a≡amodN
[symmetry]
a≡bmodN ⟺ b≡amodN
[transitivity]
a≡bmodN and b≡cmodN
⟹ a≡cmodN
6
Q
residue class of a modulo N
A
amodN := {b∈Z| b≡amodN}
7
Q
amodN=bmodN
A
⟺a≡bmodN
8
Q
a=qN+r
A
⟹a≡rmodN
⟹amodN=rmodN
9
Q
amodN
A
= a_
= {a+Nk|k∈Z}
10
Q
a is a “unit modulo N”
A
∃b_ ∈ Z/NZ :
a_ * b_ = 1_
gcd(a,N) = 1
11
Q
(Z/NZ)^X
A
subset of Z/NZ containing all units modulo N
12
Q
Euler’s totient function
A
ρ(N) = #(Z/NZ)^X
13
Q
Euler’s theorem
A
for all a_∈ (Z/NZ)^X,
(a_)^ρ(N) = 1_
14
Q
Fermat’s little theorem
A
if p is prime,
(amodp)^p = amodp
15
Q
subgroup H of G
A
H<=G
H is subset of G and group law and unit element are the same.
16
Q
subgroup criterion
A
[H1]
e∈H
[H2]
x,y∈H ⟹ x*y ∈H
[H3]
x ∈H ⟹ x^(-1) ∈H
17
Q
Lagrange
A
H is a subgroup of finite G
⟹
#H | #G
18
Q
ord(x)
A
- minimum m>0 such that x^m=e
- no such m exists ⟹ ord(x)=∞
19
Q
ord(x^(-1))
A
- ord(x) = ord(x^(-1))
- ord(x)<∞
⟹
<x>={x,x^2,...,x^ord(x)=e}
-
</x>
20
Q
ord(x)<∞
A
<x> = {x , x^2, ..., x^(ord(x)) = e}
</x>
21
Q
<x></x>
A
= ord(x)
22
Q
G<∞
A
⟹ ord(x) < ∞ ⟹ ord(x)|#G
23
Q
x^n=e
A
⟹ ord(x) | n
24
Q
G “cyclic”
A
if G=<g> for some g∈G
g is then the "generator" of G</g>
25
ord(g) = #G
⟺ G is cyclic and generated by g
, for finite G
26
homomorphism
f:X->Y : f(x*y) = f(x)*f(y)
27
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
28
isomorphism
bijective homomorphism
29
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
30
kernel of f
given homomorphism f:(X,ex)->(Y,ey)
ker(f) := {x∈X | f(x) = ey}
31
kernel properties
- ker(f) is subgroup of X
- f injective ⟺ ker(f) = {ex}
32
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
33
ρ(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
34
Euler's totient function properties
φ(NM) = φ(N) * φ(M)
for all positive integers N,M with gcd(N,M) = 1
35
S↓(Σ)
Σ non-empty set
S↓(Σ) := set of all bijections from Σ to Σ
36
symmetric group on the set Σ
(S↓(Σ) , ∘ , idΣ)
37
Cayley's theorem
every group G is isomorphic to a subgroup of S↓(G)
38
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
39
sign of permutation
ε(δ) := ∏{1<=i
40
ρ ∘ ( a1 ... al) ∘ ρ^(-1)
= (ρ(a1) ... ρ(al))
for any ρ∈S↓(n) and any l-cycle (a1 ... al) ∈S↓(n)
41
#S↓(n)
= n!
42
if a permutation can be written as a product of transpositions as 𝓣1*...*𝓣L and γ1*...*γk
⟹ L = Kmod2
43
alternating group
for n>=1
A↓(n) is the subgroup of S↓(n) consisting of all even permutations
44
elements of A↓(n) for n>=2
(n!)/2
45
A↓(n) for n>=3
the elements of A↓(n) can be written as products of 3-cycles
46
inner product
47
norm
||u|| = √ ()
48
distance
d(u,v) = √ ()
49
O(R^n, <.,.>)
the set of all linear maps φ satisfying = <φ(u), φ(v)>
50
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
51
orthogonal group
O(n) = {A∈ GLn(R) | A^(T)A = I}
52
special orthogonal group
SO(n) = {A∈ GLn(R) | A^(T)A = I and det(A) = 1}
53
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!
54
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
55
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.
56
aφ(F)
57
infinite dihedral group
D↓(∞) := the symmetry group of a circle
58
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
59
n-th dihedral group
D↓(n) := the symmetry group of Fn
60
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
61
λ↓(a)
ρ↓(b)
g↦ag
g↦gb
62
conjugation by a
the bijective map γ↓(a) : G->G : g↦aga^(-1)
63
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)
64
x,y conjugate
∃ γ↓(a) conjugation for some a:
γ↓(a) (x) = y
65
conjugacy class of x∈G
the subset of G
C↓(x) = {y∈G |∃a∈G : γ↓(a) (x) = y}
66
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
67
conjugate of a cycle (a1 ... ak) by ρ∈S↓(n)
= ρ(a1 ... ak)ρ^(-1) = (ρ(a1) ... ρ(ak))
68
cycle type of δ
δ = δ1*...*δk
with Li length of δi L1<=...<=Lk
including elements i: δi=I as 1-cycles
the sequence [L1, ... , Lk]
69
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
70
centraliser of a
N(a) := {g∈G | φ↓(g) (a) = a }
= {g∈G | ga = ag}
* G finite ⟹ #G = #C↓(a) * #N(a)
71
left coset of H in G
any subset of the form gH for g∈G
72
G/H
:= {gH : g∈G}
the set consisting of all left-cosets
73
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] = ∞
74
group action
a map G X X -> X : (g,x) ↦ g*x satisfying
[A1] e*x=x , ∀x∈X
[A2] (g*h)*x = g*(h*x) , ∀g,h∈G, ∀x∈X
75
stabiliser of x in G
G↓(x) := {g∈G : gx=x} ⊆ G
76
orbit of x under G
Gx := {gx: g∈G} ⊆ X
77
"faithful" action
if for every distinct pair g,h∈G, ∃x∈X:
g*x ≠ h*x
78
"transitive" action
if for every distinct pair x1,x2∈X, ∃g∈G:
g*x1 = x2
⟺ Gx=x for all x
79
x∈X "fix point" of G
if Gx = {x}
i.e. gx=x, ∀g∈G
80
set of all fix points in G
X^(G) := {x∈X: gx=x, ∀g∈G}
81
"fix point free" action
X^(G) = ∅
82
orbit-stabiliser theorem
for any G-set X and any x∈X one has #Gx = [G:G↓(x)]
83
sylow p-group in G
subgroup H⊆G with #H = p^n
*for a prime number p that divides the order go G
*#G = m*p^n , n>=1 gcd(p,m)=1
84
n↓(p) (G)
number of pairwise disjoint slow p-groups in G
85
sylow theorem
- #G = p^n * m
n>=1, gcd(p,m) =1
- a subgroup H with #H = p^n is a sylow p-group.
86
number of pairwise distinct sylow p-groups in G
n↓(p) (G) ≡ 1modp
n↓(p) (G) | m
87
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
88
"normal" subgroup H
H = aHa^(-1) , ∀a∈G
denoted H◁G
89
properties of normal subgroup
90
right-coset of H in G
set of form Hg for some g∈G
91
inverse L:G->G mapping left cosets to right cosets and vice versa.
L(gH) = Hg^(-1)
L(Hg) = g^(-1) H
92
index [G:H]
number of left cosets = number of right cosets
93
[G:H] = 2
⟹ H<=G is normal
94
canonical homomorphism
π : G -> G/H
the surjective homomorphism
g↦gH
95
ker(π)
= H
96
G "simple"
G ≠ {e} and {e},G are only normal subgroups of G
97
CRITERION VIII.1.2
- H◁G
- to construct homomorphism
φ:G/H->G'
to some arb. group G'
- find homomorphism ψ:G->G' : H⊂ker(ψ)
-
98
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'
99
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
100
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
101
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
102
G generated by g1,...,gn
if G finitely generated and we write G=
103
finitely generated abelian group
- a group (G,.,e) is abelian if a*b=b*a 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}
104
free abelian group
105
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
106
torsion subgroup of A
Ator = {a∈A | ord(a) < ∞}
107
rank Z^n / H
= n-k
k := rank of H
108
-
Key Links
-
Subjects
-
Company
-
Find Us
-
