Proving Even # of Transpositions for Identical Permutations

Click For Summary
SUMMARY

The discussion centers on proving that any identical permutation, denoted as (e), can only be expressed using an even number of transpositions. The standard proof involves the expression m = ∏(i - j) for 1 ≤ i < j ≤ n, and demonstrates that if a permutation σ can be represented as both an even and odd number of transpositions, it leads to a contradiction where m equals zero. This establishes that the number of transpositions for identical permutations must be even, as odd transpositions alter the sign of m, while even transpositions do not.

PREREQUISITES
  • Understanding of permutations and transpositions in group theory
  • Familiarity with mathematical notation and proofs
  • Knowledge of the symmetric group S_n
  • Basic algebraic manipulation of products and signs
NEXT STEPS
  • Study the properties of the symmetric group S_n and its elements
  • Explore the concept of even and odd permutations in detail
  • Learn about the sign of a permutation and its implications
  • Investigate alternative proofs for the parity of permutations
USEFUL FOR

Mathematicians, students of abstract algebra, and anyone interested in combinatorial proofs and the properties of permutations.

simo1
Messages
21
Reaction score
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
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$).
 

Similar threads

Replies
8
Views
5K
  • · Replies 7 ·
Replies
7
Views
3K
  • · Replies 3 ·
Replies
3
Views
5K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 11 ·
Replies
11
Views
5K
  • · Replies 4 ·
Replies
4
Views
9K
  • · Replies 26 ·
Replies
26
Views
1K
Replies
1
Views
2K
  • · Replies 4 ·
Replies
4
Views
2K