Как найти порядок элемента группы перестановок

Порядок перестановки

Запись
перестановки 
в виде произведения независимых циклов

позволяет легко
найти порядок перестановки

.

Теорема
2. Порядок
перестановки
(порядок циклической подгруппы)равен
наименьшему
общему кратному (НОК)
длин независимых циклов, входящих в
разложение .

Доказательство. Представим
перестановку
в виде произведения независимых циклов

. (7)

Тогда

Так как
циклы
независимы (они действуют на различных
множествах),
и если q – порядок циклической подгруппы,

,

то

,

где
.

Следовательно,
q – общее кратное порядков циклов _k,
которые совпадают с их длинами
.

Если q – наименьшее
положительное число, для которого

,то

и

. (8)

Основная
теорема арифметики. Каждое
положительное целое число
n не
равное единице может быть записано в
виде произведения простых чисел

.
(9)

Эта запись
единственна с точностью до порядка
следования сомножителей.

Заменив
произведения совпадающих простых чисел
в (9) их степенями, получим

где

Множество простых
чисел

.

Пример.
Два
любых целых числа m и n можно записать в
виде произведений одних и тех же простых
чисел

,

тогда

,

где

Пример. Определить
порядок перестановки
вида

.

Решение. Представим
перестановку 
в виде произведения независимых циклов,
т.е.

.

Длины
независимых цикловравны

Следовательно,
порядок рассматриваемой перестановки
равен 28.

Разложение
перестановки в произведение транспозиций.

Определение. Цикл
длиной два называется транспозицией.
Любая транспозиция имеет вид
и оставляет на местах все символы за
исключением.

Теорема. Каждая
перестановка
может быть представлена в виде произведения
транспозиции.

Доказательство. Теорема
будет доказана, если мы сможем представить
в виде произведений транспозиций каждый
из циклов _k,
входящих в разложения перестановки:
.

Рассмотрим
произвольный цикл
,
напримери произведем его разложение в произведение
транспозиций.

Алгоритм
разложения цикла
в произведение транспозиций представлен
на рисунке 2.

Цикл
транспозиции

Рис
2.
– Разложение цикла
в произведение транспозиций.

После
завершения всех операций на месте
каждого элемента цикла
оказался следующий за ним элемент, а
первый элемент перешел на последнее
место. Таким образом, циклоказался разложенным в произведение
транспозиций:

Естественно, это
разложение не единственно. Например

.

Важно
другое – и в первом и во втором его
разложении имеется равное количество
транспозиций – четыре. Если
,
то количество транспозиций равно.
Раскладывая аналогичным образом каждый
циклперестановкив произведение транспозиции, мы получим
разложение всей перестановкив произведение транспозиций.

Замечание. Количество
транспозиций в цикле
может быть и больше четырех! Возьмем
произвольную транспозицию из разложения
этого цикла, например,.
Тогда произведениесовпадает с тождественной перестановкой
и циклможно представить в виде

или

,

или

.

Легко
заметить, что во всех этих случаях число
транспозиций четно и равно 4, 6, 8. Ясно,
что способ, «удлиняющий» разложение,
не изменяет четности исходного разложения.

Теорема. Пусть

– перестановка из
,
а

. (9)

какое-либо
разложение 
в произведении транспозиций.

Тогда число

(10)

называется
четностью (сигнатурой или знаком)
перестановки 
и полностью определяется ,
т.е. не зависит от способа разложения
перестановки 
в произведение транспозиций. Кроме
того, если
,
то

. (11)

Определение. Перестановка
называется четной, если,
и нечетной, если.

Из определения
четности перестановки вытекает, что
все транспозиции – нечетные перестановки.

Действительно,
если
– транспозиция, то,
тогда

Следствие 1. Все
четные перестановки степени n образуют
подгруппу
порядка(она называется знакопеременной группой
степени n).

Следствие 2. Пусть
перестановка
разложена в произведение независимых
циклов

длин

,

где
,,
…,,
…,– длины независимых циклов.

Тогда

. (12)

Доказательство. Действительно,
по предыдущей теореме имеем

.

Кроме
того,
поскольку каждыйцикл записывается в виде произведениятранспозиций, то

.

Соседние файлы в папке ЛЕКЦИИ АиГ

• #
• #
• #
• #
• #
• #
• #
• #
• #

Для нахождения порядка перестановки достаточно разложить её в произведение независимых циклов (циклических перестановок). Тогда порядок перестановки будет равен НОК длин всех циклов.

Лемма:

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

Доказательство:

Для того, чтобы при перестановка при возведении в степень перешла сама в себя, необходимо и достаточно, чтобы любой ее элемент перешел сам в себя, что равносильно тому, что цикл, в который он входит, пройден целое число раз (если пройден не целое, то элемент не перейдет сам в себя)

Теорема (О порядке перестановки, НОК):

Порядок перестановки равен НОК длин всех её независимых циклов.

Доказательство:

Поскольку при умножении на себя каждый цикл сдвигается на 1, то для того, чтобы перестановка перешла сама в себя, необходимо и достаточно, в силу леммы, чтобы степень перестановки делилась на все длины циклов. Минимальным таким числом является НОК длин циклов.

Порядок элемента в теории групп — наименьшее положительное целое , такое что -кратное групповое умножение данного элемента на себя даёт нейтральный элемент:

.

Иными словами,  — количество различных элементов циклической подгруппы, порождённой данным элементом. Если такого не существует (или, эквивалентно, число элементов циклической подгруппы бесконечно), то говорят, что имеет бесконечный порядок. Обозначается как или .

Изучение порядков элементов группы может дать сведения о её структуре. Несколько глубоких вопросов о связи порядка элементов и порядка группы содержатся в различных проблемах Бёрнсайда, некоторые из них остаются открытыми.

Основные свойства[править | править код]

Порядок элемента равен единице тогда и только тогда, когда элемент является нейтральным.

Если всякий не нейтральный элемент в совпадает со своим обратным (то есть ), то и является абелевой, поскольку . Обратное утверждение в общем случае неверно: например, (аддитивная) циклическая группа целых чисел по модулю 6 — абелева, но число 2 имеет порядок 3:

.

Для любого целого тождество выполнено тогда и только тогда, когда делит .

Все степени элемента бесконечного порядка имеют также бесконечный порядок. Если имеет конечный порядок, то порядок равен порядку , делённому на наибольший общий делитель чисел и . Порядок обратного элемента совпадает с порядком самого элемента ().

Связь с порядком группы[править | править код]

Порядок любого элемента группы делит порядок группы. Например, в симметрической группе , состоящей из шести элементов, нейтральный элемент имеет (по определению) порядок 1, три элемента, являющихся корнями из  — порядок 2, а порядок 3 имеют два оставшихся элемента, являющихся корнями элементов порядка 2: то есть, все порядки элементов являются делителями порядка группы.

Частично обратное утверждение верно для конечных групп (теоретико-групповая теорема Коши): если простое число делит порядок группы , то существует элемент , для которого . Утверждение не выполняется для составных порядков, так, четверная группа Клейна не содержит элемента порядка четыре.

Порядок произведения[править | править код]

В любой группе .

Не существует общей формулы, связывающей порядок произведения с порядками сомножителей и . Возможен случай, когда и , и имеют конечные порядки, в то время как порядок произведения бесконечен, также возможно, что и , и имеют бесконечный порядок, в то время как конечен. Пример первого случая — в симметрической группе над целыми числами перестановки, задаваемые формулами , тогда . Пример второго случая — перестановки в той же группе , произведение которых является нейтральным элементом (перестановка , оставляющая элементы на своих местах). Если то можно утверждать, что делит наименьшее общее кратное чисел и . Следствием этого факта является, что в конечной абелевой группе порядок любого элемента делит максимальный порядок элементов группы.

Подсчёт по порядку элементов[править | править код]

Для данной конечной группы порядка , число элементов с порядком ( — делитель ) кратно , где  — функция Эйлера, дающая число положительных чисел, не превосходящих и взаимно простых с ним. Например, в случае , и имеется в точности два элемента порядка 3; при этом данное утверждение не даёт никакой полезной информации относительно элементов порядка 2, поскольку , и очень ограниченную информацию о составных числах, таких как , поскольку , и в группе имеется нуль элементов порядка 6.

Связь с гомоморфизмами[править | править код]

Гомоморфизмы групп имеют свойство понижать порядок элементов. Если является гомоморфизмом, и  — элемент конечного порядка, то делит . Если инъективно, то . Этот факт может быть использован для доказательства отсутствия (инъективного) гомоморфизма между двумя какими-либо заданными группами. (Например, не существует нетривиального гомоморфизма , поскольку любое число, за исключением нуля, в имеет порядок 5, а 5 не делит ни один из порядков 1, 2 и 3 элементов .) Другим следствием является утверждение, что сопряжённые элементы имеют одинаковый порядок.

Литература[править | править код]

• Курош А.Г. Теория групп. — Москва: Наука, 1967. — ISBN 5-8114-0616-9.
• Мельников О. В., Ремесленников В. Н., Романьков В. А. . Глава II. Группы // Общая алгебра / Под общ. ред. Л. А. Скорнякова. — М.: Наука, 1990. — Т. 1. — С. 66—290. — 592 с. — (Справочная математическая библиотека). — 30 000 экз. — ISBN 5-02-014426-6.

1

In mathematics, a permutation group is a group G whose elements are permutations of a given set M and whose group operation is the composition of permutations in G (which are thought of as bijective functions from the set M to itself). The group of all permutations of a set M is the symmetric group of M, often written as Sym(M).^[1] The term permutation group thus means a subgroup of the symmetric group. If M = {1, 2, …, n} then Sym(M) is usually denoted by S_n, and may be called the symmetric group on n letters.

By Cayley’s theorem, every group is isomorphic to some permutation group.

The way in which the elements of a permutation group permute the elements of the set is called its group action. Group actions have applications in the study of symmetries, combinatorics and many other branches of mathematics, physics and chemistry.

Basic properties and terminology[edit]

Being a subgroup of a symmetric group, all that is necessary for a set of permutations to satisfy the group axioms and be a permutation group is that it contain the identity permutation, the inverse permutation of each permutation it contains, and be closed under composition of its permutations.^[2] A general property of finite groups implies that a finite nonempty subset of a symmetric group is again a group if and only if it is closed under the group operation.^[3]

The degree of a group of permutations of a finite set is the number of elements in the set. The order of a group (of any type) is the number of elements (cardinality) in the group. By Lagrange’s theorem, the order of any finite permutation group of degree n must divide n! since n-factorial is the order of the symmetric group S_n.

Notation[edit]

Since permutations are bijections of a set, they can be represented by Cauchy’s two-line notation.^[4] This notation lists each of the elements of M in the first row, and for each element, its image under the permutation below it in the second row. If is a permutation of the set then,

For instance, a particular permutation of the set {1, 2, 3, 4, 5} can be written as

this means that σ satisfies σ(1) = 2, σ(2) = 5, σ(3) = 4, σ(4) = 3, and σ(5) = 1. The elements of M need not appear in any special order in the first row, so the same permutation could also be written as

Permutations are also often written in cycle notation (cyclic form)^[5] so that given the set M = {1, 2, 3, 4}, a permutation g of M with g(1) = 2, g(2) = 4, g(4) = 1 and g(3) = 3 will be written as (1, 2, 4)(3), or more commonly, (1, 2, 4) since 3 is left unchanged; if the objects are denoted by single letters or digits, commas and spaces can also be dispensed with, and we have a notation such as (124). The permutation written above in 2-line notation would be written in cycle notation as

Composition of permutations–the group product[edit]

The product of two permutations is defined as their composition as functions, so is the function that maps any element x of the set to . Note that the rightmost permutation is applied to the argument first, because of the way function composition is written.^[6][7] Some authors prefer the leftmost factor acting first, but to that end permutations must be written to the right of their argument, often as a superscript, so the permutation acting on the element results in the image . With this convention, the product is given by .^[8]
[9]
[10] However, this gives a different rule for multiplying permutations. This convention is commonly used in the permutation group literature, but this article uses the convention where the rightmost permutation is applied first.

Since the composition of two bijections always gives another bijection, the product of two permutations is again a permutation. In two-line notation, the product of two permutations is obtained by rearranging the columns of the second (leftmost) permutation so that its first row is identical with the second row of the first (rightmost) permutation. The product can then be written as the first row of the first permutation over the second row of the modified second permutation. For example, given the permutations,

the product QP is:

The composition of permutations, when they are written in cycle notation, is obtained by juxtaposing the two permutations (with the second one written on the left) and then simplifying to a disjoint cycle form if desired. Thus, the above product would be given by:

Since function composition is associative, so is the product operation on permutations: . Therefore, products of two or more permutations are usually written without adding parentheses to express grouping; they are also usually written without a dot or other sign to indicate multiplication (the dots of the previous example were added for emphasis, so would simply be written as ).

Neutral element and inverses[edit]

The identity permutation, which maps every element of the set to itself, is the neutral element for this product. In two-line notation, the identity is

In cycle notation, e = (1)(2)(3)…(n) which by convention is also denoted by just (1) or even ().^[11]

Since bijections have inverses, so do permutations, and the inverse σ⁻¹ of σ is again a permutation. Explicitly, whenever σ(x)=y one also has σ⁻¹(y)=x. In two-line notation the inverse can be obtained by interchanging the two lines (and sorting the columns if one wishes the first line to be in a given order). For instance

To obtain the inverse of a single cycle, we reverse the order of its elements. Thus,

To obtain the inverse of a product of cycles, we first reverse the order of the cycles, and then we take the inverse of each as above. Thus,

Having an associative product, an identity element, and inverses for all its elements, makes the set of all permutations of M into a group, Sym(M); a permutation group.

Examples[edit]

Consider the following set G₁ of permutations of the set M = {1, 2, 3, 4}:

• e = (1)(2)(3)(4) = (1)
  • This is the identity, the trivial permutation which fixes each element.
• a = (1 2)(3)(4) = (1 2)
  • This permutation interchanges 1 and 2, and fixes 3 and 4.
• b = (1)(2)(3 4) = (3 4)
  • Like the previous one, but exchanging 3 and 4, and fixing the others.
• ab = (1 2)(3 4)
  • This permutation, which is the composition of the previous two, exchanges simultaneously 1 with 2, and 3 with 4.

G₁ forms a group, since aa = bb = e, ba = ab, and abab = e. This permutation group is, as an abstract group, the Klein group V₄.

As another example consider the group of symmetries of a square. Let the vertices of a square be labeled 1, 2, 3 and 4 (counterclockwise around the square starting with 1 in the top left corner). The symmetries are determined by the images of the vertices, that can, in turn, be described by permutations. The rotation by 90° (counterclockwise) about the center of the square is described by the permutation (1234). The 180° and 270° rotations are given by (13)(24) and (1432), respectively. The reflection about the horizontal line through the center is given by (12)(34) and the corresponding vertical line reflection is (14)(23). The reflection about the 1,3−diagonal line is (24) and reflection about the 2,4−diagonal is (13). The only remaining symmetry is the identity (1)(2)(3)(4). This permutation group is known, as an abstract group, as the dihedral group of order 8.

Group actions[edit]

In the above example of the symmetry group of a square, the permutations “describe” the movement of the vertices of the square induced by the group of symmetries. It is common to say that these group elements are “acting” on the set of vertices of the square. This idea can be made precise by formally defining a group action.^[12]

Let G be a group and M a nonempty set. An action of G on M is a function f: G × M → M such that

• f(1, x) = x, for all x in M (1 is the identity (neutral) element of the group G), and
• f(g, f(h, x)) = f(gh, x), for all g,h in G and all x in M.

This pair of conditions can also be expressed as saying that the action induces a group homomorphism from G into Sym(M).^[12] Any such homomorphism is called a (permutation) representation of G on M.

For any permutation group, the action that sends (g, x) → g(x) is called the natural action of G on M. This is the action that is assumed unless otherwise indicated.^[12] In the example of the symmetry group of the square, the group’s action on the set of vertices is the natural action. However, this group also induces an action on the set of four triangles in the square, which are: t₁ = 234, t₂ = 134, t₃ = 124 and t₄ = 123. It also acts on the two diagonals: d₁ = 13 and d₂ = 24.

Group element	Action on triangles	Action on diagonals
(1)	(1)	(1)
(1234)	(t1 t2 t3 t4)	(d1 d2)
(13)(24)	(t1 t3)(t2 t4)	(1)
(1432)	(t1 t4 t3 t2)	(d1 d2)
(12)(34)	(t1 t2)(t3 t4)	(d1 d2)
(14)(23)	(t1 t4)(t2 t3)	(d1 d2)
(13)	(t1 t3)	(1)
(24)	(t2 t4)	(1)

Transitive actions[edit]

The action of a group G on a set M is said to be transitive if, for every two elements s, t of M, there is some group element g such that g(s) = t. Equivalently, the set M forms a single orbit under the action of G.^[13] Of the examples above, the group {e, (1 2), (3 4), (1 2)(3 4)} of permutations of {1, 2, 3, 4} is not transitive (no group element takes 1 to 3) but the group of symmetries of a square is transitive on the vertices.

Primitive actions[edit]

A permutation group G acting transitively on a non-empty finite set M is imprimitive if there is some nontrivial set partition of M that is preserved by the action of G, where “nontrivial” means that the partition isn’t the partition into singleton sets nor the partition with only one part. Otherwise, if G is transitive but does not preserve any nontrivial partition of M, the group G is primitive.

For example, the group of symmetries of a square is imprimitive on the vertices: if they are numbered 1, 2, 3, 4 in cyclic order, then the partition {{1, 3}, {2, 4}} into opposite pairs is preserved by every group element. On the other hand, the full symmetric group on a set M is always primitive.

Cayley’s theorem[edit]

Any group G can act on itself (the elements of the group being thought of as the set M) in many ways. In particular, there is a regular action given by (left) multiplication in the group. That is, f(g, x) = gx for all g and x in G. For each fixed g, the function f_g(x) = gx is a bijection on G and therefore a permutation of the set of elements of G. Each element of G can be thought of as a permutation in this way and so G is isomorphic to a permutation group; this is the content of Cayley’s theorem.

For example, consider the group G₁ acting on the set {1, 2, 3, 4} given above. Let the elements of this group be denoted by e, a, b and c = ab = ba. The action of G₁ on itself described in Cayley’s theorem gives the following permutation representation:

f_e ↦ (e)(a)(b)(c)

f_a ↦ (ea)(bc)

f_b ↦ (eb)(ac)

f_c ↦ (ec)(ab).

Isomorphisms of permutation groups[edit]

If G and H are two permutation groups on sets X and Y with actions f₁ and f₂ respectively, then we say that G and H are permutation isomorphic (or isomorphic as permutation groups) if there exists a bijective map λ : X → Y and a group isomorphism ψ : G → H such that

λ(f₁(g, x)) = f₂(ψ(g), λ(x)) for all g in G and x in X.^[14]

If X = Y this is equivalent to G and H being conjugate as subgroups of Sym(X).^[15] The special case where G = H and ψ is the identity map gives rise to the concept of equivalent actions of a group.^[16]

In the example of the symmetries of a square given above, the natural action on the set {1,2,3,4} is equivalent to the action on the triangles. The bijection λ between the sets is given by i ↦ t_i. The natural action of group G₁ above and its action on itself (via left multiplication) are not equivalent as the natural action has fixed points and the second action does not.

Oligomorphic groups[edit]

When a group G acts on a set S, the action may be extended naturally to the Cartesian product Sⁿ of S, consisting of n-tuples of elements of S: the action of an element g on the n-tuple (s₁, …, s_n) is given by

g(s₁, …, s_n) = (g(s₁), …, g(s_n)).

The group G is said to be oligomorphic if the action on Sⁿ has only finitely many orbits for every positive integer n.^[17][18] (This is automatic if S is finite, so the term is typically of interest when S is infinite.)

The interest in oligomorphic groups is partly based on their application to model theory, for example when considering automorphisms in countably categorical theories.^[19]

History[edit]

The study of groups originally grew out of an understanding of permutation groups.^[20] Permutations had themselves been intensively studied by Lagrange in 1770 in his work on the algebraic solutions of polynomial equations. This subject flourished and by the mid 19th century a well-developed theory of permutation groups existed, codified by Camille Jordan in his book Traité des Substitutions et des Équations Algébriques of 1870. Jordan’s book was, in turn, based on the papers that were left by Évariste Galois in 1832.

When Cayley introduced the concept of an abstract group, it was not immediately clear whether or not this was a larger collection of objects than the known permutation groups (which had a definition different from the modern one). Cayley went on to prove that the two concepts were equivalent in Cayley’s theorem.^[21]

Another classical text containing several chapters on permutation groups is Burnside’s Theory of Groups of Finite Order of 1911.^[22] The first half of the twentieth century was a fallow period in the study of group theory in general, but interest in permutation groups was revived in the 1950s by H. Wielandt whose German lecture notes were reprinted as Finite Permutation Groups in 1964.^[23]

See also[edit]

• 2-transitive group
• Rank 3 permutation group
• Mathieu group

Notes[edit]

References[edit]

• Artin, Michael (1991), Algebra, Prentice-Hall, ISBN 0-13-004763-5
• Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, ISBN 0-521-45761-0
• Dixon, John D.; Mortimer, Brian (1996), Permutation Groups, Graduate Texts in Mathematics 163), Springer-Verlag, ISBN 0-387-94599-7
• Rotman, Joseph J. (2006), A First Course in Abstract Algebra with Applications (3rd ed.), Pearson Prentice-Hall, ISBN 0-13-186267-7

Further reading[edit]

• Akos Seress. Permutation group algorithms. Cambridge Tracts in Mathematics, 152. Cambridge University Press, Cambridge, 2003.
• Meenaxi Bhattacharjee, Dugald Macpherson, Rögnvaldur G. Möller and Peter M. Neumann. Notes on Infinite Permutation Groups. Number 1698 in Lecture Notes in Mathematics. Springer-Verlag, 1998.
• Peter J. Cameron. Permutation Groups. LMS Student Text 45. Cambridge University Press, Cambridge, 1999.
• Peter J. Cameron. Oligomorphic Permutation Groups. Cambridge University Press, Cambridge, 1990.

External links[edit]

• “Permutation group”, Encyclopedia of Mathematics, EMS Press, 2001 [1994]
• Alexander Hulpke. GAP Data Library “Transitive Permutation Groups”.