You can navigate through this E-Book using the menu to the left. For E-Books that have a Chapter/Section organization each option in the menu to the left indicates a chapter and will open a menu showing the sections in that chapter. Alternatively, you can navigate to the next/previous section or chapter by clicking the links in the boxes at the very top and bottom of the material.
Also, depending upon the E-Book, it will be possible to download the complete E-Book, the chapter containing the current section and/or the current section. You can do this be clicking on the E-Book, Chapter, and/or the Section link provided below.
For those pages with mathematics on them you can, in most cases, enlarge the mathematics portion by clicking on the equation. Click the enlarged version to hide it.
We’ll start off the chapter by defining the determinant
function. This is not such an easy thing
however as it involves some ideas and notation that you probably haven’t run
across to this point. So, before we
actually define the determinant function we need to get some preliminaries out
of the way.
First, a permutation
of the set of integers 
is an arrangement of all the integers in the
list without omission or repetitions. A
permutation of will typically be denoted by where is the first number in the permutation, is the second number in the permutation, etc.
|
Example 1 List
all permutations of .
Solution
This one isn’t too bad because there are only two integers
in the list. We need to come up with
all the possible ways to arrange these two numbers. Here they are.
|
|
Example 2 List
all the permutations of
Solution
This one is a little harder to do, but still isn’t too
bad. We need all the arrangements of
these three numbers in which no number is repeated or omitted. Here they are.
|
From this point on it can be somewhat difficult to find
permutations for lists of numbers with more than 3 numbers in it. One way to make sure that you get all of them
is to write down a permutation tree. Here is the permutation tree for .
At the top we list all the numbers in the list and from this
top number we’ll branch out with each of the remaining numbers in the
list. At the second level we’ll again
branch out with each of the numbers from the list not yet written down along
that branch. Then each branch will
represent a permutation of the given list of numbers
As you can see the number of permutations for a list will
quick grow as we add numbers to the list.
In fact it can be shown that there are n! permutations of the list ,
or any list containing n distinct
numbers, but we’re going to be working with so that’s the one we’ll reference. So, the list will have permutations, the list will have permutations, etc.
Next we need to discuss inversions in a permutation. An inversion
will occur in the permutation whenever a larger number precedes a smaller
number. Note as well we don’t mean that
the smaller number is immediately to the right of the larger number, but
anywhere to the right of the larger number.
|
Example 3 Determine
the number of inversions in each of the following permutations.
(a) [Solution]
(b) [Solution]
(c) [Solution]
(d) [Solution]
(e) [Solution]
Solution
(a)
Okay, to count the number of inversions we will start at
the left most number and count the number of numbers to the right that are
smaller. We then move to the second
number and do the same thing. We
continue in this fashion until we get to the end. The total number of inversions are then the
sum of all these.
We’ll do this first one in detail and then do the
remaining ones much quicker. We’ll
mark the number we’re looking at in red and to the side give the number of
inversions for that particular number.
In the first case there are two numbers to the right of 3
that are smaller than 3 so there are two inversions there. In the second case we’re looking at the
smallest number in the list and so there won’t be any inversions there. Then with 4 there is one number to the
right that is smaller than 4 and so we pick up another inversion. There is no reason to look at the last
number in the permutation since there are no numbers to the right of it and
so won’t introduce any inversions.
The permutation has a total of 3 inversions.
[Return to Problems]
(b)
We’ll do this one much quicker. There are inversions in . Note that each number in the sum above
represents the number of inversion for the number in that position in the
permutation.
[Return to Problems]
(c)
There are inversions in .
[Return to Problems]
(d)
There are no inversions in .
[Return to Problems]
(e)
There are in .
[Return to Problems]
|
Next, a permutation is called even if the number of inversions is even and odd if the number of inversions is odd.
|
Example 4 Classify
as even or odd all the permutations of the following lists.
(a)
(b)
Solution
(a) Here’s a
table giving all the permutations, the number of inversions in each and the
classification.
|
Permutation
|
# Inversions
|
Classification
|
|
|
0
|
even
|
|
|
1
|
odd
|
(b) We’ll do the
same thing here
|
Permutation
|
# Inversions
|
Classification
|
|
|
0
|
even
|
|
|
1
|
odd
|
|
|
1
|
odd
|
|
|
2
|
even
|
|
|
2
|
even
|
|
|
3
|
odd
|
We’ll need these results later in the section.
|