# What is the most general structure on which matrix product verification can be done in $O(n^2)$ time?

In 1979, Freivalds showed that verifying matrix products over any field can be done in randomized $O(n^2)$ time. More formally, given three matrices A, B, and C, with entries from a field F, the problem of checking whether AB = C has a randomized $O(n^2)$ time algorithm.

This is interesting because the fastest known algorithm for multiplying matrices is slower than this, so checking if AB = C is faster than computing C.

I want to know what is the most general algebraic structure over which matrix product verification still has an $O(n^2)$ time (randomized) algorithm. Since the original algorithm works over all fields, I guess it works over all integral domains too.

The best answer I could find to this question was in Subcubic Equivalences Between Path, Matrix, and Triangle Problems, where they say "matrix product verification over rings can be done in $O(n^2)$ randomized time [BK95]." ([BK95]: M. Blum and S. Kannan. Designing programs that check their work. J. ACM, 42(1):269–291, 1995.)

First, are rings the most general structure on which this problem has an $O(n^2)$ randomized algorithm? Second, I couldn't see how the results of [BK95] show an $O(n^2)$ time algorithm over all rings. Can someone explain how that works?

• A stupid question: is it obvious that deterministic verification is as hard as multiplication? What if you are given not only A, B, and C but also a compact certificate; does it help anything? – Jukka Suomela Apr 7 '11 at 21:16
• @Jukka: I believe the best deterministic algorithm for this problem is no faster than matrix multiplication, but I don't know if there is a reason why this should be the case. About the second question, if AB is not equal to C, then there is a short certificate that works: the entry of C that is incorrect, and the corresponding row of A and column of B. – Robin Kothari Apr 8 '11 at 5:17

Here's a quick argument for why it works over rings. Given matrices $A$, $B$, $C$, we verify $A B = C$ by picking a random bit vector $v$, then checking if $ABv = Cv$. This clearly passes if $AB = C$.
Suppose $AB \neq C$ and $ABv = Cv$. Let $D = AB - C$. $D$ is a nonzero matrix for which $Dv = 0$. What's the probability that this occurs? Let $D[i',j']$ be a nonzero entry. By assumption, $\sum_{j} D[i',j] v[j] = 0$. With probability $1/2$, $v[j'] = 1$, so we have
$D[i',j'] + \sum_{j\neq j'} D[i',j] v[j] = 0$.
Any ring under its addition operation is an additive group, so there is a unique inverse of $D[i',j']$, i.e., $-D[i',j']$. Now, the probability of the bad event $-D[i',j'] = \sum_{j\neq j'} D[i',j] v[j]$ is at most $1/2$. (One way to see this is the "principle of deferred decisions": in order for the sum to equal $-D[i',j']$, at least one other $D[i',j]$ must be nonzero. So consider the $v[j]$'s corresponding to these other nonzero entries. Even if we set all of these $v[j]$'s except for one of them optimally, there is still equal probability for the last one being $0$ or $1$, but still only one of these values could make the final sum equal to $-D[i',j']$.) So with probability at least $1/4$, we successfully find that $Dv \neq 0$, when $D$ is nonzero. (Note $v[j]$ and $v[j']$ are independently chosen for $j \neq j'$.)
• Freivalds' algorithm picks a random vector with components in {-1,1}. That works too. If you are more careful you can get the probability of success to be at least $1/2$. – Ryan Williams Apr 8 '11 at 23:02