Product of the entries of the product of two matrices

Question

Let $A=(a_{ij})$ and $B=(b_{ij})$ be $n \times n$ integer matrices. Then $AB=(\Sigma_{k=1}^n a_{ik}b_{kj})_{ij}$. I am interested in finding the most efficient algorithm for computing the product of the entries of $AB$,

$\Pi_{i,j=1}^n (\Sigma_{k=1 }^n a_{ik}b_{kj}$).

Certainly, the most straightforward way of doing this (by using the above formula) is not the most efficient way of doing this, since there are algorithms like Strassen's algorithm which calculate all of the entries of the matrix $AB$ faster than simply applying the definition $AB=(\Sigma_k a_{ik}b_{kj})_{ij}$ to each entry.

Are there other efficient ways to compute the above product besides using algorithms like Strassen's algorithm?

Extra: What about computing the sum of the entries of $AB$,

$\Sigma_{i,j,k=1}^n a_{ik}b_{kj}$?

Answer 1

You are asking two questions. I will only answer the second one. Let $1$ be the all ones column vector of dimension $n$. The sum of all entries of $AB$ is $1^TAB1 = (1^TA)(B1)$, which gives an $O(n^2)$ algorithm: compute the vectors $1^TA$ and $B1$, each in $O(n^2)$, and then compute their inner product in $O(n)$. This corresponds to the identity $$ \sum_{i,j,k=1}^n a_{ik} b_{kj} = \sum_{k=1}^n \left(\sum_{i=1}^n a_{ik}\right) \left(\sum_{j=1}^n b_{kj}\right). $$

As for the product of all entries, I suspect you can't do better than the trivial algorithm which first computes the entire product matrix, and runs in time $O(n^\omega)$.