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