# Category:Matrix product verification

A frequently used introductory example of randomized algorithms is matrix product verification, where we are given two matrices **A** and **B** and a matrix **C** and asked whether **AB** = **C**. With currently known matrix multiplication algorithms, the obvious approach of multiplying out **AB** takes Ω(*n*^{2.37}) time. Simple randomized algorithms that instead compute **A**(**B**x) and compare it to **C**x for certain randomly chosen vectors *x* can show equality with high probability in only *O*(*n*^{2}) time.

These implementations are based primarily on R. Frievald's 1979 paper "Fast probabilistic algorithms" as surveyed in Tracy Kimbel and Rakesh Sinha's A Probabilistic Algorithm for Verifying Matrix Products Using *O*(*n*^{2}) Time and log_{2}*n* + *O*(1) Random Bits.

## Pages in category "Matrix product verification"

This category contains only the following page.