Answer to Question 2-2

Question. Suppose that A = [a_{i, j}] and B = [b_{i, j} are two n×n matrices. (Notation A = [a_{i, j}] is just a way of saying that the entry in row i and column j of A is a_{i, j}.) The matrix product C = AB is an n×n matrix defined by C = [c_{i, j}] where c_{i, j} = ∑ⁿ_k=1a_{i, k}b_{k, j}.

Notice that there are n² entries of matrix C to compute. Each involves computing a sum of n products of numbers.

Can we argue that computing the product of two n×n matrices requires time Θ(n³) time based on this?

Answer. No. This algorithm does take Θ(n³) time. But it is not at all obvious that there cannot be better algorithms.