Permutation Groups and Symmetric Groups | Abstract Algebra
Summary
TLDRThis video script delves into the concept of permutations as a fundamental aspect of abstract algebra. It defines permutations as bijections from a set to itself and explains how they form groups under function composition. The script covers the properties of group operations, such as associativity, identity, and inverses, using the symmetric group notation S_a and S_n as examples. It also provides a detailed exploration of the symmetric group S3, illustrating the composition of permutations and identifying inverses through a comprehensive table.
Takeaways
- 🔄 A permutation is a reordering of elements in a set, which can be thought of as a bijection from a set to itself.
- 🔄 The operation between permutations is function composition, where one permutation is applied before another.
- 🔄 Function composition is associative, meaning the order in which compositions are performed does not affect the result.
- 🔄 The composition of permutations is closed, meaning that composing any two permutations results in another permutation.
- 🔄 There exists an identity element in permutation groups, which is the identity function that leaves all elements unchanged.
- 🔄 Every permutation has an inverse that, when composed with the original permutation, results in the identity permutation.
- 🔄 Permutations on a set form a group, with the set of all permutations of a set denoted as S_a, and specifically for the first n positive integers as S_n.
- 🔄 Symmetric groups, denoted by S_n, represent all possible permutations of a set and can be likened to the symmetries of an object.
- 🔄 A group of permutations may refer to a subgroup of a symmetric group, not necessarily containing all permutations.
- 🔄 The number of permutations for a set of n objects is n factorial, as demonstrated by the six permutations in the symmetric group S3.
- 🔄 The inverse of a permutation can be found using a composition table, which shows the result of composing any two permutations from the group.
Q & A
What is a permutation?
-A permutation is a reordering of elements in a set, and more rigorously, it is a bijection from a set to itself, meaning it is a one-to-one and onto mapping that rearranges the elements of the set without changing their quantity.
Why are permutations considered groups in abstract algebra?
-Permutations are considered groups because they satisfy the four group axioms: closure (composition of any two permutations results in another permutation), associativity (the composition of permutations is associative), identity (there exists an identity permutation that leaves all elements unchanged), and inverses (every permutation has an inverse that undoes its effect).
What is the operation between permutations?
-The operation between permutations is function composition, where one permutation is applied after another, resulting in a new permutation.
What is the identity element in the group of permutations?
-The identity element in the group of permutations is the identity function, denoted as Epsilon, which maps each element to itself, leaving the set unchanged.
How do you find the inverse of a permutation?
-The inverse of a permutation is found by reversing the effect of the original permutation such that when composed with the original permutation, the result is the identity permutation. Each element is mapped to its original position before the permutation was applied.
What is the significance of the symmetric group notation S_a?
-The notation S_a stands for the symmetric group on the set 'a', which is the set of all permutations of the elements in 'a'. It is called 'symmetric' because each permutation can be seen as a symmetry of the set.
What is the difference between a symmetric group and a group of permutations?
-A symmetric group, denoted as S_a or S_n, contains all possible permutations of a set. A group of permutations, on the other hand, may refer to any group G that is a subgroup of a symmetric group, and does not necessarily include all permutations.
How many permutations are there in the symmetric group S3?
-There are six permutations in the symmetric group S3, as the number of permutations of 'n' objects is n factorial, and for S3, n=3, so 3! = 6.
Can you provide an example of composing two permutations from the symmetric group S3?
-Sure, if we take the permutations Beta and Gamma from S3 and compose them (Beta composed with Gamma), we first apply Gamma which swaps 1 with 2 and leaves 3 unchanged, and then apply Beta which swaps 1 with 3 and 2 with 2, resulting in a new permutation where 1 maps to 1, 2 maps to 3, and 3 maps to 2.
What does it mean for a permutation to be its own inverse?
-A permutation is its own inverse if composing it with itself results in the identity permutation. This means that applying the permutation and then applying it again leaves the set unchanged, effectively undoing the first application.
How can you verify that the composition of two permutations results in another permutation?
-You can verify this by applying the first permutation to the set, then applying the second permutation to the result of the first. If the final arrangement of elements is a bijection from the set to itself, then the composition is indeed another permutation.
Outlines
🔄 Introduction to Permutations and Groups
This paragraph introduces the concept of permutations as reorderings of elements and their mathematical definition as bijections from a set to itself. It explains the operation of function composition for combining permutations and highlights the properties that make permutations form a group, such as closure, associativity, and the existence of an identity element and inverses. The paragraph sets the stage for a deeper exploration of abstract algebra through the study of permutations.
🔄 Properties of Permutation Composition
The second paragraph delves into the properties of the operation used to combine permutations, which is function composition. It establishes that this operation is associative due to the nature of function composition and that the composition of permutations is closed, meaning that composing any two permutations results in another permutation on the same set. The paragraph also introduces the identity permutation, which leaves elements unchanged, and discusses the concept of inverse permutations, which when composed with their corresponding permutation, yield the identity permutation.
🔄 Symmetric Groups and Permutation Examples
This paragraph discusses symmetric groups, denoted as S_A or S_n, which are groups of all permutations on a set. It uses the example of the symmetric group S3, which contains all permutations of the set {1, 2, 3}, to illustrate how permutations can be combined through composition. The paragraph provides a detailed table showing the results of composing different permutations from S3, demonstrating the concept of inverse permutations and reinforcing the group properties of permutations.
🔄 Conclusion and Further Exploration
The final paragraph concludes the discussion on permutations and groups, emphasizing that permutations form groups due to the presence of an identity element, closure, associativity, and inverses. It clarifies the distinction between a symmetric group, which contains all permutations of a set, and a group of permutations, which could be a subgroup of a symmetric group. The paragraph invites the viewer to explore more examples of groups of permutations in future videos and encourages questions and video requests in the comments.
Mindmap
Keywords
💡Permutation
💡Bijection
💡Function Composition
💡Associativity
💡Closure
💡Identity Element
💡Inverse
💡Symmetric Group
💡Group
💡S3
Highlights
A permutation is defined as a bijection from a set to itself, essentially a reordering of elements.
The operation between permutations is function composition, which is associative and closed.
The identity element in permutation composition is the identity function, which leaves elements unchanged.
Every permutation has an inverse that is also a permutation, ensuring the group structure.
The set of all permutations of a set, with function composition as the operation, forms a group.
The symmetric group on a set is denoted by S_A, representing all permutations of the set.
S_n specifically refers to the symmetric group on the first n positive integers.
A group of permutations can be a subgroup of a symmetric group, not necessarily containing all permutations.
The number of permutations of n objects is n factorial, demonstrated with S3 having six elements.
The composition of two permutations results in another permutation, as shown with beta and gamma in S3.
A full table of permutations in S3 and their compositions can be used to identify inverse permutations.
Alpha permutation is its own inverse, demonstrated through its composition with itself resulting in the identity.
The concept of function composition is applied from right to left when composing permutations.
The practical application of permutations is likened to the symmetries of geometric shapes, like rotating a square.
The video provides a detailed example of composing permutations in S3, illustrating group properties.
The video concludes with an invitation for viewers to engage with questions or video requests.
Transcripts
let's go over what a group of
permutations is will cover definitions
why these things are groups we'll also
cover symmetric groups and we'll see how
we combine permutations in a group this
will give us a whole array of new
examples of groups to study as we
continue learning abstract algebra now
what is a permutation you may just think
of it as a reordering of something we
might have ABC in this order and we
could permute it into this other order
maybe we switch A and B so in A's place
we now have B and in B's place we now
have a and we leave C unchanged that
would be an example of a permutation but
for our purposes we'll need a slightly
more rigorous definition this more
rigorous definition is actually quite
simple a permutation is just a bijection
from a set to itself I'll leave a link
in the description if you need a recap
of what by objections are but here are
two quick examples of bijections from a
set to itself so these are both
permutations these are both permutations
on the set containing one two and three
this permutation Alpha takes one as an
input and sends it to two it Maps two to
one and it Maps three to itself this
other permutation beta takes one and
Maps it to two it takes two and Maps it
to three and it Maps three to one these
are each bijections from this set one
two three back to itself they basically
just Shuffle the elements around we're
thinking about how groups are
constructed with permutations so what
would the operation be between
permutations well again a permutation is
just a special type of function so the
operation is function composition and it
works quite simply if we want to compose
the permutation Alpha with the
permutation beta we would write it like
this Alpha of beta just remember how the
notation works this means that the
permutation beta is applied first and
then Alpha is applied so we start with 1
2 3 and first we apply beta that sends
one to two two to three and three to one
and then we apply Alpha which takes 2
and sends it to one it takes three and
sends it to three and it takes one and
sends it to two so the net effect of
composing Alpha with beta was to send
one to one two to three and three to two
it gave us another permutation so we've
got this idea of permutations by
ejections from sets to themselves and
we've got this operation between them
composition now let's discuss some
properties that this operation has
firstly it is associative this is
because function composition is
associative so the composition of
permutations is associative as a result
to quickly prove it let's just recall
what function composition is its
notation is this F of G of some input X
and what it means is evaluate the
function f at the function G at X so F
of G of X is f of G of x to prove this
operation is associative we need to show
that F composed with G of H of X is
equal to F of G composed with h of X and
this is done through repeated
applications of the definition F
composed with G of H is by definition F
of G decomposed with h but then F of G
composed with h is by definition F of G
of H but then F of G evaluated at h of X
is just F composed with G evaluated at h
of X which by definition is f composed
with G of H of X and so indeed
composition between permutations more
generally function composition itself is
associative earlier we took the
composition of two permutations and got
another permutation this is of course
true in general that the composition of
permutations is closed this is because
if we compose by ejections from a set a
to itself we will get another bijection
from the set a to itself so if we just
have a bunch of permutations of this at
a and we compose any two of them we'll
just get another permutation on the set
a I'll leave a link in the description
to my lesson proving that the
composition of bijections is a bijection
which thus gives us this result of
closure for permutations but I hope
you'll agree it's a fairly easy result
to accept each permutation just shuffles
a set into some order and so if we
permute a set and then permute it again
which is composing permutations you're
just going to get the set shuffled in
some order so again you're going to get
a permutation on that same set moving on
let's quickly talk about the identity do
we have an identity element when it
comes to composing permutations we
certainly do for any set a the identity
function on a is this guy we could call
Epsilon it goes from a back to a and it
takes each input and leaves it unchanged
so the identity function Epsilon of x
equals X
certainly by definition this Epsilon is
a permutation it is a bijection from a
to itself and we see if we compose
Epsilon with any other permutation that
just gives us the permutation right back
this is fairly easily demonstrated as I
wrote out in these equations just
explaining this one for example if we
compose Epsilon with any permutation F
by definition that's taking F and
plugging it into Epsilon but Epsilon
doesn't change the input so we just get
F back out so Epsilon of f is f so
indeed Epsilon is our identity element
when it comes to composing permutations
if we compose any permutation with this
identity function the permutation is
left unchanged now that we have an
identity element we can start to think
about inverses recall that permutations
are just bijections from a set to itself
off hopefully you're familiar with the
fact that bijections have inverses and
I'll leave a link in the description to
my lesson proving it if you need to see
that but we know every bijection has an
inverse that is also a by ejection and
thus every permutation has an inverse
that is also a permutation now we need
to be careful we're talking specifically
about inverse functions this doesn't
necessarily mean that these inverse
functions are the inverses in the
context of the groups that we're trying
to create but we can quickly check that
in fact they are exactly what we're
looking for if we have an inverse
function f inverse composed with the
original function f by definition we get
the identity function and here's some of
the details of that written out in One
Direction if we take F inverse which
could just be the inverse of a
permutation and compose it with f itself
well by definition that means we're
plugging f of x into F inverse but by
definition of inverse functions and in
this context inverse permutations these
guys just undo each other leaving the
inside element X unchanged so indeed we
have inverse elements for our
permutations going back to the first
permutation Alpha that we saw at the
beginning of the video this would be
Alpha inverse Alpha sends one to two but
Alpha's inverse element sends two back
to one alpha sends two to one the alpha
inverse sends one back to two and they
both leave three unchanged if we
permuted a set with Alpha and then with
Alpha inverse the set would be unchanged
if we permuted it with Alpha inverse and
then Alpha it would also be unchanged if
you compose a permutation with its
inverse that ends up not changing
anything at all you get the identity so
we've got inverse elements we've got an
identity element we've got closure we've
got associativity we've got groups and
that's our big result for any set a the
set of all permutations of a the set of
all bijections from a to itself along
with the operation of function
composition is a group these are groups
of permutations here's some common
notation S Sub a stands for the
symmetric group on the set a this is
just the set of all permutations of a
it's called a symmetric group because
each permutation of a set is like one of
the sets symmetries very much like how
you could rotate a square and place the
square back onto itself you can permute
the elements of a set and place them
back onto the set that's like a
bijection in right and then S Sub n this
is the symmetric group specifically on
the set of the first n positive integers
so the group of all permutations of 1
through n and then generally if we say a
group of permutations we're referring to
any group essay or SN any of these
symmetric groups or any subgroup of one
of these two groups so a symmetric group
S A has all permutations on the set a
but a group of permutations doesn't
necessarily need to have all
permutations so when we say a group of
permutations we could be referring to a
subgroup of asymmetric group doesn't
necessarily have to be the whole
symmetric group let's dig more into
detail with an example here is the full
symmetric group S3 every permutation on
the set of positive integers one through
three as you might expect there are six
elements you may recall that the number
of permutations of three objects is
three factorial so unsurprisingly we
have six different permutations here the
notation I've used is a common notation
for permutations that I think you'll
agree is pretty straightforward here for
Epsilon what this notation means is that
the permutation Epsilon takes one and
sends it to one takes two sends it to
two it takes three and sends it to three
this is of course the identity
permutation meanwhile the permutation
gamma sends one to two two to one and
three to three if we come over to the
permutation Kappa it sends one to three
and so on so these are all six
permutations of one two and three we can
try taking two permutations from this
symmetric group S3 and composing them
let's look at beta composed with gamma
remember when doing function composition
the function on the right acts first so
first we would apply this permutation
gamma it sends one to two two to one and
three to three then we apply beta beta
sends two to one it sends one to three
and it sends three to two so the net
effect of this composition is that one
gets sent to let me make my highlighter
a little smaller one gets sent to one
because gamma sent it to two but beta
sent two back to one two gets sent to
three because gamma sends two to one but
beta sent one to three and three gets
sent to two because gamma sends three to
three but beta takes three and sends it
two if you look back at the list of
permutations of S3 it turns out that
when we compose beta with gamma what we
get is Alpha our composition sent one to
one just like Alpha does it sent two to
three just like Alpha and it sent three
to two which is also what Alpha does
this of course isn't a surprise that
composing the permutations would give us
another permutation let's now take a
look at the full table if we compose any
two permutations from S3 what
permutation do we get here's the full
results in this table the function that
would act first the one that would be on
the right if you did function
composition is in the top row and the
function that would act second the
function that would be on the left in
function composition is here on the
leftmost column so if we want to look
for example at what we get if we compose
beta with gamma we would would go to
gamma first as the function on the right
so look at Gamma in the column and then
go down to the beta row and what we get
no surprise is Alpha and this is the
Full Table showing us what we would get
if we composed any two of these
permutations together if we looked at
Gamma of Kappa for example we would
start at Kappa and go down to the gamma
row that turns out to be beta if we want
to see what beta of alpha would be we'd
start at the alpha column and go down to
the beta row we see that that gives us
Kappa these are the full results feel
free to check them yourself as a fun
exercise using this table we can also
pick out inverse permutations if we look
at Delta for example we see that we get
Epsilon the identity function when Delta
is composed with the beta so Delta and
beta are inverses if we go to the beta
column we get the identity function at
the Delta Row the inverse of alpha
interestingly is alpha alpha is its own
inverse let's quickly go through that
calculation Alpha is the permutation
that sends one to one two to three and
three to two it's inverse based on the
table is itself so let's try taking
Alpha inverse and composing it with
Alpha and see what we get when composing
permutations another way we can write
them is like this in this sort of
product notation and again it's function
composition so we want to go from right
to left starting with this permutation
and then going to that one so let's look
at where one would get sent Alpha
inverse sends one to one and then Alpha
sends one to one so one just goes to one
Alpha inverse sends two to three but
then Alpha sends three back to two so if
we put 2 in this composition it will
first get sent to three but then get
sent back to two and then three gets
sent to two by Alpha inverse and then
Alpha sends two back to three so no
surprise if we can pose Alpha with its
inverse which happens to be itself one
just gets sent to one two to two and
three to three there is just an identity
permutation of nothing being moved at
all this is of course what you'll get if
you take any permutation from this table
and try composing it with its inverse
and if you want to try doing a few more
of those on your own here again is the
complete list of the six permutations of
S3 and I think that's enough for now
remember a permutation is just a
bijection from a set to itself we can
combine permutations with function
composition this is a closed operation
if we compose permutations from a set to
itself we get another permutation on
that same set we also have an identity
permutation which doesn't move any
elements at all and each permutation has
an inverse Additionally the operation of
composition is associative so
permutations on a set form groups we
denote the group of permutations on a
set a as S A and if that set happens to
be the first and positive integers we
denote it as s n and when we talk about
a group of permutations we might be
referring to one of these full symmetric
groups with all the permutations on a
particular set or we may be talking
about a subgroup of one of the bigger
symmetric groups in the next video we'll
see some more interesting examples of
groups of permutations let me know in
the comment if you have any questions or
video requests
[Music]
[Music]
5.0 / 5 (0 votes)