most recent 30 from http://mathoverflow.net 2013-05-21T20:33:23Z http://mathoverflow.net/feeds/question/3250 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/3250/multiplication-of-0-1-matrices peter 2009-10-29T12:12:59Z 2009-11-05T09:43:31Z

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

http://mathoverflow.net/questions/3250/multiplication-of-0-1-matrices/3253#3253 Qiaochu Yuan 2009-10-29T12:46:12Z 2009-10-29T12:46:12Z

<p>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. </p>

http://mathoverflow.net/questions/3250/multiplication-of-0-1-matrices/3256#3256 Kore Min 2009-10-29T12:59:48Z 2009-10-29T12:59:48Z

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

http://mathoverflow.net/questions/3250/multiplication-of-0-1-matrices/4236#4236 Yoo 2009-11-05T09:43:31Z 2009-11-05T09:43:31Z

<p>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.</p>