**MA415 HOMEWORK #5
Due Monday, March 27
**

**
**

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

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

Mon Mar 20 13:59:40 EST 2000