TAOCP 7.1.3 Exercise 195

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 195. ▶ [HM25] [HM25] Let A be a binary matrix having rows α1, . . . , αm of length n. Explain how to use bitwise operations to compute the rank m −r of A over the binary field {0, 1}, and to find linearly independent binary vectors θ1, . . . , θr of length m such that θjA = 0 . . . 0 for 1 ≤j ≤r. Hint: See the “triangularization” algorithm for null spaces, Algorithm 4.6.2N.

Verified: yes
Solve time: 1m16s

Solution

Let $A$ be the binary matrix with rows $\alpha_1,\ldots,\alpha_m \in {0,1}^n$. Work over the field ${0,1}$ with addition given by bitwise XOR, so that linear combinations of rows use $\oplus$ componentwise.

Construct an augmented matrix $B$ with $m$ rows of length $n+m$ defined by

$$ B_i = (\alpha_i \mid e_i), $$

where $e_i$ is the $i$-th unit vector of length $m$.

Perform Gaussian elimination over ${0,1}$ on $B$ using only row swaps and row replacements of the form

$$ R_i \leftarrow R_i \oplus R_j, $$

which preserve the row space over ${0,1}$ and preserve the invariant that each row of $B$ represents the same linear relation between original rows and coefficient vectors.

Process columns $1,\ldots,n$ as pivot columns. For each column $k$, choose a row whose left part has a $1$ in column $k$, move it into pivot position, and XOR it into every other row having a $1$ in that column. After processing all columns, the left block of $B$ is in row-echelon form over ${0,1}$.

Let $t$ be the number of pivot rows in the left block, that is, the number of rows whose left part contains a leading $1$ in some column not eliminated by previous pivots. These rows are linearly independent, since each introduces a new pivot column that is zero in all earlier pivot rows. Every remaining row has left part equal to $0\ldots 0$.

The rank of $A$ over ${0,1}$ equals $t$, since the pivot rows correspond exactly to a maximal independent subset of ${\alpha_1,\ldots,\alpha_m}$. Hence the dimension of the space of linear dependencies among rows is $m-t$, so the required value is $m-r = t$ with $r = m-t$.

For the nullspace vectors, observe that each row of the augmented matrix has the form

$$ (\text{row combination of } \alpha_i,\ \theta), $$

where $\theta \in {0,1}^m$ records the cumulative XOR combination of original unit vectors used to produce that row. Row operations preserve this interpretation because each replacement $R_i \leftarrow R_i \oplus R_j$ replaces both the left and right parts by XOR of the corresponding linear combinations.

After elimination, each row whose left part is $0\ldots 0$ satisfies

$$ \theta A = 0\ldots 0. $$

Collect all such right parts $\theta^{(1)},\ldots,\theta^{(r)}$ corresponding to zero-left rows. These vectors lie in ${0,1}^m$ and satisfy $\theta^{(j)} A = 0$ for each $j$.

These vectors are linearly independent over ${0,1}$ because each arises from a distinct elimination path and the elimination process produces a full basis of the nullspace of the left transformation matrix. Their number equals the number of zero-left rows, namely $r = m-t$.

Thus the procedure yields both the rank $t = m-r$ and a basis $\theta_1,\ldots,\theta_r$ of the solution space of $\theta A = 0\ldots 0$.

This completes the proof. ∎