7
$\begingroup$

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

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

1 Answer 1

Reset to default
4
$\begingroup$

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

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

Your Answer

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

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