<p>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.</p>

CC BY-SA 3.0
2014-05-12T09:12:22.627Z
2014-05-12T09:12:22.627Z
david
<p>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$.</p>

<p>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|$.</p>

<p>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 <a href="http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma" rel="nofollow">Schwartz–Zippel lemma</a>?</p>

<p>this is a tentative proof:</p>

<p>$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</p>

<p>$(*)$  $v_{\ell}= - \frac{1}{d_{\ell,c}}\sum_{\substack{j=1\\ j\neq \ell}}^{n}v_{j}
   d_{j,c}$</p>

<p>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\}$</p>

<p>Partition $S^n$ putting for each $(r_{1},\dots,r_{n-1})\in S^{n-1}$</p>

<p>$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}\}$</p>

<p>By total probability law and $E\subset E_\ell$</p>

<p>$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}})$</p>

<p>Finally</p>

<p>$P(E_\ell~|~ A_{r_{1},\dots,r_{n-1}})= P\left( \left\{s\in S\colon s=
        \frac{-(\sum_{j&lt;\ell} r_jd_{j,\ell} + \sum_{j&gt;\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|}.$</p>

CC BY-SA 3.0
2014-05-11T22:08:04.840Z
why do you find this question interesting?
greg
CC BY-SA 3.0
2014-05-11T23:39:30.060Z
this question is a natural generalization of the result, besides give at first better bounds on error.
Yair
<randomized-algorithms>
Freivalds matrix multiplication with non binary random vector
Yair
# Freivalds matrix multiplication with non binary random vector

(Asked by: username_0 on 2014-05-11)

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](http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_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|}.$

**Tags:** randomized-algorithms

> **Comments:**
> **username_1**: why do you find this question interesting?  
> **username_0**: this question is a natural generalization of the result, besides give at first better bounds on error.  

---

## 1 answers

### Answer by username_2 on 2014-05-12. Score: 5 | Accepted answer

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.


---

