Cyclic permutation

From Wikipedia for FEVERv2
(Redirected from Transposition (mathematics))
Jump to navigation Jump to search

This article is about group theory. Cyclic permutation_sentence_0

For cycles in homological algebra, see Chain complex § Fundamental terminology. Cyclic permutation_sentence_1

For cycles in graph theory, see Cycle (graph theory). Cyclic permutation_sentence_2

In mathematics, and in particular in group theory, a cyclic permutation (or cycle) is a permutation of the elements of some set X which maps the elements of some subset S of X to each other in a cyclic fashion, while fixing (that is, mapping to themselves) all other elements of X. Cyclic permutation_sentence_3

If S has k elements, the cycle is called a k-cycle. Cyclic permutation_sentence_4

Cycles are often denoted by the list of their elements enclosed with parentheses, in the order to which they are permuted. Cyclic permutation_sentence_5

For example, given X = {1, 2, 3, 4}, the permutation (1, 3, 2, 4) that sends 1 to 3, 3 to 2, 2 to 4 and 4 to 1 (so S = X) is a 4-cycle, and the permutation (1, 3, 2) that sends 1 to 3, 3 to 2, 2 to 1 and 4 to 4 (so S = {1, 2, 3} and 4 is a fixed element) is a 3-cycle. Cyclic permutation_sentence_6

On the other hand, the permutation that sends 1 to 3, 3 to 1, 2 to 4 and 4 to 2 is not a cyclic permutation because it separately permutes the pairs {1, 3} and {2, 4}. Cyclic permutation_sentence_7

The set S is called the orbit of the cycle. Cyclic permutation_sentence_8

Every permutation on finitely many elements can be decomposed into cycles on disjoint orbits. Cyclic permutation_sentence_9

The cyclic parts of a permutation are cycles, thus the second example is composed of a 3-cycle and a 1-cycle (or fixed point) and the third is composed of two 2-cycles, and denoted (1, 3) (2, 4). Cyclic permutation_sentence_10

Definition Cyclic permutation_section_0

A permutation is called a cyclic permutation if and only if it has a single nontrivial cycle (a cycle of length > 1). Cyclic permutation_sentence_11

For example, the permutation, written in two-line (in two ways) and also cycle notations, Cyclic permutation_sentence_12

is a six-cycle; its cycle diagram is shown at right. Cyclic permutation_sentence_13

Some authors restrict the definition to only those permutations which consist of one nontrivial cycle (that is, no fixed points allowed). Cyclic permutation_sentence_14

For example, the permutation Cyclic permutation_sentence_15

is a cyclic permutation under this more restrictive definition, while the preceding example is not. Cyclic permutation_sentence_16

The orbit of a 1-cycle is called a fixed point of the permutation, but as a permutation every 1-cycle is the identity permutation. Cyclic permutation_sentence_17

When cycle notation is used, the 1-cycles are often suppressed when no confusion will result. Cyclic permutation_sentence_18

Basic properties Cyclic permutation_section_1

One of the basic results on symmetric groups is that any permutation can be expressed as the product of disjoint cycles (more precisely: cycles with disjoint orbits); such cycles commute with each other, and the expression of the permutation is unique up to the order of the cycles. Cyclic permutation_sentence_19

The multiset of lengths of the cycles in this expression (the cycle type) is therefore uniquely determined by the permutation, and both the signature and the conjugacy class of the permutation in the symmetric group are determined by it. Cyclic permutation_sentence_20

A k-cycle has signature (−1). Cyclic permutation_sentence_21

Transpositions Cyclic permutation_section_2

"Transposition (mathematics)" redirects here. Cyclic permutation_sentence_22

For matrix transposition, see Transpose. Cyclic permutation_sentence_23

Properties Cyclic permutation_section_3

The decomposition of a permutation into a product of transpositions is obtained for example by writing the permutation as a product of disjoint cycles, and then splitting iteratively each of the cycles of length 3 and longer into a product of a transposition and a cycle of length one less: Cyclic permutation_sentence_24

In fact, the symmetric group is a Coxeter group, meaning that it is generated by elements of order 2 (the adjacent transpositions), and all relations are of a certain form. Cyclic permutation_sentence_25

One of the main results on symmetric groups states that either all of the decompositions of a given permutation into transpositions have an even number of transpositions, or they all have an odd number of transpositions. Cyclic permutation_sentence_26

This permits the parity of a permutation to be a well-defined concept. Cyclic permutation_sentence_27

See also Cyclic permutation_section_4

Cyclic permutation_unordered_list_0

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: permutation.