Problem

Given three n x n matrices A, B, and C, verify whether C = A × B using Freivald’s randomized algorithm. The goal is to check the correctness of matrix multiplication much faster than recomputing the product directly.

Example

Example 1

1
2
3

Input: A = [[1,2],[3,4]], B = [[5,6],[7,8]], C = [[19,22],[43,50]]
Output: True
Explanation: C is the correct product of A and B.

Example 2

1
2
3

Input: A = [[1,2],[3,4]], B = [[5,6],[7,8]], C = [[20,22],[43,50]]
Output: False
Explanation: C is not the correct product of A and B.

Solution

Method 1 – Freivald’s Randomized Verification

Intuition

Instead of computing A × B directly, use a random vector to probabilistically check if C = A × B. If C ≠ A × B, the algorithm will detect the error with high probability after a few iterations.

Approach

  • Repeat the following steps k times (for higher confidence):
    1. Generate a random vector r of size n with entries 0 or 1.
    2. Compute Br = B × r.
    3. Compute ABr = A × (B × r).
    4. Compute Cr = C × r.
    5. If ABr ≠ Cr, return False.
  • If all iterations pass, return True (with high probability).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

import random
class Solution:
    def freivalds(self, A: list[list[int]], B: list[list[int]], C: list[list[int]], k: int = 10) -> bool:
        n = len(A)
        for _ in range(k):
            r = [random.randint(0, 1) for _ in range(n)]
            Br = [sum(B[i][j] * r[j] for j in range(n)) for i in range(n)]
            ABr = [sum(A[i][j] * Br[j] for j in range(n)) for i in range(n)]
            Cr = [sum(C[i][j] * r[j] for j in range(n)) for i in range(n)]
            if ABr != Cr:
                return False
        return True

Complexity

  • ⏰ Time complexity: O(kn^2), where k is the number of iterations (usually small, e.g., 10).
  • 🧺 Space complexity: O(n^2), for storing matrices and vectors.