2
$\begingroup$

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

$\endgroup$

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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