is there an obvious lattice path counting interpretation for multiplying n by n (0,1) matrices ?
3 Answers
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.
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).
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.