Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

is there an obvious lattice path counting interpretation for multiplying n by n (0,1) matrices ?

share|improve this question
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.