Proofs: Wiedemann algorithm

Correctness of the Wiedemann solver full

This proof shows: correctness, termination.

We prove that WIEDEMANN-SOLVE returns only correct answers, that one try succeeds with probability at least $1 - d/|S|$ where $d = \deg \mu_{A,b}$, and hence that it terminates with probability $1$ after an expected number of tries at most $1/(1 - d/|S|)$. Notation is as on the main page: $A$ is $n \times n$ over a field $K$, $b \ne 0$, $\mathcal{K} = \operatorname{span}\{A^i b : i \ge 0\}$ has dimension $d$, and $s_i = u^T A^i b$.

Lemma 1. The vectors $b, A b, \ldots, A^{d-1} b$ form a basis of $\mathcal{K}$, and $\deg \mu_{A,b} = d \le n$.

Proof. Let $k$ be the least index with $A^k b \in \operatorname{span}\{b, \ldots, A^{k-1} b\}$. Then $b, \ldots, A^{k-1} b$ are independent, and by induction every $A^i b$ with $i \ge k$ lies in their span, because multiplying the relation for $A^k b$ by $A$ expresses $A^{k+1} b$ through $A b, \ldots, A^k b$. So $k = d \le n$. A monic $g$ of degree $e$ with $g(A) b = 0$ is a dependence among $b, \ldots, A^e b$, so $e \ge d$, and the relation for $A^d b$ gives such a $g$ of degree $d$. $\square$

Lemma 2 (annihilators of the sequence). The set of polynomials $g = \sum_j g_j x^j$ with $\sum_j g_j s_{i+j} = 0$ for all $i \ge 0$ is an ideal of $K[x]$; its monic generator $F$ is the minimal polynomial of $s$, and $F$ divides $\mu_{A,b}$.

Proof. Writing $(x \cdot s)_i = s_{i+1}$ makes the sequences a $K[x]$-module, and the annihilator of $s$ is an ideal, generated by a monic $F$ unless it is zero. If $g(A) b = 0$, then $\sum_j g_j s_{i+j} = u^T A^i g(A) b = 0$ for all $i$, so $\mu_{A,b}$ is in the ideal and $F \mid \mu_{A,b}$. $\square$

Lemma 3 (line L5). Let $N \ge 2 \deg F$. The monic polynomial of least degree that annihilates the prefix $s_0, \ldots, s_{N-1}$, which Berlekamp-Massey returns, is $F$. Line L5 uses $N = 2n \ge 2d \ge 2 \deg F$.

Proof. $F$ annihilates the prefix, so the least degree $L$ satisfies $L \le e = \deg F$. Let $g$ be monic of degree $L$ annihilating the prefix, and let $s'$ be the sequence with $s'_i = s_i$ for $i < L$ that $g$ generates for all $i$. Then $s'_i = s_i$ for all $i < N$, by induction, since both obey the recurrence of $g$ there. The sequence $t = s - s'$ is annihilated by $F g$, which has degree $e + L \le 2e \le N$, and its first $N$ terms are zero; since a sequence annihilated by a monic polynomial of degree $D$ is determined by its first $D$ terms, $t = 0$. So $g$ annihilates $s$, $F \mid g$, and $\deg g = L \le e$ forces $g = F$. $\square$

Correct outputs. If line L6 reports singularity, then $F(0) = 0$, so $x \mid F \mid \mu_{A,b}$ by Lemma 2, and $\mu_{A,b}$ divides the minimal polynomial of $A$, which therefore has the root $0$; so $0$ is an eigenvalue of $A$ and $A$ is singular. If line L9 returns $x$, the test on line L8 has verified $A x = b$. Line L1 returns $0$, the solution for $b = 0$. So every output is correct.

Lemma 4 (a good projection gives the solution). If $F = \mu_{A,b}$ and $A$ is nonsingular, then $F(0) \ne 0$ and the vector of line L7 satisfies $A x = b$.

Proof. $F(0) = 0$ would make $A$ singular, as above. With $F = \sum_{j \le d} f_j x^j$ and $f_0 \ne 0$, $0 = F(A) b = f_0 b + A \sum_{j=1}^d f_j A^{j-1} b$, so $A x = b$ for $x = -f_0^{-1} \sum_{j=1}^d f_j A^{j-1} b$. Line L7 computes this vector: the Horner loop starts with $y = f_d b = b$ and after the step for index $j$ holds $\sum_{i=j}^{d} f_i A^{i-j} b$, so it ends with $\sum_{i=1}^{d} f_i A^{i-1} b$. $\square$

Lemma 5 (Hankel criterion). Let $H(u)$ be the $d \times d$ matrix with entries $H_{ij} = s_{i+j} = u^T A^{i+j} b$ for $0 \le i, j < d$. Then $F = \mu_{A,b}$ if and only if $\det H(u) \ne 0$.

Proof. If $F \ne \mu_{A,b}$, then $\deg F < d$ by Lemma 2, and the coefficient vector of $F$, padded with zeros to length $d$, is a nonzero $c$ with $H c = 0$, since row $i$ of $H c$ is $\sum_j F_j s_{i+j} = 0$. Conversely, let $H c = 0$ with $c \ne 0$, and put $g = \sum_{j<d} c_j x^j$ and $v = g(A) b$. Then $\deg g < d$, so $v \ne 0$ by Lemma 1, and $u^T A^i v = \sum_j c_j s_{i+j} = 0$ for $i < d$. Since $v \in \mathcal{K}$ and $\mathcal{K}$ is $A$-invariant, $\mu_{A,v}$ divides $\mu_{A,b}$, so every $A^i v$ is a combination of $v, \ldots, A^{d-1} v$, and hence $u^T A^i v = 0$ for all $i \ge 0$. This says that $g$ annihilates $s$, so $F \mid g$ and $\deg F < d$. $\square$

Lemma 6 (probability). If the entries of $u$ are drawn independently and uniformly from a finite $S \subseteq K$, then $\Pr[F = \mu_{A,b}] \ge 1 - d/|S|$.

Proof. Each entry of $H(u)$ is a linear form in $u_1, \ldots, u_n$, so $\det H(u)$ is a polynomial of total degree at most $d$. It is not the zero polynomial: by Lemma 1 the $n \times d$ matrix $V = (b, A b, \ldots, A^{d-1} b)$ has rank $d$, so there is $u^*$ with $u^{*T} V = e_d^T$, that is $s_j = 0$ for $j < d - 1$ and $s_{d-1} = 1$. Then $H(u^*)$ has zeros above its anti-diagonal and ones on it, so $\det H(u^*) = \pm 1$. By the Schwartz-Zippel lemma, $\Pr[\det H(u) = 0] \le d / |S|$, and Lemma 5 converts this into the claim. $\square$

Termination. Each pass of the loop is a finite computation: $2n - 1$ products on line L4, Berlekamp-Massey on $2n$ terms, at most $d$ products on lines L7 and L8. The tries are independent. By Lemmas 4 and 6, when $A$ is nonsingular, each try returns with probability at least $1 - d/|S|$, and if $|S| > d$ this is positive, so the number of tries is geometrically distributed with mean at most $1/(1 - d/|S|)$ and is finite with probability $1$. Over $\mathbb{F}_q$ with $S = \mathbb{F}_q$ the success probability is positive even when $q \le d$: it is at least the probability that $u$ restricted to $\mathcal{K}$ generates the dual of $\mathcal{K}$ as a $K[x]$-module, which is $\prod_g (1 - q^{-\deg g}) > 0$ over the distinct irreducible factors $g$ of $\mu_{A,b}$. An implementation that bounds the number of tries reports failure after the bound, which happens with probability at most $(d/|S|)^{t}$ after $t$ tries.

Conclusion. Every output of WIEDEMANN-SOLVE is correct, and for nonsingular $A$ it returns the solution after an expected number of tries at most $1/(1 - d/|S|) \le 1/(1 - n/|S|)$. $\blacksquare$