Assume you are given a binary matrix $M$ (matrix elements are either 0 or 1) of higher dimension and a set of binary matrices $S = \{A_1, A_2, \cdots A_n\}$ of lower dimensions.
Now, I want to describe $M$ using multiplication or Kronecter product of matrices from set $S$ such that number of multiplication of matrices required in-between the Kronecter products is minimum.
It is assumed that multiple such decompositions of $M$ are possible. (If it helps to build an algorithm from here, one such possible decomposition is already known which uses lots of multiplications. We need to minimize that and find some other decomposition.)
Example (just to get give an idea, not a real example):
$M = A_1A_2A_3 \otimes A_1A_3A_2$ - Say this is the known decomposition, but here as you can see, we perform the multiplication of three matrices.
$M = A_1A_2 \otimes A_2A_3 \otimes A_2A_3$ - Say this also gives correct $M$. As you can see this only performs multiplication of two matrices at a time. (This is better solution than above)
How can we efficiently find a decomposition which uses the least number of matrix multiplications from set $S$? Is it even possible with some non-heuristic, no trial-and-error algorithm?