Pure Mathematics B3: Permutations

75 flashcards · Mathematics · by lakesare

Name 2 meanings of the word "permutation" in mathematics: in combinatorics in group theory.
in combinatorics - the result of applying the permutation function to the list of elements. in group theory - the permutation function itself.
What's a permutation in group theory?
One-to-one function S → S.
How do we refer to the element of the set being permuted?
Symbol.
[Permutation notation] How to read this cycle form notation?
Each () is a cycle of applying g repeatedly.
When do we call the cycles of the permutation disjoint?
Two cycles are disjoint when they don't share any symbol.
[Permutation notation] How to read this two-line form notation?
Each 1st row symbol maps to the 2nd row symbol.
[Permutation notation] How would we write g as a "product of cycles"?
[Permutation notation] What exactly is a cycle when it comes to permutations? This permutation f maps the symbols 1 to 5 , 2 to 6, 3 to 1, and so on, as we see by reading downwards.
The tuple we get by applying f repeatedly.
[Permutation notation] Name 2 ways in which we can reorder f.
reorder the cycles reorder the symbols within cycles
[Permutation notation] Purely physically - how does f present in: two-line form cycle form. Permutation notation is about the way we can describe one-to-one functions.
two-line form cycle form
When is a symbol fixed by a permutation?
When the permutation function maps x to x.
[Permutation notation] What's the full form of the permutation f?
[Permutation notation] Write down the two-line form of the identity permutation (e in cycle form).
[Permutation notation] How do we denote the identity permutation?
e.
[Permutation notation] Who introduced both the two-line form and the cycle form notations for permutations?
Augustin-Louis Cauchy Augustin-Louis Cauchy (1789 - 1857, France)
Express f as a composite of disjoint cycles.
In fact, since these three permutations are disjoint cycles, f is their composite in any order.
If these are the cycles of f, how would the cycles of f–1 look? The cycles of a particular permutation f.
The cycles of f−1.
[The inverse of a permutation] Purely visually - what exactly is f–1?
What is Sn?
Sn = { all permutations f: {1, ...n} ➝ {1, ...n} }
What is (Sn, ◦)?
The symmetric group of degree n. Sn = { all permutations f: {1, ...n} ➝{1, ...n} }
Symmetric group VS symmetry group.
symmetric group - (Sn, ◦), group of permutation functions symmetry group - (S, F), group of symmetries of the figure
Degree VS order?
degree - number of elements that each f maps order - |Sn|, number of elements Sn has
What order does the symmetric group of degree 3 have?
|S3| = 3! = 3 * 2 * 1 = 6
What's permutation group?
Permutation group - ({ permutations }, ◦)
Give an example of a 3-cycle.
(1 2 3)
Give an example of a transposition.
(1 2)
Give an example of 2 permutations with the same cycle structure.
E.g. (– – –)(– –) and (– –)(– – –).
Name some possible cycle structures in S4. There are five possible cycle structures in S4.
Describe these cycle structures.
What's the element order of 5-cycle? Consider the following 5-cycle in S6.
f has order 5.
What is f3 judging by the picture? Consider the following 5-cycle in S6.
What is the order of permutation f? When is fn = e.
lcm(2, 4, 3) = 12
Why is it more comfortable to use the cycle form to represent symmetries? Two-line form Cycle form
The cycle form makes it obvious that s: switches the vertices at locations 2 and 4, and fixes the vertices at locations 1 and 3.
We found the orders of each element in Pure Mathematics: Symmetry and Groups, however:How can we find the order of s directly from its cycle form? Two-line form Cycle form
It's 2, because lcm(2) = 2.
What's the symmetric group?
Sn = ({ permutations }, ∘) = ({ bijective functions from X to X }, ∘)
Why is it so that: if S(◻) = { all symmetries of a figure with n vertices } Symmetries in a cycle form or in a two-line form.then it's a subgroup of Sn?
Because: we know S(◻) forms a group we know S(◻) is a subset of Sn.
How can we obtain the subgroup of S5 from the figure with 4 vertices?
Just fix the excessive label!
Contents of S(◻) vs Sn?
S(◻) - { symmetries } Each symmetry is a function that maps one vertex to another. Sn - { permutations } Each permutation is a function that maps S to S.
[permutation = composite of transpositions] How would you express the (13254) as a composite of transpositions.
[permutation = composite of transpositions] How would you show that one and the same cycle can have different composites of transpositions.
Just take the same cycle and start it from another symbol.
[permutation = composite of transpositions] Name 2 steps to find: (19)(2367)(485) = composite of transpositions.
Express permutation as a composite of its cycles. Express each cycle as a composite of transposition.
[permutation = composite of transpositions] Imagine the proof visually.
Start writing (a1, ...).
What is parity in mathematics?
In mathematics, parity is the property of an integer of whether it is even or odd. Четность (in russian).
[permutation = composite of transpositions] When is the permutation considered even vs odd?
A permutation is: even - when permutation = (_ _) ◦ (_ _) odd - when permutation = (_ _) ◦ (_ _) ◦ (_ _)
[permutation = composite of transpositions] What's the parity of (1 2 3 4)?
(1 2 3 4) is odd.
[permutation = composite of transpositions] What's the parity of (1 3)?
(1 3) is odd, because (1 3) = (1 3), which is a composite of 1 transposition.
[permutation = composite of transpositions] Name 2 ways to find the parity of e. E.g. (1)(2).
e = (1 2) ◦ (1 2), and 2 is even! e = 0 transpositions, and 0 is even!
What's the set An?
An - { all even permutations of the set { 1, ...n} } A stands for alternating.
What's an alternating group?
An - { all even permutations of the set { 1, ...n} }
What's an interesting difference in the use of n in: Sn VS Zn?
Sn - { permutations of degree {1, ...n} } Zn - { 0, ...n – 1 }
What's the order of An?
|An| = n!/2
[Permutation notation] Name 2 notations for permutations.
two-line form This permutation f maps the symbols 1 to 5 , 2 to 6, 3 to 1, and so on, as we see by reading downwards.cycle form
What are the names of Sn VS An groups?
Sn - symmetric group - all permutations [of degree n] Each permutation is a function that maps S to S.An - alternating group - all EVEN permutations [of degree n] Each even permutation = even number of transpositions.
What are the contents of Sn VS An sets?
Sn - { all permutations } Each permutation is a function that maps S to S.An - { all even permutations } Each even permutation = even number of transpositions.
Symmetry VS permutation?
symmetry - function that keeps distances & maps F to F. permutation - one-to-one function that maps S to S.
How would we relabel the permutation x using the permutation g = (1 3 5 4)?
How would we find y(4) = ??___?? just looking at x and the renaming function g. How can you find the renamed x, but without directly renaming every symbol.
Find the symbol that was renamed as 4 (g–1) Apply x to that symbol (x) Rename result (g)
Name 2 ways to find g ◦ x ◦ g−1.
Compose 3 permutations The renaming method - rename x with g
[Conjugate of the permutation] When is the y a conjugate of x?
When there exists g such that: y = g ◦ x ◦ g−1.
[Conjugate of the permutation] What's another name for the renaming permutation g?
Conjugating permutation.
[Conjugate of the permutation] Why can we say that if 'x is a conjugate of y', then 'x and y are conjugates'?
[Conjugate of the permutation] What does the cycle structure of conjugate permutations look like?
Cycle structures of conjugates are the same. Renaming the permutation keeps its cycle structure, and conjugation is all about renaming.
[Conjugate of the permutation] What conjugating some permutation is all about?
Conjugating is about renaming the permutation a particular way!
[Conjugate of the permutation] If we have the conjugates x and y, how would we find the conjugating permutation g?
Match up the cycle form of the conjugates Read the g
What are these about: conjugate of the complex number VS conjugate of the permutation?
conjugate of the complex number - z = x - iy conjugate of the permutation - the renamed permutation
What does this notation mean (H is a set)?
g ◦ H ◦ g−1 = { g ◦ h ◦ g−1 : h∈H } The set of all elements of H conjugated by g.
How to best visually imagine the symmetric group S3?
({ permutations }, ◦)
Speak this theorem in your own words.
Renamed subgroup of Sn is still a subgroup. I think they mean "the renamed subgroup" is the conjugate of the "original subgroup".
Why bother with the compositions g ◦ x ◦ g−1 if we can just rename x?
Useful for proofs Will later allow us to apply renaming to all groups (and not just permutation groups)
How to find all subgroups of the symmetric group?
Cyclic groups - just write them all out. Symmetry groups - make up the shapes on your own!
An interesting way to find out whether this S(F) is cyclic?
It's cyclic, because S(F) has order 3, and one of its elements is of order 3.
What symmetry group S(F) is isomorphic to the symmetric group S4?
State Cayley's theorem. Arthur Cayley (1821 - 1895, Britain)
Every finite group is isomorphic to some permutation group.
[Cayley's theorem] How would you find the permutation group isomorphic to (Z6, +6)?
Obtain each associated permutation by: (1st row: 0 1 2 3 4 5 ) (2nd row: element's row) Element 2 of Z6 has the following associated permutation
[Cayley's theorem] Why is the Cayley's theorem interesting?
Cayley's theorem tells us that to study finite groups we only need to study symmetric groups Sn (and their subgroups)!