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

  • 1
    $\begingroup$ In the last paragraph: you need “for any nonzero x,” which is obvious but crucial for a solution. $\endgroup$ Commented May 13, 2012 at 18:08

1 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.

  • $\begingroup$ But i Need a One-sided Error algorith. Can someone help me? $\endgroup$
    – Queue
    Commented May 13, 2012 at 22:35
  • 2
    $\begingroup$ What makes you think this isn't one-sided? (It is.) $\endgroup$
    – rgrig
    Commented May 14, 2012 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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