Groups and permutations

Integers under addition, invertible matrices under multiplication and symmetries under composition look different, yet share a common pattern. A group isolates the rules that make reversible operations behave coherently. Studying the rules lets one proof apply to all of these settings.

1 The group axioms

A group is a set $G$ with a binary operation $G\times G\to G$ that is associative, has an identity $e$, and gives every $g\in G$ an inverse $g^{-1}$ satisfying $gg^{-1}=g^{-1}g=e$. A group is abelian if $gh=hg$ for all elements. Closure is built into calling the operation a function to $G$.

The integers form an abelian group under addition. Nonzero real numbers form an abelian group under multiplication. The invertible $n\times n$ real matrices form the generally nonabelian group $GL_n(\mathbb R)$. Nonzero integers do not form a group under multiplication: 2 lacks an integer inverse.

Cancellation and uniqueness. A group has one identity and one inverse for each element; $ab=ac$ implies $b=c$.

Proof. If $e,e'$ are identities, $e=ee'=e'$. If $u,v$ are both inverses of $g$, then $u=u(gv)=(ug)v=v$. Multiplying $ab=ac$ on the left by $a^{-1}$ and using associativity gives cancellation. $\square$

Associativity is not permission to change order. In any group, $(ab)^{-1}=b^{-1}a^{-1}$, since multiplication in either order gives the identity. The formula $a^{-1}b^{-1}$ is generally wrong.

2 Permutations and cycle notation

A permutation of a set is a bijection from it to itself. The permutations of $\{1,\ldots,n\}$ form $S_n$ under composition; in this chapter $\sigma\tau$ means apply $\tau$ first, then $\sigma$.

The cycle $(a_1\ a_2\ \cdots\ a_k)$ sends each displayed element to the next, the last to the first, and fixes all others. Every permutation decomposes into disjoint cycles: start at an element and follow its repeated images until it returns; bijectivity prevents entry into an earlier orbit without already being in it. Repeat with unused elements. Disjoint cycles commute because they affect disjoint sets. The decomposition is unique up to cycle order and cyclic rotation inside each cycle.

Example. In $S_4$, let $\sigma=(1\ 2\ 3)$ and $\tau=(1\ 4)$. Tracing images gives $\sigma\tau=(1\ 4\ 2\ 3)$, while $\tau\sigma=(1\ 2\ 3\ 4)$. They are unequal, showing noncommutativity.

The order of $g$ is the smallest positive $k$ with $g^k=e$, if one exists, and infinite otherwise. A disjoint-cycle permutation has order the least common multiple of its cycle lengths: a power fixes every element exactly when its integer exponent is divisible by every cycle length. Thus $(1\ 2\ 3)(4\ 5)$ has order 6.

A transposition exchanges two elements. Every cycle is a product of transpositions:

$$(a_1\ a_2\ \cdots\ a_k)=(a_1\ a_k)\cdots(a_1\ a_2).$$

Permutation parity can be defined by the determinant of its permutation matrix, whose columns are the images of standard basis vectors. Each transposition has determinant $-1$, and determinants multiply. Therefore any two transposition factorizations have the same parity. The sign map satisfies $\operatorname{sgn}(\sigma\tau)=\operatorname{sgn}(\sigma)\operatorname{sgn}(\tau)$.

3 Symmetry as a concrete model

Let $r$ rotate a square by $90$ degrees and $s$ reflect it across a fixed axis through opposite vertices. The eight symmetries are $e,r,r^2,r^3,s,rs,r^2s,r^3s$. Their relations are

$$r^4=e,\qquad s^2=e,\qquad sr=r^{-1}s.$$

The last relation can be checked on the four vertices: reflecting reverses the direction of rotation. It moves every occurrence of $s$ to the right and reduces any product to one of the eight displayed forms. Different texts write $D_4$ or $D_8$ for this same eight-element group; always state the convention rather than infer the size from a symbol.

Why permutation parity is independent of a chosen factorization

The determinant description above uses the multiplicativity theorem for determinants. Here is an independent proof of the parity assertion, using only real polynomial arithmetic. Put

$$V(t_1,\ldots,t_n)=\prod_{1\le i<j\le n}(t_j-t_i).$$

Swapping two variables changes the sign of this product. The factor connecting those two variables changes sign; factors connecting either of them to any third variable exchange in pairs, with two sign changes when the third index lies between them. Their paired product is unchanged. All other factors stay fixed. Thus every transposition sends $V$ to $-V$.

If the same permutation is expressed as $k$ transpositions and as $l$ transpositions, applying both expressions to $V$ gives $(-1)^kV=(-1)^lV$. Evaluate at distinct real numbers, for example $t_i=i$, so that $V\ne0$. Cancellation gives $(-1)^k=(-1)^l$. This proves parity is well defined. Concatenating transposition factorizations proves the sign multiplication law. It does not require assuming parity before proving it, or checking only a few permutations.

For completeness, permutations really do form a group: composition of two bijections is a bijection, composition is associative, the identity map is present, and the inverse bijection is again a permutation. For the square, a symmetry is determined by the image of one vertex and the image of an adjacent vertex: there are four choices for the first and two adjacent choices for the second; the remaining vertices are forced by distances. The eight displayed rotations/reflections realize all eight choices, so the enumeration is exhaustive.

4 Graded practice

E1 Foundation. Decide whether positive real numbers under multiplication and nonnegative integers under addition are groups.

E2 Cycles. Compute $(1\ 2)(2\ 3)$ and $(2\ 3)(1\ 2)$, using rightmost-first composition. Find their orders.

E3 Symmetry. In the square group above, simplify $(r^2s)(rs)$ and prove every reflection $r^ks$ has order 2.

E4 Proof. If every element of a group satisfies $g^2=e$, prove the group is abelian.

5 Full solutions

S1. Positive reals form a group: multiplication is associative, identity is 1 and inverse $1/x$ remains positive. Nonnegative integers under addition lack additive inverses for positive elements, so do not form a group.

S2. Rightmost first gives $(1\ 2\ 3)$ and $(1\ 3\ 2)$ respectively. Each has order 3. Their difference shows that transpositions need not commute.

S3. $r^2srs=r^2r^{-1}s^2=r$. From $sr^k=r^{-k}s$, $(r^ks)^2=r^kr^{-k}s^2=e$. A reflection is not the identity, so its order is exactly 2.

S4. Every element is its own inverse. Thus $ab=(ab)^{-1}=b^{-1}a^{-1}=ba$. The inverse-of-a-product rule is the essential step; one cannot simply cancel nonadjacent factors without justification.

Summary

Groups describe reversible associative operations. Permutations supply a universal concrete language for finite symmetries. Cycle structure gives orders, and careful composition conventions prevent many errors. Noncommutative reasoning preserves order at every step.