Linear Algebra/Determinants Exist/Solutions

SolutionsEdit

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.

Answer

This is the permutation expansion of the determinant of a   matrix

 

and the permutation expansion of the determinant of its transpose.

 

As with the   expansions described in the subsection, the permutation matrices from corresponding terms are transposes (although this is disguised by the fact that each is self-transpose).

This exercise is recommended for all readers.
Problem 2

This problem appears also in the prior subsection.

  1. Find the inverse of each  -permutation.
  2. Find the inverse of each  -permutation.
Answer

Each of these is easy to check.

  1. permutation                
    inverse                
  2. permutation                                                
    inverse                                                
This exercise is recommended for all readers.
Problem 3
  1. Find the signum of each  -permutation.
  2. Find the signum of each  -permutation.
Answer
  1.  ,  
  2.  ,  ,  ,  ,  ,  
Problem 4

What is the signum of the  -permutation  ? (Strang 1980)

Answer

The pattern is this.

 

So to find the signum of  , we subtract one   and look at the remainder on division by four. If the remainder is   or   then the signum is  , otherwise it is  . For  , the number   is divisible by four, so   leaves a remainder of   on division by four (more properly said, a remainder or  ), and so the signum is  . The   case has a signum of  , the   case has a signum of   and the   case has a signum of  .

Problem 5

Prove these.

  1. Every permutation has an inverse.
  2.  
  3. Every permutation is the inverse of another.
Answer
  1. Permutations can be viewed as one-one and onto maps  . Any one-one and onto map has an inverse.
  2. If it always takes an odd number of swaps to get from   to the identity, then it always takes an odd number of swaps to get from the identity to   (any swap is reversible).
  3. This is the first question again.
Problem 6

Prove that the matrix of the permutation inverse is the transpose of the matrix of the permutation  , for any permutation  .

Answer

If   then  . The result now follows on the observation that   has a   in entry   if and only if  , and   has a   in entry   if and only if  ,

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.

Answer

This does not say that   is the least number of swaps to produce an identity, nor does it say that   is the most. It instead says that there is a way to swap to the identity in exactly   steps.

Let   be the first row that is inverted with respect to a prior row and let   be the first row giving that inversion. We have this interval of rows.

 

Swap.

 

The second matrix has one fewer inversion because there is one fewer inversion in the interval (  vs.  ) and inversions involving rows outside the interval are not affected.

Proceed in this way, at each step reducing the number of inversions by one with each row swap. When no inversions remain the result is the identity.

The contrast with Corollary 4.6 is that the statement of this exercise is a "there exists" statement: there exists a way to swap to the identity in exactly   steps. But the corollary is a "for all" statement: for all ways to swap to the identity, the parity (evenness or oddness) is the same.

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.)

  1. Compute the value of   on all  -permutations.
  2. Compute the value of   on all  -permutations.
  3. Prove this.
     

Many authors give this formula as the definition of the signum function.

Answer
  1. First,   is the product of the single factor   and so  . Second,   is the product of the single factor   and so  .
  2.  
  3. Note that   is negative if and only if   and   are in an inversion of their usual order.

ReferencesEdit

  • Strang, Gilbert (1980), Linear Algebra and its Applications (2nd ed.), Hartcourt Brace Javanovich