Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We have a finite number of matrices that we wish to compute the product of . Say we wish to compute a product of n matrices and we have the subroutine to compute a pair of matrices . We also know that matrix products are associative ie :

$\left({\mathbf A \mathbf B}\right) \mathbf C$ and $\mathbf A \left({\mathbf B \mathbf C}\right)$ are same .

$$A_1A_2A_3...A_n$$

So what are the number of ways in which we can parenthesize the product ?

share|improve this question
    
I don't think that the fact that the factors are matrices is relevant to this question. May I remove the "matrices" tag? –  Marc van Leeuwen Sep 3 '12 at 11:46
    
@MarcvanLeeuwen sure you can .But I encountered this problem while trying to find out the productof matrices –  Geek Sep 3 '12 at 11:47

1 Answer 1

up vote 5 down vote accepted

If you have $n+1$ matrices, the number of ways is the Catalan number $C_n$. The number $C_n$ is given by the explicit formula $$C_n=\frac{1}{n+1}\binom{2n}{n}.$$ This particular example is the third one in the aticle linked to, in the "Applications to Combinatorics" part. It is not hard to verify that the number of ways to parenthesize $n+1$ matrices (or a product of any kind) satisfies the basic recurrence for the Catalan numbers.

share|improve this answer
    
@André Nicolas can you include the recurrence in your answer? –  Geek Sep 3 '12 at 9:47
1  
@DennisGulko: It seems that the OP intended to demonstrate associativity in $(AB)C=A(BC)$, and not to indicate that these two different ways of parenthesizing should be counted only once. –  Teddy Sep 3 '12 at 10:21
    
@Geek: You can find the recurrence in the article linked to. It's amazing how far down you need to go to find the defining recurrence in this article (as I think is true for other combinatorial numbers in Wikipedia). –  Marc van Leeuwen Sep 3 '12 at 11:50
    
@DennisGulko: I think the OP is motivating the question by writing that all ways to parenthesize give the same product. –  André Nicolas Sep 3 '12 at 13:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.