Motivation
Suppose someone supplies three square matrices and claims that the product of the first two equals the third. Computing the entire product by the elementary method takes cubic time. Verification can be cheaper if we are willing to accept a controlled probability of overlooking an incorrect claim.
The key is to test the claimed equality on a random vector. Matrix-vector multiplication takes quadratic arithmetic operations, so a few independent tests can be much cheaper than a full elementary product. We will prove precisely what the error probability means, why a correct claim is never rejected, and which fixed-input and arithmetic assumptions the analysis needs.
Definitions and algorithm
Definition 6.4.1
(Random-vector test for a matrix product)
Let be a field, let , and let . Arithmetic in is exact. The claim to verify is . Sample with independent coordinates, each uniformly chosen from the two distinct field elements and . Compute , then , and independently compute . Accept the trial if and reject otherwise.
A test uses three matrix-vector products and a vector comparison. An implementation need not compute or form the difference matrix . With dense matrices, the trial costs field operations and extra field elements beyond the input matrices. The vector must remain the same in all three products within one trial.
Theorems
Theorem 6.4.2
(One-sided verification error)
If , every trial accepts. If and the matrices are fixed before the random vector is sampled, a trial accepts with probability at most .
Theorem 6.4.3
(Independent repetition)
For an integer , run trials with independent fresh vectors and accept only if all trials accept. A correct product is always accepted; an incorrect fixed product is accepted with probability at most . Dense arithmetic cost is field operations.
The probability is over the verifier's random choices for one fixed triple of matrices. The theorem is not a statement that at most half of all possible wrong matrices fool a particular vector.
Proofs
Proof: one nonzero row is enough
Proof
(One nonzero row bounds the acceptance probability)
Write . The trial accepts exactly when . If , this equality holds for every vector, proving perfect completeness. Now suppose . Some row of contains a nonzero coefficient in column . Fix arbitrary values of all coordinates of except . In that row the equation becomes
Because is a field and , this equation has at most one solution for . Of the two possible values and , at most one can satisfy it. The remaining coordinate is still an independent fair choice after conditioning on the others, so the row vanishes with conditional probability at most . Averaging over the other coordinates gives the same bound unconditionally. The event is contained in the event that this one row vanishes, so it too has probability at most .
The proof works in every field, including characteristic two: and remain distinct, and multiplication by a nonzero element remains injective. It does not need the entries of to be independent or random. It also does not require us to know which row is nonzero; that row is used only in the analysis.
Proof X-ray
Condition on every coordinate but one
The key move reduces a matrix identity to one scalar equation: forces every row of to vanish at , so it suffices to bound the chance that a single nonzero row does. Fixing all coordinates except , where , turns that row equation into with depending only on the other coordinates. Because is a field, is invertible and the equation has at most one solution, so at most one of the two values works. Two hypotheses are used here and nowhere else: in , so the sample set has two elements, and invertibility of . Independence of the coordinates is what makes remain a fair choice after conditioning on the others. Choosing the row and the coordinate is part of the analysis only; the verifier never needs to know which they are.
Proof
(Independent repetition)
For repeated trials, the input triple and hence are unchanged, while the random vectors are independent. Each trial has acceptance probability at most for the incorrect fixed triple, so the probability that all accept is at most . If a trial rejects, stopping immediately preserves correctness and can save work. The bound counts the worst case in which all trials are performed.
A larger sampling set
The same argument allows a finite set of distinct elements. Sample each coordinate independently and uniformly from . After all other coordinates are fixed, at most one of the values satisfies the selected nonzero-row equation. Thus one trial misses an incorrect product with probability at most , and independent trials miss it with probability at most .
For a finite field , sampling uniformly from the whole field gives this bound. More generally, the subset need not be closed under addition or multiplication: only its distinctness and uniform independent sampling matter. Constructing exact uniform samples from fair bits can have a separate cost, especially when is not a power of two. The stated field-operation count treats sampling as available and charges arithmetic operations separately.
A failure probability bound can be selected in advance. With binary vectors, taking for makes the chance of accepting a fixed incorrect product at most . If a verifier checks fixed claims and wants the probability of any incorrect acceptance at most , it can allocate failure probability to each claim and apply a union bound. Independence across different claims is not required by that final union bound, although each claim's repeated trials must satisfy the independence assumptions used for its individual error estimate.
When the field is finite: the role of rank
If and the entire vector is uniform on , the actual one-trial error has a useful exact description. Let . Rank-nullity gives a kernel of dimension , so it contains of the equally likely vectors. Therefore
A nonzero difference has rank at least one, giving the earlier bound. A rank-one difference can attain that bound, while a full-rank difference is missed only on the zero vector and has error probability . The verifier does not need to compute the rank: doing so would add work, and the uniform worst-case guarantee already applies to every nonzero difference.
This exact rank formula depends on uniform sampling from the whole finite field. It cannot automatically be used for binary vectors in a larger field, because those vectors are uniform only on the subset . The one-coordinate argument remains valid for that subset and still yields the upper bound. Distinguishing an exact probability from a worst-case bound prevents an unjustified improvement of a trial budget.
Concept lensCombinatorial
Counting accepted vertices of the cube
The binary vectors are the vertices of a cube, and the same bound can be read off by counting. Take a row of with and pair each vertex having with the vertex that differs only in coordinate . Then , and the chosen row of is . That row therefore cannot vanish at both vertices of a pair, so every pair has at most one accepting vertex and at most of the vertices accept.
A high-probability conclusion also depends on when the instance is chosen. For any known nonzero test vector in dimension at least two, there is a nonzero row vector orthogonal to it, and a nonzero matrix with that row can annihilate . If a malicious prover is allowed to choose the difference matrix after learning the verifier's vector, the fixed-input theorem cannot be invoked as written. In the stated experiment, the matrices are fixed first and the verifier then samples private fresh randomness.
What the certificate means
If a trial rejects, . The vector is a short certificate that the claimed equality is false: another person can recompute the two sides and compare them. An accepting vector, by contrast, does not certify equality; a nonzero difference matrix can annihilate some vectors. Repeating accepted trials increases confidence according to the proven bound but does not turn acceptance into a deterministic proof.
The word one-sided identifies which outcome can be wrong. Rejection is always sound under exact field arithmetic. Acceptance can be wrong for an unequal product. This guarantee is useful when incorrect results must be caught with high probability but false alarms for correct computations are unacceptable. Applications should select the number of trials according to the consequences of a missed error, not describe a finite number of accepted tests as absolute certainty.
Counterexample mode
A fixed vector can miss an error
Let and let . Then is nonzero, but the vector is sent to zero by the difference. Testing this particular vector accepts an incorrect product. Random sampling limits the chance of this event for a fixed input; it does not make every individual vector a certificate.
Worked examples
Worked example 6.4.4
(A missed error and a detected error)
For and , the trial accepts precisely when the second coordinate of is zero. Among the four equally likely binary vectors, and accept, while and reject. The error probability is exactly , showing that the general binary bound can be tight.
Worked example 6.4.5
(A correct product always passes)
Over the real numbers, take and . Their product is . For , compute and . The equality is not special to this vector: associativity gives for every vector.
Worked example 6.4.6
(Three-element sampling)
Over , take and . If each coordinate is uniform in , the difference annihilates exactly when its second coordinate is zero. A trial misses the error with probability ; four independent trials miss it with probability .
Worked example 6.4.7
(Choosing a trial budget)
To bound the error by using independent binary vectors, choose , because . For one thousand fixed incorrect-or-correct claims, a union bound with gives probability of any incorrect acceptance at most . No assumption that the individual claims are independent is needed for this union bound.
Common mistakes
Common mistake
(Reusing one vector for every repetition)
Sampling one vector and reusing it for every repetition does not multiply error probabilities. In the first example, if the second coordinate is zero, the same bad vector passes every repeated check. Fresh independent vectors are the mechanism behind the exponential decrease. A fresh vector for each trial must also be independent of the fixed matrices in the statement.
Common mistake
(Reducing modulo a prime without justification)
Reducing integer matrices modulo a prime changes the problem unless the reduction is justified. An integer difference all of whose entries are multiples of that prime becomes the zero matrix modulo the prime and passes every test in that field. For instance, an integer difference entry equal to vanishes modulo . The field theorem verifies equality in the chosen field; a separate argument is needed to infer equality over the integers.
Common mistake
(Treating floating-point arithmetic as exact)
Finally, floating-point rounding is not exact field arithmetic. Rounding can create apparent inequality for a correct product or hide a small error, so the one-sided guarantee does not transfer automatically to ordinary floating-point computations. A numerical verifier needs an error analysis suited to its arithmetic model.
Summary
A random vector converts a matrix-product identity into three quadratic-time matrix-vector products. For a fixed incorrect product, a nonzero row limits the probability of an undetected error to one half for binary coordinates. Independent repetition decreases that probability exponentially, while correct products always pass in exact field arithmetic. The result depends on the sampling, fixed-input and field assumptions.
Exercises
Quick check
(Let and . List the accepting binary vectors and their probability.)
Solution · Answer
The difference is , so a trial accepts exactly when the first coordinate is zero. The accepting vectors are and , with probability .
Quick check
(Over , sample each coordinate uniformly from the whole field. Bound the probability that three independent trials accept a fixed wrong product.)
Solution · Answer
One trial has error probability at most , and independence bounds all three accepting by . Some particular wrong matrices can have a smaller probability.
Quick check
(Explain why using the same binary vector for ten repeated trials need not give error probability .)
Solution · Answer
For and , the test accepts exactly when the sampled second coordinate is zero. Reusing that same vector ten times still accepts with probability , not .
Quick check
(Give integer matrices whose product is not the claimed integer value but becomes equal to it modulo . Explain what a verifier over sees.)
Solution · Answer
Take and . The integer values and differ, but both reduce to modulo seven. The verifier over sees a correct field identity and accepts every vector; that is not an error in its field-level guarantee.