Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

Login

Username

Password

Not registered yet?

#1 2009-04-13 07:19:13

JaneFairfax
Legendary Member

Offline

Permutations


A permutation is a bijection from the set
to itself. The set of all permutations forms a group of order
under composition of mappings, called the symmetric group of degree
and denoted
.

Permutations may be odd or even. Here is the most intuitive definition I can come up with for odd and even permutations. It is not the definition given in John F. Humphreys’s book A Course in Group Theory, but it will do.

Given
, let

   


Then we say that
is even if the number of elements in
is even, and odd if
is odd. smile

Last edited by JaneFairfax (2009-04-15 03:13:43)


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.
 

#2 2009-04-13 07:42:27

JaneFairfax
Legendary Member

Offline

Re: Permutations

Note that



Hence the identity is always an even permutation.

Also



A transposition
(where
) is a permutation which maps
to
and vice versa, leaving all other numbers fixed. Consider the ordered pairs



Under the transposition
, the image of the first component of each ordered pair is
, which is greater than the second component of each ordered pair (which is fixed in the transposition)

Hence
.

Similarly, the ordered pairs



are in
, since the transposition maps the second component to
while fixing the first component.

The only other ordered pair that can belong to
is
.

, which is odd. smile


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.
 

#3 2009-04-13 07:58:59

JaneFairfax
Legendary Member

Offline

Re: Permutations

This definition of odd/even permutations is at least intuitive. Unfortunately it is also mathematically unwieldy. Try proving, using this definition, that the composition of two even permutations is an even permutation, for instance. neutral

Humphreys’s definition, in terms of properties of an n-variable polynomial (which I incidentally recognize as the determinant of the Vandermonde matrix tongue), while not so intuitive, is more amenable to mathematical manipulation. Under this more flexible definition, the set of even permutations of Sn arises naturally as the kernel of a homomorphism from Sn to a 2-element group. This is thus a subgroup of index 2, called the alternating group An – and it follows without more ado that the product of two even permutations is even. smile


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.
 

#4 2009-04-13 08:20:36

JaneFairfax
Legendary Member

Offline

Re: Permutations






Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.
 

#5 2010-11-30 01:13:44

JaneFairfax
Legendary Member

Offline

Re: Permutations

Okay, here is another definition of even and odd permutations.





Let’s look at the expression on the right-hand side. The denominator is a product of
factors, and so is the numerator. Let
be a factor in the denominator. Either
or
. In the former case
is a factor in the numberator, while in the latter case
is a factor in the numerator. Conversely, if
is a factor in the numerator, then (as
) either
is a factor in the denominator (if
) or
is a factor in the denominator (if
).

So we see that if
is a factor in the denominator then either
or
is a factor in the numerator and conversely if
is a factor in the numerator then either
or
is a factor in the denominator. It follows that
is always either +1 or −1.
We define
to be even if
is and odd if
.

Last edited by JaneFairfax (2010-12-01 04:50:12)


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.
 

#6 2010-12-01 04:25:23

JaneFairfax
Legendary Member

Offline

Re: Permutations













so we need to show that
.

We first rewrite some of the factors in this product:



Note that this is equivalent to multiplying by
which means that it leaves the value of the product unchanged. Doing this for all i, j, we can ensure that all the factors in the denominator are of the form
for
, with the corresponding factors in the numerator the same way round. Hence







as required.

Last edited by JaneFairfax (2010-12-01 04:26:35)


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.
 

#7 2010-12-07 06:55:05

JaneFairfax
Legendary Member

Offline

Re: Permutations

JaneFairfax wrote:













so we need to show that
.

We first rewrite some of the factors in this product:



Note that this is equivalent to multiplying by
which means that it leaves the value of the product unchanged. Doing this for all i, j, we can ensure that all the factors in the denominator are of the form
for
, with the corresponding factors in the numerator the same way round. Hence







as required.


Q: Who wrote the novels Mrs Dalloway and To the Lighthouse?

A: Click here for answer.
 

#8 2011-07-16 18:45:34

Chalisque
Novice

Offline

Re: Permutations

The feeling of stability that you get with a tripod is present with an even permutation but not with an odd one (and this does not depend upon any significant subtleties of your arithmetic or set-theoretic foundations) so the trick to getting a student to intuitively understand the difference between odd and evenness is to lead them somehow to this feeling, and the path is potentially different for every student since no two people start from the same point of view.

 

Board footer

Powered by FluxBB