Linear Algebra/Print version/Part 2
This is the print version of Linear Algebra You won't see this message or any elements not part of the book's content when you print or preview this page. |
Chapter IV - Determinants
In the first chapter of this book we considered linear systems and we picked out the special case of systems with the same number of equations as unknowns, those of the form where is a square matrix. We noted a distinction between two classes of 's. While such systems may have a unique solution or no solutions or infinitely many solutions, if a particular is associated with a unique solution in any system, such as the homogeneous system , then is associated with a unique solution for every . We call such a matrix of coefficients "nonsingular". The other kind of , where every linear system for which it is the matrix of coefficients has either no solution or infinitely many solutions, we call "singular".
Through the second and third chapters the value of this distinction has been a theme. For instance, we now know that nonsingularity of an matrix is equivalent to each of these:
- a system has a solution, and that solution is unique;
- Gauss-Jordan reduction of yields an identity matrix;
- the rows of form a linearly independent set;
- the columns of form a basis for ;
- any map that represents is an isomorphism;
- an inverse matrix exists.
So when we look at a particular square matrix, the question of whether it is nonsingular is one of the first things that we ask. This chapter develops a formula to determine this. (Since we will restrict the discussion to square matrices, in this chapter we will usually simply say "matrix" in place of "square matrix".)
More precisely, we will develop infinitely many formulas, one for matrices, one for matrices, etc. Of course, these formulas are related — that is, we will develop a family of formulas, a scheme that describes the formula for each size.
Section I - Definition
For matrices, determining nonsingularity is trivial.
is nonsingular iff
The formula came out in the course of developing the inverse.
is nonsingular iff
The formula can be produced similarly (see Problem 9).
is nonsingular iff
With these cases in mind, we posit a family of formulas, , , etc. For each the formula gives rise to a determinant function such that an matrix is nonsingular if and only if . (We usually omit the subscript because if is then "" could only mean "".)
1 - Exploration
This subsection is optional. It briefly describes how an investigator might come to a good general definition, which is given in the next subsection.
The three cases above don't show an evident pattern to use for the general formula. We may spot that the term has one letter, that the terms and have two letters, and that the terms , etc., have three letters. We may also observe that in those terms there is a letter from each row and column of the matrix, e.g., the letters in the term
come one from each row and one from each column. But these observations perhaps seem more puzzling than enlightening. For instance, we might wonder why some of the terms are added while others are subtracted.
A good problem solving strategy is to see what properties a solution must have and then search for something with those properties. So we shall start by asking what properties we require of the formulas.
At this point, our primary way to decide whether a matrix is singular is to do Gaussian reduction and then check whether the diagonal of resulting echelon form matrix has any zeroes (that is, to check whether the product down the diagonal is zero). So, we may expect that the proof that a formula determines singularity will involve applying Gauss' method to the matrix, to show that in the end the product down the diagonal is zero if and only if the determinant formula gives zero. This suggests our initial plan: we will look for a family of functions with the property of being unaffected by row operations and with the property that a determinant of an echelon form matrix is the product of its diagonal entries. Under this plan, a proof that the functions determine singularity would go, "Where is the Gaussian reduction, the determinant of equals the determinant of (because the determinant is unchanged by row operations), which is the product down the diagonal, which is zero if and only if the matrix is singular". In the rest of this subsection we will test this plan on the and determinants that we know. We will end up modifying the "unaffected by row operations" part, but not by much.
The first step in checking the plan is to test whether the and formulas are unaffected by the row operation of pivoting: if
then is ? This check of the determinant after the operation
shows that it is indeed unchanged, and the other pivot gives the same result. The pivot leaves the determinant unchanged
as do the other pivot operations.
So there seems to be promise in the plan. Of course, perhaps the determinant formula is affected by pivoting. We are exploring a possibility here and we do not yet have all the facts. Nonetheless, so far, so good.
The next step is to compare with for the operation
of swapping two rows. The row swap
does not yield . This swap inside of a matrix
also does not give the same determinant as before the swap — again there is a sign change. Trying a different swap
also gives a change of sign.
Thus, row swaps appear to change the sign of a determinant. This modifies our plan, but does not wreck it. We intend to decide nonsingularity by considering only whether the determinant is zero, not by considering its sign. Therefore, instead of expecting determinants to be entirely unaffected by row operations, will look for them to change sign on a swap.
To finish, we compare to for the operation
of multiplying a row by a scalar . One of the cases is
and the other case has the same result. Here is one case
and the other two are similar. These lead us to suspect that multiplying a row by multiplies the determinant by . This fits with our modified plan because we are asking only that the zeroness of the determinant be unchanged and we are not focusing on the determinant's sign or magnitude.
In summary, to develop the scheme for the formulas to compute determinants, we look for determinant functions that remain unchanged under the pivoting operation, that change sign on a row swap, and that rescale on the rescaling of a row. In the next two subsections we will find that for each such a function exists and is unique.
For the next subsection, note that, as above, scalars come out of each row without affecting other rows. For instance, in this equality
the isn't factored out of all three rows, only out of the top row. The determinant acts on each row of independently of the other rows. When we want to use this property of determinants, we shall write the determinant as a function of the rows: "", instead of as "" or "". The definition of the determinant that starts the next subsection is written in this way.
Exercises
- This exercise is recommended for all readers.
- Problem 1
Evaluate the determinant of each.
- Problem 2
Evaluate the determinant of each.
- This exercise is recommended for all readers.
- Problem 3
Verify that the determinant of an upper-triangular matrix is the product down the diagonal.
Do lower-triangular matrices work the same way?
- This exercise is recommended for all readers.
- Problem 4
Use the determinant to decide if each is singular or nonsingular.
- Problem 5
Singular or nonsingular? Use the determinant to decide.
- This exercise is recommended for all readers.
- Problem 6
Each pair of matrices differ by one row operation. Use this operation to compare with .
- Problem 7
Show this.
- This exercise is recommended for all readers.
- Problem 8
Which real numbers make this matrix singular?
- Problem 9
Do the Gaussian reduction to check the formula for matrices stated in the preamble to this section.
is nonsingular iff
- Problem 10
Show that the equation of a line in thru and is expressed by this determinant.
- This exercise is recommended for all readers.
- Problem 11
Many people know this mnemonic for the determinant of a matrix: first repeat the first two columns and then sum the products on the forward diagonals and subtract the products on the backward diagonals. That is, first write
and then calculate this.
- Check that this agrees with the formula given in the preamble to this section.
- Does it extend to other-sized determinants?
- Problem 12
The cross product of the vectors
is the vector computed as this determinant.
Note that the first row is composed of vectors, the vectors from the standard basis for . Show that the cross product of two vectors is perpendicular to each vector.
- Problem 13
Prove that each statement holds for matrices.
- The determinant of a product is the product of the determinants .
- If is invertible then the determinant of the inverse is the inverse of the determinant .
Matrices and are similar if there is a nonsingular matrix such that . (This definition is in Chapter Five.) Show that similar matrices have the same determinant.
- This exercise is recommended for all readers.
- Problem 14
Prove that the area of this region in the plane
is equal to the value of this determinant.
Compare with this.
- Problem 15
Prove that for matrices, the determinant of a matrix equals the determinant of its transpose. Does that also hold for matrices?
- This exercise is recommended for all readers.
- Problem 16
Is the determinant function linear — is ?
- Problem 17
Show that if is then for any scalar .
- Problem 18
Which real numbers make
singular? Explain geometrically.
- ? Problem 19
If a third order determinant has elements , , ..., , what is the maximum value it may have? (Haggett & Saunders 1955)
2 - Properties of Determinants
As described above, we want a formula to determine whether an matrix is nonsingular. We will not begin by stating such a formula. Instead, we will begin by considering the function that such a formula calculates. We will define the function by its properties, then prove that the function with these properties exists and is unique and also describe formulas that compute this function. (Because we will show that the function exists and is unique, from the start we will say "" instead of "if there is a determinant function then " and "the determinant" instead of "any determinant".)
- Definition 2.1
A determinant is a function such that
- for
- for
- for
- where is an identity matrix
(the 's are the rows of the matrix). We often write for .
- Remark 2.2
Property (2) is redundant since
swaps rows and . It is listed only for convenience.
The first result shows that a function satisfying these conditions gives a criteria for nonsingularity. (Its last sentence is that, in the context of the first three conditions, (4) is equivalent to the condition that the determinant of an echelon form matrix is the product down the diagonal.)
- Lemma 2.3
A matrix with two identical rows has a determinant of zero. A matrix with a zero row has a determinant of zero. A matrix is nonsingular if and only if its determinant is nonzero. The determinant of an echelon form matrix is the product down its diagonal.
- Proof
To verify the first sentence, swap the two equal rows. The sign of the determinant changes, but the matrix is unchanged and so its determinant is unchanged. Thus the determinant is zero.
For the second sentence, we multiply a zero row by −1 and apply property (3). Multiplying a zero row with a constant leaves the matrix unchanged, so property (3) implies that . The only way this can be is if .
For the third sentence, where is the Gauss-Jordan reduction, by the definition the determinant of is zero if and only if the determinant of is zero (although they could differ in sign or magnitude). A nonsingular Gauss-Jordan reduces to an identity matrix and so has a nonzero determinant. A singular reduces to a with a zero row; by the second sentence of this lemma its determinant is zero.
Finally, for the fourth sentence, if an echelon form matrix is singular then it has a zero on its diagonal, that is, the product down its diagonal is zero. The third sentence says that if a matrix is singular then its determinant is zero. So if the echelon form matrix is singular then its determinant equals the product down its diagonal.
If an echelon form matrix is nonsingular then none of its diagonal entries is zero so we can use property (3) of the definition to factor them out (again, the vertical bars indicate the determinant operation).
Next, the Jordan half of Gauss-Jordan elimination, using property (1) of the definition, leaves the identity matrix.
Therefore, if an echelon form matrix is nonsingular then its determinant is the product down its diagonal.
That result gives us a way to compute the value of a determinant function on a matrix. Do Gaussian reduction, keeping track of any changes of sign caused by row swaps and any scalars that are factored out, and then finish by multiplying down the diagonal of the echelon form result. This procedure takes the same time as Gauss' method and so is sufficiently fast to be practical on the size matrices that we see in this book.
- Example 2.4
Doing determinants
with Gauss' method won't give a big savings because the determinant formula is so easy. However, a determinant is usually easier to calculate with Gauss' method than with the formula given earlier.
- Example 2.5
Determinants of matrices any bigger than are almost always most quickly done with this Gauss' method procedure.
The prior example illustrates an important point. Although we have not yet found a determinant formula, if one exists then we know what value it gives to the matrix — if there is a function with properties (1)-(4) then on the above matrix the function must return .
- Lemma 2.6
For each , if there is an determinant function then it is unique.
- Proof
For any matrix we can perform Gauss' method on the matrix, keeping track of how the sign alternates on row swaps, and then multiply down the diagonal of the echelon form result. By the definition and the lemma, all determinant functions must return this value on this matrix. Thus all determinant functions are equal, that is, there is only one input argument/output value relationship satisfying the four conditions.
The "if there is an determinant function" emphasizes that, although we can use Gauss' method to compute the only value that a determinant function could possibly return, we haven't yet shown that such a determinant function exists for all . In the rest of the section we will produce determinant functions.
Exercises
For these, assume that an determinant function exists for all .
- This exercise is recommended for all readers.
- Problem 1
Use Gauss' method to find each determinant.
- Problem 2
- Use Gauss' method to find each.
- Problem 3
For which values of does this system have a unique solution?
- This exercise is recommended for all readers.
- Problem 4
Express each of these in terms of .
- This exercise is recommended for all readers.
- Problem 5
Find the determinant of a diagonal matrix.
- Problem 6
Describe the solution set of a homogeneous linear system if the determinant of the matrix of coefficients is nonzero.
- This exercise is recommended for all readers.
- Problem 7
Show that this determinant is zero.
- Problem 8
- Find the , , and matrices with entry given by .
- Find the determinant of the square matrix with entry .
- Problem 9
- Find the , , and matrices with entry given by .
- Find the determinant of the square matrix with entry .
- This exercise is recommended for all readers.
- Problem 10
Show that determinant functions are not linear by giving a case where .
- Problem 11
The second condition in the definition, that row swaps change the sign of a determinant, is somewhat annoying. It means we have to keep track of the number of swaps, to compute how the sign alternates. Can we get rid of it? Can we replace it with the condition that row swaps leave the determinant unchanged? (If so then we would need new , , and formulas, but that would be a minor matter.)
- Problem 12
Prove that the determinant of any triangular matrix, upper or lower, is the product down its diagonal.
- Problem 13
Refer to the definition of elementary matrices in the Mechanics of Matrix Multiplication subsection.
- What is the determinant of each kind of elementary matrix?
- Prove that if is any elementary matrix then for any appropriately sized .
- (This question doesn't involve determinants.) Prove that if is singular then a product is also singular.
- Show that .
- Show that if is nonsingular then .
- Problem 14
Prove that the determinant of a product is the product of the determinants in this way. Fix the matrix and consider the function given by .
- Check that satisfies property (1) in the definition of a determinant function.
- Check property (2).
- Check property (3).
- Check property (4).
- Conclude the determinant of a product is the product of the determinants.
- Problem 15
A submatrix of a given matrix is one that can be obtained by deleting some of the rows and columns of . Thus, the first matrix here is a submatrix of the second.
Prove that for any square matrix, the rank of the matrix is if and only if is the largest integer such that there is an submatrix with a nonzero determinant.
- This exercise is recommended for all readers.
- Problem 16
Prove that a matrix with rational entries has a rational determinant.
- ? Problem 17
Find the element of likeness in (a) simplifying a fraction, (b) powdering the nose, (c) building new steps on the church, (d) keeping emeritus professors on campus, (e) putting , , in the determinant
3 - The Permutation Expansion
The prior subsection defines a function to be a determinant if it satisfies four conditions and shows that there is at most one determinant function for each . What is left is to show that for each such a function exists.
How could such a function not exist? After all, we have done computations that start with a square matrix, follow the conditions, and end with a number.
The difficulty is that, as far as we know, the computation might not give a well-defined result. To illustrate this possibility, suppose that we were to change the second condition in the definition of determinant to be that the value of a determinant does not change on a row swap. By Remark 2.2 we know that this conflicts with the first and third conditions. Here is an instance of the conflict: here are two Gauss' method reductions of the same matrix, the first without any row swap
and the second with a swap.
Following Definition 2.1 gives that both calculations yield the determinant since in the second one we keep track of the fact that the row swap changes the sign of the result of multiplying down the diagonal. But if we follow the supposition and change the second condition then the two calculations yield different values, and . That is, under the supposition the outcome would not be well-defined — no function exists that satisfies the changed second condition along with the other three.
Of course, observing that Definition 2.1 does the right thing in this one instance is not enough; what we will do in the rest of this section is to show that there is never a conflict. The natural way to try this would be to define the determinant function with: "The value of the function is the result of doing Gauss' method, keeping track of row swaps, and finishing by multiplying down the diagonal". (Since Gauss' method allows for some variation, such as a choice of which row to use when swapping, we would have to fix an explicit algorithm.) Then we would be done if we verified that this way of computing the determinant satisfies the four properties. For instance, if and are related by a row swap then we would need to show that this algorithm returns determinants that are negatives of each other. However, how to verify this is not evident. So the development below will not proceed in this way. Instead, in this subsection we will define a different way to compute the value of a determinant, a formula, and we will use this way to prove that the conditions are satisfied.
The formula that we shall use is based on an insight gotten from property (3) of the definition of determinants. This property shows that determinants are not linear.
- Example 3.1
For this matrix .
Instead, the scalar comes out of each of the two rows.
Since scalars come out a row at a time, we might guess that determinants are linear a row at a time.
- Definition 3.2
Let be a vector space. A map is multilinear if
for and .
- Lemma 3.3
Determinants are multilinear.
- Proof
The definition of determinants gives property (2) (Lemma 2.3 following that definition covers the case) so we need only check property (1).
If the set is linearly dependent then all three matrices are singular and so all three determinants are zero and the equality is trivial. Therefore assume that the set is linearly independent. This set of -wide row vectors has members, so we can make a basis by adding one more vector . Express and with respect to this basis
giving this.
By the definition of determinant, the value of is unchanged by the pivot operation of adding to .
Then, to the result, we can add , etc. Thus
(using (2) for the second equality). To finish, bring and back inside in front of and use pivoting again, this time to reconstruct the expressions of and in terms of the basis, e.g., start with the pivot operations of adding to and to , etc.
Multilinearity allows us to expand a determinant into a sum of determinants, each of which involves a simple matrix.
- Example 3.4
We can use multilinearity to split this determinant into two, first breaking up the first row
and then separating each of those two, breaking along the second rows.
We are left with four determinants, such that in each row of each matrix there is a single entry from the original matrix.
- Example 3.5
In the same way, a determinant separates into a sum of many simpler determinants. We start by splitting along the first row, producing three determinants (the zero in the position is underlined to set it off visually from the zeroes that appear in the splitting).
Each of these three will itself split in three along the second row. Each of the resulting nine splits in three along the third row, resulting in twenty seven determinants
such that each row contains a single entry from the starting matrix.
So an determinant expands into a sum of determinants where each row of each summands contains a single entry from the starting matrix. However, many of these summand determinants are zero.
- Example 3.6
In each of these three matrices from the above expansion, two of the rows have their entry from the starting matrix in the same column, e.g., in the first matrix, the and the both come from the first column.
Any such matrix is singular, because in each, one row is a multiple of the other (or is a zero row). Thus, any such determinant is zero, by Lemma 2.3.
Therefore, the above expansion of the determinant into the sum of the twenty seven determinants simplifies to the sum of these six.
We can bring out the scalars.
To finish, we evaluate those six determinants by row-swapping them to the identity matrix, keeping track of the resulting sign changes.
That example illustrates the key idea. We've applied multilinearity to a determinant to get separate determinants, each with one distinguished entry per row. We can drop most of these new determinants because the matrices are singular, with one row a multiple of another. We are left with the one-entry-per-row determinants also having only one entry per column (one entry from the original determinant, that is). And, since we can factor scalars out, we can further reduce to only considering determinants of one-entry-per-row-and-column matrices where the entries are ones.
These are permutation matrices. Thus, the determinant can be computed in this three-step way (Step 1) for each permutation matrix, multiply together the entries from the original matrix where that permutation matrix has ones, (Step 2) multiply that by the determinant of the permutation matrix and (Step 3) do that for all permutation matrices and sum the results together.
To state this as a formula, we introduce a notation for permutation matrices. Let be the row vector that is all zeroes except for a one in its -th entry, so that the four-wide is . We can construct permutation matrices by permuting — that is, scrambling — the numbers , , ..., , and using them as indices on the 's. For instance, to get a permutation matrix matrix, we can scramble the numbers from to into this sequence and take the corresponding row vector 's.
- Definition 3.7
An -permutation is a sequence consisting of an arrangement of the numbers , , ..., .
- Example 3.8
The -permutations are and . These are the associated permutation matrices.
We sometimes write permutations as functions, e.g., , and . Then the rows of are and .
The -permutations are , , , , , and . Here are two of the associated permutation matrices.
For instance, the rows of are , , and .
- Definition 3.9
The permutation expansion for determinants is
where are all of the -permutations.
This formula is often written in summation notation
read aloud as "the sum, over all permutations , of terms having the form ". This phrase is just a restating of the three-step process (Step 1) for each permutation matrix, compute (Step 2) multiply that by and (Step 3) sum all such terms together.
- Example 3.10
The familiar formula for the determinant of a matrix can be derived in this way.
(the second permutation matrix takes one row swap to pass to the identity). Similarly, the formula for the determinant of a matrix is this.
Computing a determinant by permutation expansion usually takes longer than Gauss' method. However, here we are not trying to do the computation efficiently, we are instead trying to give a determinant formula that we can prove to be well-defined. While the permutation expansion is impractical for computations, it is useful in proofs. In particular, we can use it for the result that we are after.
- Theorem 3.11
For each there is a determinant function.
The proof is deferred to the following subsection. Also there is the proof of the next result (they share some features).
- Theorem 3.12
The determinant of a matrix equals the determinant of its transpose.
The consequence of this theorem is that, while we have so far stated results in terms of rows (e.g., determinants are multilinear in their rows, row swaps change the signum, etc.), all of the results also hold in terms of columns. The final result gives examples.
- Corollary 3.13
A matrix with two equal columns is singular. Column swaps change the sign of a determinant. Determinants are multilinear in their columns.
- Proof
For the first statement, transposing the matrix results in a matrix with the same determinant, and with two equal rows, and hence a determinant of zero. The other two are proved in the same way.
We finish with a summary
(although the final subsection contains the unfinished business of
proving the two theorems).
Determinant functions exist, are unique, and we know how to compute them.
As for what determinants are about, perhaps these lines
(Kemp 1982) help make it memorable.
Determinant none,
Solution: lots or none.
Determinant some,
Solution: just one.
Exercises
These summarize the notation used in this book for the - and - permutations.
- This exercise is recommended for all readers.
- Problem 1
Compute the determinant by using the permutation expansion.
- This exercise is recommended for all readers.
- Problem 2
Compute these both with Gauss' method and with the permutation expansion formula.
- This exercise is recommended for all readers.
- Problem 3
Use the permutation expansion formula to derive the formula for determinants.
- Problem 4
List all of the -permutations.
- Problem 5
A permutation, regarded as a function from the set to itself, is one-to-one and onto. Therefore, each permutation has an inverse.
- Find the inverse of each -permutation.
- Find the inverse of each -permutation.
- Problem 6
Prove that is multilinear if and only if for all and , this holds.
- Problem 7
Find the only nonzero term in the permutation expansion of this matrix.
Compute that determinant by finding the signum of the associated permutation.
- Problem 8
How would determinants change if we changed property (4) of the definition to read that ?
- Problem 9
Verify the second and third statements in Corollary 3.13.
- This exercise is recommended for all readers.
- Problem 10
Show that if an matrix has a nonzero determinant then any column vector can be expressed as a linear combination of the columns of the matrix.
- Problem 11
True or false: a matrix whose entries are only zeros or ones has a determinant equal to zero, one, or negative one. (Strang 1980)
- Problem 12
- Show that there are terms in the permutation expansion formula of a matrix.
- How many are sure to be zero if the entry is zero?
- Problem 13
How many -permutations are there?
- Problem 14
A matrix is skew-symmetric if , as in this matrix.
Show that skew-symmetric matrices with nonzero determinants exist only for even .
- This exercise is recommended for all readers.
- Problem 15
What is the smallest number of zeros, and the placement of those zeros, needed to ensure that a matrix has a determinant of zero?
- This exercise is recommended for all readers.
- Problem 16
If we have data points and want to find a polynomial passing through those points then we can plug in the points to get an equation/ unknown linear system. The matrix of coefficients for that system is called the Vandermonde matrix. Prove that the determinant of the transpose of that matrix of coefficients
equals the product, over all indices with , of terms of the form . (This shows that the determinant is zero, and the linear system has no solution, if and only if the 's in the data are not distinct.)
- Problem 17
A matrix can be divided into blocks, as here,
which shows four blocks, the square and ones in the upper left and lower right, and the zero blocks in the upper right and lower left. Show that if a matrix can be partitioned as
where and are square, and and are all zeroes, then .
- This exercise is recommended for all readers.
- Problem 18
Prove that for any matrix there are at most distinct reals such that the matrix has determinant zero (we shall use this result in Chapter Five).
- ? Problem 19
The nine positive digits can be arranged into arrays in ways. Find the sum of the determinants of these arrays. (Trigg 1963)
- ? Problem 21
Let be the sum of the integer elements of a magic square of order three and let be the value of the square considered as a determinant. Show that is an integer. (Trigg & Walker 1949)
- ? Problem 22
Show that the determinant of the elements in the upper left corner of the Pascal triangle
has the value unity. (Rupp & Aude 1931)
4 - Determinants Exist
This subsection is optional. It consists of proofs of two results from the prior subsection. These proofs involve the properties of permutations, which will not be used later, except in the optional Jordan Canonical Form subsection.
The prior subsection attacks the problem of showing that for any size there is a determinant function on the set of square matrices of that size by using multilinearity to develop the permutation expansion.
This reduces the problem to showing that there is a determinant function on the set of permutation matrices of that size.
Of course, a permutation matrix can be row-swapped to the identity matrix and to calculate its determinant we can keep track of the number of row swaps. However, the problem is still not solved. We still have not shown that the result is well-defined. For instance, the determinant of
could be computed with one swap
or with three.
Both reductions have an odd number of swaps so we figure that but how do we know that there isn't some way to do it with an even number of swaps? Corollary 4.6 below proves that there is no permutation matrix that can be row-swapped to an identity matrix in two ways, one with an even number of swaps and the other with an odd number of swaps.
- Definition 4.1
Two rows of a permutation matrix
such that are in an inversion of their natural order.
- Example 4.2
This permutation matrix
has three inversions: precedes , precedes , and precedes .
- Lemma 4.3
A row-swap in a permutation matrix changes the number of inversions from even to odd, or from odd to even.
- Proof
Consider a swap of rows and , where . If the two rows are adjacent
then the swap changes the total number of inversions by one — either removing or producing one inversion, depending on whether or not, since inversions involving rows not in this pair are not affected. Consequently, the total number of inversions changes from odd to even or from even to odd.
If the rows are not adjacent then they can be swapped via a sequence of adjacent swaps, first bringing row up
and then bringing row down.
Each of these adjacent swaps changes the number of inversions from odd to even or from even to odd. There are an odd number of them. The total change in the number of inversions is from even to odd or from odd to even.
- Definition 4.4
The signum of a permutation is if the number of inversions in is even, and is if the number of inversions is odd.
- Example 4.5
With the subscripts from Example 3.8 for the -permutations, while .
- Corollary 4.6
If a permutation matrix has an odd number of inversions then swapping it to the identity takes an odd number of swaps. If it has an even number of inversions then swapping to the identity takes an even number of swaps.
- Proof
The identity matrix has zero inversions. To change an odd number to zero requires an odd number of swaps, and to change an even number to zero requires an even number of swaps.
We still have not shown that the permutation expansion is well-defined because we have not considered row operations on permutation matrices other than row swaps. We will finesse this problem: we will define a function by altering the permutation expansion formula, replacing with
(this gives the same value as the permutation expansion because the prior result shows that ). This formula's advantage is that the number of inversions is clearly well-defined — just count them. Therefore, we will show that a determinant function exists for all sizes by showing that is it, that is, that satisfies the four conditions.
- Lemma 4.7
The function is a determinant. Hence determinants exist for every .
- Proof
We'll must check that it has the four properties from the definition.
Property (4) is easy; in
all of the summands are zero except for the product down the diagonal, which is one.
For property (3) consider where .
Factor the out of each term to get the desired equality.
For (2), let
.
To convert to unhatted 's, for each consider the permutation that equals except that the -th and -th numbers are interchanged, and . Replacing the in with this gives . Now (by Lemma 4.3) and so we get
where the sum is over all permutations derived from another permutation by a swap of the -th and -th numbers. But any permutation can be derived from some other permutation by such a swap, in one and only one way, so this summation is in fact a sum over all permutations, taken once and only once. Thus .
To do property (1) let and consider
(notice: that's , not ). Distribute, commute, and factor.
We finish by showing that the terms add to zero. This sum represents where is a matrix equal to except that row of is a copy of row of (because the factor is , not ). Thus, has two equal rows, rows and . Since we have already shown that changes sign on row swaps, as in Lemma 2.3 we conclude that .
We have now shown that determinant functions exist for each size. We already know that for each size there is at most one determinant. Therefore, the permutation expansion computes the one and only determinant value of a square matrix.
We end this subsection by proving the other result remaining from the prior subsection, that the determinant of a matrix equals the determinant of its transpose.
- Example 4.8
Writing out the permutation expansion of the general matrix and of its transpose, and comparing corresponding terms
(terms with the same letters)
shows that the corresponding permutation matrices are transposes. That is, there is a relationship between these corresponding permutations. Problem 6 shows that they are inverses.
- Theorem 4.9
The determinant of a matrix equals the determinant of its transpose.
- Proof
Call the matrix and denote the entries of with 's so that . Substitution gives this
and we can finish the argument by manipulating the expression on the right to be recognizable as the determinant of the transpose. We have written all permutation expansions (as in the middle expression above) with the row indices ascending. To rewrite the expression on the right in this way, note that because is a permutation, the row indices in the term on the right , ..., are just the numbers , ..., , rearranged. We can thus commute to have these ascend, giving (if the column index is and the row index is then, where the row index is , the column index is ). Substituting on the right gives
(Problem 5 shows that ). Since every permutation is the inverse of another, a sum over all is a sum over all permutations
as required.
Exercises
These summarize the notation used in this book for the - and - permutations.
- Problem 1
Give the permutation expansion of a general matrix and its transpose.
- This exercise is recommended for all readers.
- Problem 2
This problem appears also in the prior subsection.
- Find the inverse of each -permutation.
- Find the inverse of each -permutation.
- This exercise is recommended for all readers.
- Problem 3
- Find the signum of each -permutation.
- Find the signum of each -permutation.
- Problem 4
What is the signum of the -permutation ? (Strang 1980)
- Problem 5
Prove these.
- Every permutation has an inverse.
- Every permutation is the inverse of another.
- Problem 6
Prove that the matrix of the permutation inverse is the transpose of the matrix of the permutation , for any permutation .
- This exercise is recommended for all readers.
- Problem 7
Show that a permutation matrix with inversions can be row swapped to the identity in steps. Contrast this with Corollary 4.6.
- This exercise is recommended for all readers.
- Problem 8
For any permutation let be the integer defined in this way.
(This is the product, over all indices and with , of terms of the given form.)
- Compute the value of on all -permutations.
- Compute the value of on all -permutations.
- Prove this.
Many authors give this formula as the definition of the signum function.
Section II - Geometry of Determinants
The prior section develops the determinant algebraically, by considering what formulas satisfy certain properties. This section complements that with a geometric approach. One advantage of this approach is that, while we have so far only considered whether or not a determinant is zero, here we shall give a meaning to the value of that determinant. (The prior section handles determinants as functions of the rows, but in this section columns are more convenient. The final result of the prior section says that we can make the switch.)
1 - Determinants as Size Functions
This parallelogram picture
is familiar from the construction of the sum of the two vectors. One way to compute the area that it encloses is to draw this rectangle and subtract the area of each subregion.