随机算法 (Fall 2011)/Verifying Matrix Multiplication

Consider the following problem:

• Given as the input three [math]\displaystyle{ n\times n }[/math] matrices [math]\displaystyle{ A,B }[/math] and [math]\displaystyle{ C }[/math],
• check whether [math]\displaystyle{ C=AB }[/math].

We could compute [math]\displaystyle{ AB }[/math] and compare the result to [math]\displaystyle{ C }[/math]. The time complexity of fastest matrix multiplication algorithm (in theory) is [math]\displaystyle{ O(n^{2.376}) }[/math], and so is the time complexity of this method.

Here’s a very simple randomized algorithm, due to Freivalds, that runs in only [math]\displaystyle{ O(n^2) }[/math] time:

Algorithm (Freivalds)

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

The running time of the algorithm is [math]\displaystyle{ O(n^2) }[/math] because it does only 3 matrix-vector multiplications.

If [math]\displaystyle{ AB=C }[/math] then [math]\displaystyle{ A(Br) = Cr }[/math] for any [math]\displaystyle{ r \in\{0, 1\}^n }[/math], thus the algorithm always returns "yes". But if [math]\displaystyle{ AB \neq C }[/math] then the algorithm will make a mistake if it happens to choose an [math]\displaystyle{ r }[/math] for which [math]\displaystyle{ ABr = Cr }[/math]. This, however, is unlikely:

Lemma

If [math]\displaystyle{ AB\neq C }[/math] then for a uniformly random [math]\displaystyle{ r \in\{0, 1\}^n }[/math], [math]\displaystyle{ \Pr[ABr = Cr]\le \frac{1}{2} }[/math].

Proof. Let [math]\displaystyle{ D=AB-C }[/math]. We will show that if [math]\displaystyle{ D\neq \boldsymbol{0} }[/math], then [math]\displaystyle{ \Pr[Dr = \boldsymbol{0}]\le \frac{1}{2} }[/math] for a uniform random [math]\displaystyle{ r \in\{0, 1\}^n }[/math]. Since [math]\displaystyle{ D\neq \boldsymbol{0} }[/math], it must have at least one non-zero entry, say [math]\displaystyle{ D(i,j)\neq 0 }[/math]. The [math]\displaystyle{ i }[/math]-th entry of [math]\displaystyle{ Dr }[/math] is [math]\displaystyle{ (Dr)_i=\sum_{k=1}^nD(i,k)r_k }[/math]. If to the contrary, [math]\displaystyle{ Dr=\boldsymbol{0} }[/math], then [math]\displaystyle{ (Dr)_i=\sum_{k=1}^nD(i,k)r_k=0 }[/math], which is equivalent to that [math]\displaystyle{ r_j=-\frac{1}{D(i,j)}\sum_{k\neq j}^nD(i,k)r_k }[/math], i.e. once [math]\displaystyle{ r_k }[/math] for [math]\displaystyle{ k\neq j }[/math] have been chosen, there is only one value of [math]\displaystyle{ r_j }[/math] that would give us a zero [math]\displaystyle{ Dr }[/math]. However, there are two possible values [math]\displaystyle{ \{0,1\} }[/math] for [math]\displaystyle{ r_j }[/math] which are equal-probable, so with at least [math]\displaystyle{ \frac{1}{2} }[/math] probability, the choice of [math]\displaystyle{ r }[/math] fails to give us a zero [math]\displaystyle{ Dr }[/math]. [math]\displaystyle{ \square }[/math]