# Why is the probability of a false positive not 0 for Freivald's Algorithm?

Freivald's algorithm (see the wiki) is a randomized algorithm for verifying whether the product of two $$n \times n$$-matrices $$A$$ and $$B$$ yields a given matrix $$C$$ (i.e. $$AB = C$$). The way this task is accomplished is to introduce a random vector $$\vec{v} \in \mathbb{R}^{n}$$ and evaluate whether $$A(Bv) = Cv$$ The claim is that if $$AB \neq C$$, then $$AB v = Cv$$ with probability at most $$1/2$$, and they provide a justification. Their argument for why 1/2 works makes some sense to me. What I don't understand is why this bound can't be improved further by the following argument:

Claim: Suppose that $$AB \neq C$$. Then for almost all choices of $$v$$ (i.e. with probability $$1$$), $$AB v \neq Cv$$.

Proof of Claim: Note that $$AB v = Cv$$ if and only if $$(AB-C)v =0$$. Let $$D = AB-C$$. Then $$ABv = Cv$$ if and only if $$v \in \ker(D)$$. Since $$AB \neq C$$, $$D$$ is not the $$0$$-matrix meaning that $$\dim(\ker(D)) < n$$. Hence, $$\ker(D)$$ is a proper linear subspace of $$\mathbb{R}^{n}$$ and therefore has measure $$0$$. Thus, for almost all choices of $$v$$, $$D v \neq 0$$ meaning that $$ABv \neq Cv$$ with probability $$1$$.

Q.E.D.

Hence, if $$AB v = Cv$$, then $$AB = C$$ with probability $$1$$. Shouldn't this mean that the probability of failure in Freivald's algorithm is $$0$$ instead of $$2^{-k}$$?

Thanks.

• By definition, Freivald's algorithm chooses only vectors $v$ whose entries equal $0$ or $1$. In that setting, $\frac12$ is the best possible bound even over $\Bbb Q$. You could propose a variant of the algorithm and ask about bounds for that.... Jul 13, 2021 at 22:41
• Ah actually, this exists and is surprisingly recent. This arxiv post published in a journal in 2020 supplies such a variant: arxiv.org/pdf/1705.10449.pdf Jul 14, 2021 at 1:29

Algorithms can't work over $$\mathbb{R}^n$$, as you can't represent real numbers in finite space. Also, you can't pick a number uniformly at random from $$\mathbb{R}$$. Instead, usually we work over a finite field.

Then we can't do any better. Suppose we are working in the finite field with two elements, $$GF(2)$$. Suppose that

$$AB - C = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}.$$

Then it is easy to verify that Frievald's algorithm is wrong with probability $$1/2$$, as $$(AB-C)v = 0$$ holds with probability $$1/2$$ when we select $$v$$ uniformly at random. You can generalize this to a $$n\times n$$ matrix that is all zeros except for a single entry, and then the probability of false positive is $$1/2$$.

If you are working over $$\mathbb{Q}$$, then the same matrix $$AB-C$$ also provides a similar counterexample. As Greg Martin explains, Freivald's algorithm by definition chooses vectors uniformly at random from $$\{0,1\}^n$$, and then when $$v$$ is selected from this distribution, $$(AB-C)v=0$$ holds with probability $$1/2$$. (And if you are wondering whether it is possible to do better by choosing $$v$$ differently, there is no way to choose a number uniformly at random from $$\mathbb{Q}$$, so it's not clear what distribution you would use.)

• This is a good answer, and I appreciate it. However, in practice, I mainly multiply matrices over $\mathbb{Q}$. In that case, the same proof follows. In particular, when I perturb a LP for the simplex method to create nondegeneracy, I do exactly that and the justification also follows from hyperplanes being measure zero. Is there a reason why we should not do so in the rational case? Thanks again. Jul 13, 2021 at 19:04
• @KeimaKatsuragi, see edited answer.
– D.W.
Jul 13, 2021 at 22:52
• Wouldn't you do a lot better by choosing $v$ from $\{1,2\}^n$ instead? It seems obvious that you don't want the zero vector in the distribution since that's a guaranteed false positive, and zero entries in the vector more generally cause problems when the difference matrix has lots of zero entries like in your example. Jul 14, 2021 at 2:23
• @MarioCarneiro, nope, that doesn't help. Consider $$AB-C = \begin{pmatrix}0&0&0\\0&0&0\\1&-1&0\end{pmatrix}$$.
– D.W.
Jul 14, 2021 at 4:10
• @MarioCarneiro You can sure tinker with the probability in various ways. For example, choosing $v$ in $\{0,\dots,2^n-1\}^n$ will decrease the probability to $2^{-n}$. However, no matter what you do, the probability is not $0$ (it is inversely proportional to the size of the sample set for each coordinate), and there is a trade off in that choosing $v$ from a larger sample set will increase the size of the numbers involved in the computation, hence increase the complexity of the algorithm. Jul 14, 2021 at 7:55