F2 row reduction returns the unique Simon mask

Swapping two rows or replacing a row by its XOR with another preserves both the homogeneous solution set and row space: each operation has an inverse of the same form, and the new row is a combination of old rows. Thus the rank and kernel of $Y$ are preserved by [F13] and [F9]. The loops visit $n$ columns and at most $n-1$ pivot rows, with finite row scans, so they terminate.

At each pivot the selected entry is $1$, earlier pivot columns are zero below it, and XORing the pivot row clears its column in every other row. At termination the pivot columns form an identity block and all remaining rows are zero. The nonzero rows are independent because their pivot columns form an identity matrix, and they span the row space because every other row is zero. By [F13], the pivot count equals $\mathrm{rank}(Y)$; step 1.1 preserves this rank from the input. The procedure returns FAIL precisely when this rank is below $n-1$.

If the pivot count is $n-1$, there is exactly one nonpivot column. Setting its coordinate to $1$ and solving each pivot equation gives a vector in the reduced system with that coordinate nonzero. By step 1.1, it lies in the kernel of the original $Y$ and is nonzero.

Whenever $\mathrm{rank}(Y)=n-1$, the associated map has rank $n-1$ by [F10] and domain dimension $n$ by [F8]; rank-nullity [F3] gives a one-dimensional kernel. A basis of that kernel has one vector $u$, so every vector is $cu$ by [F11]; [F12] gives $c\in \{0,1\}$, hence $u$ is its unique nonzero vector. The algorithm's output from step 3.1 is therefore the unique nonzero kernel vector. In the Simon case, every row has dot product zero with $s$, so [F5] and [F9] give $s\in \ker Y$, and [F4] gives $s\mathrm{\ne }0$; thus the output is $s$.

Store the $n-1$ rows consecutively on an input work tape. To find pivots, a multitape machine may scan the whole $O(n^2)$-bit matrix once for each of at most $n$ columns; this costs $O(n^3)$ transitions including head movement. For each of at most $n-1$ pivots, copy its $n$ bits to a work tape, then scan each of at most $n-2$ other rows and XOR the copied pivot row into it when required; each scan and row update costs $O(n)$ transitions, so all row operations cost $O(n^3)$. Swaps, pivot bookkeeping, and back-substitution require at most $O(n^3)$ further transitions under the same scan representation. The finite-alphabet multitape convention [F7] therefore gives the stated $O(n^3)$ classical bit cost.