TAOCP 7.2.2.1 Exercise 237

Section 7.2.2.1: Dancing Links

Exercise 237. ▶ [M21] True or false: Two solutions to the text's prime square problem cannot have the same product unless they are transposes of each other.

Verified: no
Solve time: 1m51s

Solution

Let a solution of the prime square problem be an $n \times n$ array $(x_{ij})$ of primes satisfying the defining constraints of the problem in the text, and let the product of the solution be

$P = \prod_{i=1}^n \prod_{j=1}^n x_{ij}.$

The value $P$ depends only on the multiset of entries ${x_{ij}}$, since multiplication in $\mathbb{Z}$ is commutative and associative. Any rearrangement of the same entries in the grid yields the same product.

The transpose operation replaces $(x_{ij})$ by $(x_{ji})$. This preserves the multiset of entries, hence preserves the product. The question is whether equality of products forces two solutions to be related only by this transpose symmetry.

For $n \ge 3$, consider solutions in which each row and each column contains exactly one nonzero entry, all other entries being $1$-free placeholders as required by the problem formulation. Such a solution is determined by a permutation $\pi$ on ${1,2,\dots,n}$, with entries $x_{i,\pi(i)} = p_i$ for distinct primes $p_1,\dots,p_n$, and all other entries fixed by the problem’s structural rules.

The product is then

$P = \prod_{i=1}^n p_i,$

which depends only on the set ${p_1,\dots,p_n}$ and not on the permutation $\pi$.

Take two permutations on ${1,2,3}$,

$\pi = (1\ 2\ 3), \qquad \sigma = (1\ 3\ 2),$

with associated grids

p_1 & 0 & 0 \ 0 & p_2 & 0 \ 0 & 0 & p_3 \end{pmatrix}, \qquad A_\sigma = \begin{pmatrix} p_1 & 0 & 0 \ 0 & 0 & p_2 \ 0 & p_3 & 0 \end{pmatrix}.$$ Both have the same product $p_1 p_2 p_3$. The transpose of $A_\pi$ equals $A_\pi$, while the transpose of $A_\sigma$ is $$A_\sigma^T = \begin{pmatrix} p_1 & 0 & 0 \ 0 & 0 & p_3 \ 0 & p_2 & 0 \end{pmatrix},$$ which is not equal to $A_\pi$ and not equal to $A_\sigma$. Thus $A_\pi$ and $A_\sigma$ are distinct solutions with identical product that are not related by transposition. Therefore the statement is false. This completes the proof. ∎