Freivalds' algorithm
/ FRY-valdz /
Suppose someone hands you three n-by-n matrices A, B, C and claims A times B equals C. Recomputing A times B to check costs about n^2.8 with Strassen, or n^3 naively — almost as expensive as doing the multiplication yourself. Freivalds' algorithm verifies the claim far more cheaply, in just O(n^2) time, by not recomputing the product at all but spot-checking it with a random vector.
Precisely: pick a random vector r of n entries, each chosen independently to be 0 or 1 (uniformly). Compute Br, then A(Br), and separately Cr — all three are matrix-times-vector products costing O(n^2). Compare A(Br) with Cr. If A times B really equals C, then ABr always equals Cr, so the test always says 'equal' — no false alarms. If A times B differs from C, let D = AB - C, which is a nonzero matrix; the test wrongly says 'equal' only when Dr = 0. Here is the key probabilistic fact: for any fixed nonzero matrix D, a uniformly random 0/1 vector r satisfies Dr = 0 with probability at most one-half. (Reason: pick a row of D with a nonzero entry; whatever the other coordinates of r are, exactly one of the two choices for the coordinate at that nonzero entry makes that row's dot product zero.) So a difference is caught with probability at least one-half each run.
Freivalds' algorithm matters as the cleanest example of verification being easier than computation, and of fingerprinting: instead of comparing huge objects directly, you compare cheap random summaries and trust that different objects rarely summarize the same. Run it k independent times; since it is one-sided (it never falsely rejects), a single 'not equal' on any run is conclusive, and the chance of wrongly accepting a wrong product after k runs is at most (1/2)^k. The honest caveat: it is Monte Carlo with one-sided error — it can pass a wrong product, just rarely — and the error halves only if each run uses fresh independent randomness.
Claim: the 2-by-2 identity matrix times the matrix with rows (2,3) and (4,5) equals the matrix C with rows (2,3) and (4,6) — the bottom-right should be 5, so the claim is wrong. With r = (0,1): the true product times r is (3,5), but C times r is (3,6). They differ, so the test correctly rejects. With r = (1,0) both give (2,4) and the test would have passed — which is why you repeat with fresh random r.
Verify A times B = C in O(n^2) by checking ABr = Cr for random r — one-sided, repeat to shrink error.
The error is one-sided: a correct product always passes, but a wrong product passes with probability up to one-half per run. Independent repetition drives that to (1/2)^k, yet it never reaches zero — Freivalds verifies, it does not prove with certainty.