On Minors of Maximal Determinant Matrices

Richard P. Brent Mathematical Sciences Institute Australian National University Canberra, ACT 0200 Australia

                  minors@rpbrent.com

Judy-anne H. Osborn CARMA The University of Newcastle Callaghan, NSW 2308 Australia

           Judy-anne.Osborn@newcastle.edu.au

Abstract

By an old result of Cohn (1965), a Hadamard matrix of order n has no proper Hadamard submatrix of order m > n/2. We generalize this result to maximal determinant submatrices of Hadamard matrices, and show that an interval of length ∼ n/2 is excluded from the allowable orders. We make a conjecture regarding a lower bound for sums of squares of minors of maximal determinant matrices, and give evidence to support it. We give tables of the values taken by the minors of all maximal determinant matrices of orders ≤ 21 and make some observations on the data. Finally, we describe the algorithms that were used to compute the tables.

1 Introduction

A {+1, −1}-matrix (abbreviated “{±1}-matrix” below) is a matrix whose elements are +1 or −1. The Hadamard maximal determinant problem, posed by Hadamard [18], is to find the maximal determinant D(n) of an n × n {±1}-matrix of given order n. A matrix that attains the maximum is a maximal determinant matrix (abbreviated maxdet matrix). Such matrices, of which Hadamard matrices are a special case, are of interest in combinatorics and have applications in statistical design [23], coding theory and signal processing [20, 35, 39]. In design theory a maxdet matrix is also known as a saturated D-optimal design.

Finding maxdet matrices is in general difficult, with the difficulty depending on the congruence class of n (mod 4). Most is known for n ≡ 0 (mod 4) (the Hadamard orders), and least for n ≡ 3 (mod 4).^{1} Maxdet matrices are known for orders 1 through 21 inclusive; for n = 22 and n = 23 there are conjectures (see [35]) but as yet no proofs of maximality. Constructions exist for various infinite families and ad-hoc examples; see [36].

Consider the k × k submatrices S_{k}(A) of an n × n {±1}-matrix A, where 0 < k ≤ n. For M ∈ S_{k}(A), we say that det(M) is a minor of order k of A. Usually only the absolute value of det(M) is of interest.

One method for finding maxdet or large-determinant matrices involves choosing a largedeterminant matrix of a slightly smaller (or larger) order than the desired order, possibly perturbing it by a low-rank modification, and adding (or removing) a small number of suitably chosen rows and columns. For example, Solomon [35, 42] found a (conjectured) maxdet matrix of order 33 and determinant 441 × 2^{74} in this way by starting with an appropriate Hadamard matrix of order 32, and in [8, 27, 31] the method was used to obtain lower bounds on D(n).

This motivates our interest in the minors of maxdet matrices, and in particular the question: What is the largest order of a maxdet matrix contained as a proper submatrix of a given maxdet matrix? In this paper we answer this question for the maxdet submatrices of maxdet matrices of orders n ≤ 21 by computing all minors of maxdet matrices of these orders. Our work extends that of earlier researchers who have considered minors of Hadamard and maxdet matrices with other applications in mind, such as the problem of growth in Gaussian elimination [13, 26, 28, 29, 38].

Schmidt [37, p. 441] says “The nature of the construction ⋯ is in line with the computer assisted observation that binary matrices with maximal determinants may not contain large order submatrices with large determinants”. Whether this is true in general depends on the precise meaning of “large”. Certainly there are exceptions. For example, the maxdet {±1}-matrix of order 17 contains a maxdet (Hadamard) submatrix of order 16.

In Theorem 3 of §2 we give a new proof of an old result of Cohn [11] that a Hadamard matrix of order n can not have a proper Hadamard submatrix of order m > n/2. We then generalize the proof to cover maxdet submatrices of Hadamard matrices, and show, assuming the Hadamard conjecture, that a Hadamard matrix of order n can not have a maxdet submatrix M of order m ≥ n/2 + 5 log n unless m ≥ n − 2 (see Theorem 4). In other words, m can not lie in the interval [n/2 + 5 log n, n − 2). Without the assumption of the Hadamard conjecture, we can still exclude an interval [n/2 + o(n), n − o(n)) of length ∼ n/2; see Theorem 6 and Remark 7. These results partially confirm the remark of Schmidt quoted above. However, they apply only to sub-matrices of Hadamard matrices. Except in small cases that are amenable to explicit computation, we have not excluded the possibility that a maxdet matrix of order n ≢ 0 (mod 4) has a maxdet submatrix of any given order m < n.

In §3 we define two sequences related to the sets of minors of maxdet matrices, and give the first 21 terms of each sequence.

1See Ðokovic and Kotsireas [15] for a recent summary of what is known about the cases n ≡ 2 (mod 4), and Brent et al. [7] for the cases n ≡ 1 (mod 2).

In §4 we describe the minors that occur in maxdet matrices of orders 1 through 21, and make some observations on the patterns that occur. We mention a result (Proposition 16), on small minors of Hadamard matrices, which was suggested by the data before a proof was found.

Motivated by Turán’s result [44] that the expected value of det(A)^{2} is m! for random {±1} matrices of order m, we consider the mean value of det(M)^{2} over all m × m submatrices of maxdet matrices of order n ≥ m, and conjecture that it is bounded below by m! (see Conjecture 15). The conjecture is consistent with our computations for 1 ≤ m ≤ n ≤ 21.

Finally, in §5 we describe the algorithms that we used to compute minors of square {±1}- matrices, as well as some related algorithms that were considered but rejected for various reasons.

1.1 Hadamard equivalence and HT-equivalence^{2}

Two {±1}-matrices are Hadamard equivalent if one can be obtained from the other by negating rows or columns, and/or by interchanging rows or columns. Clearly the answers to the questions posed above about minors are the same for all matrices in a Hadamard equivalence class, and also for any matrix A and its transpose (dual) A^{T}. Hence, it is useful to define the notion of HT-equivalence by saying that two matrices A and B are HT-equivalent if A is Hadamard-equivalent to B or A is Hadamard-equivalent to B^{T}. For example, there are 5 distinct Hadamard equivalence classes of Hadamard matrices of order 16, but two of these classes contain matrices that are dual to those in the other class, so there are only 4 distinct HT-equivalence classes.

2 Excluded minors of Hadamard matrices

In this section we consider the possible orders of submatrices M of a Hadamard matrix H, satisfying the condition that M is Hadamard (see Theorem 3) or, more generally, that M is a maxdet matrix (see Theorems 4–6).

Recently Szöllősi [43, Proposition 5.5] established an elegant correspondence between the minors of order m and of order n − m of a Hadamard matrix of order n. His result applies to complex Hadamard matrices, of which {±1} Hadamard matrices are a special case. More precisely, if d + m = n, 0 < d < n, then corresponding to each m × m submatrix with determinant μ there is a d × d submatrix with determinant ±n^{n/2−d}μ. Only special cases (for small d or m) were known before Szöllősi (see for example [13, 28, 38, 40]). This is perhaps surprising, as Szöllősi’s critical Lemma 5.7 follows in a straightforward manner from Jacobi’s determinant identity [21]. We use the following corollary of Szöllősi’s theorem.^{3} Corollary 1. Suppose that a Hadamard matrix H of order n has an m × m submatrix M, where n/2 ≤ m ≤ n. Then

2There seems to be no widely-accepted name for this concept. In [5] HT-equivalence is called “extended Hadamard equivalence”. Wanless [45] calls an HT-equivalence class a “resemblance class”.

3Corollary 1 is essentially the same as Cohn [11, Theorem 3], the difference being that Cohn replaces D(n − m) by the Hadamard bound. However, Cohn’s proof is quite different from ours.

| det(M)| ≤ n^{m−n/2}D(n − m) .

Proof. By Szöllősi’s theorem, | det(M)| = n^{n/2−d}| det(M′)|, where d = n − m and M′ is some d × d submatrix of H. Since n/2 − d = m − n/2 and | det(M′)| ≤ D(d) by the definition of D, the corollary follows.

The following lower bound on D(m) is given in [8, Corollary 3].

Proposition 2. Assume the Hadamard conjecture.^{4} Then, for m ≥ 4, we have D(m) ≥ 4m^{m/2−1}.

Suppose that a Hadamard matrix H of order n has a maxdet submatrix M of order m. Corollary 1 gives an upper bound on | det(M)|, and Proposition 2 gives a lower bound. Theorems 3–4 show that these bounds are incompatible for certain values of m. Theorem 3 considers the case that M is a Hadamard matrix, and Theorem 4 considers the more general case that M is a maxdet matrix. We have stated Theorem 4 under the assumption of the Hadamard conjecture, but a weaker result is provable without this assumption – see Theorem 6.

Theorem 3 was proved by Cohn [11, Theorem 2], but we give a different proof which generalizes to give proofs of Theorems 4–6.

Theorem 3 (Cohn). Let H be a Hadamard matrix of order n having a Hadamard submatrix M of order m < n. Then m ≤ n/2.

Proof. The theorem is trivial if m ≤ n/2, so assume that n > m > n/2. Let d = n − m. Since M exists and | det(M)| = m^{m/2}, Corollary 1 and Hadamard’s bound for D(d) give

m^{m/2} ≤ n^{m−n/2}d^{d/2} .  (1)

Squaring both sides of (1), we have (m/n)^{m} ≤ (d/n)^{d}. Taking n-th roots and defining x := m/n ∈ (0, 1), we see that

x^{x} ≤ (1 − x)^{1−x}.

This inequality is equivalent to f(x) ≤ 0, where f : [0, 1] → ℝ is defined by

f(x) = \begin{cases}x ln x − (1 − x) ln(1 − x), & if x ∈ (0, 1); \\ 0, & otherwise. \end{cases}

It is easy to verify that f(1/2) = 0, f′(x) = 2 + ln x + ln(1 − x), and

f′′(x) = \frac{1 − 2x}{x(1 − x)} < 0 in (1/2, 1).

Thus, f(x) > 0 in (1/2, 1), so we must have x ≤ 1/2 or x = 1. The case x = 1 is ruled out because it implies that m = n, contrary to the assumption that m < n. Thus x ≤ 1/2, which implies that m ≤ n/2.

4It is sufficient to assume that Hadamard matrices of order 4k exist for all positive integers k ≤ (m+2)/4.

This is known to be true for 4k < 668, see [24, 39].

Theorem 4. Assume the Hadamard conjecture. Let H be a Hadamard matrix of order n having a maxdet submatrix M of order m < n. Then m < (n/2 + 5 ln n) or m ≥ n − 2.

Proof. The result is trivial if m ≤ n/2, and n/2+5 ln n > n−3 for n ≤ 28, so we can assume that m > n/2 > 14. By Proposition 2 and Corollary 1, we have

m^{m/2} (\frac{4}{m}) ≤ n^{m−n/2}d^{d/2},  (2)

where d = n − m. We prefer to use the slightly weaker inequality

m^{m/2} (\frac{4}{n}) ≤ n^{m−n/2}d^{d/2}.  (3)

Taking logarithms, and defining x := m/n and f as in the proof of Theorem 3, we obtain

f(x) ≤ \frac{2 ln(n/4)}{n}.  (4)

The right side of this inequality is positive (since n > 4) and independent of x (this is why we used (3) instead of (2)). We showed in the proof of Theorem 3 that f(1/2) = f(1) = 0 and f′′(x) < 0 on (1/2, 1). Let

x_{max} = (1 + \sqrt{1 − 4/e^{2}})/2 ≈ 0.84

be the (unique) point in (1/2, 1) at which f′(x) vanishes. Thus f(x) attains its maximum value at x = x_{max}. Since 2 ln(n/4)/n < 0.14 < f(x_{max}) ≈ 0.15 for n > 28, the inequality (4) is not satisfied for all x ∈ (1/2, 1), and there is a unique interval (x_{0}, x_{1}) ⊆ (1/2, 1) on which f(x) > 2 ln(n/4)/n, with x_{max} ∈ (x_{0}, x_{1}). (Here x_{0} and x_{1} depend on n but not on m.) It follows that there can not exist a maxdet submatrix of order m with x_{0} < m/n < x_{1}.

To locate x_{1} we consider the case d = n − m = 3. The inequality (3) gives

(\frac{n − 3}{n})^{n−3} ≤ \frac{27}{16n} ,  (5)

but the left side of this inequality is bounded away from zero as n → ∞, whereas the right side tends to zero. Thus, the inequality can not hold for large n. In fact, a computation shows that (5) can only hold for n < 29. Thus, for n ≥ 29 an interval (x_{0}, x_{1}) as above exists, with x_{1} > 1 − 3/n, so m = n − 3 is not a possible order of a maxdet submatrix M.

We now show that nx_{0} < n/2 + 5 ln n. Define ν := n/2, δ := m − ν. Thus m = ν + δ, d = ν − δ, and squaring the inequality (3) gives

(ν + δ)^{ν+δ} (\frac{2}{ν})^{2} ≤ (2ν)^{2δ}(ν − δ)^{ν−δ} ,

or equivalently

(\frac{ν + δ}{ν − δ} )^{ν} ≤ (\frac{ν}{2})^{2} (\frac{4ν^{2}}{ν^{2} − δ^{2}} )^{δ} .  (6)

Write z := δ/ν = 2x − 1. We can assume that

0 < z < z_{max} = 2x_{max} − 1 = \sqrt{1 − 4/e^{2}} ≈ 0.68 .

Taking logarithms in (6) gives

\frac{δ}{z} ln (\frac{1 + z}{1 − z} ) ≤ δ(ln 4 − ln(1 − z^{2})) + 2 ln(ν/2).  (7)

Collecting the terms involving δ gives

δ(2 − ln 4 − ε(z)) ≤ 2 ln(ν/2),

where

ε(z) = 2 − \frac{1}{z} ln (\frac{1 + z}{1 − z} ) − ln(1 − z^{2}) = ∑_{k=1}^{∞} \frac{z^{2k}}{k(2k + 1)}

is monotonic increasing on [0, z_{max}], so

ε(z) ≤ ε(z_{max}) < 0.1803,

and thus 2 − ln 4 − ε(z) > 0.4334 for z ∈ (0, z_{max}). It follows that

δ < \frac{2 ln(ν/2)}{0.4334} < 5 ln n.

Remark 5. We do not expect the values m = n − 1 or m = n − 2 to occur for n > 4. They have to be included as possibilities simply because the lower bound on D(n) given by Proposition 2 is too weak to exclude them. It is possible to have m > n/2, for example a maxdet submatrix of order m = n/2 + 1 occurs in Hadamard matrices of orders n = 4 and n = 12.

We can prove a result similar to, but weaker than, Theorem 4 without assuming the Hadamard conjecture. Let the prime gap function λ(n) be the maximum gap between consecutive primes (p_{i}, p_{i+1}) with p_{i} ≤ n. Then we have:

Theorem 6. Let H be a Hadamard matrix of order n ≥ 4 having a maxdet submatrix M of order m < n, and let λ(n) be the prime gap function. Then there exist positive constants c_{1}, c_{2} such that m < n/2 + c_{1}λ(n) ln n or m ≥ n − c_{2}λ(n).

Sketch of proof. The proof is similar to that of Theorem 4, but uses [8, Theorem 1 and Corollary 1] in place of Proposition 2. Thus (3) is replaced by

m^{m/2} (\frac{4}{ne})^{λ(n/2)/2} ≤ n^{m−n/2}d^{d/2},

and (4) by

f(x) ≤ λ(n/2) \frac{ln(ne/4)}{n} .

The remainder of the proof follows that of Theorem 4, except that some of the explicit constants have to be replaced by O(λ(n/2)) terms, and we have to assume that n is sufficiently large, say n ≥ n_{0}. At the end, we can increase c_{1} or c_{2} if necessary to ensure that n/2 + c_{1}λ(n) ln n > n − c_{2}λ(n) for 4 ≤ n < n_{0}.

Remark 7. By a result of Baker, Harman and Pintz [2], λ(n) = O(n^{21/40}), so the excluded interval in Theorem 6 has length ∼ n/2.

Remark 8. It should be possible to sharpen Theorems 4–6 by using the (asymptotically sharper) bounds on D(m) given in [10] instead of the bound of Proposition 2 (this is work in progress).

3 Sequences related to minors

In this section we define two sequences related to the minors of maxdet matrices, and give the first 21 terms in each sequence [34]. In the following definitions, ℕ denotes the positive integers.

For the convenience of the reader, Tables 1–2 give some data taken from Orrick and Solomon [35], where references to the original sources may be found. Table 1 gives the spectrum of possible (absolute values of) determinants of {±1}-matrices of order n ≤ 11, normalized by the usual factor 2^{n−1}. In this and other tables, the notation “a..b” is shorthand for “{x ∈ ℕ : a ≤ x ≤ b}”. Table 2 gives Δ(n) := D(n)/2^{n−1} for n ≤ 21.

n  Spectrum {| det(A)|/2^{n−1}}
1 {1}
2 {0, 1}
3 {0, 1}
4 {0..2}
5 {0..3}
6 {0..5}
7 {0..9}
8 {0..18, 20, 24, 32}
9 {0..40, 42, 44, 45, 48, 56}
{0..102, 104, 105, 108, 110, 112,
10 116, 117, 120, 125, 128, 144}
{0..268, 270..276, 278..280, 282..286,
11 288, 291, 294..297, 304, 312, 315, 320}

Table 1: Spectrum of {±1}-matrices of order n ≤ 11, from Orrick and Solomon [35]; for n = 13 see [7].

We are interested in when the full spectrum of possible minor values occurs in the minors of maxdet matrices of given order n.

\begin{matrix}n & Δ(n) & n & Δ(n) & n & Δ(n) & n & Δ(n) \\ – & – & 1 & 1 & 2 & 1 & 3 & 1 \\ 4 & 2 & 5 & 3 & 6 & 5 & 7 & 9 \\ 8 & 4 × 2^{3} & 9 & 7 × 2^{3} & 10 & 18 × 2^{3} & 11 & 40 × 2^{3} \\ 12 & 6 × 3^{5} & 13 & 15 × 3^{5} & 14 & 39 × 3^{5} & 15 & 105 × 3^{5} \\ 16 & 8 × 4^{7} & 17 & 20 × 4^{7} & 18 & 68 × 4^{7} & 19 & 833 × 4^{6} \\ 20 & 10 × 5^{9} & 21 & 29 × 5^{9} & – & – & – & – \end{matrix}

Table 2: Maximal determinants Δ(n) = D(n)/2^{n−1}, n ≤ 21, from Orrick and Solomon [35].

Definition 9. The full-spectrum threshold of an n × n {±1} matrix A is the maximum m_{f} ≤ n such that the full spectrum of possible values occurs for the minors of order m_{f} of A.

Definition 10. The full-spectrum threshold m_{f} : ℕ → ℕ is the maximum of the fullspectrum threshold of A over all maxdet matrices A of order n.

We write m_{f}(A) or m_{f}(n) to denote the full-spectrum thresholds of Definitions 9 or 10 respectively; which is meant should be clear from the context. The values of m_{f}(n) for 1 ≤ n ≤ 21 are given in Table 3. We note that the full-spectrum threshold m_{f}(A) does depend on the HT-equivalence class of A. For example, the four HT-equivalence classes for order 16 give four different values m_{f} ∈ {5, 6, 7, 8}, see Tables 23–26.

For the reasons mentioned in §1, we are also interested in the largest order of a maxdet matrix contained as a proper submatrix of a given maxdet matrix. We make some definitions analogous to Definitions 9–10.

Definition 11. The complementary depth of an n × n {±1} matrix A is the maximum m_{d} < n such that a maxdet matrix of order m_{d} occurs as a proper submatrix of A, or 0 if n = 1. The depth of A is d(A) := n − m_{d}(A).

Definition 12. The complementary depth m_{d} : ℕ → ℤ is the maximum of the complementary depth of A over all maxdet matrices A of order n. The depth d : ℕ → ℤ is defined by d(n) := n − m_{d}(n).

We write d(A) or d(n) for the depths of Definitions 11 or 12 respectively; similarly for m_{d}(A) and m_{d}(n). Clearly d(A) depends on the HT-equivalence class of A – for example, see Tables 30–32 for the three HT-equivalence classes of order 18 with depths 7, 7 and 10. From Definition 12, d(n) is the minimum of d(A) over all maxdet matrices A of order n, so d(18) = 7. Computed values of d(n), m_{d}(n) and m_{f}(n) for 1 ≤ n ≤ 21 are given in Table 3. It is clear from the definitions that m_{f}(n) ≤ m_{d}(n) for n > 1.

If n ≡ 0 (mod 8) then d(n) = n/2 in the range of our computations. If n ≡ 4 (mod 8) then both d(n) = n/2 (for n = 20) and d(n) = n/2 − 1 (for n = 4, 12) are possible. We see from Table 3 that the computed values all satisfy d(n) ≤ (n + 1)/2. It is interesting that the value d = 1 occurs for n ≤ 7, n = 9 and n = 17 (contrary to the remark of Schmidt quoted in §1).

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ d & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 4 & 1 & 2 & 3 & 5 \\ m_{d} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 4 & 8 & 8 & 8 & 7 \\ m_{f} & 1 & 1 & 2 & 2 & 3 & 4 & 6 & 4 & 6 & 6 & 7 & 6 \end{matrix}

\begin{matrix}n & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 \\ d & 6 & 7 & 8 & 8 & 1 & 7 & 10 & 10 & 10 \\ m_{d} & 7 & 7 & 7 & 8 & 16 & 11 & 9 & 10 & 11 \\ m_{f} & 7 & 7 & 7 & 8 & 8 & 8 & 9 & 8 & 10 \end{matrix}

Table 3: Depths d(n) of largest maxdet proper submatrices, complementary depth m_{d}(n) = n − d(n), and full-spectrum threshold m_{f}(n); see Definitions 10–12.

4 Further results and observations on minors

In Tables 6–43, which may be found in the Appendix at the end of the paper, we give computational results on the minors of maxdet matrices of order n ≤ 21. Here we make some empirical observations on the results and mention a fact (Proposition 16) that was suggested by them.

Let k = ⌊n/4⌋. Factors of the form k^{2k}, k^{2k−1}, …, k^{2}, k are present as we descend through the minors of maxdet matrices of even order n. For Hadamard matrices this is an easy consequence of the Hadamard bound n^{n/2} and Szöllősi’s theorem, but for n ≡ 2 (mod 4) we do not have a simple explanation. Factors of the form k^{2k−1}, k^{2k−2}, …, k are present in the minors of maxdet matrices with order n ≡ 1 (mod 4), and factors of the form k^{2k−2}, k^{2k−3}, …, k are present if n ≡ 3 (mod 4). It is an open question whether this behaviour persists for n > 21. The observed divisibility properties are related to the structure of the Gram matrices A^{T} A of maxdet matrices A, but in general this structure is unknown. For a summary of what is currently known, see [35].

The presence of high powers of k = ⌊n/4⌋ in the minors of order m, and high powers of a possibly different integer k′ = ⌊m/4⌋ in the maximal determinants of order m, gives one explanation of why certain minors can not meet the maximal determinant for that order.^{5} For example, Table 19 shows that a Hadamard matrix of order n = 12 has minors of order 11 with scaled value 3^{5}, but Δ(11) = 5 × 2^{6}, which contains a high power of 2, not of 3.

Proposition 13 is from [9, Theorem 1]. The upper bound is sharp because it is attained for Hadamard matrices. For the case that A is a Hadamard matrix, the result is due to de Launey and Levin [31, Proposition 2].

Proposition 13. Let A be a square {±1} matrix of order n ≥ m > 1. Then the mean value E(det(M)^{2}) of det(M)^{2}, taken over all m × m submatrices M of A, satisfies

5Of course, this begs the question of why the maximal determinants are divisible by a high power of k′ – we do not have a convincing explanation for this unless the order m is such that the Hadamard, Barba [3], or Ehlich-Wojtas [16, 47] bound is achieved, in which case it follows from the form of the relevant bound, see Osborn [36, pp. 98–99].

E(det(M)^{2}) ≤ n^{m}/\binom{n}{m} .  (8)

Moreover, equality holds in (8) iff A is a Hadamard matrix.

Remark 14. For random {±1} matrices M of order m, the expected value of det(M)^{2} is m!, by a result of Turán [44]. The last sentence of Proposition 13 implies that E(det(M)^{2}) ≥ m! for the order-m submatrices M of a Hadamard matrix, with strict inequality if m > 1.

As a check on the correctness of our programs, we computed the mean value of det(M)^{2} for submatrices of order m of maxdet matrices of order n ≤ 21, and 2 ≤ m ≤ n. The results agreed with the predictions of Proposition 13. The following conjecture is consistent with our computations.

Conjecture 15. Let A be a maxdet matrix. Then the mean value E(det(M)^{2}) of det(M)^{2} taken over all m × m submatrices M of A satisfies the inequality

E(det(M)^{2}) ≥ m!  (9)

Moreover, the inequality (9) is strict for m > 1.

Table 4 gives some data for orders 13 ≤ n ≤ 15 to support Conjecture 15. In the table, R_{L}(m, n) is the ratio of E(det(M)^{2}), for submatrices M of order m of a maxdet matrix of order n, to the conjectured lower bound m!. Similarly, R_{H}(m, n) is the ratio of E(det(M)^{2}) to the upper bound (8). We see that R_{L}(m, n) > 1 for 2 ≤ m ≤ n (as conjectured), and the lower bound is reasonably good for m ≤ 5, but deteriorates for larger m. The upper bound is within a factor of three of E((det M)^{2}) for all m. A similar pattern occurs for all orders n ≤ 21, except that R_{H}(m, n) = 1 if n is a Hadamard order, in accordance with Proposition 13.

The frequencies of occurrence of small singular submatrices of Hadamard matrices are given in the following Proposition [9, Corollary 4], which was suggested by the computational results before we found a proof. The case m = 2 is implicit in a paper of Little and Thuente [32, p. 254].

Proposition 16. Let H be a Hadamard matrix of order n, and let Z(m, H) be the number of minors of order m of H that vanish. Then

Z(2, H) = n^{2}(n − 1)(n − 2)/8, and  (10)

Z(3, H) = n^{2}(n − 1)(n − 2)(n − 4)(5n − 4)/288.  (11)

Remark 17. There is no analogue of Proposition 16 for minors of order m > 3, because the value of Z(m, H) can depend on the HT-equivalence class of H, so is not given by a polynomial in m (unless m ≤ 3). For example, the four HT-equivalence classes of Hadamard matrices of order 16 have 1717520, 1712912, 1710608, and 1709456 vanishing minors of

m R_{L}(m, 13) R_{H}(m, 13) R_{L}(m, 14) R_{H}(m, 14) R_{L}(m, 15) R_{H}(m, 15)
2  1.077  0.994  1.067  0.991  1.059  0.988
3  1.259  0.983  1.222  0.973  1.195  0.966
4  1.611  0.968  1.516  0.948  1.445  0.935
5  2.283  0.949  2.054  0.917  1.890  0.897
6  3.625  0.928  3.072  0.882  2.694  0.852
7  6.560  0.904  5.139  0.843  4.233  0.804
8  13.81  0.879  9.773  0.802  7.427  0.752
9  34.80  0.851  21.58  0.759  14.79  0.699
10 109.4  0.823  56.93  0.715  34.14  0.645
11 457.4  0.795  187.0  0.671  94.00  0.592
12 2864  0.765  815.6  0.627  321.7  0.540
13 35796  0.736  5318  0.584  1461  0.491
14  69137  0.542  9902  0.444
15  133638  0.399

Table 4: Ratio of E(det(M)^{2}) to lower and upper bounds, 13 ≤ n ≤ 15. For definitions of R_{L}(m, n) and R_{H}(m, n), see text.

order 4. For maxdet matrices of order n ≡ 3 (mod 4), we sometimes find different numbers of vanishing minors of order 2. For example, if n = 11, we get 1391, 1389, and 1401 vanishing minors for the three HT-equivalence classes. The right-hand-side of eqn. (10), which by [9, Corollary 3.1] is a lower bound on the number of vanishing minors in this non-Hadamard case, gives 1362 (rounded up).

Finally, we briefly consider the frequencies (or multiplicities) with which the different values of | det(M)/2^{n−1}| occur for minors of order m of a maxdet matrix of order n. In Table 5 we give the results of computations for m = 7, n = 15, which gives the typical behaviour that we have observed.^{6} The second column gives the observed multiplicity of a minor with | det(M)|/2^{n−1} equal to the integer in the first column. The third column gives the multiplicities observed when taking a random sample of \binom{15}{7}^{2} = 41409225 uniformly distributed {±1}-matrices of order m (we call this the random model). It is clear from the table that the actual distribution is nothing like the distribution for the random model. A χ^{2} test gives an absurdly small probability < 10^{−10^{10}} that the two samples were drawn from the same distribution. Similar behaviour occurs for other values of m ≥ 2. For example, when m = 2 we find 5187 zero minors and 5838 nonzero minors, but for random matrices of order 2 we expect zero and nonzero values to occur with equal probability.

Table 5 shows that the normalized minors are biased towards even values. For the random model, this bias can be explained by reducing to the {0, 1} case and considering the evaluation of the determinant in ℤ/2ℤ. Then, for large n, we expect even values to occur about 71% of the time.^{7} This prediction is in agreement with the data for the random model (the third column). For the second column we find that even values occur about 69% of the time, which is close to the prediction for the random model. Thus, although the actual

6Data on multiplicities for other values of m and n may be found at [4].

7The precise constant in the limit as n → ∞ is 1 − ∏_{k≥1}(1 − 2^{−k}), see [6, 17, 30].

multiplicity multiplicity in
| det(M)|/2^{n−1}| of minors random model ratio
0  12857784  24030613  0.54
1  8402100  11140444  0.75
2  10831128  4662108  2.32
3  3483909  924336  3.77
4  3935280  504938  7.79
5  622842  76496  8.14
6  927162  55811  16.61
7  129576  7769  16.68
8  201900  6102  33.09
9  17544  608  28.86
total  41409225  41409225

Table 5: Comparison of observed multiplicities of minors of order 7 in a maxdet matrix of order 15 with a random model

distribution differs considerably from that of the random model, the bias towards even values persists. In comparison with the random model, the extreme bias in favour of even values in the tail of the distribution compensates for a bias against zero minors.

5 Algorithms for computing the set of minors

Recall that S_{k}(A) is the set of k×k submatrices of an n×n {±1}-matrix A, where 0 < k ≤ n. In this section we describe algorithms for enumerating all the minors of A. Our application is to maxdet matrices, but the algorithms apply to all square {±1}-matrices A, and with trivial changes they would also apply to rectangular {±1}-matrices.

In our enumeration we consider only the absolute values of minors, normalized by the factor 2^{n−1} which always divides the determinant of an n × n {±1}-matrix, so the set of minors of A is defined to be the set

S(A) = ∪_{k=1}^{n}{| det(M)|/2^{n−1} : M ∈ S_{k}(A)}.

There are \binom{n}{k} possible choices of rows and \binom{n}{k} possible choices of columns for a minor of order k, so altogether a total of

T_{n} := ∑_{k=1}^{n} \binom{n}{k}^{2} = \binom{2n}{n} − 1 ∼ \frac{4^{n}}{\sqrt{πn}}

possibilities to consider when finding the set S(A) for an n × n matrix A. In this section we consider four possible algorithms (of which we used two) for finding S(A). Their running times all involve the factor 4^{n}, so none of them is practical for n much larger than 20, but they differ significantly in the factor multiplying 4^{n} and in their space requirements.

Each algorithm has two variants: the first just determines the set S(A) of minors; the second also counts the multiplicity of each minor, that is, how often a given value d ∈ S(A) occurs. We describe the first variant of each algorithm, and briefly mention the changes required for the second variant.

In the descriptions of the algorithms we explain how to compute the complete set S(A); it should be clear how to compute the subset of S(A) corresponding to the minors of a given order k.

5.0.1 Algorithm A

Algorithm A simply considers, for each k in {1, 2, …, n}, the set of all k × k submatrices of A, and evaluates the determinant of each such submatrix M by Gaussian elimination with partial pivoting, using floating-point arithmetic. The computed determinant is scaled by division by 2^{n−1} and rounded to the nearest integer.

Clearly there is a danger that rounding errors during the process of Gaussian elimination could lead to an incorrectly rounded integer result. However, our experiments, using IEEE standard 64-bit floating-point arithmetic [1], showed that this is not a problem for the values of n that we considered (n ≤ 25). Gaussian elimination with partial pivoting is numerically stable [19, 46], and the maximum scaled determinant of a 25 × 25 {±1}-matrix is 42 × 6^{11} = 15237476352, meeting the Barba bound [3, 35], so only requires 34 bits of precision, significantly fewer than the 53 bits provided by IEEE standard arithmetic. As a precaution, our implementation prints a warning and halts if the fractional part of a scaled determinant exceeds 1/8; this never occurred for n ≤ 25.

Gaussian elimination requires O(k^{3}) arithmetic operations to evaluate the determinant of a k×k matrix. As is traditional in numerical analysis, we count multiplications/divisions but ignore additions/subtractions. With this convention, Gaussian elimination requires k^{3}/3 + O(k^{2}) operations. Thus the total cost is

W_{A} ∼ ∑_{k=1}^{n} \binom{n}{k}^{2} \frac{k^{3}}{3} ∼ \frac{4^{n}n^{5/2}}{24\sqrt{π}} .

The storage requirements of Algorithm A are minimal, apart from the space required to store the results, that is the set S(A) of minors and (if required) their multiplicities. This is common to all the algorithms considered – they all need space to store their results.

The set S(A) can be represented using one bit for each possible value | det |/2^{n−1}. From the Hadamard bound, this requires at most 2^{1−n}n^{n/2} + 1 bits. For example, if n = 20, it requires 19531251 bits (2.33 MB). For n = 24 it requires 519 MB, which is still feasible. For the variant that counts multiplicities, each bit needs to be replaced by an integer word (say 32 bits or 4 bytes), so the storage required would be acceptable for n = 20 (75 MB) but excessive for n = 24 (16 GB), since the computers available to us typically have memories of 1 to 4 GB.

Fortunately, a much more economical representation of S(A) is usually possible, because not all minors in the range [0, ⌊2^{1−n}n^{n/2}⌋] actually occur. The set S(A) is usually quite sparse, especially when the order n of A is divisible by 4. For example, with Hadamard matrices of order 16, we have #S(A) < 100 (see §4). Thus, instead of using 131073 bits to represent S(A), we can use a hash table with say 200 words [25]. With such an implementation, the storage requirements are moderate for n ≤ 25.

5.0.2 Algorithm B

Algorithm B is similar to Algorithm A, but uses a rank-1 updating formula to update the inverse and determinant of each k × k submatrix B of A if we already know the inverse and determinant of a submatrix that differs from B in only one row or column. The inverse updating formula

(B + uv^{T})^{−1} = B^{−1} − (1 + v^{T} B^{−1}u)^{−1}B^{−1}uv^{T} B^{−1}

is known at the Sherman-Morrison formula [41] – the determinant updating formula

det(B + uv^{T}) = det(B)(1 + v^{T} B^{−1}u)

seems to be known only as a “matrix determinant lemma”.

Since the updating steps require ∼ k^{2} operations, the complexity is

W_{B} ∼ 4^{n}n^{3/2}/\sqrt{π} ,

so W_{A}/W_{B} ∼ n/24.

We did not use Algorithm B because the constant factors involved make it slower than Algorithm A for n ≤ 20, and because it is difficult to guarantee a correctly rounded integer result due to possible numerical instability. Also, even with exact arithmetic, we would have to use a different method whenever B is singular.

5.0.3 Algorithm C

Algorithm C uses integer arithmetic and evaluates each k × k determinant using the method (attributed to Laplace) of expansion by minors, see for example [33, Chapter 4]. To compute a k × k minor det(B), we need to know the (k − 1) × (k − 1) minors formed by deleting the first row and an arbitrary column of B. If these minors have been saved from a previous computation, then the work involved in computing one minor | det(B)| is only k multiplications (by ±1) and k − 1 integer additions, plus any overheads involved in retrieving the previously stored values. If we assume, for purposes of comparison with Algorithms A–B, that the work involved amounts to k operations, then the total cost is

W_{C} = ∑_{k=1}^{n} \binom{n}{k}^{2}k ∼ \frac{4^{n}n^{1/2}}{2\sqrt{π}} ,

giving W_{A}/W_{C} ∼ n^{2}/12.

Unfortunately, this algorithm has a potentially large memory requirement. If we compute the minors of order k in increasing order k = 1, 2, …, n, then to compute the minors of order k we need all \binom{n}{k−1}^{2} minors of order k − 1. In the worst case, when k ≈ n/2, the memory required to store the minors of order k − 1 and k is about 4^{n+1}/(πn) words, which is too large to be practical for the values of n that we wish to consider. More memory-efficient implementations are possible, but complicated. For this reason we discarded Algorithm C and implemented a slightly slower, but much simpler algorithm, Algorithm D.

5.0.4 Algorithm D

The idea of Algorithm D is the same as that of Algorithm C. However, when computing the minors of order k of an n × n matrix A, the outer loop runs over all \binom{n}{k} combinations of k rows of A. Having selected these k rows, forming a k × n matrix B, we now compute all minors of order k of B. At the j-th step we compute all minors of order j in the last j rows of B. Thus the number of operations (counting as for Algorithm C) to compute the minors of order k of B is

∑_{j=1}^{k} \binom{n}{j}j

and the space requirement is at most 2\binom{n}{⌊n/2⌋} ∼ 2^{n+ \frac{3}{2}} /\sqrt{πn} words, much less than for Algorithm C. The overall operation count is

∑_{k=1}^{n} \binom{n}{k} ∑_{j=1}^{k} \binom{n}{j}j = 4^{n−1}n.

This is larger than the operation count for Algorithm C by a factor ∼ \sqrt{πn}/2, but smaller than the operation count for Algorithm A by a factor ∼ n^{3/2}/(6\sqrt{π}).

If a parallel implementation is desired, then it is easy to parallelize over the outer loop – different processors can work on different combinations of k rows of A in parallel.

We ran both Algorithms A and D on small cases to check the correctness of our implementations. For the large cases we used mainly Algorithm D, which is much faster than Algorithm A for the most time-consuming cases (k ≈ n/2), as expected from the operation counts given above.

6 Acknowledgements

We thank Will Orrick for his advice and assistance in locating several of the references, and Warren Smith for pointing out the connection between Jacobi and Szöllősi. We also thank an anonymous referee for useful suggestions and corrections.

References

[1] ANSI/IEEE, IEEE Standard for Binary Floating-Point Arithmetic, ANSI-IEEE Standard 754-2008, IEEE, New York, 2008. Revision of IEEE 754-1985.

[2] R. C. Baker, G. Harman, and J. Pintz, The difference between consecutive primes, II, Proc. London Math. Soc. (3) 83 (2001), 532–562.

[3] G. Barba, Intorno al teorema di Hadamard sui determinanti a valore massimo, Giorn. Mat. Battaglini 71 (1933), 70–86.

[4] R. P. Brent, The Hadamard maximal determinant problem, http://maths.anu.edu.

    au/~brent/maxdet/ .

[5] R. P. Brent, Finding D-optimal designs by randomised decomposition and switching, Australs. J. Combin. 55 (2013), 15–30.

[6] R. P. Brent and B. D. McKay, Determinants and ranks of random matrices over ℤ_{m}, Discrete Math. 66 (1987), 35–49.

[7] R. P. Brent, W. P. Orrick, J. H. Osborn, and P. Zimmermann, Maximal determinants and saturated D-optimal designs of orders 19 and 37, submitted. Available at http://

arxiv.org/abs/1112.4160v1.

[8] R. P. Brent and J. H. Osborn, General lower bounds on maximal determinants of binary matrices, submitted. Preprint, August 9 2012, available at http://arxiv.org/abs/

1208.1805v1.

[9] R. P. Brent and J. H. Osborn, Bounds on minors of binary matrices, Bull. Aust. Math. Soc., 26 November 2012. Longer version, 14 September 2012, available at http://

arxiv.org/abs/1208.3330v3.

[10] R. P. Brent, J. H. Osborn and W. D. Smith, Lower bounds on maximal determinants of ±1 matrices via the probabilistic method, preprint, 3 December 2012, available at

http://arxiv.org/abs/1211.3248v2.

[11] J. H. E. Cohn, Hadamard matrices and some generalisations, Amer. Math. Monthly 72 (1965), 515–518.

[12] C. J. Colbourn and J. H. Dinitz, eds., The CRC Handbook of Combinatorial Designs, 2nd edition, CRC Press, 2006.

[13] J. Day and B. Peterson, Growth in Gaussian elimination, Amer. Math. Monthly 95 (1988), 489–513.

[14] J. H. Dinitz and D. R. Stinson, eds., Contemporary Design Theory: A Collection of Surveys, Wiley, 1992.

[15] D. Z. Ðoković and I. S. Kotsireas, New results on D-optimal matrices, J. Combin. Des. 20 (2012), 278–289.

[16] H. Ehlich, Determinantenabschätzungen für binäre Matrizen, Math. Z. 83 (1964), 123– 132.

[17] J. Goldman and G.-C. Rota, On the foundations of combinatorial theory IV: finite vector spaces and Eulerian generating functions, Studies in Appl. Math. 49 (1970), 239–258.

[18] J. Hadamard, Résolution d’une question relative aux déterminants, Bull. des Sci. Math. 17 (1893), 240–246.

[19] N. Higham, Accuracy and Stability of Numerical Algorithms, 2nd edition, SIAM, 2002.

[20] K. J. Horadam, Hadamard Matrices and their Applications, Princeton University Press, 2007.

[21] C. G. J. Jacobi, De formatione et proprietatibus determinantium, J. Reine Angew. Math.22 (1841), 285–318. Also in Ges. Werke, Vol. 3, Reimer, Berlin, 1884, pp. 356– 392.

[22] J. Kahn, J. Komlós, and E. Szemerédi, On the probability that a random ±1-matrix is singular, J. Amer. Math. Soc. 8 (1995), 223–240.

[23] H. Kharaghani and W. Orrick, D-optimal designs, in [12, Chapter V.3, 295–297].

[24] H. Kharaghani and B. Tayfeh-Rezaie, A Hadamard matrix of order 428, J. Combin. Des. 13 (2005), 435–440.

[25] D. E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, Addison-Wesley, 1998.

[26] C. Koukouvinos, E. Lappas, M. Mitrouli, and J. Seberry, An algorithm to find formulæ and values of minors for Hadamard matrices: II, Linear Alg. Appl. 371 (2003), 111–124.

[27] C. Koukouvinos, M. Mitrouli, and J. Seberry, Bounds on the maximum determinant for (1, −1) matrices, Bull. Inst. Combin. Appl. 29 (2000), 39–48.

[28] C. Koukouvinos, M. Mitrouli, and J. Seberry, An algorithm to find formulæ and values of minors for Hadamard matrices, Linear Alg. Appl. 330 (2001), 129–147.

[29] C. Kravvaritis and M. Mitrouli, A technique for computing minors of binary Hadamard matrices and application to the growth problem, Elect. Trans. Numer. Anal., 31 (2008), 49–67.

[30] G. Landsberg, Über eine Anzahlbestimmung und eine damit zusammenhängende Reihe, J. Reine Angew. Math. 111 (1893), 87–88.

[31] W. de Launey and D. A. Levin, (1, −1)-matrices with near-extremal properties, SIAM J. Discrete Math. 23 (2009), 1422–1440.

[32] C. H. C. Little and D. J. Thuente, The Hadamard conjecture and circuits of length four in a complete bipartite graph, J. Austral. Math. Soc. (Series A) 31 (1981), 252–256.

[33] T. Muir, A Treatise on the Theory of Determinants, Dover, 1960.

[34] OEIS Foundation Inc., The On-Line Encyclopedia of Integer Sequences, 2012.

[35] W. P. Orrick and B. Solomon, The Hadamard maximal determinant problem, available

    at http://www.indiana.edu/~maxdet/ .

[36] J. H. Osborn, The Hadamard Maximal Determinant Problem, Honours Thesis,

    University of Melbourne, 2002, 142 pp. http://wwwmaths.anu.edu.au/~osborn/
    publications/pubsall.html .

[37] K. W. Schmidt, Lower bounds for maximal (0, 1)-determinants, SIAM J. Appl. Math. 19 (1970), 440–442.

[38] J. Seberry, T. Xia, C. Koukouvinos and M. Mitrouli, The maximal determinant and subdeterminants of ±1 matrices, Linear Algebra Appl. 373 (2003), 297–310.

[39] J. Seberry and M. Yamada, Hadamard matrices, sequences, and block designs, in [14, Ch. 11].

[40] F. R. Sharpe, The maximum value of a determinant, Bull. Amer. Math. Soc. 14 (1907), 121–123.

[41] J. Sherman and W. J. Morrison, Adjustment of an inverse matrix corresponding to a change in one element of a given matrix, Ann. Math. Statistics 21 (1950), 124–127.

[42] B. Solomon, Personal communication to W. Orrick, 18 June 2002.

[43] F. Szöllősi, Exotic complex Hadamard matrices and their equivalence, Cryptogr. Com-

    mun. 2 (2010), 187–198. Available at http://arxiv.org/abs/1001.3062v2.

[44] P. Turán, On extremal problems concerning determinants, Math. Naturwiss. Anz. Ungar. Akad. Wiss. 59 (1940), 95–105.

[45] I. M. Wanless, Permanents of matrices of signed ones, Linear Multilin. Algebra 53 (2005), 427–433.

[46] J. H. Wilkinson, The Algebraic Eigenvalue Problem, Clarendon Press, Oxford, 1965 (reprinted 1988).

[47] W. Wojtas, On Hadamard’s inequality for the determinants of order non-divisible by 4, Colloq. Math. 12 (1964), 73–83.

6.1 Appendix: Tables of minors for orders ≤ 21

In Tables 6–43, k = ⌊n/4⌋, where n is the order of the {±1}-matrix. The first column gives the order m of the minor, 1 ≤ m ≤ n. The second column gives the set of absolute values of the minors of order m, divided by the known factor 2^{m−1}. In this column the notation “{a, b, …} × k^{α}” is a shorthand for “{ak^{α}, bk^{α}, …}”, etc. For n ∈ {19, 21} we have abbreviated the entry in the second column by giving only the minimum and maximum rather than the complete set, using “(min, max)” instead of “{a, b, …}”. In such cases we write “(a, b) × k^{α}” instead of “(ak^{α}, bk^{α})”.

In the third column we give the scaled maximum determinant Δ(m) = D(m)/2^{m−1} (redundant, but included for easy comparison with the entries in the second column). The fourth column answers whether some minor meets the maximum possible determinant for its order (see Table 2), and the last column answers whether the full spectrum of possible values of minors (as given in Table 1) occurs.

If there is more than one HT-equivalence class for an order n, the classes are listed in the same order as they are given in [35]. The information given in Tables 6–43 is sufficient to uniquely identify each HT-equivalence class.

To avoid making this Appendix excessively long, we have omitted details such as the frequency of occurrence of each minor value. Further information is available on our website [4].

Orders 1–6

m {minors} Δ(m) max? full?
1  {1}  1  yes yes

Table 6: n = 1, k = 0, m_{f} = 1

m {minors} Δ(m) max? full?
2  {1}  1  yes no
1  {1}  1  yes yes

Table 7: n = 2, k = 0, d = 1, m_{f} = 1

m  {minors} Δ(m) max? full?
3 {1} 1 yes no
1–2 full spectrum 1  yes yes

Table 8: n = 3, k = 0, d = 1, m_{f} = 2

m  {minors} Δ(m) max? full?
4  {2}  2  yes no
3  {1}  1  yes no
1–2 full spectrum 1  yes yes

Table 9: n = 4, k = 1, d = 1, m_{f} = 2

m  {minors} Δ(m) max? full?
5  {3}  3  yes no
4  {1, 2}  2  yes no
1–3 full spectrum 1  yes yes

Table 10: n = 5, k = 1, d = 1, m_{f} = 3

m  {minors} Δ(m) max? full?
6  {5}  5  yes no
5  {1..3}  3  yes no
1–4 full spectrum ≤ 2 yes yes

Table 11: n = 6, k = 1, d = 1, m_{f} = 4

Orders 7–11(a)

m  {minors} Δ(m) max? full?
7 {9} 9 yes no
1–6 full spectrum ≤ 5 yes yes

Table 12: n = 7, k = 1, d = 1, m_{f} = 6

m  {minors} Δ(m) max? full?
8  {2} × 2^{4}  2 × 2^{4} yes no
7  {1} × 2^{3}  9  no  no
6  {0, 1} × 2^{2}  5  no  no
5  {0, 1} × 2^{1}  3  no  no
1–4 full spectrum ≤ 2  yes yes

Table 13: n = 8, k = 2, d = 4, m_{f} = 4

m  {minors}  Δ(m) max? full?
9  {7} × 2^{3}  7 × 2^{3} yes no
8 {2, 3, 4, 6, 8} × 2^{2} 8 × 2^{2} yes no
7  {0..4} × 2^{1}  9  no  no
1–6 full spectrum  ≤ 5  yes yes

Table 14: n = 9, k = 2, d = 1, m_{f} = 6

m  {minors} Δ(m) max? full?
10  {9} × 2^{4}  9 × 2^{4} yes no
9  {3, 6} × 2^{3} 7 × 2^{3} no  no
8 {0..5, 8} × 2^{2} 8 × 2^{2} yes no
7 {0..4} × 2^{1} 9 no no
1–6 full spectrum ≤ 5  yes yes

Table 15: n = 10, k = 2, d = 2, m_{f} = 6

m  {minors}  Δ(m) max? full?
11  {20} × 2^{4}  20 × 2^{4} yes no
10 {0, 2..8, 10, 12, 16} × 2^{3} 18 × 2^{3} no  no

{0, 2..4, 6, 8..10, 12..24,

9  26..33, 36, 40, 48}  56  no  no
8  {0..18, 20, 24}  32  no  no
1–7  full spectrum  ≤ 9  yes yes

Table 16: n = 11(a), k = 2, d = 4, m_{f} = 7

Orders 11(b)–12

m  {minors}  Δ(m) max? full?
11  {20} × 2^{4}  20 × 2^{4} yes no
10 {0, 1, 4..6, 8..11, 14, 16} × 2^{3} 18 × 2^{3} no  no

{0, 2..4, 6, 8..24, 26..28,

9  30..32, 36, 40, 44, 48}  56  no  no
8  {0..18, 20, 24}  32  no  no
1–7  full spectrum  ≤ 9  yes yes

Table 17: n = 11(b), k = 2, d = 4, m_{f} = 7

m  {minors}  Δ(m) max? full?
11  {20} × 2^{4}  20 × 2^{4} yes no
10 {4, 6, 8, 12, 16} × 2^{3} 18 × 2^{3} no  no
9 {0..4, 6, 8, 12} × 2^{2} 14 × 2^{2} no  no
8 {0..8, 12, 16} × 2^{1} 16 × 2^{1} yes no
7  {0..8}  9  no  no
1–6  full spectrum  ≤ 5  yes yes

Table 18: n = 11(c), k = 2, d = 3, m_{f} = 6

m  {minors}  Δ(m) max? full?
12  {2} × 3^{6}  2 × 3^{6} yes no
11  {1} × 3^{5}  5 × 2^{6} no  no
10 {0, 1} × 3^{4} 3^{2} × 2^{4} no  no
9  {0, 1} × 3^{3} 7 × 2^{3} no  no
8  {0..2} × 3^{2}  2^{5}  no  no
7  {0..3} × 3^{1}  3^{2}  yes no
1–6 full spectrum ≤ 5  yes yes

Table 19: n = 12, k = 3, d = 5, m_{f} = 6

Orders 13–15

m  {minors}  Δ(m) max? full?
13  {5} × 3^{6}  5 × 3^{6} yes no
12 {2, 3} × 3^{5} 6 × 3^{5} no  no
11 {0..3} × 3^{4} 5 × 2^{6} no  no
10 {0..4} × 3^{3} 3^{2} × 2^{4} no  no
9  {0..5} × 3^{2} 7 × 2^{3} no  no
8  {0..6} × 3^{1}  2^{5}  no  no
1–7 full spectrum ≤ 9  yes yes

Table 20: n = 13, k = 3, d = 6, m_{f} = 7

m  {minors}  Δ(m) max? full?
14  {13} × 3^{6}  13 × 3^{6} yes no
13 {4, 6, 7, 9} × 3^{5} 15 × 3^{5} no  no
12 {0..7, 9, 10} × 3^{4} 18 × 3^{4} no  no
11 {0..9, 11} × 3^{3} 5 × 2^{6} no  no
10  {0..13} × 3^{2}  3^{2} × 2^{4} no  no
9  {0..15} × 3^{1}  7 × 2^{3} no  no
8  {0..18, 20}  2^{5}  no  no
1–7 full spectrum  ≤ 9  yes yes

Table 21: n = 14, k = 3, d = 7, m_{f} = 7

m  {minors}  Δ(m) max? full?
15  {35} × 3^{6}  35 × 3^{6} yes no
14 {7, 8, 12, 14, 17, 18, 21, 23, 27} × 3^{5} 39 × 3^{5} no  no
13  {0..21, 23, 24, 26, 27} × 3^{4}  45 × 3^{4} no  no
12  {0..22, 24..27} × 3^{3}  54 × 3^{3} no  no
11  {0..29, 31, 35} × 3^{2}  5 × 2^{6} no  no
10  {0..36, 39, 40} × 3^{1}  3^{2} × 2^{4} no  no
9  {0..36, 38..40, 42, 44, 45}  56  no  no
8  {0..18, 20, 24}  32  no  no
1–7  full spectrum  ≤ 9  yes yes

Table 22: n = 15, k = 3, d = 8, m_{f} = 7

Order 16

m  {minors}  Δ(m) max? full?
16  {2} × 4^{8}  2 × 4^{8} yes no
15  {1} × 4^{7}  35 × 3^{6} no  no
14 {0, 1} × 4^{6} 13 × 3^{6} no  no
13 {0, 1} × 4^{5} 5 × 3^{6} no  no
12 {0..2} × 4^{4} 2 × 3^{6} no  no
11 {0..3} × 4^{3} 5 × 2^{6} no  no
10 {0..2} × 2^{5} 9 × 2^{4} no  no
9  {0..2} × 2^{4} 7 × 2^{3} no  no
8  {0..4} × 2^{3}  32  yes no
7  {0..2} × 2^{2}  9  no  no
6  {0..2} × 2^{1}  5  no  no
1–5 full spectrum ≤ 3  yes yes

Table 23: n = 16(a), k = 4, d = 8, m_{f} = 5

m  {minors} Δ(m) max? full?
11–16 as for 16(a)  –  –  no
10  {0..5} × 4^{2} 9 × 4^{2} no  no
9  {0..4} × 2^{3} 7 × 2^{3} no  no
8  {0..6, 8} × 2^{2} 32  yes no
7  {0..4} × 2^{1}  9  no  no
1–6 full spectrum ≤ 5  yes yes

Table 24: n = 16(b), k = 4, d = 8, m_{f} = 6

m  {minors}  Δ(m) max? full?
10–16  as for 16(b)  –  –  no
9  {0..9} × 4^{1}  14 × 4^{1} no  no
8 {0..10, 12, 16} × 2^{1} 16 × 2^{1} yes no
1–7  full spectrum  ≤ 9  yes yes

Table 25: n = 16(c), k = 4, d = 8, m_{f} = 7

m  {minors} Δ(m) max? full?
9–16 as for 16(c) – – no
1–8 full spectrum ≤ 32 yes yes

Table 26: n = 16(d), k = 4, d = 8, m_{f} = 8

m  {minors}  Δ(m) max? full?
17  {5} × 4^{8}  5 × 4^{8} yes no
16  {2, 3, 8} × 4^{7}  8 × 4^{7} yes no
15  {0..4} × 4^{6}  35 × 3^{6} no  no
14  {0..4} × 4^{5}  13 × 3^{6} no  no
13  {0..7} × 4^{4}  5 × 3^{6} no  no
12  {0..9} × 4^{3}  2 × 3^{6} no  no
11  {0..13, 15} × 4^{2}  20 × 4^{2} no  no
10 {0..21, 24, 27} × 4^{1} 36 × 4^{1} no  no
9 {0..40, 42, 44, 45, 48}  56  no  no
1–8  full spectrum  ≤ 32  yes yes

Table 27: n = 17(a), k = 4, d = 1, m_{f} = 8

m  {minors}  Δ(m) max? full?
10–17 as for 17(a)  –  –  no
9 {0..22, 24} × 2^{1} 28 × 2^{1} no  no
1–8 full spectrum ≤ 32  yes yes

Table 28: n = 17(b), k = 4, d = 1, m_{f} = 8

m  {minors}  Δ(m) max? full?
11–17  as for 17(a)  –  –  no
10  {0..10, 12} × 2^{3} 18 × 2^{3} no  no
9  {0..12} × 2^{2}  14 × 2^{2} no  no
8 {0..10, 12, 16} × 2^{1} 16 × 2^{1} yes no
1–7  full spectrum  ≤ 9  yes yes

Table 29: n = 17(c), k = 4, d = 1, m_{f} = 7

m  {minors}  Δ(m) max? full?
18  {17} × 4^{8}  17 × 4^{8} yes no
17  {6, 7, 10, 11} × 4^{7}  20 × 4^{7} no  no
16  {0..8, 10, 11, 13} × 4^{6} 32 × 4^{6} no  no
15  {0..16} × 4^{5}  35 × 3^{6} no  no
14  {0..20} × 4^{4}  13 × 3^{6} no  no
13  {0..24, 26, 28} × 4^{3}  5 × 3^{6} no  no
12 {0..38, 40, 41, 44, 52} × 4^{2} 2 × 3^{6} no  no
11 {0..62, 64, 68, 80} × 4^{1} 80 × 4^{1} yes no

{0..94, 96..98, 100..102,

10  104, 108, 112, 128}  144  no  no
9  {0..40, 42, 44, 45, 48}  56  no  no
1–8  full spectrum  ≤ 32  yes yes

Table 30: n = 18(a), k = 4, d = 7, m_{f} = 8

m  {minors}  Δ(m) max? full?
14–18  as for 18(a)  –  –  no
13  {0..24, 26, 28, 32} × 4^{3} 5 × 3^{6} no  no
12 {0..38, 40, 41, 44, 64} × 4^{2} 2 × 3^{6} no  no
11  {0..62, 64, 68, 80} × 4^{1} 80 × 4^{1} yes no
10  {0..52, 54, 56, 64} × 2^{1} 72 × 2^{1} no  no
9  {0..40, 42, 44, 45, 48}  56  no  no
1–8  full spectrum  ≤ 32  yes yes

Table 31: n = 18(b), k = 4, d = 7, m_{f} = 8

m  {minors}  Δ(m) max? full?
14–18  as for 18(a)  –  –  no
13  {0..24, 32} × 4^{3} 5 × 3^{6} no  no
12 {0..37, 40, 64} × 4^{2} 2 × 3^{6} no  no
11  {0..32} × 2^{3}  40 × 2^{3} no  no
10  {0..28, 32} × 2^{2} 36 × 2^{2} no  no
9  {0..22, 24} × 2^{1} 28 × 2^{1} no  no
1–8  full spectrum  ≤ 32  yes yes

Table 32: n = 18(c), k = 4, d = 10, m_{f} = 8

m (min, max) |minor| Δ(m) max? full?
19  (833, 833) × 4^{6}  833 × 4^{6} yes no
18  (140, 784) × 4^{5}  1088 × 4^{5} no  no
17  (0, 672) × 4^{4}  1280 × 4^{4} no  no
16  (0, 676) × 4^{3}  2048 × 4^{3} no  no
15  (0, 1050) × 4^{2}  35 × 3^{6}  no  no
14  (0, 1470) × 4^{1}  13 × 3^{6}  no  no
13  (0, 1904)  3645  no  no
12  (0, 756)  1458  no  no
11  (0, 312)  320  no  no
10  (0, 128)  144  no  no
1–9  full spectrum  ≤ 56  yes yes

Table 33: n = 19(a), k = 4, d = 10, m_{f} = 9

m (min, max) |minor| Δ(m) max? full?
19  (833, 833) × 4^{6}  833 × 4^{6} yes no
18  (168, 616) × 4^{5}  1088 × 4^{5} no  no
17  (0, 672) × 4^{4}  1280 × 4^{4} no  no
16  (0, 740) × 4^{3}  2048 × 4^{3} no  no
15  (0, 1024) × 4^{2}  35 × 3^{6}  no  no
14  (0, 1536) × 4^{1}  13 × 3^{6}  no  no
13  (0, 2048)  3645  no  no
12  (0, 1024)  1458  no  no
11  (0, 288)  320  no  no
10  (0, 128)  144  no  no
1–9  full spectrum  ≤ 56  yes yes

Table 34: n = 19(b), k = 4, d = 10, m_{f} = 9

m (min, max) |minor| Δ(m) max? full?
14–19  as for 19(b)  –  –  –
13  (0, 2560)  3645 no  no
1–12  as for 19(b)  –  –  –

Table 35: n = 19(c), k = 4, d = 10, m_{f} = 9

m  {minors}  Δ(m) max? full?
20  {2} × 5^{10}  2 × 5^{10} yes no
19  {1} × 5^{9}  833 × 4^{6} no  no
18  {0, 1} × 5^{8}  17 × 4^{8} no  no
17  {0, 1} × 5^{7}  5 × 4^{8}  no  no
16  {0..2} × 5^{6}  2 × 4^{8}  no  no
15  {0..3} × 5^{5}  35 × 3^{6} no  no
14  {0..5} × 5^{4}  13 × 3^{6} no  no
13  {0..9} × 5^{3}  5 × 3^{6}  no  no
12  {0..18, 20, 24, 32} × 5^{2}  2 × 3^{6}  no  no
11  {0..40, 42, 44, 48} × 5^{1}  64 × 5^{1} no  no
10 {0..92, 95, 96, 100, 104, 108, 112, 125, 144}  144  yes no
9  {0..40, 42, 44, 48}  56  no  no
1–8  full spectrum  ≤ 32  yes yes

Table 36: n = 20(a), k = 5, d = 10, m_{f} = 8

m  {minors}  Δ(m) max? full?
12–20  as for 20(a)  –  –  no
11  {0..40, 42, 44, 45, 48} × 5^{1}  64 × 5^{1} no  no

{0..90, 92, 93, 95..102, 104, 108,

10  112, 117, 120, 125, 128, 144}  144  yes no
9  {0..40, 42, 44, 45, 48}  56  no  no
1–8  full spectrum  ≤ 32  yes yes

Table 37: n = 20(b), k = 5, d = 10, m_{f} = 8

m  {minors}  Δ(m) max? full?
11–20  as for 20(b)  –  –  no

{0..88, 90, 92, 93, 96, 99, 100, 102,

10 104, 108, 112, 120, 125, 128, 144} 144 yes no
1–9  as for 20(b)  –  –  –

Table 38: n = 20(c), k = 5, d = 10, m_{f} = 8

Order 21(a)–(b)

m (min, max) |minor| Δ(m) max? full?
21  (29, 29) × 5^{9}  29 × 5^{9} yes no
20  (10, 30) × 5^{8}  50 × 5^{8} no  no
19  (0, 35) × 5^{7}  833 × 4^{6} no  no
18  (0, 40) × 5^{6}  17 × 4^{8} no  no
17  (0, 45) × 5^{5}  5 × 4^{8}  no  no
16  (0, 65) × 5^{4}  2 × 4^{8}  no  no
15  (0, 100) × 5^{3}  35 × 3^{6} no  no
14  (0, 240) × 5^{2}  13 × 3^{6} no  no
13  (0, 416) × 5^{1}  5 × 3^{6}  no  no
12  (0, 800)  1458  no  no
11  (0, 320)  320  yes no
10  (0, 144)  144  yes no
1–9  full spectrum  ≤ 56  yes yes

Table 39: n = 21(a), k = 5, d = 10, m_{f} = 9

m (min, max) |minor| Δ(m) max? full?
15–21  as for 21(a)  –  –  no
14  (0, 216) × 5^{2}  13 × 3^{6} no  no
13  (0, 400) × 5^{1}  5 × 3^{6} no  no
12  (0, 800)  1458  no  no
11  (0, 320)  320  yes no
1–10  full spectrum  ≤ 144 yes yes

Table 40: n = 21(b), k = 5, d = 10, m_{f} = 10

Order 21(c)–(e)

m (min, max) |minor| Δ(m) max? full?
15–21  as for 21(a)  –  –  no
14  (0, 200) × 5^{2}  13 × 3^{6} no  no
13  (0, 400) × 5^{1}  5 × 3^{6} no  no
12  (0, 800)  1458  no  no
11  (0, 304)  320  no  no
10  (0, 144)  144  yes no
1–9  full spectrum  ≤ 56  yes yes

Table 41: n = 21(c), k = 5, d = 11, m_{f} = 9

m (min, max) |minor| Δ(m) max? full?
15–21  as for 21(a)  –  –  no
14  (0, 240) × 5^{2}  13 × 3^{6} no  no
13  (0, 416) × 5^{1}  5 × 3^{6} no  no
12  (0, 800)  1458  no  no
11  (0, 320)  320  yes no
1–10  full spectrum  ≤ 144 yes yes

Table 42: n = 21(d), k = 5, d = 10, m_{f} = 10

m (min, max) |minor| Δ(m) max? full?
15–21  as for 21(a)  –  –  no
14  (0, 212) × 5^{2}  13 × 3^{6} no  no
13  (0, 368) × 5^{1}  5 × 3^{6} no  no
12  (0, 800)  1458  no  no
11  (0, 288)  320  no  no
10  (0, 144)  144  yes no
1–9  full spectrum  ≤ 56  yes yes

Table 43: n = 21(e), k = 5, d = 11, m_{f} = 9

2010 Mathematics Subject Classification: Primary 05B20; Secondary 15B34, 62K05. Keywords: Hadamard matrices, maximal determinant matrices, saturated D-optimal designs, minors.

(Concerned with sequences \underline{A003432}, \underline{A003433}, \underline{A215644}, and \underline{A215645}.)

Received August 19 2012; revised version received March 10 2013. Published in Journal of Integer Sequences, March 10 2013.

Return to Journal of Integer Sequences home page. 30