12

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.

tskuzzy
  • 35,812
  • 14
  • 73
  • 140
  • 3
    All efficiently solvable (and checkable) problems reduce to NP-complete problems. It is the reduction from a NP-complete problem to your problem that should annoying. – aelguindy Feb 13 '12 at 22:23
  • As @ElKamina said, it's a Eulerian trail problem, see also my answer [here](http://stackoverflow.com/a/9046177/1011995). – Daniel Fischer Feb 13 '12 at 22:36

2 Answers2

14

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

ElKamina
  • 7,747
  • 28
  • 43
0

Create a compatibility matrix (let's call it CM) such as CM[x,y] = 1 if the matrix x can be multuplied by y, 0 if not. if Determinant(CM) <> 0 there is an order.

It's just an intuition, I apologize if I'm wrong (unfortunately I couldn't find a solid proof).

loscuropresagio
  • 1,922
  • 15
  • 26
  • Definitely untrue. Consider the case of two 2x2 matrices. Then your matrix is [[1,1][1,1]], which has a determinant of 0. – Simon Nickerson Feb 14 '12 at 07:43
  • That's true, but this also means that you consider that a matrix can be multiplied by itself. In the case of a square matrix, that's absolutely true, but in this particular scenario we are looking for a sequence of matrixes multiplied by each other, which means that we should consider a matrix not compatible with itself. This obviously is not a proof that I'm right, just a considerations. Thanks though for the comment, if you find another counterexample, I'll appreciate. – loscuropresagio Feb 14 '12 at 10:22
  • Good point. How about a 1x2 and a 2x3 matrix. Then I think your matrix is [[0,1][0,0]], which also has a determinant of 0, even though you can multiply these elements together. – Simon Nickerson Feb 14 '12 at 15:03
  • Smart. How about this: determinant is 0 because A is compatible with B and B is NOT compatible with A. In other words: if Det(CM)<>0 then we have a RING (M1 compatible M2 compatible... Mn compatible M1). So, I think that we should consider the RANK. In order to have N matrices to be multiplied by each other, the rank of the compatibility matrix must be N-1. In general the rank tells us how many matrices can be multiplied. Further more, CM is in fact an incidence matrix. This matrix describes the graph in which matrices are the nodes and compatibility between them are the edges. – loscuropresagio Feb 14 '12 at 15:47