# linear algebra – 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.