Linear Algebra/Determinants Exist/Solutions

Solutions 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). Problem 2 This problem appears also in the prior subsection. <li> Find the inverse of each -permutation. <li> Find the inverse of each -permutation. Answer Each of these is easy to check. <li> <TR> <TD style="border-right:2px black solid; border-bottom:2px solid black;"> permutation    <TD style="border-bottom:2px solid black;">       <TD style="border-bottom:2px solid black;">    <TR> <TD style="border-right:2px solid black;">inverse    <TD>       <TD>    <li> <TR> <TD style="border-right:2px solid black; border-bottom:2px solid black;"> permutation    <TD style="border-bottom:2px solid black;">       <TD style="border-bottom:2px solid black;">       <TD style="border-bottom:2px solid black;">       <TD style="border-bottom:2px solid black;">       <TD style="border-bottom:2px solid black;">       <TD style="border-bottom:2px solid black;">    <TR> <TD style="border-right:2px solid black;"> inverse    <TD>       <TD>       <TD>       <TD>       <TD>       <TD>    Problem 3 <li> Find the signum of each -permutation. <li> Find the signum of each -permutation. Answer <li> , <li> , , , , , 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 5exer:PermInvFacts Prove these. <li> Every permutation has an inverse. <li> <li> Every permutation is the inverse of another. Answer <li> Permutations can be viewed as one-one and onto maps . Any one-one and onto map has an inverse. <li> 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). <li> This is the first question again. Problem 6exer:PermInvIffMatTrans 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 , 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. 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.) <li> Compute the value of on all -permutations. <li> Compute the value of on all -permutations. <li> Prove this. Many authors give this formula as the definition of the signum function. Answer <li> First, is the product of the single factor and so . Second, is the product of the single factor and so . <li> <li> Note that is negative if and only if and are in an inversion of their usual order. References Gilbert Strang Linear Algebra and its Applications 2nd Hartcourt Brace Javanovich 1980