Solution to Problem 10470 proposed by D. Knuth in the American Math. Monthly, 102 no. 7 (1995) p. 655 Luis Goddyn, Dept. of Mathematics and Statistics, Simon Fraser University, Burnaby, BC, Canada V5A 1S6

                                        goddyn@sfu.ca

Sept 21, 1995

Answer to part (a). Let (a_{ij}) be an n by n matrix and let M be the set of permutations σ of [n] := {1, 2, …, n} such that ∏_{i=1}^{n} a_{i,σ(i)} ≠ 0. Let σ ∈ M, and suppose that σ has exactly z(σ) orbits on [n]. If (a_{ij}) is a special matrix, then for each orbit Z of σ, the multiset {a_{i,σ(i)} : i ∈ Z} contains exactly one 1, with the remaining entries being −1. Thus ∏_{i=1}^{n} a_{i,σ(i)} = (−1)^{n−z(σ)} = sign(σ) and we have the following.

For any special matrix (a_{ij}), det(a_{ij}) = ∑_{σ∈M} sign(σ) ∏_{i=1}^{n} a_{i,σ(i)} = |M|.  (1)

A subset S ⊆ [n] is called a barrier of (a_{ij}) if |N(S)| < |S| where N(S) := {j ∈ [n] : ∃i ∈ S, a_{ij} ≠ 0}. Phillip Hall’s theorem (On representatives of subsets. J. London Math. Soc. 10 (1935) 26–30) asserts the following.

For any matrix (a_{ij}), |M| = 0 if and only if (a_{ij}) has a barrier.

With this and (1) we have shown that a special matrix (a_{ij}) is minimal if and only if it has a barrier, but changing any entry a_{ij} with i ≥ j from 0 to 1 results in a matrix with no barriers.

Let (a_{ij}) be a special n by n matrix, and let S ⊆ [n]. Because of the −1 entries in (a_{ij}) we have {i + 1 : i ∈ S − {n}} ⊆ N(S) whence |N(S)| ≥ |S| − 1. If S is a barrier, then this inequality is tight and we have the following.

Every barrier S of an n by n special matrix contains n and satisfies N(S) = {j : j − 1 ∈ S − {n}}. (2)

Let (a_{ij}) be a minimal matrix and let S be a barrier of (a_{ij}) having minimum cardinality. Suppose there is an entry a_{ij} = 0 such that j ≤ i. If either i ∉ S or j ∈ N(S), then S is also a barrier of the special matrix obtained by changing a_{ij} to 1, contradicting the minimality of (a_{ij}). It follows that S is the unique barrier of (a_{ij}) and, by (2), the entries of (a_{ij}) are completely determined by S as follows.

a_{ij} = \{ \begin{matrix}1 & if j ≤ i and either i ∉ S or j − 1 ∈ S \\ −1 & if j = i + 1 \\ 0 & otherwise. \end{matrix}  (3)

As (3) defines an n by n minimal matrix for any subset S ⊆ [n] with n ∈ S, there are exactly 2^{n−1} such matrices.

Answer to part (b). Let S = {s_{1}, s_{2}, …, s_{k}} ⊆ [n] where s_{1} < s_{2} < ⋯ < s_{k} = n, let T = [n] − S, and let (a_{ij}) be the minimal matrix determined by S as above. Each 1 which appears in (a_{ij}) has one of two types:

type-T: a_{ij} = 1 where i ∈ T and 1 ≤ j ≤ i.

type-S: a_{ij} = 1 where i ∈ S, j − 1 ∈ S and j ≤ i.

The number of type-T entries in (a_{ij}) is ∑ T. We count the type-S entries by summing over the columns in {j : j − 1 ∈ S}; for any r ∈ {1, 2, …, k − 1}, there are exactly k − r type-S entries a_{ij} with j = s_{r} + 1, namely those with i ∈ S ∩ \{j, j + 1, …, n\} = \{s_{r+1}, s_{r+2}, …, s_{k}\}. In total there are ∑_{r=1}^{k−1}(k − r) = \binom{|S|}{2} type-S entries in (a_{ij}). The number of zeros appearing on or below the diagonal in (a_{ij}) is calculated \binom{n+1}{2} − ∑ T − \binom{|S|}{2} = ∑ S − \binom{|S|}{2} = ∑_{r=1}^{k}(s_{r} − r + 1). For a fixed k, this sum is maximized when S = \{n − k + 1, n − k + 2, …, n\} whence the sum equals k(n − k + 1). This expression attains the maximum value ⌊(n + 1)^{2}/4⌋ when k is an integer closest to (n + 1)/2. Including the zeros above the diagonal, we have that the maximum number of zeros in an n by n minimal matrix is

⌊(n + 1)^{2}/4⌋ + \binom{n − 1}{2} = ⌊(3n^{2} − 4n + 5)/4⌋ = n^{2} − ⌈(n + 5)(n − 1)/4⌉.

□