6
$\begingroup$

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 ?

  • 1
    I don't think that the fact that the factors are matrices is relevant to this question. May I remove the "matrices" tag?2012-09-03
  • 0
    @MarcvanLeeuwen sure you can .But I encountered this problem while trying to find out the productof matrices2012-09-03

1 Answers 1

10

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.

  • 0
    @André Nicolas can you include the recurrence in your answer?2012-09-03
  • 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.2012-09-03
  • 0
    @Geek: You can find the recurrence [in the article linked to](http://en.wikipedia.org/wiki/Catalan_number#First_proof). 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).2012-09-03
  • 0
    @DennisGulko: I think the OP is motivating the question by writing that all ways to parenthesize give the same product.2012-09-03