Page 237 - Linear Algebra Done Right

228
To put this into a form that does not depend on the particular per-
mutation (p 1 ,...,p n ), let a j,k denote the entry in row j, column k,of A;
thus Chapter 10. Trace and Determinant

0 if j = p k ;
a j,k =
c k if j = p k .
Then

10.22 det A = sign(m 1 ,...,m n ) a m 1 ,1 ...a m n ,n ,
(m 1 ,...,m n )∈perm n
because each summand is 0 except the one corresponding to the per-
mutation (p 1 ,...,p n ).
Consider now an arbitrary matrix A with entry a j,k in row j, col-
umn k. Using the paragraph above as motivation, we guess that det A
should be defined by 10.22. This will turn out to be correct. We can
now dispense with the motivation and begin the more formal approach.
First we will need to define the sign of an arbitrary permutation.
Some texts use the The sign of a permutation (m 1 ,...,m n ) is defined to be 1 if the
unnecessarily fancy number of pairs of integers (j, k) with 1 ≤ j< k ≤ n such that j ap-
term signum, which pears after k in the list (m 1 ,...,m n ) is even and −1 if the number of
means the same such pairs is odd. In other words, the sign of a permutation equals 1 if
as sign. the natural order has been changed an even number of times and equals
−1 if the natural order has been changed an odd number of times. For
example, in the permutation (2, 3,...,n, 1) the only pairs (j, k) with
j< k that appear with changed order are (1, 2), (1, 3),...,(1,n); be-
cause we have n − 1 such pairs, the sign of this permutation equals
(−1) n−1 (note that the same quantity appeared in 10.19).
The permutation (2, 1, 3, 4), which is obtained from the permutation
(1, 2, 3, 4) by interchanging the first two entries, has sign −1. The next
lemma shows that interchanging any two entries of any permutation
changes the sign of the permutation.

10.23 Lemma: Interchanging two entries in a permutation multiplies
the sign of the permutation by −1.

Proof: Suppose we have two permutations, where the second per-
mutation is obtained from the first by interchanging two entries. If the
two entries that we interchanged were in their natural order in the first
permutation, then they no longer are in the second permutation, and