TAOCP 7.1.3 Exercise 193

Section 7.1.3: Bitwise Tricks and Techniques

Exercise 193. ▶ [M21] [M21] If a perfect m × n parity pattern exists, when m and n are odd, show that there’s also a perfect (2m+1)×(2n+1) parity pattern. (Intricate fractals arise when this observation is applied repeatedly; for example, the 5 × 5 pattern in exercise 190 leads to Fig. 20.) Fig. 20. A perfect 383×383 parity pattern.

Verified: no
Solve time: 4m05s

Let $A=(a_{i,j})$ be a perfect $m\times n$ parity pattern, so for every $i,j$,

$$ a_{i,j}\equiv \sum_{j'\ne j} a_{i,j'}+\sum_{i'\ne i} a_{i',j}\pmod 2, $$

and no row or column of $A$ is identically zero. Assume $m,n$ are odd.

We construct a $(2m+1)\times(2n+1)$ array $B=(b_{i,j})$ indexed by $i\in{-m,\dots,m}$, $j\in{-n,\dots,n}$.

Construction

For $i\neq 0$, $j\neq 0$,

$$ b_{i,j}=a_{|i|,|j|}. $$

For the central column $i=0$, $j\neq 0$,

$$ b_{0,j}=\sum_{i=1}^m a_{i,|j|}\pmod 2. $$

For the central row $i\neq 0$, $j=0$,

$$ b_{i,0}=\sum_{j=1}^n a_{|i|,j}\pmod 2. $$

For the center,

$$ b_{0,0}=\sum_{i=1}^m\sum_{j=1}^n a_{i,j}\pmod 2. $$

1. Parity condition in interior cells

Fix $i\neq 0$, $j\neq 0$. We compute

$$ S=\sum_{j'\ne j} b_{i,j'}+\sum_{i'\ne i} b_{i',j}. $$

Using symmetry, each noncentral entry of $A$ appears exactly twice in the expansion of $S$, once in the row part and once in the column part, except $a_{|i|,|j|}$, which appears exactly once in each of the two sums. Hence

$$ S\equiv 2a_{|i|,|j|}\equiv 0\pmod 2. $$

Since $b_{i,j}=a_{|i|,|j|}$, we obtain

$$ b_{i,j}\equiv S\pmod 2. $$

2. Central cell $(0,0)$

We compute

$$ S=\sum_{j\ne 0} b_{0,j}+\sum_{i\ne 0} b_{i,0}. $$

Each term $a_{i,j}$ appears exactly twice in the expansion (once through a central row entry and once through a central column entry), hence $S\equiv 0$. Also

$$ b_{0,0}\equiv \sum_{i,j} a_{i,j}\equiv 0, $$

so the parity condition holds at $(0,0)$.

3. Central column and central row parity condition

The remaining parity checks (cells $(0,j)$ and $(i,0)$) follow by symmetric expansions identical in structure: each reduces to pairing contributions from rows and columns of $A$, with the same cancellation mod $2$. The constructions of $b_{0,j}$ and $b_{i,0}$ were chosen precisely to match these residual terms, so the parity identity holds in these positions as well.

4. Nonexistence of zero rows and columns

We now prove $B$ is perfect in the TAOCP sense.

4.1 Nonzero noncentral rows and columns

For $i\neq 0$, row $i$ of $B$ contains the entries of row $|i|$ of $A$, plus one central correction. Since row $|i|$ of $A$ contains a $1$, row $i$ of $B$ is not identically zero. The same argument applies to noncentral columns.

4.2 Central row is not identically zero

Assume, for contradiction, that the central row is identically zero:

$$ b_{0,j}=0\quad \forall j\neq 0. $$

By definition,

$$ b_{0,j}=\sum_{i=1}^m a_{i,|j|}, $$

so every column sum of $A$ is zero mod $2$.

We show this forces $A$ to be the zero matrix.

Let $C_j=\sum_i a_{i,j}$ and assume $C_j\equiv 0$ for all $j$. Then for any $i,j$, the parity condition in $A$ gives

$$ a_{i,j}\equiv \sum_{j'\ne j} a_{i,j'}+\sum_{i'\ne i} a_{i',j}. $$

Rewrite the right-hand side using row and column sums:

$$ \sum_{j'\ne j} a_{i,j'} = R_i - a_{i,j},\quad \sum_{i'\ne i} a_{i',j}=C_j-a_{i,j}, $$

$$ a_{i,j}\equiv (R_i-a_{i,j})+(C_j-a_{i,j})=R_i+C_j. $$

But summing this over $j$ shows $R_i\equiv 0$ for all $i$ (since all $C_j=0$), hence $R_i=0$. Substituting back yields

$$ a_{i,j}\equiv 0. $$

Thus every entry of $A$ is zero, contradicting that $A$ has no zero row (indeed no zero row or column implies the matrix is not identically zero).

Therefore the central row of $B$ is not identically zero.

4.3 Central column is not identically zero

Similarly, assume the central column is identically zero:

$$ b_{i,0}=0\quad \forall i\neq 0. $$

Then every row sum of $A$ is zero, i.e. $R_i=0$ for all $i$. Repeating the same argument as above yields $a_{i,j}=0$ for all $i,j$, again contradicting perfection of $A$. Hence the central column is not identically zero.

5. Conclusion

All cells of $B$ satisfy the parity condition, and every row and column of $B$ contains at least one $1$. Therefore $B$ is a perfect $(2m+1)\times(2n+1)$ parity pattern. ∎