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.