<p>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$. </p>

<p>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&#39;,j&#39;]$ be a nonzero entry. By assumption, $\sum_{j} D[i&#39;,j] v[j] = 0$. With probability $1/2$, $v[j&#39;] = 1$, so we have </p>

<p>$D[i&#39;,j&#39;] + \sum_{j\neq j&#39;} D[i&#39;,j] v[j] = 0$.</p>

<p>Any ring under its addition operation is an additive group, so there is a unique inverse of $D[i&#39;,j&#39;]$, i.e., $-D[i&#39;,j&#39;]$. Now, the probability of the bad event $-D[i&#39;,j&#39;] = \sum_{j\neq j&#39;} D[i&#39;,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&#39;,j&#39;]$, at least one other $D[i&#39;,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  <em>optimally</em>, 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&#39;,j&#39;]$.)
So with probability at least $1/4$, we successfully find that $Dv \neq 0$, when $D$ is nonzero. (Note $v[j]$ and $v[j&#39;]$ are independently chosen for $j \neq j&#39;$.)</p>

<p>As you see, the above argument depends on subtraction. So it won't work (for example) on arbitrary commutative semirings. Perhaps you could relax the multiplicative properties of the algebraic structure, and still get the result?</p>

CC BY-SA 3.0
2011-04-08T18:20:02.067Z
Nice, thanks. I see your point about there being a possibility of reducing the constraints on the multiplicative structure. Just for my information, isn't this the same algorithm as that in the original paper of Freivalds?
Robin Kothari
CC BY-SA 3.0
2011-04-08T23:02:12.873Z
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
CC BY-SA 2.5
2011-04-07T21:47:25.000Z
2011-04-07T21:52:53.967Z
2011-04-07T21:52:53.967Z
Ryan Williams
<p>In 1979, <a href="https://doi.org/10.1007/3-540-09526-8_5" rel="nofollow noreferrer">Freivalds</a> showed that verifying matrix products over any field can be done in randomized <span class="math-container">$O(n^2)$</span> 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 <span class="math-container">$O(n^2)$</span> time algorithm.</p>
<p>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.</p>
<p>I want to know what is the most general algebraic structure over which matrix product verification still has an <span class="math-container">$O(n^2)$</span> time (randomized) algorithm. Since the original algorithm works over all fields, I guess it works over all integral domains too.</p>
<p>The best answer I could find to this question was in <a href="http://www.eecs.berkeley.edu/%7Evirgi/tria-mmult-conf.pdf" rel="nofollow noreferrer">Subcubic Equivalences Between Path, Matrix, and Triangle Problems</a>, where they say &quot;matrix product verification over rings can be done in <span class="math-container">$O(n^2)$</span> randomized time [BK95].&quot; ([BK95]: M. Blum and S. Kannan.  <a href="https://dl.acm.org/doi/10.1145/73007.73015" rel="nofollow noreferrer">Designing programs that check their work.</a> J. ACM, 42(1):269–291, 1995.)</p>
<p>First, are rings the most general structure on which this problem has an <span class="math-container">$O(n^2)$</span> randomized algorithm? Second, I couldn't see how the results of [BK95] show an <span class="math-container">$O(n^2)$</span> time algorithm over all rings. Can someone explain how that works?</p>

CC BY-SA 2.5
2011-04-07T21:16:33.737Z
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
CC BY-SA 3.0
2011-04-08T05:17:33.997Z
@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
<ds.algorithms><linear-algebra><matrix-product>
What is the most general structure on which matrix product verification can be done in $O(n^2)$ time?
Robin Kothari
# What is the most general structure on which matrix product verification can be done in $O(n^2)$ time?

(Asked by: username_0 on 2011-04-07)

In 1979, [Freivalds](https://doi.org/10.1007/3-540-09526-8_5) 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](http://www.eecs.berkeley.edu/%7Evirgi/tria-mmult-conf.pdf), 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.](https://dl.acm.org/doi/10.1145/73007.73015) 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?

**Tags:** ds.algorithms, linear-algebra, matrix-product
> **Comments:**
> **username_1**: 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?  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_2 on 2011-04-07. Score: 17 | Accepted answer

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'$.)

As you see, the above argument depends on subtraction. So it won't work (for example) on arbitrary commutative semirings. Perhaps you could relax the multiplicative properties of the algebraic structure, and still get the result?

> **Comments:**
> **username_0**: Nice, thanks. I see your point about there being a possibility of reducing the constraints on the multiplicative structure. Just for my information, isn't this the same algorithm as that in the original paper of Freivalds?  
> **username_2**: 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$.  

---

