CS341 Study Guide - Randomized Algorithm, Triangular Matrix, C Data Types
Document Summary
Reading for this lecture: sections 25. 1 and 25. 2 of clrs. Therefore, in o(n +1) steps (under the unit-cost model), we can compute the total number of distinct walks between all pairs of vertices, by doing all the matrix multiplications in. I + m + m2 + + mn-1 (where i is the identity matrix) and adding up the results. Here denotes the best exponent for matrix multiplication known; currently = 2. 3728639. Now if we think of i + m + m2 + + mn-1 as the sum of a geometric series, then we could write this as (i-mn)(i-m)-1, where the -1 means matrix inverse. Now mn = 0 because g is acyclic (so there are no length-n paths), so this is just (i- For an arbitrary m, the matrix (i-m) may not be invertible, but in this particular case (where m represents an acyclic graph), the inverse will indeed exist. (do you see why?)
