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.

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email