Question

What is the best order to form the product ABCD if A, B, C, and D are matrices with dimensions $\mathbf{30}\mathbf{\times }\mathbf{10}\mathbf{,}\mathbf{10}\mathbf{\times }\mathbf{40}\mathbf{,}\mathbf{40}\mathbf{\times }\mathbf{50}\mathbf{,}\mathbf{50}\mathbf{\times }\mathbf{30}$respectively?.

Short answer

A((BC)D)

First multiply B and C, then multiply this product with D and finally multiply A with this previous product.

Step-by-step solution

Given

Given:

A$30\times 10$matrix

B$10\times 40$matrix

C$40\times 50$matrix

D$50\times 30$matrix.

The matrix product ABCD can be determined in five ways:

$\left(\right(AB\left)C\right)D,\left(AB\right)\left(CD\right),\left(A\right(BC\left)\right)D,A\left(\right(BD\left)D\right),A\left(B\right(CD\left)\right)$(Note: we first multiply the two matrices in the most inner set of brackets).

Determine Multiplication

Multiplying a $p\times q$ matrix and a $q\times r$ matrix requires pqr multiplications.

AB requires $30\cdot 10\cdot 40=12000$multiplications.

BC requires$10\cdot 40\cdot 50=20000$multiplications.

CD requires$40\cdot 50\cdot 30=60000$multiplications.

Product of AB and C requires$30\cdot 40\cdot 50=60000$multiplications.

Product of A and BC requires$30\cdot 10\cdot 50=15000$multiplications.

Product of BC and D requires$30\cdot 10\cdot 30=9000$multiplications.

Product of B and CD requires $10\cdot 50\cdot 30=15000$multiplications.

Product of AB and CD requires role="math" localid="1668665662254" $10\cdot 40\cdot 30=12000$multiplications.

Product of ABC and D requires $30\cdot 50\cdot 30=45000$multiplications.

Product of A and BCD requires$30\cdot 10\cdot 30=9000$multiplications.

Combining this information, we can determine the number of multiplications required for each matrix product (Note: The product in the most inner set of brackets occur first, then the product in the outer set of brackets and then the remaining two products):

(AB)C)D requires $12000+60000+45000=117000$multiplications.

(AB)(CD) requires $12000+60000=72000$multiplications.

(A(BC))D requires $20000+15000+45000=80000$multiplications.

A((BC)D) requires $20000+15000+9000=44000$multiplications.

A(B(CD)) requires $60000+12000+9000=81000$multiplications.

Thus A((BC)D) requires the least number of multiplications.