TheoremStatement: Literature-sourcedProof: AI-generatedprecheck passaudited 2026-09-12

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Freivalds' one-trial matrix-product test has one-sided error

Statement

Let $F$ be a field and let $A, B, C \in M_{n} (F)$ . Choose a random vector $r \in {0, 1}^{n}$ uniformly and accept exactly when $A (B r) = C r$ .

Then:

if $C = A B$ , the test accepts with probability $1$ ; 2. if $C \neq A B$ , the test accepts with probability at most $1 / 2$ .

So one trial gives a one-sided-error randomized test for matrix products.

Facts & Assumptions

Given: a field $F$ , matrices $A, B, C \in M_{n} (F)$ , and a uniform random vector $r \in {0, 1}^{n}$ .

[L1]

Matrix products and matrix-vector products are defined by finite sums over matching indices (Rectangular matrix multiplication and the identity matrix $I_{n}$ , including zero-sized shapes).

[L2]

In a field, distinct scalars remain distinct and every nonzero scalar is invertible (Field).

Proof

technique · direct

1.1L1given

If $C = A B$ , then the equality $C r = (A B) r = A (B r)$ follows directly from the finite-sum definition in [L1]. So the test always accepts a correct product.

1.2L2choosealgebra

Assume $C \neq A B$ and put $D : = C - A B \neq 0$ . Then some row $d = (d_{1}, \dots, d_{n})$ of $D$ is nonzero. Choose the largest index $j$ with $d_{j} \neq 0$ ; this is possible because the row is finite.

2.1L2step 1.2algebra

Fix all random bits of $r$ except $r_{j}$ . The equation $(D r)_{i} = 0$ for the chosen row has the form $d_{j} r_{j} = - \sum_{ℓ < j} d_{ℓ} r_{ℓ}$ , because $d_{ℓ} = 0$ for $ℓ > j$ . By [L2], $d_{j}$ is invertible, so at most one value of $r_{j}$ can satisfy this equation. Since $r_{j}$ is uniform on ${0, 1}$ and $0 \neq 1$ in a field by [L2], the conditional probability that this row equation holds is at most $1 / 2$ . Therefore $P (D r = 0) \leq 1 / 2$ , and hence the acceptance probability when $C \neq A B$ is at most $1 / 2$ .

3.1step 1.1step 2.1∎

Steps 1.1 and 2.1 prove the one-sided error bound for a single trial of the test. Repeating with fresh random vectors multiplies the failure probability.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

8 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach (standard reference, not scraped)
Jiri Matousek, Thirty-three Miniatures, Section on Freivalds' algorithm (standard reference, not scraped)