GATE Civil 2013 | Question: 2

Question

What is the minimum number of multiplications involved in computing the matrix product $PQR?$ Matrix P has $4$ rows an $2$ columns, matrix $Q$ has $2$ rows and $4$ columns, and matrix R has $4$ rows and $1$ column. __________

Answer 1

To find the minimum number of multiplications, we must compare the two possible parenthesizations: $(PQ)R$ and $P(QR)$.

Given Dimensions:

• $P$: $4 \times 2$

• $Q$: $2 \times 4$

• $R$: $4 \times 1$

Case 1: $(PQ)R$

1. Multiply $P$ and $Q$: The number of multiplications is $4 \times 2 \times 4 = 32$. The resulting matrix $(PQ)$ has dimensions $4 \times 4$.

2. Multiply $(PQ)$ and $R$: The number of multiplications is $4 \times 4 \times 1 = 16$.

3. Total Multiplications: $32 + 16 = \mathbf{48}$.

Case 2: $P(QR)$

1. Multiply $Q$ and $R$: The number of multiplications is $2 \times 4 \times 1 = 8$. The resulting matrix $(QR)$ has dimensions $2 \times 1$.

2. Multiply $P$ and $(QR)$: The number of multiplications is $4 \times 2 \times 1 = 8$.

3. Total Multiplications: $8 + 8 = \mathbf{16}$.

---

2. Final Answer

The minimum number of multiplications is 16.