Linear Algebra/Determinants Exist/Solutions

From Wikibooks, open books for an open world
Jump to navigation Jump to search

Solutions[edit | edit source]

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. 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. Note that is negative if and only if and are in an inversion of their usual order.

References[edit | edit source]

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