My Math Forum Doubts from transposition, fixing and Identity
 User Name Remember Me? Password

 Abstract Algebra Abstract Algebra Math Forum

September 15th, 2014, 08:45 AM   #1
Newbie

Joined: May 2014
From: Singapore

Posts: 11
Thanks: 0

Doubts from transposition, fixing and Identity

Dear All,
Please see the attachment for the text i will be referring to.

what does "I = τ1 · · · τm, where each τj is a transposition acting on {1, . . . , n}. Clearly, m != 1, thus m ≥ 2. Suppose, for the moment, that τm does not fix n".

what does fixing n mean in a transposition?

what are a.b and c??? I thought all transpositions started with 1?

what does this whole sentence mean "It follows that we can now write I as a product of m transpositions in which the first transposition to be applied fixes n (this was proved under the assumption that τm(n) != n, and I is already in this form if τm(n) = n)." ?

Thanks.....
Attached Images
 Capture.jpg (92.6 KB, 6 views)

September 16th, 2014, 07:20 AM   #2
Senior Member

Joined: Mar 2012

Posts: 294
Thanks: 88

Quote:
 Originally Posted by AspiringPhysicist Dear All, Please see the attachment for the text i will be referring to. what does "I = τ1 · · · τm, where each τj is a transposition acting on {1, . . . , n}. Clearly, m != 1, thus m ≥ 2. Suppose, for the moment, that τm does not fix n". what does fixing n mean in a transposition? what are a.b and c??? I thought all transpositions started with 1? what does this whole sentence mean "It follows that we can now write I as a product of m transpositions in which the first transposition to be applied fixes n (this was proved under the assumption that τm(n) != n, and I is already in this form if τm(n) = n)." ? please help me understand lemma 1.4.3 with an example?? Thanks.....

I suggest getting more well-acquainted with $S_3$ which has 6 elements, and $S_4$ which has 24...the full symmetry groups get very big, fairly fast, and it becomes hard to write down everything explicitly for $n > 4$ (the multiplication table for $S_5$ has 14,400 entries).

What we want to do is prove the PARITY (evenness/oddness) of a transposition decomposition of the identity is invariant. The "number" of transpositions it takes to do so is NOT invariant for example, in $S_3$:

$I = (1\ 3)(1\ 3) = (1\ 3)(1\ 3)(1\ 2)(1\ 2) = (1\ 3)(1\ 2)(1\ 2)(1\ 2)(1\ 2)(1\ 3)$

so we have a way to write the identity as a product of 2,4 or 6 transpositions right there.

Transpositions need not "start with a 1", in $S_4$ we have the following transpositions:

(1 2), (1 3), (1 4), (2 3), (2 4), (3 4)

of which only the first 3 involve 1.

The first transposition only moves 1 and 2 (they swap places), so it fixes 3 and 4. Similarly (1 3) fixes 2 and 4, and so on.

*********

Ok, so we have an induction argument to carry out. Our base case is $n = 2$.

We assume that for some $n-1$ (maybe just 2, we don't know yet) the theorem is true.

We can thus regard our transpositions as elements of $S_{n-1}$. Now all of these can also be regarded as elements of $S_n$ that fix $n$.

Now we suppose we have some arbitrary product of transpositions in $S_n$ that equals the identity. Here's our strategy:

Suppose that the last transposition fixes $n$. Then we have a SHORTER product:

$\tau_1\cdots\tau_{m-1}$ that fixes $n$ as well. If $\tau_{m-1}$ ALSO fixes $n$, we keep going. If ALL of them fix $n$, then they all can be considered as lying in $S_{n-1}$, and we can apply our induction hypothesis to conclude that $m$ is even.

Of course, the assumption that $\tau_m(n) = n$ might not be TRUE. So here, we take a slightly different tack: we show we can re-write our product with DIFFERENT transpositions, in such a way that $m$ isn't changed.

So if $\tau_m(n) \neq n$ it must be that $\tau_m$ is of the form $(a\ n)$ for some number $a \in \{1,2,3,\dots,n-1\}$.

Next we look at the "next-to-last" transposition. There are 4 cases:

1. $\tau_{m-1}(n) = n$ and $\tau_{m-1}(a) = a$.

This implies that $\tau_{m-1}$ and $\tau_m$ are disjoint 2-cycles, so they commute, and we can just switch the order.

2. 1. $\tau_{m-1}(n) = n$ and $\tau_{m-1}(a) = b$ <--this is the same $a$ as we have in $\tau_m$.

In this case, we have:

$\tau_{m-1}\tau_m = (a\ b)(a\ n) = (a\ n\ b) = (b\ n)(a\ b) = \sigma_{m-1}\sigma_m$

Note we still have 2 transpositions at the end, but the product:

$I = \tau_1\tau_2\cdots \tau_{m-2}\sigma_{m-1}\sigma_m$

has the same number of transpositions ($m$), but now the last one fixes $n$.

3. $\tau_{m-1}(n) = a$.

In this case $\tau_{m-1} = \tau_m$, and we can either "cancel them" (reducing $m$ by 2, which doesn't change its parity), or replace them both with:

$(a\ b)(a\ b)$ (where neither $a$ nor $b$ is $n$).

4. $\tau_{m-1}(n) = b \neq a$.

In this case, we have:

$\tau_{m-1}\tau_m = (b\ n)(a\ n) = (a\ b\ n) = (a\ n)(a\ b)$

so again, we can replace the last TWO transpositions with two more such that the last one fixes $n$.

So in any case, we can arrange it so our last transposition fixes $n$, without changing $m$.

We can keep doing this, until we've done this for every transposition except $\tau_1$.

Now if $\tau_2\cdots\tau_m$ fixes $n$ since:

$I = \tau_1(\tau_2\cdots\tau_m)$

it must be that $\tau_2\cdots\tau_m = (\tau_1)^{-1} = \tau_1$.

Since $\tau_2\cdots\tau_m$ fixes $n$ so does $\tau_1$, and thus the whole product fixes $n$-we apply our induction hypothesis, and we are done.

 Tags doubts, fixing, identity, transposition

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post rightsidedbrain Algebra 3 June 3rd, 2014 12:16 AM Sadlercomfort Linear Algebra 5 April 28th, 2014 05:19 AM randomFire Algebra 6 February 1st, 2011 12:17 AM skylineview945r2 Algebra 5 January 9th, 2011 04:23 PM pauliewalnuts Calculus 2 May 6th, 2008 08:09 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top