algorithm - Detecting when matrix multiplication is possible

Question

Here is an interesting problem that I encountered in a programming competition:

Problem statement: Given the dimensions of n matrices, determine if there exists an ordering such that the matrices can be multiplied. If there exists one, print out the size (product of the dimensions) of the resultant matrix.

My observations: This reduces to the NP-complete hamiltonian path problem if you consider each matrix as a vertex and draw a directed edge between matrices that can be multiplied. I solved this by simply brute-forcing the problem but this is clearly very slow. I was wondering if there are any clever optimizations for this particular instance of the problem.

Answer 1

1. Create a node for each dimension length. That is, if there is a matrix of dimension (m,n), then m and n will be vertices in the graph.

2. For every matrix of size (m,n) connect nodes m and n with a directed edge (there can be multiple edges between two nodes).

3. Now finding a eularian trail would give the multiplication order.

See http://en.wikipedia.org/wiki/Euler_path for finding Eularian trails. Complexity is pretty close to linear ( O(nlog^3n loglogn) where n is the number of edges = number of matrices) .