is there an obvious lattice path counting interpretation for multiplying n by n (0,1) matrices ?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
2
|
|
|
|
|
5
|
Well, there is a path counting interpretation. If the first matrix describes a collection of red edges of a graph and the second matrix describes a collection of blue edges of a graph, then their product describes the set of ways to traverse a red edge and then a blue edge. |
||
|
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
3
|
Yes, you can imagine a three columns graph, each column has n points. The resultant matrix (AB)_ij= # of path from i-th point in the first column to j-th column in the last column. Actually, if we assume the Word RAM computational model, the above interpretation leads to an O(n^3/log^2 n) time algorithm, which is better than O(n^3). |
||
|
|
|
0
|
To add to other answers, you might want to play with a weighted path counting interpretation (rather than composition of linear maps interpretation) for multiplication of matrices with not necessarily integer entries. Strongly related is to view a n by m matrix as a bipartite graph (with weighted edges) with n vertices on one side and m vertices on the other side (instead of viewing a matrix as a linear map). This viewpoint is useful when you are learning Markov chains or shifts of finite types. |
||
|
|
