Composition of Transpositions Proof

Asked Mar 31 '17 at 02:45

Active Mar 31 '17 at 03:46

Viewed 156 times

Here is the question that I'm working on:

Show that if $n \geq 2$, then every permutation of $\{1,2,...,n\}$ can be expressed as the composition of transpositions of the form ($1$ $a$), where $a = 2,3,...,n$.

We'll, let's say that we call such a set $S$ such that it has the elements $$S = \{1,2,3\}.$$

Then it's obvious that the composition of transpositions for this set if given by $$(13),(12)$$

That's the case only when $n = 3$ and $a = 2,3$. Visually, I know that this result will happen for other values of $n$ and $a$, but describing this observation as a proof is where I'm stuck on. How should I start the proof?

EDIT It seems the way to handle this problem is to give a proof by induction on $n$.

edited Mar 31 '17 at 03:46

asked Mar 31 '17 at 02:45

John W. Smith

1,597

Any permutation on all $n$ elements can be written as $(1, a, b, \ldots c, d, n) = (1, n)(1, d)(1, c) \ldots (1, b)(1, a)$. – Benjamin Dickman Mar 31 '17 at 02:53
Ah yes I believe I saw a proof of this on my textbook. But that's all there is to it? – John W. Smith Mar 31 '17 at 02:56
@BenjaminDickman: What you have shown is any cycle can be expressed so. You need to add a remark to make it complete. – P Vanchinathan Mar 31 '17 at 02:56
What type of remark should he add? – John W. Smith Mar 31 '17 at 03:03

Composition of Transpositions Proof

0 Answers0