Linear-Algebra-Done-Right · Unit 28 · Video 2 · Interactive Practice

Swaps, Inversions and the Sign of a Permutation

IKey Formulas

Formula	Name	What it says
$\alpha(\dots, v_k, \dots, v_j, \dots) = -\alpha(\dots, v_j, \dots, v_k, \dots)$	Swapping two inputs	An alternating form changes sign
$\operatorname{sign}(j_1, \dots, j_m) = (-1)^N$	Sign of a permutation	$N$ = number of pairs out of order (inversions)
$\operatorname{sign}(\text{after a swap}) = -\operatorname{sign}(\text{before})$	Swaps flip the sign	A swap changes $N$ by an odd number
$\alpha(v_{j_1}, \dots, v_{j_m}) = \operatorname{sign}(j_1, \dots, j_m)\,\alpha(v_1, \dots, v_m)$	Rearranging inputs	Only the sign of the permutation matters

Key Insight: $(2, 3, \dots, m, 1)$ has $m - 1$ inversions, so moving the first input to the last slot multiplies $\alpha$ by $(-1)^{m-1}$ .

IICounting Inversions Swap by Swap

Every swap of two entries changes the number of inversions by an odd number, so the sign flips each time.

Start from

IIIWhere the Odd Change Comes From

The swapped pair changes the count by $\pm 1$ ; each entry between them changes it by $2$ , $-2$ or $0$ .

Permutation Left position 1 Right position 5

IVQuiz Questions

Problem 1 · Count the Inversions

Given: the permutation $(3, 1, 4, 2) \in \operatorname{perm} 4$ . Find its number of inversions $N$ and its sign.

How many inversions?

What is the sign?

✅ Correct! The inversions are

\{1, 3\}

\{2, 3\}

and

\{2, 4\}

, so the sign is

(-1)^3 = -1

❌ Not quite. An inversion need not be two neighbours:

2

comes after

3

even though

1

and

4

sit between them.

❌ Not quite. Check all

\binom{4}{2} = 6

pairs of numbers and ask whether the smaller one appears after the larger.

❌ Check the sign. The sign is

(-1)^N

with

N

the number of inversions.

Show solution

Check the six pairs of numbers in the list $3, 1, 4, 2$ :

$\{1, 2\}$ , $\{1, 4\}$ , $\{3, 4\}$ : the smaller number comes first, natural order.
$\{1, 3\}$ : $1$ comes after $3$ . $\{2, 3\}$ : $2$ comes after $3$ . $\{2, 4\}$ : $2$ comes after $4$ . These are inversions.

So $N = 3$ and $\operatorname{sign}(3, 1, 4, 2) = (-1)^3 = -1$ .

Problem 2 · A Cyclic Rearrangement

Given: $\alpha \in V_{\text{alt}}^{(3)}$ and $v_1, v_2, v_3 \in V$ . Express $\alpha(v_2, v_3, v_1)$ in terms of $\alpha(v_1, v_2, v_3)$ .

✅ Correct!

(2, 3, 1)

has two inversions, so its sign is

+1

❌ Not quite. Moving

v_1

to the end looks like one move, but it takes two swaps:

(2, 3, 1)

has

m - 1 = 2

inversions.

❌ Not quite. No input is repeated and nothing says the list is dependent; rearranging can only change the sign.

❌ Not quite. Rearranging inputs multiplies the value by the sign of the permutation, which is

\pm 1

Show solution

The inputs are $v_{j_1}, v_{j_2}, v_{j_3}$ with $(j_1, j_2, j_3) = (2, 3, 1)$ . Its inversions are $\{1, 2\}$ and $\{1, 3\}$ ( $1$ appears after both), so $N = 2$ and the sign is $+1$ :

\alpha(v_2, v_3, v_1) = \operatorname{sign}(2, 3, 1)\,\alpha(v_1, v_2, v_3) = \alpha(v_1, v_2, v_3).

Check with swaps: swapping slots $1$ and $3$ gives $-\alpha(v_1, v_3, v_2)$ , and swapping slots $2$ and $3$ gives $\alpha(v_1, v_2, v_3)$ .

Problem 3 · After One Swap

Given: a permutation with $7$ inversions. Two of its entries are swapped. Which number could be the new number of inversions?

✅ Correct! A swap changes the count by an odd number, and

4 - 7 = -3

is odd.

❌ Not quite. That is a change of

\pm 2

, an even number. A swap always changes the number of inversions by an odd number.

❌ Not quite. A change of

0

is even; the swapped pair alone contributes

\pm 1

and everything else contributes an even amount.

❌ Not quite. Use the parity of the change.

Show solution

Swapping two entries changes the number of inversions by $\pm 1$ (the swapped pair) plus $2$ , $-2$ or $0$ for each entry between them, plus $0$ for every other pair. The total change is odd.

From $7$ : a new count of $9$ , $5$ or $7$ would be a change of $+2$ , $-2$ or $0$ , all even. Only $4$ (a change of $-3$ ) is possible. In general, a swap turns an odd count into an even one and an even count into an odd one.

Problem 4 · Reversing Six Inputs

Given: $\alpha \in V_{\text{alt}}^{(6)}$ and $v_1, \dots, v_6 \in V$ . Express $\alpha(v_6, v_5, v_4, v_3, v_2, v_1)$ in terms of $\alpha(v_1, \dots, v_6)$ .

✅ Correct! Every one of the

15

pairs is out of order, and

(-1)^{15} = -1

❌ Not quite. Three swaps (

v_1 \leftrightarrow v_6

v_2 \leftrightarrow v_5

v_3 \leftrightarrow v_4

) restore the order, and three is odd.

❌ Not quite. A rearrangement multiplies

\alpha

\pm 1

. Count the inversions of

(6, 5, 4, 3, 2, 1)

Show solution

In $(6, 5, 4, 3, 2, 1)$ every smaller number appears after every larger one, so all $\binom{6}{2} = 15$ pairs are inversions. Hence

\alpha(v_6, v_5, v_4, v_3, v_2, v_1) = (-1)^{15}\,\alpha(v_1, \dots, v_6) = -\alpha(v_1, \dots, v_6).

Check with swaps: exchanging slots $1 \leftrightarrow 6$ , $2 \leftrightarrow 5$ and $3 \leftrightarrow 4$ restores the order in three swaps, an odd number.

Solved: 0 / 4