Znaménko inverzní premutace
Úloha číslo: 2445
Ukažte čtyřmi způsoby, proč má inverzní permutace \(p^{-1}\) stejné znaménko jako původní permutace \(p\)?
Nápověda
Uvažte cykly, počet inverzí, rozklad na transpozice a zachování znaménka při skládání.
Řešení
Permutace \(p\) a \(p^{-1}\) mají stejné délky cyklů (a na stejných prvvcích), protože permutace \(p^{-1}\) vznikne z \(p\) otočením šipek v grafu cyklů.
Permutace \(p\) a \(p^{-1}\) mají stejný počet inverzí, protože v bipartitním grafu permutace zůstanou křížení nezměněna pokud otočíme směr šipek.
Je-li \(p=t_1\circ t_2\circ…\circ t_k\) rozklad \(p\) na transpozice, pak \(p^{-1}=t_k\circ t_{k-1}\circ…\circ t_1\). Snadno ověříme, že složením získáme identitu.
Z rovnice \(sgn(p)\cdot sgn(p^{-1})=sgn(p\circ p^{-1})=sgn(\imath)=1\) plyne okamžitě, že \(sgn(p)= sgn(p^{-1})\).