Группа перестановок — различия между версиями

Материал из synset
Перейти к: навигация, поиск
Строка 61: Строка 61:
 
Чтобы их найти, берём первый элемент, номер которого не совпадает с номером позиции (8) и идём на 8-е место. Там стоит 3. Поэтому идём на 3-е место. Там 1, и так как на первом месте стоит 8-ка с которой мы начали, цикл <math>\textstyle [8\;3\;1]</math> замыкается.
 
Чтобы их найти, берём первый элемент, номер которого не совпадает с номером позиции (8) и идём на 8-е место. Там стоит 3. Поэтому идём на 3-е место. Там 1, и так как на первом месте стоит 8-ка с которой мы начали, цикл <math>\textstyle [8\;3\;1]</math> замыкается.
  
−
Цикл записывают опуская индексы, так как их всегда можно восстановить. Для этого необходимо в качестве индекса ставить номер ''предыдущего'' объекта в списке цикла, считая предыдущим для первого элемента &mdash; последний: \parbox{3cm}{
+
Цикл записывают опуская индексы, так как их всегда можно восстановить. Для этого необходимо в качестве индекса ставить номер ''предыдущего'' объекта в списке цикла, считая предыдущим для первого элемента &mdash; последний:  
  
 
:<center><math>[8\;3\;1]=(8_1\;3_8\;1_3)</math></center>
 
:<center><math>[8\;3\;1]=(8_1\;3_8\;1_3)</math></center>
−
 
−
} \parbox{4cm}{
 
  
 
<center>[[File:cicles.png]]</center>
 
<center>[[File:cicles.png]]</center>
−
 
−
} \parbox{5cm}{
 
  
 
:<center><math>\;\;\;\;[7\;9\;6\;2]=(7_2\;9_7\;6_9\;2_6)</math></center>
 
:<center><math>\;\;\;\;[7\;9\;6\;2]=(7_2\;9_7\;6_9\;2_6)</math></center>
−
 
−
} \parbox{3cm}{ <center>
 
  
 
<center>[[File:cicles2.png]]</center>
 
<center>[[File:cicles2.png]]</center>
  
−
} </center> При таком алгоритме записи циклов любые циклические перестановки <math>\textstyle [8\;3\;1]</math>, <math>\textstyle [1\;8\;3]</math>, <math>\textstyle [3\;1\;8]</math> являются одной и той же перестановкой. Смысл цикла состоит в круговой перестановке объектов &mdash; 8 идёт на третье место, 3 идёт на первое, а 1 на восьмое. Заметим, что мы различаем обозначения для цикла (квадратные скобки) и для перестановки (круглые).
+
При таком алгоритме записи циклов любые циклические перестановки <math>\textstyle [8\;3\;1]</math>, <math>\textstyle [1\;8\;3]</math>, <math>\textstyle [3\;1\;8]</math> являются одной и той же перестановкой. Смысл цикла состоит в круговой перестановке объектов &mdash; 8 идёт на третье место, 3 идёт на первое, а 1 на восьмое. Заметим, что мы различаем обозначения для цикла (квадратные скобки) и для перестановки (круглые).
  
 
Если два цикла, например <math>\textstyle [8\;3\;1]</math> и <math>\textstyle [7\;9\;6\;2]</math> не имеют пересекающихся элементов, то произведение содержащих им перестановок можно выполнять в любом порядке:
 
Если два цикла, например <math>\textstyle [8\;3\;1]</math> и <math>\textstyle [7\;9\;6\;2]</math> не имеют пересекающихся элементов, то произведение содержащих им перестановок можно выполнять в любом порядке:

Версия 18:20, 27 сентября 2012

Примеры и определения << Оглавление (Последняя версия в: Глава 5) >> Еще немного определений

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \bullet} Рассмотрим ещё один важный класс групп. Пусть имеется Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n} упорядоченных объектов, пронумерованных цифрами от 1 до Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n} \textstyle . Эти объекты можно переставить местами Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n!=2\cdot 3\cdot...\cdot n/} способами (на первое место поставим один их Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n} предметов; для каждой из этих Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle n} возможностей, на второе место поставим один из Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle (n-1)} оставшихся предметов, и т.д.). Например, для трёх объектов возможно 6 перестановок:

Sym tbl06.png

Каждой перестановке мы присвоили имя "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a} -Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle f} ", и будем её считать операцией, переводящей первоначальный порядок Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle e=(1\;2\;3)} в некоторый другой. Перестановки Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \{a,\;b,\;c\}} задействуют только пары элементов, оставляя третий неизменным. Оставшиеся две являются циклическим сдвигом вправо Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \{d\}} и влево Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \{f\}} .

Композиция двух последовательных перестановок, снова является перестановкой. Представим все возможные композиции перестановок трёх объектов при помощи таблицы умножения. Ясно, что если мы переставим первый и второй объект, а затем повторим эту операцию, то получится исходный порядок. Поэтому Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a^2=b^2=c^2=e} . Сдвинув исходный порядок вправо (Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle d} ), а затем повторив этот сдвиг мы получим Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle f=d^2} . Аналогично рассуждая дальше, сформируем таблицу умножения:

Sym tbl07.png

Эта группа называется группой перестановок или симметрической группой и обозначается как Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{S_3}} . Очевидно, что она не абелева. Например: Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle (a\, b=f)\neq (b\, a=d)} . Аналогично строится группа перестановок Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle n} объектов Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{S_n}} . Она имеет порядок Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle n!} и при Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle n>2} также является не абелевой.

Обратим внимание на блок 2x2 в правом нижнем углу состоящий из элементов Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle f} и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle d} . Это подгруппа Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{C_3}\subset \mathbf{S_3}} . Понятно, что циклические сдвиги вправо или влево вместе с единичным порядком являются замкнутыми операциями и образуют группу Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{C_3}=\{e, d,f\}} . Она является инвариантной (проверьте).

Группа Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{S}_3} изоморфна Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{D}_3} . Действительно, номера вершин треугольника на рисунке Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{D}_3} (стр.\,\pageref{group_D3_pic}), перечисляемые по часовой стрелки, начиная с верхней, являются перестановками трёх чисел (так, только при Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle n=3} ).

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Перестановки можно считать всюду определёнными обратимыми целочисленными функциями Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x(i)} , где Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle i} — позиция элемента, а Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x(i)} — его номер. Результат композиции двух последовательных перестановок Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle z=x\cdot y} равен:

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle z(i) = x\bigl(y(i)\bigr).}

Обратная Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bar{x}} к Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x} перестановка удовлетворяет уравнению:

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \bar{x}\bigl(x(i)\bigr) ={x}\bigl(\bar{x}(i)\bigr) = i.}

Соответственно, единичная перестановка — это "'линейная функция" Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle e(i)=i} .

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} При вычислении результата композиции двух перестановок можно поступать следующим образом. Рассмотрим, например Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a\cdot f=b} . Запишем первую перестановку, поставив у номера объекта индекс равный его текущему положению в списке:

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \overbrace{(2_1\;1_2\;3_3)}^{a}\cdot\overbrace{(2\;3\;1)}^{f}=\overbrace{(1\;3\;2)}^{b},}

На первом месте в Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle f} стоит 2. Это означает, что Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle f} применённая к уже сделанной Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a} , должна на первое место поставить второй элемент Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a} , т.е. "1". Аналогично третий элемент ("3") идёт на второе место, и первый ("2") на третье. Таким образом для записи композиции Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle x\cdot y} необходимо взять второй список, и вместо его цифр Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle y=(i,j, k,...)} записать элементы первого списка с индексами Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle i,j,k,...} :

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle (...\,x_i\,...y_j...z_k...)\cdot(i\,\,j\,k\,...) = (x\, y\, z\,....).}

Например, выполним более длинное умножения двух перестановок девяти объектов:

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle ( 8_1\;2_2\;1_3\;4_4\;5_5\;6_6\;7_7\;3_8\;9_9)\cdot(1\;7\;3\;4\;5\;2\;9\;8\;6)=(8\;7\;1\;4\;5\;2\;9\;3\;6).}

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Чтобы для данной перестановки записать обратную к ней, необходимо значение номера позиции элемента поставить на место номера этого элемента:

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle (...\,x_i\,...y_j...z_k...)^{-1} = (...\,i_x\,...j_y...k_z...).}

Для этого достаточно переставить местами число и его индекс, и после этого отсортировать по возрастанию индекса. Например

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle d^{-1}=(3_1\;1_2\;2_3)^{-1}=(1_3\;2_1\;3_2)=(2\;3\;1)=f.}

В результате: Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle d\cdot d^{-1} = (3_1\;1_2\;2_3)\;(2\;3\;1)=(1\;2\;3)=e} .

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Любую перестановку можно характеризовать по числу одновременно задействованных в ней объектов. Так, в Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{S_3}} элемент "Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle a=(2\;1\;3)} " переставляет местами первые два объекта, а положение третьего оставляет неизменным. Замкнутые группы переставляемых объектов называются циклами. В перестановке может быть несколько циклов:

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle p=(8_1\;7_2\;1_3\;4_4\;5_5\;2_6\;9_7\;3_8\;6_9)=[8\;3\;1]\cdot[7\;9\;6\;2]}

Чтобы их найти, берём первый элемент, номер которого не совпадает с номером позиции (8) и идём на 8-е место. Там стоит 3. Поэтому идём на 3-е место. Там 1, и так как на первом месте стоит 8-ка с которой мы начали, цикл Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle [8\;3\;1]} замыкается.

Цикл записывают опуская индексы, так как их всегда можно восстановить. Для этого необходимо в качестве индекса ставить номер предыдущего объекта в списке цикла, считая предыдущим для первого элемента — последний:

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle [8\;3\;1]=(8_1\;3_8\;1_3)}
Cicles.png
Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \;\;\;\;[7\;9\;6\;2]=(7_2\;9_7\;6_9\;2_6)}
Cicles2.png

При таком алгоритме записи циклов любые циклические перестановки Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle [8\;3\;1]} , Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle [1\;8\;3]} , Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle [3\;1\;8]} являются одной и той же перестановкой. Смысл цикла состоит в круговой перестановке объектов — 8 идёт на третье место, 3 идёт на первое, а 1 на восьмое. Заметим, что мы различаем обозначения для цикла (квадратные скобки) и для перестановки (круглые).

Если два цикла, например Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle [8\;3\;1]} и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle [7\;9\;6\;2]} не имеют пересекающихся элементов, то произведение содержащих им перестановок можно выполнять в любом порядке:

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{array}{l} (\mathbf{8}_1\;2_2\;\mathbf{1}_3\;4_4\;5_5\;6_6\;7_7\;\mathbf{3}_8\;9_9)\cdot(1\;\mathbf{7}\;3\;4\;5\;\mathbf{2}\;\mathbf{9}\;8\;\mathbf{6})=(8\;7\;1\;4\;5\;2\;9\;3\;6),\\ (1_1\;\mathbf{7}_2\;3_3\;4_4\;5_5\;\mathbf{2}_6\;\mathbf{9}_7\;8_8\;\mathbf{6}_9)\cdot (\mathbf{8}\;2\;\mathbf{1}\;4\;5\;6\;7\;\mathbf{3}\;9)=(8\;7\;1\;4\;5\;2\;9\;3\;6).\\ \end{array}}

Таким образом, выявление циклов позволяет разбить перестановку на композицию более простых перестановок.

Циклы состоящие из двух объектов называются транспозициями. Двойное применение транспозиции даёт единичную перестановку. Аналогично, тройное применение цикла длинной 3 даёт исходный порядок:

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{array}{l} \;[8\;3\;1]^2 \;=\; (8_1\;3_8\;1_3)\,(8_1\;3_8\;1_3) = (3_1\;1_8\;8_3)\\ \;[8\;3\;1]^3 \;=\; (3_1\;1_8\;8_3)\,(8_1\;3_8\;1_3) = (1_1\;8_8\;3_3) = e \end{array}}

Понятно, что если цикл имеет длину Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle n} , то его Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle n} -я степень даст единичную перестановку (мы Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle n} раз по кругу переставим объекты, вернувшись к исходному порядку).

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \bullet} Изоморфизм групп иногда приобретает очень любопытные формы. Пронумеруем элементы Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \{e,a,b,c\}} группы Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{D_2}} цифрами от 1 до 4. Представим каждую строку таблицы умножения в виде списка номеров элементов, поставив первым номер элемента в заголовке строки:

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{array}{rrr|c|cc|} \multicolumn{2}{r}{1} & \multicolumn{1}{r}{e} & \multicolumn{1}{c}{a} & \multicolumn{1}{c}{b} & \multicolumn{1}{c}{c}\\ \cline{4-6} &2 &a & \bullet & c &b\\ \cline{4-6} \mathbf{D_2}:\;&3 &b & c & \bullet &a\\ &4 &c & b & a & \bullet \\ \cline{4-6} \end{array} \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; \begin{array}{l} p_e=(1\;2\;3\;4)\\ p_a=(2\;1\;4\;3)\\ p_b=(3\;4\;1\;2)\\ p_c=(4\;3\;2\;1)\\ \end{array}}

В каждой строке, включая её заголовок, элемент встречается один и только один раз. Поэтому строки таблицы умножения (вместе с единичной Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p_e} ) являются перестановками четырех элементов. Так как в этом случае возможно Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle 24} перестановки, то Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p_e,p_a,p_b,p_c} — лишь некоторое подмножество из группы Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{S_4}} . Однако это подмножество перестановок замечательным образом оказывается группой с той же таблицей, что и у Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{D_2}} ! Например,

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \begin{array}{l} p_a\, p_b = (2_1\;1_2\;4_3\;3_4)\, (3\;4\;1\;2) = (4\;3\;2\;1) = p_c,\\ p_a\, p_a = (2_1\;1_2\;4_3\;3_4)\, (2\;1\;4\;3) = (1\;2\;3\;4) = p_e. \end{array}}

Этот эффект возникает благодаря теореме Кэли:

\it Любая конечная группа G изоморфна некоторой подгруппе группы перестановок Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{S_n}} .

Действительно, рассмотрим группу с Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle n} элементами Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{G}=\{g_1,...,g_{n}\}} . Каждому элементу Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle g_i} поставим в соответствие перестановку исходного порядка (строка с заголовком Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle g_i} ):

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle p_i = (g_i\,g_1,\;g_i\,g_2,\;..., g_i\, g_{n}).}

Единичной (исходной) перестановкой будем считать упорядоченные по индексу элементы Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p_e=(g_1,\;g_2,\;,...,\;g_n)} . Рассмотрим композицию двух перестановок Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p_i} и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p_j} , созданных при помощи Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle g_i} и Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle g_j} :

Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle p_i\, p_j = (g_i\,g_1,\;..., g_i\, g_{n})\, (g_j\,g_1,\;..., g_j\, g_{n})=(g_i\,g_j\,g_1,\;..., g_i\, g_j\, g_{n}) = p_k.}

Действительно, пусть Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle g_j\,g_1=g_s} . При умножении перестановок, мы должны на первое место результата поставить элемент из списка Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p_i} под номером Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle s} . В силу упорядоченности в Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p_i} по второму индексу — это Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle g_i\,g_s} или Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle g_i\,g_j\,g_1} . Аналогично для остальных элементов списка. Следовательно, перестановка Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p_k=p_i\, p_j} получается при помощи Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle g_k=g_i\,g_j} и таблица умножения перестановок Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle p_i} изоморфна группе Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \mathbf{G}} . Невозможно разобрать выражение (MathML с переходом в SVG или PNG (рекомендуется для современных браузеров и инструментов повышения доступности): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «https://wikimedia.org/api/rest_v1/»:): {\displaystyle \textstyle \square}



Примеры и определения << Оглавление (Последняя версия в: Глава 5) >> Еще немного определений

Релятивистский мир - лекции по теории относительности, гравитации и космологии