Performing computations on matrices are one of the fundamental operations in numerical computing. In particular, if we want to multiply an matrix by an matrix, this operation has complexity, producing an matrix. Therefore, if we want to multiply several matrices in a chain, the cost of this operation depends on the sequence in which we perform the multiplications.
For example, assume that we have the following matrices:
- A having dimensions 10 x 40
- B having dimensions 40 x 10
- C having dimensions 10 x 50
And, we want to compute A*B*C. We can perform the computation either like this, (A*B)*C, or like this, A*(B*C). The cost of the first approach is proportional to 10*40*10+10*10*50=9000. The cost of the second approach is 40*10*50+10*40*50=40000. It is therefore evident that the order of operations has a significant...