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$ May 13 '12 at 18:08

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
    May 13 '12 at 22:35
  • 2
    $\begingroup$ What makes you think this isn't one-sided? (It is.) $\endgroup$
    – rgrig
    May 14 '12 at 8:03

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.