Page 171 - 35Linear Algebra

8.1 The Determinant Formula 171

We can consider a permutation σ as an invertible function from the set of
numbers [n] := {1, 2, . . . , n} to [n], so can write σ(3) = 5 in the above
example. In general we can write

1 2 3 4 5

,
σ(1) σ(2) σ(3) σ(4) σ(5)
but since the top line of any permutation is always the same, we can omit it
and just write:

σ = σ(1) σ(2) σ(3) σ(4) σ(5)
and so our example becomes simply σ = [4 2 5 1 3].
The mathematics of permutations is extensive; there are a few key prop-
erties of permutations that we’ll need:

• There are n! permutations of n distinct objects, since there are n choices
for the first object, n − 1 choices for the second once the first has been
chosen, and so on.

• Every permutation can be built up by successively swapping pairs of

objects. For example, to build up the permutation 3 1 2 from the

trivial permutation 1 2 3 , you can first swap 2 and 3, and then
swap 1 and 3.

• For any given permutation σ, there is some number of swaps it takes to
build up the permutation. (It’s simplest to use the minimum number of
swaps, but you don’t have to: it turns out that any way of building up
the permutation from swaps will have have the same parity of swaps,
either even or odd.) If this number happens to be even, then σ is
called an even permutation; if this number is odd, then σ is an odd
permutation. In fact, n! is even for all n ≥ 2, and exactly half of the
permutations are even and the other half are odd. It’s worth noting
that the trivial permutation (which sends i → i for every i) is an even
permutation, since it uses zero swaps.

Definition The sign function is a function sgn that sends permutations
to the set {−1, 1} with rule of correspondence defined by

1 if σ is even
sgn(σ) =
−1 if σ is odd.

171