Lowest number of Matrix multiplication

Question

I have to find the lowest number of multiplications needed to multiply these Matrixes $A_1$ (11x15) $A_2$ (15x8) $A_3$ (8x15) $A_4$ (15x18)

So I did something like $A_1(A_2(A_3A_4)) = 7290$

$(A_1A_2)(A_3A_4)= 5064$

$A_1((A_2A_3)A_4)= 8820$

$((A_1A_2)A_3)A_4=5610$

$(A_1(A_2A_3))A_4)=7245$

So the lowest number would be 5064 Am i doing this wrong?

Answer 1

I checked your results , they are correct.

They are always 3 adjacent matrices products ordered from 1 to 3. Let identify the products by this index, they are 6 but 2 are equivalent.

$123$ : $OP[( (M_m^n M_n^p ) M_p^n ) M_n^q] = n mp + OP[( M_m^p M_p^n ) M_n^q] = n mp + p mn + OP[M_m^n M_n^q] = n mp + p mn + n mq$

$132$ : $OP[(M_m^n M_n^p) (M_p^n M_n^q )] = n mp + OP[(M_p^n M_n^q )] = nmp + npq + OP[M_m^p M_p^q ] = n mp + n pq + p mq$

$312$ : $( M_m^n M_n^p ) ( M_p^n M_n^q )$ identical to the previous

$213$ : $OP[(M_m^n ( M_n^p M_p^n )) M_n^q] = p nn + OP[(M_m^n M_n^n ) M_n^q] = p nn + n mn + OP[M_m^n M_n^q ] = p nn + n mn + n mq$

$231$ : $OP[M_m^n ((M_n^p M_p^n) M_n^q))] = p nn + OP[M_m^n (M_n^n) M_n^q)] = p nn + n nq + OP[M_m^n M_n^q] = p nn + n nq + n mq$

$321$ : $OP[M_m^n ( M_n^p ( M_p^n M_n^q ) )] = n pq + OP[M_m^n ( M_n^p M_p^q) ] = n pq + p nq + OP[ M_m^n M_n^q ] = n pq + p nq + n mq$

copy past in scratchpas of firefox and then type (Ctrl+L) to show the result

var res , m=11 , p=8 , n=15 , q= 18 ,
A = n*m*p + p*m*n + n*m*q ,
B = n*m*p + n*p*q + p*m*q ,
C = p*n*n + n*m*n + n*m*q ,
D = p*n*n + n*n*q + n*m*q ,
E = n*p*q + p*n*q + n*m*q ;

res = A+" "+B+" "+C+" "+D+" "+E ;


/*
5610 5064 7245 8820 7290
*/

$(M_m^n M_n^p) (M_p^n M_n^q ) = 5064$ is the lower way to compute, as you found.