A probabilistic algorithm for verifying matrix products using \(O(n^ 2)\) time and \(\log_ 2n+O(1)\) random bits (Q1209332)

The following problem is considered: given three \(n\times n\) matrices \(A\), \(B\) and \(C\), how difficult is it to verify whether \(AB=C\)? Freivalds' probabilistic algorithm to verify matrix products using \(O(n^ 2)\) multiplications and additions, and \(n\) bits of randomness is known. This algorithm selects a vector \(v\) at random from \(\{-1,1\}^ n\). It then computes the products \(A(Bv)\) and \(Cv\), and accepts (reports that \(AB\neq C\)) if and only if \(ABv\neq Cv\). A similar method is proposed in this paper, but the vector \(v\) is chosen from a set of less than \(4n\) vectors, requiring only \(\lceil log_ 2n\rceil+1\) random bits. In section 2 the simplest version of the algorithm for integer matrices is presented. Section 3 shows how to improve the bit complexity. Section 4 extends the algorithm to matrices over finite fields and Section 5 shows how to reduce the error probability.