Automata 8 part 2

Matrix product verification (the problem)

You are given three square matrices A, B and C, each of size n×n (n rows and n columns) with ordinary number entries. The task is just to decide YES or NO: does AB equal C? You are NOT asked to work out AB from scratch — only to check whether the C you were handed is the correct product.

The naive (obvious) verification algorithm

Multiply A and B the normal way, then compare the result entry-by-entry with C. Normal matrix multiplication takes O(n³) time. ("O(n³)", read "order n-cubed", just means the number of steps grows roughly like n³.) Each entry needs n multiplications and n additions = O(n), and there are n² entries, so n² × O(n) = O(n³). This is slow.

Why O(n²) is the target

Even the cleverest known multiplication algorithms take O(n^ω) time, where ω ("omega") is a constant between 2 and 3 — still more than O(n²). Since the answer matrix has n² entries, just writing C down already costs about n². So the goal is to VERIFY that AB = C in only O(n²) time — faster than ever computing the product.

Two matrices are equal exactly when they act the same on every column vector

A column vector v is a single column of n numbers (size n×1). "Xv" means matrix X multiplied by that column, giving another column. Fact: matrices X and Y are equal if and only if Xv = Yv for EVERY possible v. The catch: there are infinitely many vectors v, so we can't test them all directly.

ALG′ — the random vector algorithm

Pick ONE random column vector v: each of its n entries is set to +1 or −1 by tossing a fair coin. Then check whether (AB)v = Cv. If they match, output "AB = C"; otherwise output "AB ≠ C". This replaces the impossible "test all v" with a single cheap random test.

The associativity trick: (AB)v = A(Bv)

Multiplication can be regrouped without changing the result. Forming AB first costs O(n³) — exactly what we want to avoid. Instead compute Bv first (an n×n matrix times an n×1 vector = O(n²), giving a vector), then multiply A by that vector (again O(n²)). Computing Cv is also O(n²). So ALG′ runs in O(n²) total.

Cost of multiplying matrices: O(mnp)

Multiplying a matrix of size m×n by a matrix of size n×p takes O(m·n·p) time — just multiply the three sizes. So matrix × column-vector is n×n times n×1 = O(n·n·1) = O(n²). This is why "matrix times vector" is far cheaper than "matrix times matrix" (O(n²) vs O(n³)).

Correctness and the ½ error bound

If AB = C: every v gives ABv = Cv, so ALG′ is always right (probability 1, no error). If AB ≠ C: a random v might unluckily still give ABv = Cv. The probability of this bad event is at most ½, written Pr[ABv = Cv] ≤ ½. So one run is wrong with probability at most ½. ("Pr[ ]" just means "probability of".)

One-sided error

ALG′ can only be wrong in ONE direction. It might wrongly say "AB = C" when really AB ≠ C, but it never wrongly says "AB ≠ C" (when AB = C it is always correct). Because mistakes only happen on one kind of input, repeating the algorithm can drive the error down very fast.

Error reduction by repetition (the formula)

Run the one-sided algorithm T times with fresh coins; give the "error-prone" answer only if ALL runs agree on it. If one run is correct with probability at least p, the error after T runs is at most (1−p)^T ≤ e^(−pT) (using the handy inequality 1−z ≤ e^(−z)). To force the error to at most ε ("epsilon", your target error), choose T = ⌈(1/p)·ln(1/ε)⌉. (⌈ ⌉ means round up; ln is the natural logarithm.) Worked example: p = 1/n and ε = 1/n give T = n·ln n = O(n log n).

Monte Carlo algorithm

A randomised algorithm that ALWAYS runs in polynomial time and gives the correct answer with high probability. Its error can be one-sided (mistakes only on one type of input, like ALG′) or two-sided (can err either way). The matrix-verification algorithms ALG′ and ALG are examples of one-sided Monte Carlo algorithms.

Computing A(Bv), where A and B are n×n matrices and v is an n×1 column vector, takes time:

• O(n³)
• O(n²)
• O(n)
• O(n⁴)

O(n²)

ALG′ picks a random ±1 vector v and checks (AB)v = Cv. If AB ≠ C, the probability it wrongly outputs "AB = C" is at most:

• 1
• 1/2
• 0
• 1/n

1/2

A one-sided algorithm is correct on a given input with probability 1/n, and you want the error to be at most 1/n by repeating it. The number of repetitions needed is about:

• O(log n)
• O(n)
• O(n log n)
• O(n²)

O(n log