Math 2.0

statement theorem

Decomposition of a permutation into transpositions

Statement

Let n≥2n \geq 2. Each permutation in SnS_n is a product of transpositions.

Remarks

A kk-cycle is a product of k−1k - 1 transpositions, for example (a1 a2 … ak)=(a1 ak)(a1 ak−1)⋯(a1 a2)(a_1\ a_2\ \dots\ a_k) = (a_1\ a_k)(a_1\ a_{k-1}) \cdots (a_1\ a_2). With the disjoint cycle decomposition, this gives the result, and the identity is (1 2)(1 2)(1\ 2)(1\ 2). The decomposition is not unique, but the parity of the number of factors is unique.

Explanations

L1 human

You can sort any arrangement of objects by swapping two objects at a time. So each permutation is a chain of swaps. Different chains can give the same permutation, but they are all of even length or all of odd length.

What this node needs for W1
  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a node is. They do not measure its truth.

What this needs

To read this node, read these 7 nodes in this order. The foundations come first, and the list ends with this node.

Cycle notation, concept, no evidence levelCycle notationconceptGroup, concept, no evidence levelGroupconceptSymmetric group, definition, no evidence levelSymmetric groupdefinitionDisjoint cycles commute, statement, no evidence levelDisjoint cycles commu…statementTransposition, definition, no evidence levelTranspositiondefinitionDecomposition of a permutation into disjoint cycles, statement, no evidence levelDecomposition of a pe…statementDecomposition of a permutation into transpositions, statement, no evidence levelDecomposition of a pe…statement
Each node uses the nodes above it. The colour of the bar on a box shows the evidence level, and the box also gives it as text. The list below has the same nodes.
  • no evidence level
  1. Cycle notation concept
  2. Group concept
  3. Symmetric group definition
  4. Disjoint cycles commute statement
  5. Transposition definition
  6. Decomposition of a permutation into disjoint cycles statement
  7. Decomposition of a permutation into transpositions statement

What depends on this

12 nodes use this node, directly or through other nodes.

Sources

  1. Web https://en.wikipedia.org/wiki/Symmetric_group, Transpositions, sign, and the alternating group
  2. Web https://en.wikipedia.org/wiki/Cyclic_permutation, Properties

What links here

Used by