Problem Detail: 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, 0right}^n$ satisfy $x cdot s = 0$, where $x cdot s$ denotes the scalar product$sum_{i=1}^{n} x_is_i$.
Asked By : Queue
Answered By : rgrig
If $AB=C$, then $A(Bx)=Cx$ for all vectors $x$. Generate vectors randomly and check. This known as Freivalds’ algorithm. Wikipedia has details.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/1809
