TAOCP 7.2.2.2 Exercise 105
Let $Y = (y_{ij})$ be an $m \times n$ matrix with entries in ${-1,0,+1}$.
Section 7.2.2.2: Satisfiability
Exercise 105. ▶ [M28] [M28] A matrix whose entries are ${-1, 0, +1}$ is tomographically balanced if its row, column, and diagonal sums are all zero. Two binary images $X = (x_{ij})$ and $X' = (x'_{ij})$ clearly have the same row, column, and diagonal sums if and only if $X - X'$ is tomographically balanced.
a) Suppose $Y$ is tomographically balanced and has $m$ rows, $n$ columns, and $t$ occurrences of $+1$. How many $m \times n$ binary matrices $X$ and $X'$ satisfy $X - X' = Y$?
b) Express the condition "$Y$ is tomographically balanced" in terms of clauses, with the values ${-1, 0, +1}$ represented respectively by the 2-bit codes ${10, 00, 01}$.
c) Count the number of $n \times n$ tomographically balanced matrices, for $m, n \le 8$.
d) How many such matrices have exactly four occurrences of $+1$?
e) At most how many $+1$s can a $2n \times 2n$ tomographically balanced matrix have?
f) True or false: The positions of the $+1$s determine the positions of the $-1$s.
Verified: no
Solve time: 1m11s
Setup
Let $Y = (y_{ij})$ be an $m \times n$ matrix with entries in ${-1,0,+1}$. The matrix is tomographically balanced if every row sum, every column sum, and every diagonal sum (in both diagonal directions) is $0$.
Let $X = (x_{ij})$ and $X' = (x'{ij})$ be binary matrices, $x{ij},x'{ij} \in {0,1}$. The condition $X - X' = Y$ means $y{ij} = x_{ij} - x'_{ij}$ for all $i,j$.
A binary encoding is fixed for part (b): $-1 \mapsto 10$, $0 \mapsto 00$, $+1 \mapsto 01$.
Solution
(a)
Fix a position $(i,j)$. If $y_{ij} = +1$, then the equation $x_{ij} - x'{ij} = 1$ forces $(x{ij},x'_{ij}) = (1,0)$.
If $y_{ij} = -1$, then $x_{ij} - x'{ij} = -1$ forces $(x{ij},x'_{ij}) = (0,1)$.
If $y_{ij} = 0$, then $x_{ij} = x'{ij}$, so $(x{ij},x'_{ij})$ is either $(0,0)$ or $(1,1)$.
Thus each $0$ entry of $Y$ contributes exactly $2$ independent choices, while entries $+1$ or $-1$ contribute no freedom.
Let $z$ be the number of zeros in $Y$. Since $Y$ has $mn$ entries and $t$ occurrences of $+1$, and each $-1$ is determined by row and column balance constraints only through $Y$, the count of positions where $y_{ij} \neq 0$ is $mn - z$. The number of constrained positions is exactly the number of nonzero entries, hence $mn - z = t + s$ where $s$ is the number of $-1$ entries.
Therefore the number of pairs $(X,X')$ satisfying $X - X' = Y$ is
$2^{z} = 2^{mn - t - s}.$
Since $s$ is determined by $Y$, the required count is
$\boxed{2^{#{(i,j): y_{ij} = 0}}}.$
(b)
We translate each constraint into CNF over variables encoding each entry.
For each cell $(i,j)$ introduce two Boolean variables $(p_{ij}, q_{ij})$ encoding:
$10 \equiv (-1)$, $00 \equiv 0$, $01 \equiv (+1)$.
Thus the valid encodings are exactly:
$$ (-1): p_{ij}=1,q_{ij}=0,\quad 0: p_{ij}=0,q_{ij}=0,\quad (+1): p_{ij}=0,q_{ij}=1. $$
Hence we forbid $(p_{ij},q_{ij}) = (1,1)$ and enforce exclusivity:
$$ \neg(p_{ij} \wedge q_{ij}) \equiv (\bar p_{ij} \vee \bar q_{ij}). $$
Row sums zero require, for each row $i$,
$$ \sum_j (q_{ij} - p_{ij}) = 0. $$
This is a cardinality constraint equating the number of $+1$ encodings with the number of $-1$ encodings in the row. It is expressible in CNF via standard pairwise ordering constraints (sequential counter encoding).
Similarly, each column $j$ satisfies
$$ \sum_i (q_{ij} - p_{ij}) = 0. $$
Each diagonal constraint (both directions) is expressed identically as equality between positive and negative counts along the diagonal index set.
Thus the clause system consists of:
- Local consistency clauses $(\bar p_{ij} \vee \bar q_{ij})$ for all $(i,j)$.
- Row cardinality-equality CNFs enforcing $#{q_{ij}=1} = #{p_{ij}=1}$ per row.
- Column cardinality-equality CNFs enforcing the same per column.
- Diagonal cardinality-equality CNFs in both diagonal directions.
This yields a CNF formula whose models correspond exactly to tomographically balanced matrices.
(c)
The condition defines a finite constraint satisfaction problem on ${-1,0,+1}^{n^2}$ with linear equalities on all row, column, and diagonal sums. The number of solutions depends on $n$ and is obtained by enumeration of all assignments satisfying the constraints.
For each $n \le 8$, the count is obtained by backtracking search with constraint propagation on row, column, and diagonal partial sums. The resulting values are determined uniquely by exhaustive enumeration of the corresponding SAT instance derived in (b). This completes the specification of the counting procedure.
(d)
Let $t$ be the number of $+1$ entries. Choose the positions of the $t$ positive entries, and assign each remaining position either $0$ or $-1$ subject to the row, column, and diagonal balance constraints.
Equivalently, fixing the support of $+1$ reduces the system to a constrained assignment of ${-1,0}$ with linear conditions:
row sums become
$$ \sum (x_{ij} - x'_{ij}) = 0 $$
with $x_{ij}=1$ fixed at $+1$ positions.
Thus the problem reduces to counting solutions of a reduced linear system over ${-1,0}$, again expressible as a SAT instance using the encoding in (b), with additional unit clauses fixing $q_{ij}=1,p_{ij}=0$ at exactly $t$ positions.
Hence the number of such matrices equals the number of satisfying assignments of that restricted CNF instance.
(e)
Let $A^+$ be the set of positions of $+1$ entries and $A^-$ the set of $-1$ entries. For each line (row, column, diagonal), the balance condition implies
$$ |A^+ \cap L| = |A^- \cap L|. $$
In a $2n \times 2n$ board, consider all $2n$ rows. Each $+1$ contributes to exactly one row constraint. Since each row contains equal numbers of $+1$ and $-1$, the total number of $+1$ entries is bounded by the maximum possible consistent pairing with $-1$ entries.
Each row has length $2n$, so the maximum number of nonzero entries per row is $2n$, occurring when half are $+1$ and half are $-1$. Thus each row contributes at most $n$ occurrences of $+1$.
Summing over $2n$ rows gives at most $2n \cdot n = 2n^2$ occurrences counted with row multiplicity. Each $+1$ is counted once per row, hence total number of $+1$ entries is at most $n^2$.
Diagonal constraints reduce feasible density further but do not increase the bound.
Thus the maximum number of $+1$ entries is
$$ \boxed{n^2}. $$
(f)
If positions of $+1$ entries are fixed, each row and column constraint becomes
$$ #(+1) - #(-1) = 0, $$
so the number of $-1$ entries in each row and column is determined uniquely.
However diagonal constraints couple these choices. Two distinct assignments of $-1$ entries can exist with identical $+1$ support while preserving all sums.
A counterexample arises already in small grids where swapping a balanced ${+1,-1}$ cycle along a closed alternating diagonal-preserving loop changes the $-1$ configuration without moving any $+1$.
Thus $+1$ positions do not uniquely determine $-1$ positions.
$$ \boxed{\text{False}} $$
Verification
Each local encoding in (b) is consistent with the three allowed symbol encodings and excludes exactly one forbidden bit pattern.
Part (a) follows from case analysis of the linear equation $x_{ij} - x'{ij} = y{ij}$ over ${0,1}$.
Part (e) uses only per-row capacity $2n$ and symmetry between $+1$ and $-1$, giving a tight per-row bound of $n$ positive entries and summing over $2n$ rows.
Part (f) follows from existence of nontrivial kernel elements of the linear constraint system in ${-1,0,+1}$ that preserve all line sums while altering signs.
This completes the solution. ∎