Consider a square, sparse matrix $M[a_1,a_2]:1\leq a_1,a_2\leq N$ of non-negative entries. My question is for a given even $L>1$, how to efficiently compute the sum $$ S:=\sum_{a!}M[a_1,a_2]\cdot M[a_3,a_4]\cdots M[a_{L-1},a_L] $$ where sum ranges only over index vectors $(a_1,a_2,\ldots,a_L)$ all of whose entries are unique.
I'm also interested in methods to compute a part of the full sum. Here is one: Suppose we color half of the indexes $\{1,\ldots,N\}$ white, and the others black, and consider only those terms of $S$ for which each factor $M[a,b]$ has a white index for $a$ and a black index for $b$. This post gives an efficient recursive calculation. Apparently this trick only gets us an exponentially small proportion of the full sum.
Consider the adjacency graph, $G_M$, which is the graph with $N$ nodes having edges between $a_1$ and $a_2$ iff $M[a_1,a_2]\neq 0$. There seems to be some connection between the complexity of $S$ and the separability of $G_M$. For instance, the result of the previous paragraph means that $S$ can be computed efficiently if $G_M$ is bipartite.
For another example, suppose that $G$ is a union of two disconnected subgraphs $G_1,G_2$ which are connected by a single edge $E=[1,2]$ where $j\in G_j$. Let $S_j$ denote the partial sum obtained by restricting to elements of $G_j$. Then $S$ can be written as a sum of two terms, one of which contains $M[1,2]$ and the other of which doesn't; each term can be factored over the elements of $G_j$ and therefore contain significantly fewer terms than $S$. Thus, near-disconnectedness of $G$ seems to imply a substantial reduction in the complexity of computing $S$.
That's as far as I've gotten. Thanks for reading!
