Compute compositions in a declared order

Try

A permutation is a bijection from a set to itself. In Sₙ the set is the n labels 1 through n, and the operation is composition. Throughout this unit στ means first apply τ, then σ. State this convention before tracing a product; reversing it changes many answers.

Let σ=(1 2) swap the first two labels and τ=(2 3) swap the last two. Predict whether swapping adjacent labels in opposite orders has the same result.

Predict

The cycle (1 2 3) sends one to two, two to three, and three to one. It does not mean swapping one with two and then two with three in an unspecified order. Predict the inverse cycle and the number of repetitions needed to return every label to its starting position.

Experiment

Use this finite S₃ explorer to compare both composition orders. Its notation p∘q means apply q first. Choose a pair, predict one image, then check the full trace and inverse. The exhaustive table is evidence about these six permutations; the general proofs below explain the group structure.

Live experiment: order changes composition

Choose two rearrangements of the symbols 1, 2 and 3. In p∘q, apply q first, then p. Predict where each input goes and whether exchanging the order will change the result. Cycle (1 2 3) means 1→2, 2→3, 3→1; unlisted symbols stay fixed.

Permutation p e (identity)(1 2)(2 3)(1 3)(1 2 3)(1 3 2)Permutation q e (identity)(1 2)(2 3)(1 3)(1 2 3)(1 3 2)Reset experiment

Trace both orders on every input

Input x	q(x)	p(q(x))	p(x)	q(p(x))
1	1	2	2	3
2	3	3	1	1
3	2	1	3	2

p∘q = (1 2 3); q∘p = (1 3 2). These selected maps do not commute: at least one input has different outputs. One such pair disproves commutativity of the whole group.

The inverse of p is (1 2). Its order is 2: composing p with itself that many times first returns to the identity. Every map is bijective; the inverse undoes it on all three inputs.

Inspect the complete composition table for S₃

Rows act after columns. Each entry is row∘column, so the left-hand factor comes from the row. There are six bijections because the images can be selected in 3·2·1 ways.

All 36 compositions; e denotes the identity

Row ∘ column	e (identity)	(1 2)	(2 3)	(1 3)	(1 2 3)	(1 3 2)
e (identity)	e (identity)	(1 2)	(2 3)	(1 3)	(1 2 3)	(1 3 2)
(1 2)	(1 2)	e (identity)	(1 2 3)	(1 3 2)	(2 3)	(1 3)
(2 3)	(2 3)	(1 3 2)	e (identity)	(1 2 3)	(1 3)	(1 2)
(1 3)	(1 3)	(1 2 3)	(1 3 2)	e (identity)	(1 2)	(2 3)
(1 2 3)	(1 2 3)	(1 3)	(1 2)	(2 3)	(1 3 2)	e (identity)
(1 3 2)	(1 3 2)	(2 3)	(1 3)	(1 2)	e (identity)	(1 2 3)

Closure can be checked in this complete finite table. Associativity follows more generally from function composition: ((p∘q)∘r)(x)=p(q(r(x)))=(p∘(q∘r))(x). It does not require commutativity and is not proved by checking just the selected pair.

Try two distinct transpositions, then a cycle and its inverse. Find a commuting pair with neither map equal to e. Give a symbolic associativity argument before using the table. Calculations enumerate this exact six-element group; they do not establish claims about every finite or infinite group. Settings are temporary.

Trace both compositions explicitly rather than manipulating cycle symbols as if they were numbers.

Starting label	τ then σ	σ then τ
1	2	3
2	3	1
3	1	2

Thus στ=(1 2 3), while τσ=(1 3 2). They differ already at the image of one. Both are reversible, and composition is associative, yet the group is nonabelian. The inverse of στ is τ⁻¹σ⁻¹, which here equals τσ because each transposition is its own inverse.

Understand

Every permutation of a finite set decomposes into disjoint cycles. Begin at an unused label, follow its successive images until it returns, then repeat with another unused label. Bijectivity prevents a chain from entering an earlier cycle without already belonging to it. Disjoint cycles commute because they act on separate sets of labels. Overlapping cycles generally do not.

For example, the mapping 1→3,3→5,5→1,2→4,4→2 gives (1 3 5)(2 4). Its inverse reverses both cycles: (1 5 3)(2 4). Its order is six, the least common multiple of three and two. A power is identity exactly when every cycle has completed an integer number of revolutions, proving the least-common-multiple rule.

The symmetric group satisfies the group axioms because compositions of bijections are bijections, function composition is associative, the identity map changes nothing, and inverse bijections exist. The number of permutations is n!: choose the first image in n ways, the second in n−1 ways, and continue without repeats.

Cayley’s theorem says every group is isomorphic to a subgroup of a permutation group. For g∈G, let L_g(x)=gx. Its inverse is L_(g⁻¹), and L_g∘L_h=L_(gh). If L_g=L_h, evaluating at e gives g=h. Therefore g↦L_g is an injective homomorphism. This argument works for infinite groups too, using permutations of the underlying set G rather than a finite Sₙ.

Apply

Create a five-label permutation as a mapping table, convert it to cycles, and reconstruct the table from your cycles. This round trip checks missing labels and accidental overlap. Then multiply it by a transposition in both orders and identify one label witnessing any difference.

In written proofs, distinguish a computation in one symmetric group from Cayley’s general representation theorem. The theorem does not say every group is a full symmetric group, only that it embeds into a permutation group. The image can be much smaller.

Continue

Next assign each permutation a sign. Different transposition factorizations can have different lengths, but their parity agrees. That invariance needs a proof before “even permutation” becomes a well-defined term.