# A Simplified Proof For The Application Of Freivalds' Technique to Verify Matrix Multiplication

Source: [A Simplified Proof For The Application Of Freivalds' Technique to Verify Matrix Multiplication](<https://www.sota2.com/research/paper/68fa600b1e209131ce9ed68a>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-10-28T13:56:26.275Z

Authors: Vamsi K. Kundeti

Published: 2009-12-19T18:54:20.000Z

## Abstract

Fingerprinting is a well known technique, which is often used in designing Monte Carlo algorithms for verifying identities involving ma- trices, integers and polynomials. The book by Motwani and Raghavan \[1\] shows how this technique can be applied to check the correctness of matrix multiplication -- check if AB = C where A, B and C are three nxn matrices. The result is a Monte Carlo algorithm running in time $Theta(n^2)$ with an exponentially decreasing error probability after each indepen- dent iteration. In this paper we give a simple alternate proof addressing the same problem. We also give further generalizations and relax various assumptions made in the proof.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/0912.3925>)

[PDF](<https://arxiv.org/pdf/0912.3925.pdf>)
