1
$\begingroup$

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

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.