Discussion on question by Math55: Proof verification - Any $\sigma \in S_n$ can be written as the product of at most $n - 1$ transpositions

Feeds

17:05

Q: Proof verification - Any $\sigma \in S_n$ can be written as the product of at most $n - 1$ transpositions

Any $\sigma \in S_n$ can be written as the product of at most $n - 1$ transpositions My proof: Let $\sigma \in S_n$. $\sigma$ can be represented in cycle notation in one of these forms: $(a_1 … a_n)$, $(a_1 … a_{n_1})$, $(a_1, a_2)$, $(1)$. If $\sigma = (a_1 … a_n)$, then it can be decomposed a...

Shaun

What about the identity? (It is the product of any non-negative even number of transpositions.)

Haziq Muhammad

@Shaun Well $(1) = (a_1 a_2) (a_1 a_2)$ since a transposition is its own inverse. So does that mean this proposition does not apply for $n$ less than $3$?

Shaun

Just pick an even number greater than $n-1$.

Vercassivelaunos

The identity is the empty product of transpositions, so it's a product of 0 transpositions.

Haziq Muhammad

@Vercassivelaunos So does that mean my proof is sound?

kabenyuk

17:05

@Math55: Your proof is absolutely correct and complete. With this correction $\sigma\neq e$.

Shaun

It is also the product of an arbitrary non-negative even number of transpositions, @Vercassivelaunos.

Peter

Intuitively , it is clear that we can achieve every permutation with at most $n-1$ transpositions : If the first element is not the desired one, swap the desired element with the current first one. Repeat this for the second, third , and so on until the $n-1$ th element. If all numbers in the positions $1$ to $n-1$ are as desired, the last number must be correct as well.

Vercassivelaunos

To be honest, I don't really get your proof. What is $n_1$? And are you saying that any permutation is just a cycle?

@Shaun: it is, but that doesn't help in the case of $n\in\{1,2\}$

Haziq Muhammad

@Vercassivelaunos Sorry it should have been $n-1$. Just edited it

Shaun

You can always multiply an element by the identity, too.

Well, $$e=(12)(12)(12)(12).$$

Peter

17:05

@Shaun For the given problem , this does not matter anyway , since the claim is only that we need AT MOST $n-1$ transpositions. "Exactly $n-1$" would be wrong anyway in general since the number of transpositions has a parity fixed by the permutation.

kabenyuk

@Math55: I recommend looking at here

Shaun

That's not what I'm saying, @Peter. Besides, if an element had $n-1$ transpositions, then just multiply by $(12)(12)$.

Peter

We need not rule out the identical permutation since it can be considered as the empty product of tranpositions , so we need $0$ transposition in this case.

Shaun

The problem is, @Peter, that the OP needed to specify that the transportations need to be disjoint.

Vercassivelaunos

I disagree with this being a duplicate of the linked question. While the answer to this question follows from those in the "duplicate", this question is more elementary, and can have helpful answers which are easier to grasp than the answers to the duplicate.

last day (15 days later) »

all rooms