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 ?

  • 0
    @Marcva$n$Leeuwen sure $y$ou can .But I encountered this problem while tr$y$ing 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
    @DennisGulko: I think the OP is motivating the question by writing that all ways to parenthesize give the same product.2012-09-03