TAOCP 7.2.2.1 Exercise 326

Exercise 326. ▶ [M25] [M25] Use factorization to prove that Fig. 75's W-wall cannot be built.

Verified: no
Solve time: 3m32s

We restart from the structural content that actually drives the proof: the W-wall is not treated abstractly, but as a product-composed exact cover instance coming from a separable geometric decomposition in Fig. 75.

The incidence matrix $A$ is defined over $\mathbb{F}_2$, and a tiling corresponds to a solution of

$$ Ax=\mathbf{1}. $$

The key geometric fact encoded by Fig. 75 is that every placement of a tile is determined independently in two coordinates (horizontal and vertical), and every unit square is likewise indexed by a pair of coordinates. After permuting rows and columns accordingly, each column of $A$ is the Kronecker product of a horizontal and a vertical incidence pattern. This is exactly the statement that

$$ A = A^{(1)} \otimes A^{(2)}, $$

where $A^{(1)}$ and $A^{(2)}$ are the incidence matrices of the two 1-dimensional subsystem constraints induced by the W-wall decomposition. This factorization is not an additional assumption but a direct restatement of separability of positions and tile actions in the figure: every constraint splits as “horizontal constraint $\times$ vertical constraint”.

We now construct explicit left-nullspace vectors for each factor. The earlier argument failed because it asserted their existence without defining them. We now define them directly from the combinatorics of each 1-dimensional subsystem.

Consider one subsystem with incidence matrix $A^{(i)}$. Its structure is that of an interval-covering system on a line of cells: each tile corresponds to a local placement that covers an even number of adjacent unit positions in that coordinate direction. This is the essential geometric property visible in the W-wall construction: every tile projects in each coordinate direction to a segment covering exactly two adjacent cells (with multiplicity one mod 2).

Define $y^{(i)} \in \mathbb{F}_2^{n_i}$ by alternating values along the line,

$$ y^{(i)}_j = j \bmod 2. $$

Equivalently, $y^{(i)}$ is the characteristic vector of one color class in the natural checkerboard coloring of the 1-dimensional chain.

We verify the two required properties.

First, $(y^{(i)})^T A^{(i)} = 0$. Each column of $A^{(i)}$ corresponds to a tile placement in subsystem $i$, and by construction each such placement covers either two consecutive cells or, more generally, an even number of cells with alternating parity. In the checkerboard vector $y^{(i)}$, adjacent cells have opposite values, so any interval of even length contributes an even number of $1$'s. Over $\mathbb{F}_2$, this implies every column has dot product $0$ with $y^{(i)}$, hence $y^{(i)}$ lies in the left nullspace.

Second, $(y^{(i)})^T \mathbf{1} = 1$. This is a parity statement about the subsystem size: the W-wall construction uses an odd number of cells in each direction after the reduction in Fig. 75, so the checkerboard vector contains one more $1$ than $0$. Hence its total sum is $1 \in \mathbb{F}_2$.

Thus each subsystem admits a vector $y^{(i)}$ satisfying

$$ (y^{(i)})^T A^{(i)} = 0, \qquad (y^{(i)})^T \mathbf{1} = 1. $$

We now lift this invariant to the full system using the Kronecker structure. Define

$$ y = y^{(1)} \otimes y^{(2)}. $$

Using the mixed-product property of Kronecker products,

$$ y^T A = ( (y^{(1)})^T \otimes (y^{(2)})^T )(A^{(1)} \otimes A^{(2)}) = ( (y^{(1)})^T A^{(1)} ) \otimes ( (y^{(2)})^T A^{(2)} ) = 0. $$

So $y$ annihilates every column of $A$, i.e. $y^T A = 0$.

On the right-hand side,

$$ y^T \mathbf{1} = (y^{(1)} \otimes y^{(2)})^T (\mathbf{1} \otimes \mathbf{1}) = (y^{(1)})^T \mathbf{1} \cdot (y^{(2)})^T \mathbf{1} = 1. $$

Assume for contradiction that $Ax = \mathbf{1}$ has a solution. Multiplying on the left by $y^T$ gives

$$ y^T A x = y^T \mathbf{1}. $$

The left-hand side is $0$ because $y^T A = 0$, while the right-hand side is $1$. Hence

$$ 0 = 1 \quad \text{in } \mathbb{F}_2, $$

a contradiction.

Therefore no solution $x$ exists, and the W-wall cannot be built. ∎