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

Preprint · Vamsi K. Kundeti

- Archive id: arxiv:0912.3925
- Published: 2009-12-19
- arXiv: https://arxiv.org/abs/0912.3925
- Source URL: https://arxiv.org/abs/0912.3925
- PDF: https://arxiv.org/pdf/0912.3925
- Provenance: arxiv

## 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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.