Understanding the Odd Permutation Product Mystery

[johnnyboy2005]

i was wondering if anyone can help me understand why the product of two odd permutations is odd? i came across this on a website but it didn't help me understand why. thanks for the help

 

[HallsofIvy]

Do you understand what "even" and "odd" permutations are? Every permutation can be reduced to a sequence of "two-element swaps": for example, the permutation that changes 1234 into 3124 can be written as
(13)(12): first swap 1 and 3: 1234-> 3214, then swap 1 and 2: 3214->3124.
Of course, there are many different ways to do that:
(23)(13) will work or even (14)(34)(24)(14): 1234->4231->3241->3421->3124 but anyone permutation will consist of either an even number of swaps or an odd number no matter how that is done. An even permutation is one that requires and even number of "swaps", an odd permutation is one that requires an odd number of permutations.
One way of taking the product of two permutations is to just combine their "swaps"
1234->3214 can be written as (13) so the permutation
formed by 1234->3214 followed by 1234->3214 can be written
(13)(12)(13). The number of swaps in the product is just the sum of the number of swaps in each: in particular, the sum of 2 odd numbers is even, so the product of two odd permutations is an even permutation.

 

[-Job-]

I guess we can visualize this with a graph where each possible permutation is represented with a node and there is an edge between two nodes A and B if by swapping two digits in A's permutation (transposition) we get B. Suppose the nodes A and B aren't connected, then we are interested in a path from A to B (which gives a sequence of transpositions that transform A into B). If the path has odd length then it is an odd permutation, otherwise it is even. It is a fact that a permutation is either odd or even, meaning that if there is a path of even length from A to B, then all paths from A to B are of even length. (A way to see what is going on is to try to create a permutation graph with nodes A, B and C. You cannot connect A, B and C so that they from a triangle, because this would mean that from node A you can get to B with a path of length 1 A->B and a path of length 2 A-> C -> B, which implies that there is a transposition that is equivalent to two transpositions, which cannot be)
If you have an odd permutation from A -> B and an odd permutation from B -> C, then you have a path from A to B of odd length and a path from B to C of odd length. Hence there is a path from A to C of odd+odd = even length, so all paths from A to C are even and any permutation from A to C is an even permutation.

 

[matt grime]

Halls is perfectly correct with his definition. At the risk of unnecessarily introducing another (unnecessary) idea (I stil can't tell what Job's getting at) there is another way of thinking about even and oddness. (Incidentally, in case you've not realized, the product of two odd elements is even.)

The permutation group can be realized as a set of nxn matrices. Pick a vector space of n dimensions with basis

e_1,...,e_n

each permutation acts by permuting basis elements. This defines a linear map or matrix.

The determinant of this matrix is the sign of the element, 1 for even elements -1 for odd elements. (You can put any of these permutation matrices into the identity matrix by swapping rows, the number of row swaps is odd or even depending on if the element is odd or even).

And we all know that det(AB)=det(A)det(B) so if A and B are odd (ie determinant -1) then AB is even

 

[johnnyboy2005]

great, thanks so much for your replies. everything was pretty clear. Just have a question for Halls,:

you wrote
1234 into 3124 can be written as (13)(12): this i understand...


first swap 1 and 3: 1234-> 3214, then swap 1 and 2: 3214->3124.
can u please explain how swapping 1 and 2 changes 3214 into 3124?


Of course, there are many different ways to do that: (23)(13) will work or even (14)(34)(24)(14): 1234->4231->3241->3421->

thanks again, this is a great web site...lots of help and quick replies

 

[HallsofIvy]

first swap 1 and 3: 1234-> 3214, then swap 1 and 2: 3214->3124.
can u please explain how swapping 1 and 2 changes 3214 into 3124?

Be careful: I don't mean swapping what is in the first and second places: I specifically meant swapping the symbols 1 and 2. The 3 in the first place and the 4 in the last place don't change. 1 moves from 2nd to 3rd place while 2 moves from 3rd to 2nd place.

3214
3124

"1" and "2" have swapped positions.

 

[-Job-]

At the risk of unnecessarily introducing another (unnecessary) idea (I stil can't tell what Job's getting at)...

In a model where each permutation of n digits is represented by a node and where there is an edge between two nodes A and B iff there is a single transposition of the permutation of A that transforms it to B. Then you can talk about the lengths of permutations as the length of the paths from an initial permutation A to a final permutation B.
In such a graph if the path to B (from A) is odd, then B is an odd permutation of A, otherwise it is even. We know that if B is an odd permutation of A then it can't be even as well, meaning that if there is a path of odd length from A to B, then all paths from A to B are of odd length.
So if B is an odd permutation of A and C is an odd permutation of B, then there are paths of odd length from A to B and from B to C. Hence we can get from A to C by traversing the two odd paths A->B->C which gives a path of even length. So the product of two odd permutations is even.
To me this seems like an easy way to visualize what's going on (i've seen it used in proofs regarding the properties of hypercubic networks).

 

[johnnyboy2005]

fantastic! thanks a lot guys, i have figured it out.

 

[matt grime]

So it is a graph G, its vertex set is S_n and there is an edge from s to t if st^{-1} is a transposition ('transposition that transforms it' doesn't make much sense unless you define 'transformations' by transpositions). Why didn't you say so... The sign of a permutation is then the parity of any path from the node of the identity to it.

As with all of these we need to prove that our definition is well defined (Ie it is always an even/odd number of transpositions). My 'proof' that odd composed odd is even sidesteps this entirely but at no point do I prove rigorously that the determinant is the the same as the sign.. That is something I've never seen done. Does anyone have a nice proof of this?

 

[Galileo]

This is how I was introduced to it. By a lemma:
There exists a unique map [itex]\varepsilon: S_n \to \{\pm 1\}[/itex] with the following properties:
(1) If [itex]\sigma[/itex] is a transposition (2 element swap), then [itex]\varepsilon(\sigma)=-1[/itex]
(2) For arbitrary elements [itex]\sigma, \tau \in S_n[/itex] we have [itex]\varepsilon(\sigma \tau)=\epsilon(\sigma)\epsilon(\tau)[/itex].
(Note from self: [itex]\varepsilon[/itex] is thus a homomorphism from S_n to the multiplicative group [itex]\{1,-1\}[/itex]).
Proof: Since every permutation is a product of transpositions it's clear there can only exist one such function. But because a permutation can be written as such a product in many different ways, it's not so clear it should exist at all.
We define [itex]\varepsilon[/itex] by considering the function [itex]F:\mathbb{R}^n\to \mathbb{R}[/itex] as follows:
[tex]F(x_1,x_2,...,x_n)=\prod_{1\leq i < j \leq n}(x_i-x_j)[/tex]
Notice that F is not the zero function. For [itex]\sigma \in S_n[/itex] we define the function [itex]\sigma F : \mathbb{R}^n \to \mathbb{R}[/itex] given by:
[tex](\sigma F)(x_1,x_2,...,x_n)=\prod_{1\leq i < j \leq n}(x_{\sigma(i)}-x_{\sigma(j)})[/tex]
This function is the same as F with a possible switch in sign of the images. So we define [itex]\epsilon(\sigma)[/itex] as [itex]\sigma F=\varepsilon(\sigma) F[/itex]
If [itex]\sigma[/itex] is a transposition (i j), then we can construct [itex]\sigma F[/itex] from F, by switching [itex]x_i-x_j[/itex] with [itex]x_j-x_i[/itex]. That's because every other factor with [itex]x_i[/itex] or [itex]x_j[/itex] can be paired with some element [itex]x_k, k\not= i,j[/itex]. We get four pairs for each k:
[tex](x_i-x_k)(x_j-x_k), \quad (x_i-x_k)(x_k-x_j), \quad (x_k-x_i)(x_j-x_k), \quad (x_ki-x_i)(x_k-x_j)[/tex]
All these factors are invariant under the transposition (i j). Therefore [itex]\varepsilon(\sigma)=-1[/itex] for a transposition [itex]\sigma[/itex]
From the relation [itex](\sigma \tau)F=\sigma(\tau F)[/itex] it's easy to see that [itex]\varepsilon(\sigma \tau)F=\varepsilon(\sigma)\varepsilon(\tau)F[/itex].
-------
The proof looks complicated, but once you get the idea it's not that bad. If we call the permutations which are mapped to 1 even and the ones that are mapped to -1 odd you got the required result.

 

[matt grime]

No, that's good and simple. I'd never bothered to look for a proof, I just remember being told that it was hard.

You have effectively shown an explicit homomorphism from S_n into C_2 that doesn't require the notion that sign is well defined a priori. However, you haven't actually checked that this is indeed a homomorphism (or an action of S_n, or representation depending on your view). You've merely said 'from the relation that (st)F=s(tF)' without verifying that is true.I imagine this is merely messy and not actually hard though.