Matrix Chain

Question

Total no. of ways to perform matrix multiplication having 7 matrices is ?

Total no. of ways to by which we  could parenthesize 7 matrices is ?

Does the above two questions are different or same ?

Plz explain the answer.

Comments

total number of ways to multiply n matrix = (n-1)th catalan number = $\frac{\binom{2(n-1)}{(n-1)}}{n}$

---

That is correct for no of ways to perform multiplication ?Am I correct?

But what is the answer for "Total no. of ways to parenthesize" .

Answer 1

Both are same questions.

Let's solve the question.

1. if there are two matrices A & B, there are only 1 way to multiply them as AxB
2. If there are three matrices A, B and C then there are 2 ways as (A(BC)) and ((AB)C)
3. If there are 4 matrices A,B,C and D then
 (A(BCD)) = 2 ways, as three matrices B, C, & D can be multiplied 2 ways as shown above.
OR
((AB)(CD)) = 1 way
OR
((ABC)D) = 2 ways
there are total 5 ways to multiply 4 matrices.
4. If there are 5 matrices A, B, C, D and E then
(A(BCDE)) = 5 ways
((AB)(CDE)) = 2 ways
((ABC)(DE)) = 2 ways
((ABCD)E)) = 5 Ways
total = 14 ways.
5. If there are 6 matrices A,B,C,D,E and F then
(A(BCDEF)) = 14 ways
((AB)(CDEF)) = 5 ways
((ABC)(DEF)) = 2x2 = 4 ways
((ABCD)(EF)) = 5 ways
((ABCDE)F) = 14 ways
total = 14 + 5 + 4 + 5 +14 = 42 ways.

6. if there are 7 matrices, A,B,C,D,E,F, and G then
(A(BCDEFG)) = 42 ways
((AB(CDEFG)) = 14 ways
((ABC)(DEFG)) = 2x5 = 10 ways
((ABCD)(EFG)) = 5x2=10 ways
((ABCDE)(FG)) = 14 ways
((ABCDEF)G) = 42 ways
Total = 42+14+10+10+14+42 = 132 ways
  

Comments

Any formula as it will be time consuming in the exam ?

---

formula is already in the best answer...

---

why there is n-1 is taken in catalan number?

in number of binary search tree we take catalan number =n

Answer 2

2n!/n!*(n+1)! Where n=number of matrices -1

Answer 3

Both are different questions.

1- the number of ways to perform matrix multiplication is 132.

As we have direct formula for this.

(2n!)/(n+1)!*n!

If we have 7 matrix then n should be 6.

2- number of ways to parenthesis means at starting how many ways we can split the matrix.

For 3 matrix we can split 2 ways

For 4 we can split 3 ways.

Thus for 7 matrix we can split or parenthesis 6 ways.

Comments

Suraj123  

For 3 matrix we can split 2 ways

For 4 we can split 3 ways.

Thus for 7 matrix we can split or parenthesis 6 ways.

 How??

Answer 4

The question can also be solved by recurrence relation.

T(n) = T(1)T(n-1)+T(2)T(n-2).......T(n-1)T(1)

T(0)=1

T(1)=1

T(2)=1

T(3)=2

T(4)=5

T(5)=14

T(6)=42

T(7)=132