Proving that the parity of a permutation is well defined.

In summary, the theorem that all proofs use for the identity permutation in Sn is that the identity permutation has even parity. Then, by letting a be one of the first elements to appear in a transposition representation of a permutation in Sn, and identifying all other transpositions in the representation that also feature a, the proof can be completed using two defined "moves" that "move" a in a specified direction. This can eventually cancel two transpositions, leaving a representation with 2 less transpositions which proves the theorem through an induction argument. However, there may exist another, shorter proof that does not involve this "moving" argument and instead uses the definition of sign as the product of inversions. This proof is discussed in detail on Wikipedia.
  • #1
espen180
834
2
All the proofs I have seen for this theorem uses the same argument: First prove that the identity permutation has even parity. Then let a be (one of) the first elements to appear in a transposition representation of a permutation in Sn. Then identify all the other transpositions in the representation that also feature a and play with the order and such using two defined "moves" that "move" a in a specified direction. Since only a finite number of transpositions feature a, we can eventually cancel two, leaving us with a representation of 2 less transpositions. The theorem follows by an induction argument.

I think this is a somewhat ugly and clumsy proof, probably my least favorite in my algebra book. Does anyone know if there exists another, shorter proof, which does not invoke this "moving" argument?
 
Physics news on Phys.org
  • #2
espen180 said:
All the proofs I have seen for this theorem uses the same argument: First prove that the identity permutation has even parity. Then let a be (one of) the first elements to appear in a transposition representation of a permutation in Sn. Then identify all the other transpositions in the representation that also feature a and play with the order and such using two defined "moves" that "move" a in a specified direction. Since only a finite number of transpositions feature a, we can eventually cancel two, leaving us with a representation of 2 less transpositions. The theorem follows by an induction argument.

I think this is a somewhat ugly and clumsy proof, probably my least favorite in my algebra book. Does anyone know if there exists another, shorter proof, which does not invoke this "moving" argument?


If [itex]\sigma\in S_n[/itex] is a permutation, the DEFINITION of the sign of [itex]\sigma[/itex] is [itex]Syg(\sigma):=\prod_{1\leq i< j\leq n}\frac{i-j}{\sigma(i)-\sigma(j)}[/itex] .

I can't see how the above can't be well defined: the above is 1 if the number of inversions in the order of each pair [itex] (i,j)[/itex] in the image of [itex]\sigma[/itex] is even,

and -1 otherwise. What is there to proof?

DonAntonio
 
  • #3
Assuming that is given as the definition of sign, which it isn't always

Wikipedia discusses the equivalence of the two definitions and gives several elegant proofs in my opinion (which equivalently can be thought of as proving that the sign is well defined in the number of transpositions sense)

http://en.wikipedia.org/wiki/Parity_of_a_permutation
 
  • #4
Office_Shredder said:
Assuming that is given as the definition of sign, which it isn't always

Wikipedia discusses the equivalence of the two definitions and gives several elegant proofs in my opinion (which equivalently can be thought of as proving that the sign is well defined in the number of transpositions sense)

http://en.wikipedia.org/wiki/Parity_of_a_permutation



Well, then it may be what you wrote in the last lines: take one definition and prove that another one is equivalent to it.

This though wasn't what the OP wanted, at least from what I can understand in his question.

DonAntonio
 
  • #5


I understand your concern with the elegance and simplicity of a proof. However, in mathematics, the most important aspect of a proof is its correctness and logical coherence. The "moving" argument you mention is a commonly used technique in induction proofs and is a valid way to prove the parity of a permutation is well-defined.

That being said, there may be alternative proofs that use different techniques or logic, but they may not necessarily be shorter or simpler. I suggest exploring different resources or consulting with other mathematicians to see if there are any alternative proofs that you find more elegant.

Additionally, it is important to remember that sometimes the most straightforward or intuitive approach may not always lead to a valid proof. The fact that the "moving" argument may seem clumsy does not diminish its validity as a proof.

In conclusion, while it is always valuable to seek out different perspectives and approaches to a proof, the most important aspect is ensuring its correctness and logical coherence.
 

FAQ: Proving that the parity of a permutation is well defined.

What is the definition of parity in a permutation?

In mathematics, the parity of a permutation refers to whether the permutation can be expressed as an even or odd number of transpositions. In simpler terms, it is a way to determine whether the permutation has an even or odd number of inversions (pairs of elements that are out of order).

Why is proving the well-definedness of parity important?

Proving the well-definedness of parity is important because it ensures that the concept of parity holds true for all permutations, regardless of how they are written or expressed. It also allows us to make generalizations and draw conclusions based on the properties of parity.

How is the parity of a permutation calculated?

The parity of a permutation can be calculated by counting the number of inversions in the permutation. If the number of inversions is even, the permutation has an even parity. If the number of inversions is odd, the permutation has an odd parity.

What is an example of a permutation with even parity?

An example of a permutation with even parity is (1, 3, 2), which can be expressed as two transpositions: (1, 2) and (2, 3). This permutation has two inversions (3, 2) and (1, 2), making it an even permutation.

Can a permutation have both even and odd parity?

No, a permutation can only have either even or odd parity. This is because the number of inversions in a permutation is always either even or odd, and therefore the parity of a permutation is also either even or odd.

Similar threads

Replies
1
Views
2K
Replies
3
Views
1K
Replies
2
Views
3K
Replies
10
Views
2K
Replies
1
Views
4K
Replies
1
Views
1K
Back
Top