Correctness of Freivald algorithm for checking matrix multiplication, why is the probability of checking $AB \neq C$ at least 1/2?

Question

I am going to consider Freivald's algorithm in the field mod 2. So in this algorithm we want to check wether $$AB = C$$ and be correct with high probability.

The algorithm choose a random $r$ n-bit vector and if $$A(Br) = Cr$$ then outputs YES, otherwise outputs no.

I want to show that it has has one-sided success probability 1/2. For that I want to show that when $AB = C$ then the algorithm is correct with probability 1 and when $AB \neq C$ then the probability of it being correct is at least 1/2.

When $AB = C$ its clear that the algorithm is always correct because:

$$ A(Br) = (AB)r = Cr$$

So, if $AB=C$, then $A(Br)$ is always equal to $Cr$.

The case when $AB \neq C$ is a little trickier. Let $D = AB - C$. When the multiplication are not equal then $D \neq 0$. Let a good $r$ be a vector that discovers the incorrect multiplication (i.e. $D \neq 0$ and $Dr \neq 0$, multiplying by $r$ makes it still zero). let a bad $r$ be a vector that makes us mess up, i.e. conclude the multiplication is correct when is not. In other words, when $D \neq 0$ (i.e. multiplication was done correctly $AB = C$) but when we use $r$ to check this we get the wrong conclusion (i.e. $Dr = 0$, when in fact $D \neq 0$).

The high level idea of the proof is, if we can show that for every bad $r$ there is a good $r$, then half the $r$'s are good so our algorithm is about 1/2 percent of the time correct. This high level idea of the proof makes sense to me, however, what is not clear to me is the precise detail of the inequality (whether $Pr[error] \geq \frac{1}{2}$ or the other way round).

So consider the case where $D \neq 0 $ i.e. $AB \neq C$. In this case then we have that at least one entry $(i,j)$ in $D$ is not zero (its 1 cuz we are doing mod 2). Let that entry be $d_{i,j}$. Let $v$ be a vector such that it picks up that entry. i.e. $Dv \neq 0$ such that $(Dv)_{i} = d_{i,j}$. In this case, if we have a bad $r$ (i.e. an r such that when $D \neq 0$ yields $Dr = 0$ ) then we could make it into a good vector $r'$ by flipping its $i$ coordinate. i.e.

$$ r' = r +v_i$$

This mapping from Bad to Good is clearly 1 to one. i.e. it clear that the equation $ r' = r +v_i$ only maps to one unique $r'$, so it cannot be one to many. Now lets see that its not many to one either. If there was another $\tilde r$ s.t. $\tilde r = r'$ then that would mean

$$r' = r+ v_i = \tilde r + v_i \;\; (\operatorname{mod} \; 2) \implies r = \tilde r \;\; (\operatorname{mod} \; 2)$$

So its one to one. Therefore, the for each Bad $r$ there is a good $r'$. However, it is not clear to me why that would imply:

$$ Pr[A(Br) \neq C] = Pr[Dr \neq 0] \geq \frac{1}{2}$$

I see why it would be exactly equal to 1 but it is not clear to me at all why it implies the above inequality.

Answer 1

Let $G$ be the number of good vectors, and $B$ be the number of bad vectors. The proof shows that $G \geq B$, since the mapping from the bad vectors to the good ones is one-to-one. Since all vectors are equally likely, $$ \Pr[Dr \neq 0] = \frac{G}{G+B} \geq \frac{1}{2}. $$ The last inequality is a bit of algebra I leave to you.

Answer 2

Let $D=[d_{k,l}]$. If $d_{i,j}\not=0$, then $Prob(Dr\not=0)\geq Prob(i^{th}$ line of $Dr$ is $\not=0)=1/2$.