68 CHAPTER 5. SOME IMPORTANT LINEAR ALGEBRA

Now consider the last claim. In computing sgnn (i1, · · · , iθ−1,n, iθ+1, · · · , in) there willbe the product of n−θ negative terms

(iθ+1−n) · · ·(in−n)

and the other terms in the product for computing sgnn (i1, · · · , iθ−1,n, iθ+1, · · · , in) are thosewhich are required to compute sgnn−1 (i1, · · · , iθ−1, iθ+1, · · · , in) multiplied by terms of theform (n− i j) which are nonnegative. It follows that

sgnn (i1, · · · , iθ−1,n, iθ+1, · · · , in) = (−1)n−θ sgnn−1 (i1, · · · , iθ−1, iθ+1, · · · , in)

It is obvious that if there are repeats in the list the function gives 0.

Lemma 5.3.2 Every ordered list of distinct numbers from {1,2, · · · ,n} can be obtainedfrom every other such ordered list by a finite number of switches. Also, sgnn is unique.

Proof: This is obvious if n = 1 or 2. Suppose then that it is true for sets of n− 1elements. Take two ordered lists of numbers, P1,P2. Make one switch in both to place n atthe end. Call the result Pn

1 and Pn2 . Then using induction, there are finitely many switches

in Pn1 so that it will coincide with Pn

2 . Now switch the n in what results to where it was inP2.

To see sgnn is unique, if there exist two functions, f and g both satisfying 5.3.4 and5.3.5, you could start with f (1, · · · ,n) = g(1, · · · ,n) = 1 and applying the same sequenceof switches, eventually arrive at f (i1, · · · , in) = g(i1, · · · , in) . If any numbers are repeated,then 5.3.5 gives both functions are equal to zero for that ordered list.

Definition 5.3.3 When you have an ordered list of distinct numbers from {1,2, · · · ,n} , say

(i1, · · · , in) ,

this ordered list is called a permutation. The symbol for all such permutations is Sn. Thenumber sgnn (i1, · · · , in) is called the sign of the permutation.

A permutation can also be considered as a function from the set

{1,2, · · · ,n} to {1,2, · · · ,n}

as follows. Let f (k) = ik. Permutations are of fundamental importance in certain areasof math. For example, it was by considering permutations that Galois was able to give acriterion for solution of polynomial equations by radicals, but this is a different directionthan what is being attempted here.

In what follows sgn will often be used rather than sgnn because the context supplies theappropriate n.