MA415 HOMEWORK #5
Due Monday, March 27

1. Section 5.5, #1, 3, 11, 14, 16.
2. Section 6.1, #4, 6, 14.
3. Redefine the ``product'' of two matrices A and B as C=AB, where

   

   Let W be the matrix of edges weights for a simple graph; i.e., equals the weight of edge ij. We define for and if ij is not an edge. Assume for all i,j. Prove by induction on n that entry i,j of equals the weight of a minimum weight path from i to j that uses no more than n edges, where the power is computed according to the new matrix product rule. Then use this to prove that when , the i,j entry of equals the weight of the minimum weight path from i to j. Finally, by repeated squaring, use this method to solve Problem 9 in Section 6.1.

• About this document ...