Freivalds' algorithm (named after Rūsiņš Mārtiņš Freivalds) is a probabilistic randomized algorithm used to verify matrix multiplication. Given three n × n matrices , , and , a general problem is to verify whether . A naïve algorithm would compute the product explicitly and compare term by term whether this product equals . However, the best known matrix multiplication algorithm runs in time. Freivalds' algorithm utilizes randomization in order to reduce this time bound to with high probability. In time the algorithm can verify a matrix product with probability of failure less than . The algorithm Input Three n × n matrices , , and . Output Yes, if ; No, otherwise. Procedure Generate an n × 1 random 0/1 vector . Compute . Output "Yes" if ; "No," otherwise. Error If , then the algorithm always returns "Yes". If , then the probability that the algorithm returns "Yes" is less than or equal to one half. This is called one-sided error. By iterating the algorithm k times and returning "Yes" only if all iterations yield "Yes", a runtime of and error probability of is achieved. Example Suppose one wished to determine whether: A random two-element vector with entries equal to 0 or 1 is selected say and used to compute: This yields the zero vector, suggesting the possibility that AB = C. However, if in a second trial the vector is selected, the result becomes: The result is nonzero, proving that in fact AB ≠ C. There are four two-element 0/1 vectors, and half of them give the zero vector in this case ( and ), so the chance of randomly selecting these in two trials (and falsely concluding that AB=C) is 1/22 or 1/4. In the general case, the proportion of r yielding the zero vector may be less than 1/2, and a larger number of trials (such as 20) would be used, rendering the probability of error very small. Error analysis Let p equal the probability of error. We claim that if A × B = C, then p = 0, and if A × B ≠ C, then p ≤ 1/2. Case A × B = C This is regardless of the value of , since it uses only that . Hence the probability for error in this case is: Case A × B ≠ C Let such that Where . Since , we have that