Consider the matrix chain A1A2A3, where A1 has dimension 20 × 10, A3 has dimensi
ID: 3910974 • Letter: C
Question
Consider the matrix chain A1A2A3, where A1 has dimension 20 × 10, A3 has dimension 10 × 5 and A2 has dimension 5 × 3. Which of the following parenthesizations require the minimum number of scalar multiplications?
a. ((A1A2)A3)
b. All parenthesizations have the same number of scalar multiplications.
c.(A1(A2A3)
This chain of matrices cannot be parenthesized because the sequence of matrices is incompatible.
**dont swap A2 and A3**
d.This chain of matrices cannot be parenthesized because the sequence of matrices is incompatible.
**dont swap A2 and A3**
Explanation / Answer
(A) For ((A1A2)A3) the total number of scalar multiplications can not be determined as the dimensions of A1 and A2 are not compatible.
(B) This option is wrong as for two matrices of dimension mxn and nxp the total number of scalar multiplication required is mxnxp.
(C) For (A1(A2A3)) the total number of scalar multiplications can not be determined as the dimensions of A2 and A3 are not compatible. We can not swap A2 and A3 as matrix multiplication is not commutative. Which means for two matrices A and B there is A*B<>B*A.
(D) is CORRECT. This chain of matrices cannot be parenthesized because the sequence of matrices is incompatible. Also matrix multiplication is not commutative. Which means for two matrices A and B there is A*B<>B*A.
Hope this helps.