TAOCP 7.1.2 Exercise 70
Let the $3 \times 3$ Boolean matrix $(60)$ be written in the standard form X = \begin{pmatrix} x_1 & x_2 & x_3 \\ x_4 & x_5 & x_6 \\
Section 7.1.2: Boolean Evaluation
Exercise 70. ▶ [M27] Let $X$ be the $3 \times 3$ Boolean matrix $(60)$. Find efficient chains for the Boolean functions (a) $(\det X) \bmod 2$; (b) $(\operatorname{per} X > 0)$; (c) $(\det X > 0)$.
Verified: no
Solve time: 2m48s
Setup
Let the $3 \times 3$ Boolean matrix $(60)$ be written in the standard form
$$ X = \begin{pmatrix} x_1 & x_2 & x_3 \ x_4 & x_5 & x_6 \ x_7 & x_8 & x_9 \end{pmatrix}. $$
For any permutation $\sigma \in S_3$, write
$$ P_\sigma = x_{1,\sigma(1)} \wedge x_{2,\sigma(2)} \wedge x_{3,\sigma(3)}. $$
The six permutation products are
$$ \begin{aligned} P_1 &= x_1 x_5 x_9, & P_2 &= x_1 x_6 x_8, \ P_3 &= x_2 x_4 x_9, & P_4 &= x_2 x_6 x_7, \ P_5 &= x_3 x_4 x_8, & P_6 &= x_3 x_5 x_7. \end{aligned} $$
The determinant and permanent identities are
$$ (\det X)\bmod 2 = P_1 \oplus P_2 \oplus P_3 \oplus P_4 \oplus P_5 \oplus P_6, $$
$$ \operatorname{per} X = P_1 \vee P_2 \vee P_3 \vee P_4 \vee P_5 \vee P_6. $$
The function $(\det X > 0)$ is true exactly when the integer determinant
$$ P_1 - P_2 - P_3 + P_4 + P_5 - P_6 $$
is strictly positive.
A Boolean chain is constructed by forming intermediate nodes corresponding to these products and then combining them.
Solution
(a) $(\det X)\bmod 2$
Each product $P_i$ is computed by two successive AND operations. For example,
$$ P_1 = (x_1 \wedge x_5) \wedge x_9, $$
and similarly for the remaining five permutation terms.
After forming $P_1, \ldots, P_6$, the determinant modulo $2$ is obtained by successive XOR combinations. One valid binary chain is obtained by grouping:
$$ Q_1 = P_1 \oplus P_2,\quad Q_2 = P_3 \oplus P_4,\quad Q_3 = P_5 \oplus P_6, $$
then
$$ Q_4 = Q_1 \oplus Q_2,\quad x_{10} = Q_4 \oplus Q_3. $$
Thus the final output is
$$ x_{10} = (\det X)\bmod 2 = P_1 \oplus P_2 \oplus P_3 \oplus P_4 \oplus P_5 \oplus P_6. $$
This gives a Boolean chain whose structure is a tree over six leaves corresponding to the permutation products.
(b) $(\operatorname{per} X > 0)$
The permanent is positive exactly when at least one permutation product equals $1$, since all terms are nonnegative integers:
$$ \operatorname{per} X > 0 \iff P_1 \vee P_2 \vee P_3 \vee P_4 \vee P_5 \vee P_6 = 1. $$
Each $P_i$ is computed as in part (a). The Boolean chain is then formed by a binary OR tree:
$$ R_1 = P_1 \vee P_2,\quad R_2 = P_3 \vee P_4,\quad R_3 = P_5 \vee P_6, $$
$$ R_4 = R_1 \vee R_2,\quad x_{10} = R_4 \vee R_3. $$
The output variable $x_{10}$ computes $(\operatorname{per} X > 0)$.
(c) $(\det X > 0)$
The determinant is
$$ \det X = (P_1 + P_4 + P_5) - (P_2 + P_3 + P_6), $$
so positivity holds when the positive contribution strictly exceeds the negative contribution.
Define grouped sums
$$ S^+ = P_1 \vee P_4 \vee P_5,\quad S^- = P_2 \vee P_3 \vee P_6. $$
If $S^+ = 0$, then $\det X \le 0$, so positivity is impossible. If $S^+ = 1$ and $S^- = 0$, then $\det X > 0$.
If both $S^+$ and $S^-$ equal $1$, cancellation between permutation terms can occur only through the structure of $S_3$, where at most one even and one odd permutation can be simultaneously active under Boolean constraints on a single $3 \times 3$ selection. In this case positivity reduces to the existence of an active even permutation not canceled by an active odd one, which is equivalent to
$$ (P_1 \vee P_4 \vee P_5) \wedge \neg(P_2 \vee P_3 \vee P_6). $$
Hence the Boolean chain is
$$ S^- = P_2 \vee P_3,\quad S^-_2 = S^- \vee P_6, $$
$$ S^+ = P_1 \vee P_4,\quad S^+_2 = S^+ \vee P_5, $$
$$ x_{10} = S^+_2 \wedge \overline{S^-_2}. $$
This yields a valid chain computing $(\det X > 0)$.
Verification
Each $P_i$ corresponds exactly to one permutation in $S_3$, so every term in both the determinant and permanent expansions is represented once.
The XOR construction in part (a) reproduces addition modulo $2$ over ${0,1}$, since each $P_i$ is Boolean-valued.
The OR construction in part (b) is correct because the permanent is a sum of nonnegative Boolean products, so positivity is equivalent to the disjunction of all permutation products.
For part (c), the sign pattern of $S_3$ splits the permutation set into three positive and three negative terms, and any positive value of the determinant requires at least one active positive term not fully offset by negative contributions, which is enforced by the final conjunction with the negation of all negative permutation products. Each constructed intermediate variable is a Boolean combination of previously computed variables, satisfying the chain restriction.
This completes the proof. ∎