======Подстановки ======
<wrap hide>проверено</wrap>
===== Подстановка =====
__Определение 1.__ Произвольное [[:glossary:mapping#виды_отображений|взаимно однозначное отображение]] [[:glossary:set|множества]] первых <latex>n</latex> [[:glossary:set:integer:positive|натуральных чисел]] называется **подстановкой**((permutation)) <latex>n</latex>**-го порядка**.

__Замечание 1.__ Часто подстановки называют **перестановками**.

Обычно подстановку <latex>\pi</latex> изображают следующим образом: <latex>\begin{pmatrix}1 & 2 & \ldots & n\\ i_1 & i_2 & \ldots & i_n\end{pmatrix}</latex>, что задает образы всех элементов: <latex>\pi(1)=i_1</latex>, <latex>\pi(2)=i_2</latex> и так далее. Также используют запись <latex>\begin{pmatrix}i_1 & i_2 & \ldots & i_n\\ k_1 & k_2 & \ldots & k_n\end{pmatrix}</latex>.

__Пример 1.__ Подстановку <latex>\begin{pmatrix}1 & 2 & 3\\ 3 & 2 & 1\end{pmatrix}</latex> можно записать также в виде <latex>\begin{pmatrix}2 &1 & 3\\ 2 & 3 & 1\end{pmatrix}</latex>, так как в обоих случаях мы имеем отображение <latex>1\mapsto 3</latex>, <latex>2\mapsto 2</latex>, <latex>3\mapsto 1</latex>.

__Определение 2.__ Элемент <latex>k\in\{1,\ldots,n\}</latex> подстановки <latex>\pi</latex> называется **действительно перемещаемым**, если <latex>k\neq\pi(k)</latex>.

__Пример 2.__ В подстановке <latex>\begin{pmatrix}1 & 2 & 3\\ 3 & 2 & 1\end{pmatrix}</latex> два действительно перемещаемых символа: 1 и 3.

Операция умножения на подстановках определяется как [[:glossary:mapping:composite|композиция отображений]], причем знак композиции <latex>\circ</latex> обычно опускают <WRAP centeralign><latex>\begin{pmatrix}i_1 & i_2 & \ldots & i_n\\ k_1 & k_2 & \ldots & k_n\end{pmatrix}\begin{pmatrix}1 & 2 & \ldots & n\\ i_1 & i_2 & \ldots & i_n\end{pmatrix}=\begin{pmatrix}i_1 & i_2 & \ldots & i_n\\ k_1 & k_2 & \ldots & k_n\end{pmatrix}\circ\begin{pmatrix}1 & 2 & \ldots & n\\ i_1 & i_2 & \ldots & i_n\end{pmatrix}=\begin{pmatrix}1 & 2 & \ldots & n\\ k_1 & k_2 & \ldots & k_n\end{pmatrix}</latex>.</WRAP>
===== Транспозиции и циклы=====
__Определение 3.__ **Циклической подстановкой**((cyclic permutation)), или **циклом**((cycle)) называется такая подстановка <latex>\pi\in S_n</latex>, что при повторении ее достаточное число раз всякий из действительно перемещаемых ею символов может быть переведен в любой другой из этих символов. Для обозначения цикла используют запись <latex>(i\quad\pi(i)\quad\ldots\quad\pi^{t-1}(i))</latex>, где <latex>t</latex> --- число действительно перемещаемых символов подстановки, которое называется **длиной цикла**((cycle length)).

__Пример 3.__ В подстановке <WRAP centeralign><latex>\pi=\begin{pmatrix}1 & 2 & 3 & 4 & 5 & 6 & 7 & 8\\ 3 & 2 & 6 & 5 & 1 & 4 & 7 & 8\end{pmatrix}</latex></WRAP> действительно перемещаемыми символами являются 1, 3, 4, 5, 6. Выберем любой из них, например, 3. <latex>\pi(3)=6,\,\pi(6)=4,\,\pi(4)=5</latex>, <latex>\pi(5)=1,\,\pi(1)=3</latex>. Поэтому цикл можно записать как <latex>(3\quad 6\quad 4\quad 5\quad 1)</latex>.

__Определение 4.__ Циклы называются **независимыми**((independent)), если они не имеют общих действительно перемещаемых символов.

__Предложение 1.__ Любая подстановка <latex>\pi\neq e</latex> из <latex>S_n</latex> может быть разлжена в произведение попарно независимых циклов. Такое представление определено однозначно с точностью до порядка перемножения циклов.

__Пример 4.__ <latex>\begin{pmatrix}1 & 2 & 3 & 4 & 5\\ 3 & 5 & 1 & 2 & 4\end{pmatrix}=(1\quad 3)(2\quad 5\quad 4)</latex> --- разложение подстановки в произведение попарно независимых циклов.

__Определение 5.__ Цикл длины 2 называется **транспозицией**((transposition)).

__Предложение 2.__ Каждая подстановка может быть представлена в виде произведения транспозиций.
<hidden onVisible="Доказательство." onHidden="Доказательство."  initialState="invisible">
Покажем, что каждый цикл может быть представлен в виде произведения транспозиций. Действительно, <WRAP centeralign><latex>(i\quad\pi(i)\quad\ldots\quad\pi^{t-1}(i))=(i\quad\pi^{t-1}(i))(i\quad\pi^{t-2}(i))\ldots(i\quad\pi^{2}(i))(i\quad\pi(i))</latex>.</WRAP>
Так как любая подстановка представляется в виде произведения циклов, то достаточно записать каждый цикл в виде произведения транспозиций.
</hidden>

В отличие от представления в произведение попарно независимых циклов, представление в виде произведения транспозиций может не быть единственным.

__Пример 5.__ Подстановка <latex>\begin{pmatrix}1 & 2 & 3 & 4\\ 2 & 3 & 1 & 4\end{pmatrix}</latex> может быть разложена в произведение транспозиций <latex>(1\quad 3)(1\quad 2)</latex> или <latex>(1\quad 3)(2\quad 4)(1\quad 2)(1\quad 4)</latex>.
===== Четность подстановки =====
__Определение 6.__ Пусть <latex>\pi=\tau_1\ldots\tau_k</latex> --- разложение подстановки <latex>\pi</latex> в произведение транспозиций. Тогда число <latex>\varepsilon(\pi)=(-1)^k</latex> называется **знаком**((signature))(**четностью**) подстановки <latex>\pi</latex>. Подстановка называется **четной**((even)), если <latex>\varepsilon(\pi)=1</latex> и **нечетной**((odd)) в противном случае.

__Предложение 3.__ Четность подстановки не зависит от способа разложения подстановки в произведение транспозиций.

__Предложение 4.__ Для двух подстановок <latex>\pi_1</latex> и <latex>\pi_2</latex> четность их произведения равна произведению четностей: <WRAP centeralign><latex>\varepsilon(\pi_1\pi_2)=\varepsilon(\pi_1)\varepsilon(\pi_2)</latex>.</WRAP>
<hidden onVisible="Доказательство." onHidden="Доказательство."  initialState="invisible">
Пусть <latex>\pi_1=\tau_1\ldots\tau_k</latex>, <latex>\pi_2=\tau_{k+1}\ldots\tau_{k+l}</latex>, значит, <latex>\varepsilon(\pi_1)=(-1)^k</latex> и <latex>\varepsilon(\pi_2)=(-1)^l</latex>. Тогда <latex>\pi_1\pi_2=\tau_1\ldots\tau_k\tau_{k+1}\ldots\tau_{k+l}</latex> --- разложение подстановки в произведение транспозиций. Поэтому <WRAP centeralign><latex>\varepsilon(\pi_1\pi_2)=(-1)^{k+l}=(-1)^k(-1)^l=\varepsilon(\pi_1)\varepsilon(\pi_2)</latex>.</WRAP>
</hidden>

__Предложение 5.__ Пусть <latex>\pi</latex> --- цикл длины <latex>l</latex>. Тогда его четность равна <latex>\varepsilon_{\pi}=(-1)^{l-1}</latex>.
<hidden onVisible="Доказательство." onHidden="Доказательство."  initialState="invisible">
Утверждение следует из того, что цикл длины <latex>l</latex> представим в виде произведения <latex>l-1</latex>-й транспозиции <WRAP centeralign><latex>(i\quad\pi(i)\quad\ldots\quad\pi^{l-1}(i))=(i\quad\pi^{l-1}(i))(i\quad\pi^{l-2}(i))\ldots(i\quad\pi^{2}(i))(i\quad\pi(i))</latex>.</WRAP>
</hidden>

__Определение 7.__ Пусть <latex>\pi=\pi_1\pi_2\ldots\pi_k</latex> --- разложение подстановки в произведение независимых циклов длин <latex>l_1,l_2,\ldots,l_k</latex>. Число <latex>d_{\pi}=l_1+\ldots+l_k-k</latex> называется **декрементом**((decrement)) подстановки <latex>\pi</latex>.

__Предложение 6.__ Пусть <latex>\pi=\pi_1\pi_2\ldots\pi_k</latex> --- разложение подстановки в произведение независимых циклов длин <latex>l_1,l_2,\ldots,l_k</latex>. Тогда четность подстановки <latex>\pi</latex> вычисляется по формуле <WRAP centeralign><latex>\varepsilon_{\pi}=(-1)^{d_{\pi}}</latex>.</WRAP> 
<hidden onVisible="Доказательство." onHidden="Доказательство."  initialState="invisible">
По предложению 5 <latex>\varepsilon(\pi_i)=(-1)^{l_i-1}</latex> для <latex>1\leqslant i\leqslant k</latex>. По предложению 4 <WRAP centeralign><latex>\varepsilon(\pi)=\varepsilon(\pi_1)\ldots\varepsilon(\pi_k)=(-1)^{l_1-1}\ldots(-1)^{l_k-1}=(-1)^{l_1+\ldots l_k-k}=(-1)^{d_{\pi}}</latex>.</WRAP>
</hidden>

__Пример 6.__ Любая транспозиция --- это нечетная подстановка. Подстановка из примера 4 нечетная, так как декремент <latex>(2-1)+(3-1)</latex> --- нечетное число.

__Пример 7.__ Любая подстановка, в разложении которой на независимые циклы все циклы имеют нечетные длины <latex>l_1,l_2,\ldots,l_k</latex>, четна, так как ее декремент --- это сумма <latex>k</latex> четных чисел <latex>(l_1-1)+(l_2-1)+\ldots+(l_k-1)</latex>.
===== См. также =====
  * [[:glossary:group:symmetric|Группа подстановок]]
===== Литература =====
  * [[http://www.ozon.ru/context/detail/id/21839075/?partner=lds1938|Кострикин А.И. «Введение в алгебру. Основы алгебры», МЦНМО, 2012.]]
  * [[http://www.ozon.ru/context/detail/id/17563348/?partner=lds1938|Курош А.Г. «Курс высшей алгебры», Лань, 2008.]]

{{tag>"абстрактная алгебра" "группа" "декремент" "знак подстановки" "множество" "отображение" "перестановка" "подстановка"  "транспозиция" "цикл" "четность подстановки"}}