geeksforgeeks

Question

Let A1, A2, A3, and A4 be four matrices of dimensions 10 x 5, 5 x 20, 20 x 10, and 10 x 5, respectively. The minimum number of scalar multiplications required to find the product A1A2A3A4 using the basic matrix multiplication method is:  

(A)  1500  

(B)  2000  

(C)  500  

(D)  100

Comments

Answer is 1500.

Refer this: https://gateoverflow.in/39587/gate-cse-2016-set-2-question-38

Answer 1

In matrix multiplication, the number of scalar multiplications required is equal to the product of the dimensions involved. For example, if we want to multiply two matrices A (m × n) and B (n × p), the number of scalar multiplications required is m × n × p.

Given:
- A1 has dimensions 10 × 5
- A2 has dimensions 5 × 20
- A3 has dimensions 20 × 10
- A4 has dimensions 10 × 5

To find the product A1A2A3A4, we need to perform the multiplications in the following order:
1. A3A4 (20 × 10 and 10 × 5)
2. A2(A3A4) (5 × 20 and 20 × 5)
3. A1(A2(A3A4)) (10 × 5 and 5 × 5)

Let's calculate the number of scalar multiplications required for each step:
1. A3A4: 20 × 10 × 5 = 1000
2. A2(A3A4): 5 × 20 × 5 = 500
3. A1(A2(A3A4)): 10 × 5 × 5 = 250

The total number of scalar multiplications required is the sum of these three steps:
1000 + 500 + 250 = 1750

but this is not the minimum number of scalar multiplications.

if we change the order of multiplications and try to eliminate bigger n in A(mxn).B(nxp) then we will get fewer number of scalar multiplications.

To find the product A1A2A3A4 with changed order of multiplication, we need to perform the multiplications in the following order:
1. A2A3 (5 × 20 and 20 × 10)
2. (A2A3)A4 (5 × 10 and 10 × 5)
3. A1((A2A3)A4) (10 × 5 and 5 × 5)

Let's calculate the number of scalar multiplications required for each step:
1. A3A4: 5 × 20 × 10 = 1000
2. A2(A3A4): 5 × 10 × 5 = 250
3. A1(A2(A3A4)): 10 × 5 × 5 = 250

The total number of scalar multiplications required is the sum of these three steps:
1000 + 250 + 250 = 1500

Therefore, the minimum number of scalar multiplications required to find the product A1A2A3A4 using the basic matrix multiplication method is 1500.

Comments

1500 is the answer:

https://gateoverflow.in/39587/gate-cse-2016-set-2-question-38

---

yes you are right, I didn't thought about changing the order of multiplication. thanks for pointing out the error in my solution. I will correct it now.