Permutations

What you will be able to do

Given a permutation in one-line or cycle notation, the learner can convert between the notations, count inversions, decompose into disjoint cycles and transpositions, determine the sign by either route, compose permutations, and use the sign in the Leibniz formula and in reading a permutation matrix's determinant.

Orientation

The minus sign in the determinant

$det (\begin{matrix} a & b \\ c & d \end{matrix}) = a d - b c$ . The subtraction is not decoration: one of the two products is signed negative, and which one is decided by a rearrangement of the column indices. The determinants unit gave the rule that swapping two rows negates the determinant, and observed that a permutation matrix has determinant $+ 1$ or $- 1$ according to whether its permutation is even or odd, without saying what a permutation is, or what makes one even.

This unit supplies both. A permutation is a rearrangement of ${1, \dots, n}$ ; its sign records whether reaching it takes an even or odd number of swaps. That this is well defined at all requires proof. A rearrangement can be undone by swaps in many different ways, and the count varies, but its parity never does.

With the sign in hand, the determinant has a closed definition rather than a recursive recipe: a sum over all $n!$ rearrangements, each term signed. Every property the determinants unit stated, the row-swap rule, the value of a triangular matrix, the vanishing on dependent columns, reads off that formula.

Definition

Two routes to the same sign

The canonical definition gives inversions and cycles as two descriptions of one quantity. What follows is why each is stated the way it is, and when to reach for which.

Why inversions are counted over pairs, not positions. An inversion is a pair out of order, so the count is over $(\binom{n}{2})$ pairs and the maximum is $(\binom{n}{2})$ , attained by the full reversal. Counting displaced elements instead would not work: in $(2 3 1)$ every element has moved, yet the permutation is even. Displacement measures how far things travelled; inversions measure how many relative orders were reversed, and only the second has the parity property.

Why adjacent swaps settle it. Swapping two neighbours changes exactly one pair's relative order, so it changes $inv$ by exactly $\pm 1$ . Since the identity has zero inversions, sorting any $σ$ by adjacent swaps takes $inv (σ)$ of them, and the parity of any other route must match. That is the whole argument for well-definedness, and it is why $(- 1)^{inv}$ deserves to be called the sign rather than one measurement among several.

Why a $k$ -cycle is $k - 1$ transpositions. Writing $(a_{1} a_{2} \dots a_{k}) = (a_{1} a_{k}) (a_{1} a_{k - 1}) \dots (a_{1} a_{2})$ uses $k - 1$ factors, and no shorter product can do it: each transposition joins at most two orbits, and a $k$ -cycle must be assembled from $k$ singletons. So the parity of a cycle is the parity of $k - 1$ , opposite to the parity of $k$ itself.

cycle length $k$	transpositions $k - 1$	permutation is
2	1	odd
3	2	even
4	3	odd
5	4	even

A permutation's sign is the product over its disjoint cycles. Fixed points are 1-cycles contributing zero transpositions, so they never affect the sign, which is why omitting them from the notation is safe.

Why sign is multiplicative. Composing appends one transposition list to another, so the counts add and the parities add modulo 2. Hence $sgn (σ τ) = sgn (σ) sgn (τ)$ , and since $σ σ^{- 1}$ is the identity with sign $+ 1$ , $sgn (σ^{- 1}) = sgn (σ)$ .

Which route to take. Given one-line notation, count inversions, it is a scan. Given cycle notation, read the lengths, it is arithmetic on small numbers. Converting notation just to use the other route is wasted work, and computing both is the standard way to check a sign under exam conditions.

Representation

All six permutations of three things

$S_{3}$ is small enough to write out completely, which makes every claim in this unit checkable by inspection.

one-line	cycles	inversions	sign	$det P$
$(1 2 3)$	identity	0	$+ 1$	$+ 1$
$(1 3 2)$	$(2 3)$	1	$- 1$	$- 1$
$(2 1 3)$	$(1 2)$	1	$- 1$	$- 1$
$(2 3 1)$	$(1 2 3)$	2	$+ 1$	$+ 1$
$(3 1 2)$	$(1 3 2)$	2	$+ 1$	$+ 1$
$(3 2 1)$	$(1 3)$	3	$- 1$	$- 1$

Three even, three odd. The even half always has exactly $n! / 2$ members for $n \geq 2$ .

Take $(3 2 1)$ . By inversions: the pairs $(3, 2)$ , $(3, 1)$ and $(2, 1)$ are all out of order, so $inv = 3$ and the sign is $- 1$ . By cycles: $1 \mapsto 3 \mapsto 1$ is a 2-cycle and 2 is fixed, so one transposition, sign $- 1$ . The routes agree, as they must.

Note the two 3-cycles, $(1 2 3)$ and $(1 3 2)$ . Each has length 3, hence 2 transpositions, hence sign $+ 1$ . An odd length giving an even permutation. The two 2-cycles have even length and are odd. The lengths and parities run opposite throughout the table.

Where the signs go. The Leibniz formula for a $3 \times 3$ matrix has one term per row of this table:

det A = a_{11} a_{22} a_{33} - a_{11} a_{23} a_{32} - a_{12} a_{21} a_{33} + a_{12} a_{23} a_{31} + a_{13} a_{21} a_{32} - a_{13} a_{22} a_{31},

three added and three subtracted, matching the three even and three odd permutations exactly. The familiar rule-of-Sarrus diagonals are these six terms rearranged, which is also why Sarrus has no analogue for $n \geq 4$ : the count of terms is $n!$ , not $2 n$ .

Figure

The three-cycle (1 2 3) as a closed path

1 → 2 → 3 → 1, a single orbit of length three

The permutation $(1 2 3)$ drawn as what it does: $1 \mapsto 2$ , $2 \mapsto 3$ , $3 \mapsto 1$ .

Cycle notation is a description of this journey, which is why it is read as a loop rather than a list of positions. Following the arrows from any starting point returns there after three steps, and that length is the order of the permutation.

It also settles the sign without counting inversions. A cycle of length $k$ is a product of $k - 1$ transpositions, so this one is two swaps and therefore even, matching the $+ 1$ the table records for $(2 3 1)$ . The table above remains the complete reference; this shows what one of its rows means as an action.

Example

Six permutations and where their signs come from

Each of these is worked by both routes, so the agreement is visible rather than asserted.

The identity, $(1 2 3 4)$ in $S_{4}$ . No pair is out of order, so $inv = 0$ and the sign is $+ 1$ . As cycles it is four fixed points, contributing no transpositions. It is the one permutation whose matrix is $I$ , with $det I = 1$ agreeing.

A transposition, $(2 1 3 4)$ . One pair is inverted, the leading $2$ against the $1$ , so $inv = 1$ and the sign is $- 1$ . As cycles, $(1 2)$ with 3 and 4 fixed: a single swap. This is the smallest odd permutation, and its matrix is the elementary row-exchange matrix whose determinant the determinants unit gave as $- 1$ .

A 3-cycle, $(2 3 1)$ in $S_{3}$ . The inverted pairs are $(2, 1)$ and $(3, 1)$ , so $inv = 2$ and the sign is $+ 1$ . As cycles it is $(1 2 3)$ , one cycle of length 3, hence $3 - 1 = 2$ transpositions. Odd length, even permutation. The relationship that trips people, seen here in the smallest case.

A 4-cycle, $(2 3 4 1)$ in $S_{4}$ . The inverted pairs are $(2, 1)$ , $(3, 1)$ and $(4, 1)$ , three, so the sign is $- 1$ . As cycles it is $(1 2 3 4)$ , one cycle of length 4, hence 3 transpositions. Even length, odd permutation, the mirror of the previous case.

Two disjoint swaps, $(2 1 4 3)$ in $S_{4}$ . Inverted pairs: $(2, 1)$ and $(4, 3)$ , so $inv = 2$ and the sign is $+ 1$ . As cycles, $(1 2) (3 4)$ : two transpositions, each contributing $- 1$ , and $(- 1)^{2} = + 1$ . Signs multiply across disjoint cycles.

The reversal, $(4 3 2 1)$ in $S_{4}$ . Every one of the $(\binom{4}{2}) = 6$ pairs is inverted, so the sign is $(- 1)^{6} = + 1$ . As cycles it is $(1 4) (2 3)$ , again two transpositions. Reversing four elements is even, although reversing three is odd; the parity depends on $n$ through $(\binom{n}{2})$ and is not a property of "reversing".

Two of them, the 3-cycle and the double swap, have the same sign by different structures. Two others, the 3-cycle and the 4-cycle, differ in sign by one unit of length. And the count of inversions is never the count of transpositions, $(4 3 2 1)$ has six inversions and two transpositions, only their parity is shared, which is precisely what the sign records.

Worked example

Signs by both routes, a composition, and a determinant

1. $σ = (1 3 5 2 4)$ in $S_{5}$ .

Inversion route. Compare every pair $i < j$ and count those with $σ (i) > σ (j)$ . Taking each entry against those to its right:

entry	larger than, to its right	count
1	—	0
3	2	1
5	2, 4	2
2	—	0
4	—	0

So $inv (σ) = 3$ and $sgn (σ) = (- 1)^{3} = - 1$ .

Cycle route. Trace: $1 \mapsto 1$ , a fixed point. $2 \mapsto 3 \mapsto 5 \mapsto 4 \mapsto 2$ , closing a 4-cycle. So $σ = (2 3 5 4)$ with 1 fixed. One cycle of length 4 is $4 - 1 = 3$ transpositions, giving sign $(- 1)^{3} = - 1$ .

Both routes give $- 1$ . The permutation is odd, despite its only nontrivial cycle having even length, which is exactly the relationship, not a coincidence.

2. $τ = (4 3 2 1)$ in $S_{4}$ , the full reversal.

Inversions. Every one of the $(\binom{4}{2}) = 6$ pairs is out of order, so $inv (τ) = 6$ and the sign is $(- 1)^{6} = + 1$ .

Cycles. $1 \mapsto 4 \mapsto 1$ and $2 \mapsto 3 \mapsto 2$ : two transpositions, $τ = (1 4) (2 3)$ , sign $(- 1) (- 1) = + 1$ .

The reversal of four elements is even. Reversals alternate: $inv = (\binom{n}{2})$ , which is even for $n \equiv 0, 1 (\mod 4)$ and odd otherwise.

3. Composing in $S_{4}$ . Let $p = (2 3 4 1)$ and $q = (3 1 4 2)$ , and compute $p \circ q$ , meaning apply $q$ first.

$(p \circ q) (i) = p (q (i))$ , so:

(p \circ q) (1) = p (3) = 4, (p \circ q) (2) = p (1) = 2, (p \circ q) (3) = p (4) = 1, (p \circ q) (4) = p (2) = 3,

giving $p \circ q = (4 2 1 3)$ .

Signs. $p$ is the 4-cycle $(1 2 3 4)$ , so three transpositions, $sgn (p) = - 1$ . For $q$ : $1 \mapsto 3 \mapsto 4 \mapsto 2 \mapsto 1$ , also a 4-cycle, $sgn (q) = - 1$ . Multiplicativity predicts $sgn (p \circ q) = (- 1) (- 1) = + 1$ .

Check by inversions on $(4 2 1 3)$ : the pairs out of order are $(4, 2)$ , $(4, 1)$ , $(4, 3)$ and $(2, 1)$ , four of them, so the sign is $(- 1)^{4} = + 1$ .

Note $q \circ p = (1 4 2 3)$ , a different permutation, with inversions $(4, 2)$ and $(4, 3)$ , so sign $+ 1$ as well. Composition does not commute; its sign does.

4. A $3 \times 3$ determinant by the Leibniz formula. Take

A = (\begin{matrix} 2 & - 1 & 3 \\ 0 & 4 & 1 \\ 5 & 2 & - 2 \end{matrix}) .

Sum over the six permutations, each term taking one entry per row and column:

$σ$	sign	term	value
$(1 2 3)$	$+$	$a_{11} a_{22} a_{33}$	$2 \cdot 4 \cdot (- 2) = - 16$
$(1 3 2)$	$-$	$a_{11} a_{23} a_{32}$	$- (2 \cdot 1 \cdot 2) = - 4$
$(2 1 3)$	$-$	$a_{12} a_{21} a_{33}$	$- ((- 1) \cdot 0 \cdot (- 2)) = 0$
$(2 3 1)$	$+$	$a_{12} a_{23} a_{31}$	$(- 1) \cdot 1 \cdot 5 = - 5$
$(3 1 2)$	$+$	$a_{13} a_{21} a_{32}$	$3 \cdot 0 \cdot 2 = 0$
$(3 2 1)$	$-$	$a_{13} a_{22} a_{31}$	$- (3 \cdot 4 \cdot 5) = - 60$

Total: $- 16 - 4 + 0 - 5 + 0 - 60 = - 85$ .

Check by cofactor expansion along the first column: $2 \cdot det (\begin{matrix} 4 & 1 \\ 2 & - 2 \end{matrix}) - 0 + 5 \cdot det (\begin{matrix} - 1 & 3 \\ 4 & 1 \end{matrix}) = 2 (- 8 - 2) + 5 (- 1 - 12) = - 20 - 65 = - 85$ .

The two definitions agree, as the determinants unit's theorem promised, and the Leibniz route shows where each minus sign came from.

Principle

Why parity is well defined

The sign is defined by $(- 1)^{inv (σ)}$ , which is unambiguous because $inv$ is a count of pairs. The substantive claim is the other one: that every way of writing $σ$ as a product of transpositions uses a number of factors with the same parity. Without it, "even permutation" would name nothing.

The argument. Let $t$ be any transposition, swapping the values at positions $i < j$ . Claim: composing with $t$ changes $inv$ by an odd number.

First take $t$ adjacent, $j = i + 1$ . Exactly one pair changes relative order, the pair at those two positions, so $inv$ changes by exactly $\pm 1$ , which is odd.

A general transposition of positions $i$ and $j$ with $d = j - i$ is a product of $2 d - 1$ adjacent swaps: move the entry at $i$ rightwards to $j$ in $d$ steps, then move the displaced entry leftwards back to $i$ in $d - 1$ steps. So $inv$ changes by a sum of $2 d - 1$ odd numbers, and $2 d - 1$ is odd, so the total change is odd.

Now suppose $σ = t_{1} t_{2} \dots t_{m}$ . Starting from the identity with $inv = 0$ and applying $m$ transpositions, each flipping the parity of $inv$ , the final parity is the parity of $m$ . But the final permutation is $σ$ , whose inversion count is fixed. So every decomposition of $σ$ has $m \equiv inv (σ) (\mod 2)$ .

What this rules out. It is impossible to write the identity as a product of an odd number of transpositions, or a single transposition as a product of an even number. The obstruction is not that nobody has managed it; it is that the inversion count forbids it.

Consequences used later.

$sgn$ is a homomorphism onto ${+ 1, - 1}$ : $sgn (σ τ) = sgn (σ) sgn (τ)$ .
Its kernel, the even permutations, is the alternating group $A_{n}$ , of size $n! / 2$ for $n \geq 2$ , exactly half, because multiplying by one fixed transposition is a bijection between the even and odd halves.
$sgn (σ^{- 1}) = sgn (σ)$ , since their product is the identity.
The determinant is well defined by the Leibniz formula, since each term's sign depends only on $σ$ and not on how $σ$ was reached.

That last point is the reason this argument belongs in a linear algebra course rather than only an algebra one. Without parity invariance the determinant's $n!$ terms would have no consistent signs, and $det$ would not be a function at all.

Check your understanding

Cycle length against parity

The single most common error in this material is reading a cycle's length as its parity. Settle it now, before the determinant work depends on it.

The relationship. A cycle of length $k$ decomposes into $k - 1$ transpositions. Parity therefore tracks $k - 1$ , not $k$ :

cycle	length $k$	transpositions	parity
$(1 2)$	2	1	odd
$(1 2 3)$	3	2	even
$(1 2 3 4)$	4	3	odd
$(1 2 3 4 5)$	5	4	even

Even length, odd permutation. Odd length, even permutation. The words invert.

Verify one by hand. $(1 2 3 4)$ in one-line notation is $(2 3 4 1)$ , since $1 \mapsto 2$ , $2 \mapsto 3$ , $3 \mapsto 4$ , $4 \mapsto 1$ . Its inversions are the pairs $(2, 1)$ , $(3, 1)$ and $(4, 1)$ , three of them, so the sign is $(- 1)^{3} = - 1$ , odd. The cycle route agrees: $4 - 1 = 3$ transpositions.

Several cycles. Multiply the signs. For $(2 1 4 3) = (1 2) (3 4)$ : two 2-cycles, each odd, product $(- 1) (- 1) = + 1$ , so the permutation is even. Its inversion count is 2, confirming it.

A quick self-test. Before continuing, decide the sign of each, then check against the answers below.

$(1 2 3 4 5 6)$ in $S_{6}$
$(1 3) (2 5 4)$ in $S_{5}$
The identity in $S_{7}$

Answers. (1) length 6, five transpositions, odd. (2) a 2-cycle (odd) times a 3-cycle (even), product odd. (3) no transpositions at all, even, fixed points contribute nothing, which is why they are omitted from the notation without affecting the sign.

Extra support (1)

Contrast

Same length, opposite sign; same sign, different structure

Two permutations of the same size, opposite signs.

	$σ = (2 3 1)$	$τ = (2 1 3)$
cycles	$(1 2 3)$	$(1 2)$ , with 3 fixed
transpositions	2	1
inversions	2	1
sign	$+ 1$	$- 1$
moves how many elements	3	2

$σ$ displaces more elements than $τ$ and is nonetheless the even one. Amount of disturbance is not what the sign measures, only the parity of the swap count is.

Same sign, different cycle structure. In $S_{4}$ , both $(1 2 3)$ and $(1 2) (3 4)$ are even: the first is one 3-cycle, two transpositions; the second is two 2-cycles, also two transpositions. Their one-line forms are $(2 3 1 4)$ with inversions 2, and $(2 1 4 3)$ with inversions 2. Equal signs, and no other structural resemblance, sign is a single bit, and it does not determine the permutation.

The reversal, which alternates. The full reversal of $n$ elements has $(\binom{n}{2})$ inversions:

$n$	$(\binom{n}{2})$	sign
2	1	$- 1$
3	3	$- 1$
4	6	$+ 1$
5	10	$+ 1$
6	15	$- 1$

Reversing four elements is even; reversing three is odd. Nothing about "reversal" fixes a sign. It depends on $n$ through a binomial coefficient, and the pattern has period 4.

Where the contrast bites. Given a matrix whose rows have been reversed, whether $det$ changes sign depends on the size. For a $4 \times 4$ the reversal is even, so the determinant is unchanged; for a $3 \times 3$ it is odd and the determinant negates. Reasoning from "a reversal is a lot of swapping, so it must flip the sign" gives the wrong answer half the time.

Optional enrichment (1)

Application

Permutation matrices, $P A = L U$ , and the triple product

Permutation matrices. For $σ \in S_{n}$ , let $P_{σ}$ have a 1 in position $(i, σ (i))$ and zeros elsewhere. Then $P_{σ}$ permutes coordinates, and

det P_{σ} = sgn (σ) .

The Leibniz sum has exactly one nonzero term, the one matching $σ$ , and its value is a product of $n$ ones carrying the sign. This is the claim the determinants unit asserted, now derived.

The geometry agrees: a permutation matrix maps the unit cube to itself, so the volume scale factor is 1, and the sign records whether orientation is preserved. An even permutation is a rotation of the cube; an odd one includes a reflection.

Since $P_{σ}$ is orthogonal with $P_{σ}^{- 1} = P_{σ}^{T}$ , and $det$ of an orthogonal matrix is $\pm 1$ , the two possible determinants correspond exactly to the two cosets of $A_{n}$ in $S_{n}$ .

$P A = L U$ . Elimination with partial pivoting exchanges rows, and the exchanges are recorded in a permutation matrix $P$ . Taking determinants of $P A = L U$ :

det P \cdot det A = det L \cdot det U .

With $L$ unit lower triangular, $det L = 1$ , and $det U$ the product of the pivots. So

det A = sgn (σ) \prod_{i} u_{i i},

where $σ$ is the permutation of the row exchanges. This is how determinants are actually computed: $O (n^{3})$ elimination plus one sign, rather than the $n!$ terms of the definition. For $n = 20$ that is the difference between a few thousand operations and $2.4 \times 10^{18}$ of them.

A practical consequence: counting the row swaps during elimination is enough. An odd number of swaps means the sign is $- 1$ , and forgetting to track them is the standard way to get a determinant right up to sign.

The triple product. The vector geometry unit stated that $u \cdot (v \times w)$ is unchanged under cyclic permutation of the three vectors and changes sign under a swap. Both follow immediately: the triple product is a $3 \times 3$ determinant whose rows are the three vectors, a cyclic permutation of three elements is a 3-cycle with sign $+ 1$ , and a swap is a transposition with sign $- 1$ .

Beyond determinants. The sign homomorphism is why $A_{n}$ exists as a subgroup of index 2, which underlies the solvability arguments behind the impossibility of a general quintic formula. And in physics the antisymmetry of fermionic wavefunctions under particle exchange is the statement that the wavefunction transforms by $sgn (σ)$ . The Slater determinant is a Leibniz sum whose signs are exactly these.

Next step

Practice Permutations

Practice this

Permutations

The minus sign in the determinant

Two routes to the same sign

All six permutations of three things

The three-cycle (1 2 3) as a closed path

Six permutations and where their signs come from

Signs by both routes, a composition, and a determinant

Why parity is well defined

Cycle length against parity

Same length, opposite sign; same sign, different structure

Permutation matrices, $P A = L U$ , and the triple product

Settings

Focus timer

Today

Last seven days

Where the time went

Recent sessions

Settings

Notifications

Your history

Permutations

The minus sign in the determinant

Two routes to the same sign

All six permutations of three things

The three-cycle (1 2 3) as a closed path

Six permutations and where their signs come from

Signs by both routes, a composition, and a determinant

Why parity is well defined

Cycle length against parity

Same length, opposite sign; same sign, different structure

Permutation matrices, P A = L U , and the triple product

Permutation matrices, $P A = L U$ , and the triple product