Freivalds' algorithm verify matrices (over a field) product $A \times B = C$ by choosing a random binary vector $r$ and verifying if $A(Br)=Cr$ which fails if $AB \neq C$ with probability at most $1/2$.
It seems to me that it can be done by choosing $r$ in some set $S$ which include $0$ resulting that the algorithm fails with probability $\leq 1/|S|$.
All I could find about the algorithm uses binary vector; is the above approach possible? And, as another question, is it possible deduce Freivalds result from Schwartz–Zippel lemma?
this is a tentative proof:
$Dv= (AB-C)v = 0$ imply there exists $\ell, c$ such that $d_{\ell,c}\neq 0$ and $\sum_{j=1}^{n}v_{j} d_{j,c}=0$, thus
$(*)$ $v_{\ell}= - \frac{1}{d_{\ell,c}}\sum_{\substack{j=1\\ j\neq \ell}}^{n}v_{j} d_{j,c}$
Let $E=\big\{v \in S^{n}\colon {v}{D}={0}\big\}$ and $E_\ell = \left\{(v_1,v_2,\dots,v_n)\in S^{n}\colon (*)\right\}$
Partition $S^n$ putting for each $(r_{1},\dots,r_{n-1})\in S^{n-1}$
$A_{r_{1},\dots,r_{n-1}} = \{r_1\}\times \cdots \times \{r_{\ell-1}\} \times S \times \{r_{\ell}\} \times \cdots \times \{r_{n-1}\}$
By total probability law and $E\subset E_\ell$
$P(E) = \sum_{(r_{1},\dots,r_{n-1})}P(E\cap A_{r_{1},\dots,r_{n-1}})\leq$ $\sum_{(r_{1},\dots,r_{n-1})}P(E_\ell\cap A_{r_{1},\dots,r_{n-1}})=$ $\sum_{(r_{1},\dots,r_{n-1})}P(E_\ell~|~ A_{r_{1},\dots,r_{n-1}}) P(A_{r_{1},\dots,r_{n-1}})$
Finally
$P(E_\ell~|~ A_{r_{1},\dots,r_{n-1}})= P\left( \left\{s\in S\colon s= \frac{-(\sum_{j<\ell} r_jd_{j,\ell} + \sum_{j>\ell} r_{j-1}d_{j,\ell}) }{d_{\ell,c}} \right\}\right) \leq \frac 1{|S|}$ and $P(E)\leq \sum_{(r_{1},\dots,r_{n-1})}\frac 1{|S|} P(A_{r_{1},\dots,r_{n-1}}) =\frac 1{|S|}.$
