Probabilistic test of matrix multiplication with one-sided error

Question

Given three matrices $A, B,C \in \mathbb{Z}^{n \times n}$ we want to test whether $AB \neq C$. Assume that the arithmetic operations $+$ and $-$ take constant time when applied to numbers from $\mathbb{Z}$.

How can I state an algorithm with one-sided error that runs in $O(n^2)$ time and prove its correctness?

I tried it now for several hours but I can't get it right. I think I have to use the fact that for any $x \in \mathbb{Z}^n$ at most half of the vectors $s \in S = \left\{1, 0\right\}^n$ satisfy $x \cdot s = 0$, where $x \cdot s$ denotes the scalar product$\sum_{i=1}^{n} x_is_i$.

Answer 1

If $AB=C$, then $A(Bx)=Cx$ for all vectors $x$. Generate vectors randomly and check. This known as Freivalds' algorithm. Wikipedia has details.