## Factorization with (1,i)

### Task number: 2458

Show that every permutation on $$n$$ elements can be decomposed into transpositions of form $$(1,i)$$ for $$i \in \{2,…, n\}$$.

Determine a bound of the length of the resulting factorization.

• #### Hint

Derive and use $$(a,b)=(c,a)(c,b)(c,a)$$.

• #### Resolution

First detrmine the cycles.

The cycle containing 1, e.g. $$(1,a,b,c,…)$$ factorize as $$(1,a,b,c,…)=(1,a)(1,b)(1,c)…$$

Other cycles, e.g. $$(a,b,c,…)$$ factorize first as $$(a,b,c,…)=(a,b)(a,c)…$$ Every transposition rewrite as $$(a,b)=(1,a)(1,b)(1,a)$$, i.e. $$(a,b)(a,c)…=(1,a)(1,b)(1,a)(1,a)(1,c)(1,a)…$$ After the elimination of consecutive pairs $$(1,a)(1,a)$$ we get rozklad $$(1,a)(1,b)(1,c)…(1,a)$$.

The length of the factorization is bounded by $$\frac{2n-1}{3}=1+\frac{2}{3}(n-2)$$, it is attained when the permutation has all cycles of length two.