Вычисление порядка перестановки в группе перестановок — различия между версиями
Martoon (обсуждение | вклад) м |
|||
| (не показаны 3 промежуточные версии 2 участников) | |||
| Строка 1: | Строка 1: | ||
| − | + | Для нахождения порядка перестановки достаточно разложить её в произведение независимых циклов (циклических перестановок). Тогда порядок перестановки будет равен [[Наименьшее общее кратное|НОК]] длин всех циклов. | |
| − | |||
| − | Для нахождения порядка перестановки достаточно разложить её в произведение независимых циклов (циклических перестановок). Тогда порядок перестановки будет равен НОК длин всех циклов. | ||
{{Лемма | {{Лемма | ||
| − | |id= | + | |id=lm1 |
|statement= | |statement= | ||
| − | Для того, чтобы | + | Для того, чтобы перестановка при возведении в степень перешла сама в себя, необходимо и достаточно, чтобы каждый цикл был пройден целое число раз. |
|proof= | |proof= | ||
Для того, чтобы при перестановка при возведении в степень перешла сама в себя, необходимо и достаточно, чтобы любой ее элемент перешел сам в себя, что равносильно тому, что цикл, в который он входит, пройден целое число раз (если пройден не целое, то элемент не перейдет сам в себя) | Для того, чтобы при перестановка при возведении в степень перешла сама в себя, необходимо и достаточно, чтобы любой ее элемент перешел сам в себя, что равносильно тому, что цикл, в который он входит, пройден целое число раз (если пройден не целое, то элемент не перейдет сам в себя) | ||
| Строка 11: | Строка 9: | ||
{{Теорема | {{Теорема | ||
|id=th4 | |id=th4 | ||
| + | |about=О порядке перестановки, НОК | ||
|statement= | |statement= | ||
Порядок перестановки равен НОК длин всех её независимых циклов. | Порядок перестановки равен НОК длин всех её независимых циклов. | ||
Версия 23:21, 11 января 2013
Для нахождения порядка перестановки достаточно разложить её в произведение независимых циклов (циклических перестановок). Тогда порядок перестановки будет равен НОК длин всех циклов.
| Лемма: |
Для того, чтобы перестановка при возведении в степень перешла сама в себя, необходимо и достаточно, чтобы каждый цикл был пройден целое число раз. |
| Доказательство: |
| Для того, чтобы при перестановка при возведении в степень перешла сама в себя, необходимо и достаточно, чтобы любой ее элемент перешел сам в себя, что равносильно тому, что цикл, в который он входит, пройден целое число раз (если пройден не целое, то элемент не перейдет сам в себя) |
| Теорема (О порядке перестановки, НОК): |
Порядок перестановки равен НОК длин всех её независимых циклов. |
| Доказательство: |
| Поскольку при умножении на себя каждый цикл сдвигается на 1, то для того, чтобы перестановка перешла сама в себя, необходимо и достаточно, в силу леммы, чтобы степень перестановки делилась на все длины циклов. Минимальным таким числом является НОК длин циклов. |
