Proving Even # of Transpositions for Identical Permutations

In summary, a standard proof for the number of transpositions being even for any identical permutation is to consider the expression $\displaystyle m = \prod_{1\leq i < j \leq n} (i - j)$ and its permutation $\sigma(m) = \prod_{1 \leq i < j < \leq n} (\sigma(i) - \sigma(j))$, where $\sigma$ is a transposition, and show that it cannot be both an even and odd number of transpositions.
  • #1
simo1
29
0
is there any easier way of proving that no matter how an identical permutation say (e) is written the number of transpositins is even.

my work
i tried let t_1...t_n be m transpositions then try to prove that e can be rewritten as a product of m-2transpositions.
i had x be any numeral appearing in one of the transpositions t_1...t_n where t_k=(xa) and t_k is the last transposition in e=t_1t_2...t_m. i tried this and it seems very long:(
 
Physics news on Phys.org
  • #2
That is actually a difficult thing to prove, although it "seems" obvious it should be true.

This is the "standard" proof:

Consider the expression:

$\displaystyle m = \prod_{1\leq i < j \leq n} (i - j)$.

We define:

$\displaystyle \sigma(m) = \prod_{1 \leq i < j < \leq n} (\sigma(i) - \sigma(j))$ for $\sigma \in S_n$.

Note that if $\sigma$ is a transposition, that $\sigma(m) = -m$. Also note that no matter what permutation $\sigma$ is, we have:

$\sigma(m) = \pm m$.

Note also that if $\sigma = \tau\pi$ we have:

$\displaystyle\sigma(m) = \tau(\pi(m)) = \prod_{1 \leq i < j < \leq n} (\tau(\pi(i)) - \tau(\pi(j)))$

Now if a permutation $\sigma$ could be written as both an even number and odd number of transpositions, we obtain:

$m = -m \implies m = 0$, which is impossible, since all the factors of $m$ are non-zero (An odd number of transpositions changes the sign of $m$ an odd number of times, resulting in $-m$, and an even number of transpositions changes the sign of $m$ an even number of times, resulting in no change to $m$).
 

FAQ: Proving Even # of Transpositions for Identical Permutations

What is the concept of identical permutations?

Identical permutations refer to a set of numbers or objects that can be rearranged in the same order without changing the overall result. In other words, the elements in the set can be rearranged in different ways, but the end result will still be the same.

How do transpositions relate to identical permutations?

Transpositions are a type of permutation that involves swapping two elements in a set. For identical permutations, transpositions can be used to rearrange the elements without changing the overall result.

Why is it important to prove that there is an even number of transpositions for identical permutations?

Proving that there is an even number of transpositions for identical permutations is crucial because it helps us understand the structure and properties of these permutations. It also allows us to develop efficient algorithms for solving problems involving identical permutations.

How can we prove that there is an even number of transpositions for identical permutations?

One way to prove this is by using the concept of parity. Parity refers to whether a number is even or odd. We can assign a parity value to each transposition and show that the overall parity for identical permutations is always even, indicating an even number of transpositions.

Can this concept be applied to other types of permutations?

Yes, the concept of proving an even number of transpositions can be applied to other types of permutations as well, such as even and odd permutations. It is a fundamental concept in the study of permutations and can be extended to various mathematical and scientific fields.

Back
Top