# Verifying Matrix Multiplication

Consider the following problem:

• Input: Three ${\displaystyle n\times n}$ matrices ${\displaystyle A,B}$ and ${\displaystyle C}$.
• Output: return "yes" if ${\displaystyle C=AB}$ and "no" if otherwise.

A naive way of checking the equality is first computing ${\displaystyle AB}$ and then comparing the result with ${\displaystyle C}$. The (asymptotically) fastest matrix multiplication algorithm known today runs in time ${\displaystyle O(n^{2.376})}$. The naive algorithm will take asymptotically the same amount of time.

# Freivalds Algorithm

The following is a very simple randomized algorithm, due to Freivalds, running in only ${\displaystyle O(n^{2})}$ time:

 Algorithm (Freivalds) pick a vector ${\displaystyle r\in \{0,1\}^{n}}$ uniformly at random; if ${\displaystyle A(Br)=Cr}$ then return "yes" else return "no";

The product ${\displaystyle A(Br)}$ is computed by first multiplying ${\displaystyle Br}$ and then ${\displaystyle A(Br)}$. The running time is ${\displaystyle O(n^{2})}$ because the algorithm does 3 matrix-vector multiplications in total.

If ${\displaystyle AB=C}$ then ${\displaystyle A(Br)=Cr}$ for any ${\displaystyle r\in \{0,1\}^{n}}$, thus the algorithm will return a "yes" for any positive instance (${\displaystyle AB=C}$). But if ${\displaystyle AB\neq C}$ then the algorithm will make a mistake if it chooses such an ${\displaystyle r}$ that ${\displaystyle ABr=Cr}$. However, the following lemma states that the probability of this event is bounded.

 Lemma If ${\displaystyle AB\neq C}$ then for a uniformly random ${\displaystyle r\in \{0,1\}^{n}}$, ${\displaystyle \Pr[ABr=Cr]\leq {\frac {1}{2}}}$.
Proof.
 Let ${\displaystyle D=AB-C}$. The event ${\displaystyle ABr=Cr}$ is equivalent to that ${\displaystyle Dr=0}$. It is then sufficient to show that for a ${\displaystyle D\neq {\boldsymbol {0}}}$, it holds that ${\displaystyle \Pr[Dr={\boldsymbol {0}}]\leq {\frac {1}{2}}}$. Since ${\displaystyle D\neq {\boldsymbol {0}}}$, it must have at least one non-zero entry. Suppose that ${\displaystyle D(i,j)\neq 0}$. We assume the event that ${\displaystyle Dr={\boldsymbol {0}}}$. In particular, the ${\displaystyle i}$-th entry of ${\displaystyle Dr}$ is ${\displaystyle (Dr)_{i}=\sum _{k=1}^{n}D(i,k)r_{k}=0.}$ The ${\displaystyle r_{j}}$ can be calculated by ${\displaystyle r_{j}=-{\frac {1}{D(i,j)}}\sum _{k\neq j}^{n}D(i,k)r_{k}.}$ Once all ${\displaystyle r_{k}}$ where ${\displaystyle k\neq j}$ are fixed, there is a unique solution of ${\displaystyle r_{j}}$. That is to say, conditioning on any ${\displaystyle r_{k},k\neq j}$, there is at most one value of ${\displaystyle r_{j}\in \{0,1\}}$ satisfying ${\displaystyle Dr=0}$. On the other hand, observe that ${\displaystyle r_{j}}$ is chosen from two values ${\displaystyle \{0,1\}}$ uniformly and independently at random. Therefore, with at least ${\displaystyle {\frac {1}{2}}}$ probability, the choice of ${\displaystyle r}$ fails to give us a zero ${\displaystyle Dr}$. That is, ${\displaystyle \Pr[ABr=Cr]=\Pr[Dr=0]\leq {\frac {1}{2}}}$.
${\displaystyle \square }$

When ${\displaystyle AB=C}$, Freivalds algorithm always returns "yes"; and when ${\displaystyle AB\neq C}$, Freivalds algorithm returns "no" with probability at least 1/2.

To improve its accuracy, we can run Freivalds algorithm for ${\displaystyle k}$ times, each time with an independent random ${\displaystyle r\in \{0,1\}^{n}}$, and return "yes" iff all running instances pass the test.

 Freivalds' Algorithm (multi-round) pick ${\displaystyle k}$ vectors ${\displaystyle r_{1},r_{2},\ldots ,r_{k}\in \{0,1\}^{n}}$ uniformly and independently at random; if ${\displaystyle A(Br_{i})=Cr_{i}}$ for all ${\displaystyle i=1,\ldots ,k}$ then return "yes" else return "no";

If ${\displaystyle AB=C}$, then the algorithm returns a "yes" with probability 1. If ${\displaystyle AB\neq C}$, then due to the independence, the probability that all ${\displaystyle r_{i}}$ have ${\displaystyle ABr_{i}=C_{i}}$ is at most ${\displaystyle 2^{-k}}$, so the algorithm returns "no" with probability at least ${\displaystyle 1-2^{-k}}$. Choose ${\displaystyle k=O(\log n)}$. The algorithm runs in time ${\displaystyle O(n^{2}\log n)}$ and has a one-sided error (false positive) bounded by ${\displaystyle {\frac {1}{\mathrm {poly} (n)}}}$.