10
$\begingroup$

Freivald's algorithm (see the wiki) is a randomized algorithm for verifying whether the product of two $n \times n$-matrices $A$ and $B$ yields a given matrix $C$ (i.e. $AB = C$). The way this task is accomplished is to introduce a random vector $\vec{v} \in \mathbb{R}^{n}$ and evaluate whether $$A(Bv) = Cv$$ The claim is that if $AB \neq C$, then $AB v = Cv$ with probability at most $1/2$, and they provide a justification. Their argument for why 1/2 works makes some sense to me. What I don't understand is why this bound can't be improved further by the following argument:

Claim: Suppose that $AB \neq C$. Then for almost all choices of $v$ (i.e. with probability $1$), $AB v \neq Cv$.

Proof of Claim: Note that $AB v = Cv$ if and only if $(AB-C)v =0$. Let $D = AB-C$. Then $ABv = Cv$ if and only if $v \in \ker(D)$. Since $AB \neq C$, $D$ is not the $0$-matrix meaning that $\dim(\ker(D)) < n$. Hence, $\ker(D)$ is a proper linear subspace of $\mathbb{R}^{n}$ and therefore has measure $0$. Thus, for almost all choices of $v$, $D v \neq 0$ meaning that $ABv \neq Cv$ with probability $1$.

Q.E.D.

Hence, if $AB v = Cv$, then $AB = C$ with probability $1$. Shouldn't this mean that the probability of failure in Freivald's algorithm is $0$ instead of $2^{-k}$?

Thanks.

$\endgroup$
2
  • 1
    $\begingroup$ By definition, Freivald's algorithm chooses only vectors $v$ whose entries equal $0$ or $1$. In that setting, $\frac12$ is the best possible bound even over $\Bbb Q$. You could propose a variant of the algorithm and ask about bounds for that.... $\endgroup$ Jul 13, 2021 at 22:41
  • 1
    $\begingroup$ Ah actually, this exists and is surprisingly recent. This arxiv post published in a journal in 2020 supplies such a variant: arxiv.org/pdf/1705.10449.pdf $\endgroup$
    – Alex B.
    Jul 14, 2021 at 1:29

1 Answer 1

12
$\begingroup$

Algorithms can't work over $\mathbb{R}^n$, as you can't represent real numbers in finite space. Also, you can't pick a number uniformly at random from $\mathbb{R}$. Instead, usually we work over a finite field.

Then we can't do any better. Suppose we are working in the finite field with two elements, $GF(2)$. Suppose that

$$AB - C = \begin{pmatrix} 0 & 0 \\ 1 & 0 \end{pmatrix}.$$

Then it is easy to verify that Frievald's algorithm is wrong with probability $1/2$, as $(AB-C)v = 0$ holds with probability $1/2$ when we select $v$ uniformly at random. You can generalize this to a $n\times n$ matrix that is all zeros except for a single entry, and then the probability of false positive is $1/2$.

If you are working over $\mathbb{Q}$, then the same matrix $AB-C$ also provides a similar counterexample. As Greg Martin explains, Freivald's algorithm by definition chooses vectors uniformly at random from $\{0,1\}^n$, and then when $v$ is selected from this distribution, $(AB-C)v=0$ holds with probability $1/2$. (And if you are wondering whether it is possible to do better by choosing $v$ differently, there is no way to choose a number uniformly at random from $\mathbb{Q}$, so it's not clear what distribution you would use.)

$\endgroup$
8
  • 1
    $\begingroup$ This is a good answer, and I appreciate it. However, in practice, I mainly multiply matrices over $\mathbb{Q}$. In that case, the same proof follows. In particular, when I perturb a LP for the simplex method to create nondegeneracy, I do exactly that and the justification also follows from hyperplanes being measure zero. Is there a reason why we should not do so in the rational case? Thanks again. $\endgroup$
    – Alex B.
    Jul 13, 2021 at 19:04
  • $\begingroup$ @KeimaKatsuragi, see edited answer. $\endgroup$
    – D.W.
    Jul 13, 2021 at 22:52
  • $\begingroup$ Wouldn't you do a lot better by choosing $v$ from $\{1,2\}^n$ instead? It seems obvious that you don't want the zero vector in the distribution since that's a guaranteed false positive, and zero entries in the vector more generally cause problems when the difference matrix has lots of zero entries like in your example. $\endgroup$ Jul 14, 2021 at 2:23
  • $\begingroup$ @MarioCarneiro, nope, that doesn't help. Consider $$AB-C = \begin{pmatrix}0&0&0\\0&0&0\\1&-1&0\end{pmatrix}$$. $\endgroup$
    – D.W.
    Jul 14, 2021 at 4:10
  • 2
    $\begingroup$ @MarioCarneiro You can sure tinker with the probability in various ways. For example, choosing $v$ in $\{0,\dots,2^n-1\}^n$ will decrease the probability to $2^{-n}$. However, no matter what you do, the probability is not $0$ (it is inversely proportional to the size of the sample set for each coordinate), and there is a trade off in that choosing $v$ from a larger sample set will increase the size of the numbers involved in the computation, hence increase the complexity of the algorithm. $\endgroup$ Jul 14, 2021 at 7:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.