Q$1$ Matrix Multiplication

We are given six matrices $A_1,A_2,A_3,A_4,A_5$ and $A_6$ for which we wish to compute the product

$A=A_1*A_2*A_3*A_4*A_5*A_6$ where $A_i$ is a $d_{i-1}{d}_i$ matrix. Since matrix multiplication is

associative we can parenthesize the expression for A any way we wish and we will end up with the

same result. What is the minimum number of scalar multiplications we have to perform if $d_0=3,$

$d_1=4,d_2=6,d_3=4,d_4=2,d_5=3$ and $d_6=5?$ How do we parenthesize the expression for $A$

to achieve this number? In subquestions $1\mathrm{.}1-1\mathrm{.}5$ you should provide the entries of the dynamic

programming table $M[i,j]$ as stated; recall that $M[i,j],$ for $j>i,$ holds the minimum number of

multiplications required for computing the product $A_i*A_{i+1}*dots*A_j.$

Q$1\mathrm{.}1$

Give the values of M$[$i$,$i$+1]$ for i$=1,...,5$ separated by a single blank symbol.

Q$1\mathrm{.}2$

Give the values of M$[$i$,$i$+2]$ for i$=1,...,4$ separated by a single blank symbol.

Q$1\mathrm{.}3$

Give the values of M$[$i$,$i$+3]$ for i$=1,...,3$ separated by a single blank symbol.

Q$1\mathrm{.}4$

Give the values of M$[1,5]$ and M$[2,6]$ separated by a single blank symbol.

Q$1\mathrm{.}5$

Give the value of M$[1,6].$

Q$1\mathrm{.}6$

How do you place the parentheses to compute A by the minimum number of scalar multiplications? For multiplication from left to right write $(((($A$1$A$2)$A$3)$A$4)$A$5)$A$6.$

Q$1\mathrm{.}7$

How many ways to place the paratheses to compute A are there that achieve the minimum number of scalar multiplications?