Determinant via Permutations

In the article Determinant, the determinant is defined recursively — via expansion along a row. Here we give the equivalent direct definition via permutations, which explains where the signs of the terms come from and why a determinant of order $n$ consists of $n!$ terms.

Permutations and Inversions

Consider $n$ distinct numbers $1, 2, \dots, n$ . Any ordering of them $α_{1}, α_{2}, \dots, α_{n}$ is called a permutation. There are $n!$ permutations in total.

Definition. A pair of entries $α_{i}, α_{j}$ of a permutation forms an inversion (a disorder) if the larger entry comes before the smaller one, i.e.

i < j, but α_{i} > α_{j} .

Denote the number of inversions of a permutation $σ$ by $∣ σ ∣$ .

Example. In the permutation $3, 1, 5, 7, 4, 2, 6$ the inversions form the pairs:

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

for a total of $∣ σ ∣ = 2 + 2 + 3 + 1 = 8$ . In the "natural" permutation $1, 2, \dots, n$ there are no inversions: $∣ σ ∣ = 0$ .

Definition. A permutation is called even if the number of inversions $∣ σ ∣$ is even, and odd if it is odd. The sign of a permutation is defined as $(- 1)^{∣ σ ∣}$ .

Transposition

Definition. A transposition is an operation that swaps two entries of a permutation (leaving the rest in place).

Theorem. A single transposition flips the parity of a permutation.

Proof. First consider a transposition of adjacent entries $\dots α β \dots \to \dots β α \dots$ . Every pair except the pair $(α, β)$ itself keeps its mutual order, while for this pair the presence/absence of an inversion flips. So the number of inversions changes by $\pm 1$ , and the parity flips.

A transposition of arbitrary entries with $k$ entries between them reduces to an odd number of adjacent transpositions: shift $α$ rightward to $β$ 's position ( $k + 1$ steps), then shift $β$ leftward to $α$ 's original position ( $k$ steps) — $2 k + 1$ adjacent transpositions in total. Each flips the parity, and an odd number of them flips the overall parity.

A substitution of degree $n$ is a one-to-one map of the set ${1, \dots, n}$ onto itself; it is written in two-row form $σ = (1 α_{1} 2 α_{2} \dots \dots n α_{n})$ , and its parity coincides with the parity of the bottom permutation.

Definition of the Determinant

Definition. The determinant of a square matrix $A = (a_{ij})$ of order $n$ is the algebraic sum of $n!$ terms

det A = σ \sum (- 1)^{∣ σ ∣} a_{1 α_{1}} a_{2 α_{2}} \dots a_{n α_{n}},

where the sum runs over all permutations $σ = (α_{1}, \dots, α_{n})$ of the numbers $1, \dots, n$ . Each term takes exactly one entry from every row and every column; the sign " $+$ " is used for an even permutation, " $-$ " for an odd one.

Consistency with Small Orders

$n = 1$ : one permutation $(1)$ , $∣ σ ∣ = 0$ : $det = a_{11}$ .
$n = 2$ : the permutations $(1, 2)$ and $(2, 1)$ with $∣ σ ∣ = 0, 1$ :

det A = a_{11} a_{22} - a_{12} a_{21} .

$n = 3$ : $3! = 6$ permutations give

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

— this is exactly the rule of triangles. Here the even permutations $(1, 2, 3), (2, 3, 1), (3, 1, 2)$ correspond to a " $+$ " sign, and the odd ones $(2, 1, 3), (1, 3, 2), (3, 2, 1)$ to a " $-$ " sign.

Example: Finding the Sign of a Term

With what sign does the product

a_{14} a_{26} a_{35} a_{41} a_{53} a_{67} a_{72} ?

enter a 7th-order determinant? Here, for rows $1, \dots, 7$ , the columns chosen are $4, 6, 5, 1, 3, 7, 2$ , i.e. the permutation

σ = (14263541536772) .

Counting the inversions of the bottom row gives $∣ σ ∣ = 12$ — an even number, so the term enters with a " $+$ " sign.

Relation to the Recursive Definition

The direct (via permutations) and recursive (via expansion along a row) definitions are equivalent: both the Laplace expansion and all the properties of determinants can be derived from the permutation formula. The direct definition is convenient for proofs (for example, the property about a sign change under a row swap is exactly a transposition, which flips parity), while the recursive one is convenient for computations.