# Freivalds matrix multiplication with non binary random vector

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|}.$

• why do you find this question interesting? – mobius dumpling May 11 '14 at 22:08
• this question is a natural generalization of the result, besides give at first better bounds on error. – Yair May 11 '14 at 23:39

The answer to both questions is yes. The matrix $A B - C$ gives rise to a linear application over your field $\mathbb F$, which is a multivariate polynomial of total degree $d=1$. By the Schwartz-Zippel lemma, when $x$ is drawn from $S^n$ (where $S \subseteq {\mathbb F}$), the probability that $(A B - C) x = 0$ is at most $d/|S| = 1/|S|$, provided that $A B \neq C$. As you observe, this can also be proved directly using the standard argument for Freivald's algorithm.