Freivalds’ algorithm for verifying Matrix Multiplication
Reading time: 30 minutes  Coding time: 12 minutes
Freivalds' algorithm is a probabilistic randomized algorithm used to verify matrix multiplication. Given three n x n matrices, Freivalds' algorithm determines in O(kn^2) whether the matrices are equal for a chosen k value with a probability of failure less than 2^k.
Freivalds' algorithm

Input: n×n matrices A, B and C.

We would like to verify if A×B=C.
Choose a n×1 column vector r→∈{0,1}n, uniformly and at random. In other words, each component of the vector is either 0 or 1 and chosen randomly and uniformly. 
Compute A⋅(B⋅r) and C⋅r. This takes Θ(n^2) time.

Now comes the output
 If A⋅(B⋅r)≠C⋅r, output FALSE. In other words, we say that the given matrix multiplication is incorrect. This has a probability of correctness = 1.
 If A⋅(B⋅r)=C⋅r, output TRUE. In other words, we say that the given matrix multiplication is correct. This has a probability of correctness ≥1/2.
Example
Let A,B,C are the matrices such that A × B = C.A random twoelement vector with entries equal to 0 or 1 is selected Vector r=[1,1] .
This yields the zero vector, suggesting the possibility that AB = C. However, if in a second trial the vector r=[1,0] is selected, the result becomes:
The result is nonzero, proving that in fact AB ≠ C.
There are four twoelement 0/1 vectors, and half of them give the zero vector in this case Vector r=[0,0] and r=[1,1].so the chance of randomly selecting these in two trials (and falsely concluding that AB=C) is 1/22 or 1/4. In the general case, the proportion of r yielding the zero vector may be less than 1/2, and a larger number of trials would be used, rendering the probability of error very small.
Error analysis
Let p equal the probability of error. We claim that if A × B = C, then p = 0, and if A × B ≠ C, then p ≤ 1/2.
Case A × B = C:
Regardless of the value of vector r, since it uses only that A × B  C =0. Hence the probability for error in this case would be zero.
Case A × B ≠ C:
Since A × B ≠ C, we have that some element of D is nonzero. Suppose that the element d≠0.For some constant y. Using Bayes' Theorem, we can partition over y.
Pseudocode
 Generate an n × 1 random 0/1 vector r.
 Compute P = A × (Br) – Cr.
 Return true if P = ( 0, 0, …, 0 )T, return false otherwise.
Br = matrix B multiplied by Vector r.
Cr = matrix C multiplied by Vector r.
Complexity

Worst case time complexity:
Θ(kn^2)

Space complexity:
Θ(n^2)
k = number of times the algorithm iterates.
Implementations
 C++
C++
#include <iostream> #include <stdio.h> #include <stdlib.h> using namespace std; int main(int argc, char **argv) { cout << "Enter the dimension of the matrices: " << endl; int n; cin >> n; cout << "Enter the 1st matrix: " << endl; double a[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> a[i][j]; } } cout << "Enter the 2nd matrix: " << endl; double b[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> b[i][j]; } } cout << "Enter the result matrix: " << endl; double c[n][n]; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> c[i][j]; } } //random generation of the r vector // containing only 0/1 as its elements double r[n][1]; for (int i = 0; i < n; i++) { r[i][0] = rand() % 2; } //test A * (b*r)  (C*) = 0 double br[n][1]; for (int i = 0; i < n; i++) { for (int j = 0; j < 1; j++) { for (int k = 0; k < n; k++) { br[i][j] = br[i][j] + b[i][k] * r[k][j]; } } } double cr[n][1]; for (int i = 0; i < n; i++) { for (int j = 0; j < 1; j++) { for (int k = 0; k < n; k++) { cr[i][j] = cr[i][j] + c[i][k] * r[k][j]; } } } double abr[n][1]; for (int i = 0; i < n; i++) { for (int j = 0; j < 1; j++) { for (int k = 0; k < n; k++) { abr[i][j] = abr[i][j] + a[i][k] * br[k][j]; } } } // br = multiplyVector(b, r, n); // cr = multiplyVector(c, r, n); // abr = multiplyVector(a, br, n); //abrcr for (int i = 0; i < n; i++) { abr[i][0] = cr[i][0]; } bool flag = true; for (int i = 0; i < n; i++) { if (abr[i][0] == 0) continue; else flag = false; } if (flag == true) cout << "True"; else cout << "False"; }
Applications

Fingerprinting is a well known technique, which is often used in designing Monte Carlo algorithms for verifying identities involving matrices, integers and polynomials.

Freivalds' algorithm frequently arises in introductions to probabilistic algorithms due to its simplicity and how it illustrates the superiority of probabilistic algorithms in practice for some problems.