# Matrix Chain Multiplication

### Efficient way to multiply a chain of matrices

The idea of this algorithm is to find the most efficient way to multiply a chain (sequence) of matrices. Because matrix multiplication is associative there can be more than one way of multiplying the chain of matrices.
Matrices: ( A1, A2, A3 )
Ways
( ( A1 . A2 ) . A3 )
( A1 . ( A2 . A3 ) )

Note : Matrix A1 can be multiplied with Matrix A2 only if number of columns of A1 is equal to number of rows of A2. Similarly A2 can be multiplied with A3 if number of columns in A2 is same as the number of rows in A3.

Example of Matrix Chain Multiplication

Matrices : A1 dimensions: ( 3 * 5 ) , A2 dimensions: ( 5 * 4 ) and A3 dimensions: ( 4 * 6 )
Option 1 : ( ( A1 . A2 ) . A3 ) = ( ( 3 * 5 ) . ( 5 * 4 ) ) . ( 4 * 6 )
Option 2 : ( A1 . ( A2 . A3 ) ) = ( 3 * 5 ) . ( ( 5 * 4 ) . ( 4 * 6) )

Steps Option 1 Option 2
1 Multiplication operations ( 3 * 5 ) . ( 5 * 4 ) = 3 . 5 . 4 = 60 Multiplication operations ( 5 * 4 ) . ( 4 * 6 ) = 5 . 4 . 6 = 120
2 Resultant matrix ( 3 * 5 ) . ( 5 * 4 ) = ( 3 . 4 ) Resultant matrix ( 5 * 4 ) . ( 4 * 6 ) = ( 5 . 6 )
3 Multiplication operations ( 3 * 4 ) . ( 4 * 6 ) = 3 . 4 . 6 = 72 Multiplication operations ( 3 * 5 ) . ( 5 * 6 ) = 3 . 5 . 6 = 90
4 Resultant matrix ( 3 * 4 ) . ( 4 * 6 ) = ( 3 . 6 ) Resultant matrix ( 3 * 5 ) . ( 5 * 6 ) = ( 3 . 6 )
5 Total Operations = 60 + 72 = 132 Total Operations = 120 + 90 = 210

Option 1 is clearly efficient than Option 2.

Generalizing based on the above example, consider

Matrices Dimensions
A1 (Rows) P0 X (Columns) P1
A2 (Rows) P1 X (Columns) P2
A3 (Rows) P2 X (Columns) P3
AN (Rows) PN-1 X (Columns) PN
```Let M[1, N] represents the minimum number of multiplications needed for computing the product of A1, A2, ..., AN.

M[1, N] = minimum of ( M[1, 1] + M[2, N] + P0 . P1 . PN ,
M[1, 2] + M[3, N] + P0 . P2 . PN ,
M[1, 3] + M[4, N] + P0 . P3 . PN ,
...
M[1, N-1] + M[N, N] + P0 . PN-1. PN )
```

M[1, 1] + M[2, N] + P0 . P1 . PN indicates A1 . ( A2 . A3 … AN )
The multiplication A1 . ( A2 . A3 … AN ) cancels out P2, P3, P4, …, PN-1.
M[1, 2] + M[3, N] + P0 . P2 . PN indicates ( A1 . A2 ) . ( A3 … AN )
The multiplication ( A1 . A2 ) . ( A3 … AN ) cancels out P3, P4, …, PN-1.

M[1, N-1] + M[N, N] + P0 . PN-1 . PN indicates ( A1 . A2 . A3 . AN-1 ) . AN
The multiplication ( A1 . A2 . A3 . AN-1 ) . AN cancels out P1, P2, …, PN-2.

Thus we can generalize
For k from i upto j-1
M[ i, j ] = min ( M[ i, k ] + M[ k+1, j ] + P[ i-1 ] . P[ k ] . P[ j ] )

Below is an example of bottom up calculations for finding the minimum number of multiplication operations needed for multiplying the matrices Number of multiplications needed for matrices chain of length 1 is 0.

```M[1,1] = 0, M[2,2] = 0, M[3,3] = 0, M[4,4] = 0
```

Finding the least number of multiplication needed for matrices chain of length 2

```for(1<=k<2)  M[1,2]  = min( M[1,1] + M[2,2] + P0.P1.P2 i.e 0 + 0 + 5.4.6 = 120 ) = min(120) = 120
for(2<=k=2)  M[2,3]  = min( M[2,2] + M[3,3] + P1.P2.P3 i.e 0 + 0 + 4.6.2 = 48 )  = min(48) = 48
for(3<=k<4)  M[3,4]  = min( M[3,3] + M[4,4] + P2.P3.P4 i.e 0 + 0 + 6.2.7 = 84 )  = min(84) = 84
```

Finding the least number of multiplication needed for matrices chain of length 3

```for(1<=k<3)  M[1,3]  = min( ( M[1,1] + M[2,3] + P0.P1.P3 ) i.e 0 + 48 + 5.4.2 = 88 ,                            ( M[1,2] + M[3,3] + P0.P1.P3 ) i.e 120 + 0 + 6.5.2 = 180 ) = min(88, 180) = 88
for(2<=k<4)  M[2,4]  = min( ( M[2,2] + M[3,4] + P1.P2.P4 ) i.e 0 + 84 + 4.6.7 = 252,                            ( M[2,3] + M[4,4] + P1.P3.P4 ) i.e 48 + 0 + 4.2.7  = 104 ) = min(252, 104) = 104
```

Finding the least number of multiplication needed for matrices chain of length 4

```for(1<=k<4)  M[1,4]  = min( ( M[1,1] + M[2,4] + P0.P1.P4 ) i.e 0 + 104 + 5.4.7 = 244,                            ( M[1,2] + M[3,4] + P0.P2.P4 ) i.e 120 + 84 + 5.6.7 = 414,                            ( M[1,3] + M[4,4] + P0.P3.P4 ) i.e 88 + 0 + 5.2.7 = 158 ) = min(244, 414, 158) = 158
```

Time complexity of matrix chain multiplication : O(n^3), where n is the number of matrices.

C++ : Implementation of matrix chain multiplication using dynamic programming in C++11

``````#include<iostream>
#include<vector>
#include<map>

using namespace std;
typedef vector<int> VI;
int max_val = 99999999;

class Matrix{

public:
// Below function computes the minimum number of multiplications needed to find the product of the chain of matrices in bottom up fashion

int MatrixChainMultiplication (vector<int> p) {

//Number of matrices
int N = p.size()-1;

// We want to return M[N] as the optimal cost of product of multiplying 1..N matrices
int M[N+1][N+1];

// Multiplications needed for a single matrix is 0
for (int i=1; i<=N; i++) {
M[i][i] = 0;
}

// Loop from chain len of size 2 upto the N (number of matrices)
for (int len=2; len <= N; len++) {
/* Chain of length 2 [A1,A2], [A2,A3] and [A3,A4]
Chain of length 3 [A1,A2,A3] and [A2,A3,A4]
Chain of length 4 [A1,A2,A3,A4]
For example: For a chain of length 2, i goes from 1 upto 3 and j goes from 2 upto 4
i  j
A1 A2
A2 A3
A3 A4
*/
for (int i=1; i <= N-len+1; i++) {
int j = i+len-1;
M[i][j] = max_val;
for (int k=i; k<=j-1; k++) { // Since i<=k<j, k goes from i upto j-1;
int q = M[i][k] + M[k+1][j] + p[i-1]*p[k]*p[j];
if (M[i][j] > q){
M[i][j] = q;
}
}
}
}
return M[N];
}
};

int main(){

Matrix m;
vector<int> dimensions1 = {40, 20, 30, 10, 30}; // 26000
cout << m.MatrixChainMultiplication (dimensions1) << endl;

vector<int> dimensions2 = {10, 20, 30, 40, 30}; // 30000
cout << m.MatrixChainMultiplication (dimensions2) << endl;

vector<int> dimensions3 = {10, 20, 30}; // 6000
cout << m.MatrixChainMultiplication (dimensions3) << endl;

vector<int> dimensions4 = {5, 4, 6, 2, 7}; // 158
cout << m.MatrixChainMultiplication (dimensions4) << endl;

return 0;
};
``````

Output showing the minimum number of multiplications needed to multiply the chain of matrices using dynamic programming

``````26000
30000
6000
158
``````