The Stack Overflow podcast is back! Listen to an interview with our new CEO.
4 added 4 characters in body
source | link

Assumption 1b): $Y ≤ X$
$BA$ has dimension $Y \times Y$. This is the optimal ordering for all products involving A$A$ and B$B$. Thus, the solution is optimally found as $A(BA)^{n-1}B$.

Assumption 1b): $Y ≤ X$
$BA$ has dimension $Y \times Y$. This is the optimal ordering for all products involving A and B. Thus, the solution is optimally found as $A(BA)^{n-1}B$.

Assumption 1b): $Y ≤ X$
$BA$ has dimension $Y \times Y$. This is the optimal ordering for all products involving $A$ and $B$. Thus, the solution is optimally found as $A(BA)^{n-1}B$.

3 deleted 1 character in body
source | link

Assumption 1b): $Y ≤ X$
$BA$ has dimension $Y \times Y$. This is the optimal ordering for all products involving A and B. Thus, the solution is optimally found as $A(BA)^{n-1}*B$$A(BA)^{n-1}B$.

Assumption 1b): $Y ≤ X$
$BA$ has dimension $Y \times Y$. This is the optimal ordering for all products involving A and B. Thus, the solution is optimally found as $A(BA)^{n-1}*B$.

Assumption 1b): $Y ≤ X$
$BA$ has dimension $Y \times Y$. This is the optimal ordering for all products involving A and B. Thus, the solution is optimally found as $A(BA)^{n-1}B$.

2 added 1157 characters in body
source | link

Disclaimer: The following method has not been rigorously proven to be optimal. An informal proof is provided.

In summary:
1) The first step in solving $(A_1 A_2 \cdots A_n)^m$ is to solve $(A_1 A_2 \cdots A_n)^2$.
2) Solving $(A_1 A_2 \cdots A_n)^2$ is best approached as an instance of the Matrix Chain Multiplication problem.
3) Using the n-tuple ordering $G$ from the solution in (2) will give us the solution to (1) as some flavor of $A_1 \cdot A_2 \cdot G^{m-1} \cdot A_n$ (note that any other groupings from solving (2) should be applied as well).

Informal proof
Considering the simplest case using two matrices, $(AB)^n$, we note that $A$ and $B$ have dimension $X \times Y$ and $Y \times X$ respectively. Any product using $A$ and $B$ has one of the following dimensions:

$X \times Y$
$Y \times X$
$Y \times Y$
$X \times X$

We have either $X < Y$ or $Y ≤ X$.

Assumption 1a): $X < Y$
$AB$ has dimension $X \times X$, and this ordering is guaranteed to be optimal from a bottom-up approach. Any other configuration of $A$ and $B$ is either equally good, or worse. Thus, the problem is optimally solved as $(AB)^n$.

Assumption 1b): $Y ≤ X$
$BA$ has dimension $Y \times Y$. This is the optimal ordering for all products involving A and B. Thus, the solution is optimally found as $A(BA)^{n-1}*B$.

This concludes the proof, and we have only looked at the two orderings found in $ABAB$, the square problem.

Using more matrices, the argument is similar. Perhaps an inductive proof is possible? The general idea is that solving the MCM for the square will find the optimal size for the operations with all involved matrices considered.

Disclaimer: The following method has not been rigorously proven to be optimal.

In summary:
1) The first step in solving $(A_1 A_2 \cdots A_n)^m$ is to solve $(A_1 A_2 \cdots A_n)^2$.
2) Solving $(A_1 A_2 \cdots A_n)^2$ is best approached as an instance of the Matrix Chain Multiplication problem.
3) Using the n-tuple ordering $G$ from the solution in (2) will give us the solution to (1) as some flavor of $A_1 \cdot A_2 \cdot G^{m-1} \cdot A_n$ (note that any other groupings from solving (2) should be applied as well).

Disclaimer: The following method has not been rigorously proven to be optimal. An informal proof is provided.

In summary:
1) The first step in solving $(A_1 A_2 \cdots A_n)^m$ is to solve $(A_1 A_2 \cdots A_n)^2$.
2) Solving $(A_1 A_2 \cdots A_n)^2$ is best approached as an instance of the Matrix Chain Multiplication problem.
3) Using the n-tuple ordering $G$ from the solution in (2) will give us the solution to (1) as some flavor of $A_1 \cdot A_2 \cdot G^{m-1} \cdot A_n$ (note that any other groupings from solving (2) should be applied as well).

Informal proof
Considering the simplest case using two matrices, $(AB)^n$, we note that $A$ and $B$ have dimension $X \times Y$ and $Y \times X$ respectively. Any product using $A$ and $B$ has one of the following dimensions:

$X \times Y$
$Y \times X$
$Y \times Y$
$X \times X$

We have either $X < Y$ or $Y ≤ X$.

Assumption 1a): $X < Y$
$AB$ has dimension $X \times X$, and this ordering is guaranteed to be optimal from a bottom-up approach. Any other configuration of $A$ and $B$ is either equally good, or worse. Thus, the problem is optimally solved as $(AB)^n$.

Assumption 1b): $Y ≤ X$
$BA$ has dimension $Y \times Y$. This is the optimal ordering for all products involving A and B. Thus, the solution is optimally found as $A(BA)^{n-1}*B$.

This concludes the proof, and we have only looked at the two orderings found in $ABAB$, the square problem.

Using more matrices, the argument is similar. Perhaps an inductive proof is possible? The general idea is that solving the MCM for the square will find the optimal size for the operations with all involved matrices considered.

1
source | link