This material is still unfinished. For related material please go to the determinant spectrum page.
Lemma: Let delta(n) be the maximum value in the set
D_n{1,-1}, i.e. in the set {d | d = det(A)
for some A an order n {1,-1}-matrix}. For every
n greater than 127, n*log(n)/2 -log(delta(n))
is less than n*(epsilon)/2, where
epsilon is less than log(4/3).
Note that delta(n) is the maximum value in both the sets D_n{1,-1} and D_n{1,0,-1} (the latter allowing determinants of matrices of order n whose entries come from the set {1,0,-1}). Thus, it will suffice to provide for each sufficiently large n an order n {1,0,-1} matrix D and corresponding epsilon such that n*log(n) - 2*log(det(D)) < n*epsilon < n*log(4/3).
I will call a number h a Hadamard number if there is a Hadamard matrix of order h. I assume there is a positive real number r>=2 with the following property: For all sufficiently large n, there are non-negative integers s and k such that s < 4 and such that there are k Hadamard numbers r_i with n = r_1 + r_2 + ... + r_k +s with r_i at least r*r_{i+1} for i from 1 to k-1, and with r_k is greater than s. Thus, n is the sum of a sequence of numbers which, with the exception of the final term, is a sequence of Hadamard numbers majorized by the geometric sequence r^(1-n) * r_1.
As 2^m is a Hadamard number for any non-negative integer m, we note that r=2 has the desired property for all positive n (taking care to handle the case k=0). In what follows, better results will occur when n/r_1 is close to 1 and when r is as large as possible. I will generally ask that n be greater than 4r.
Given n and its decomposition into Hadamard numbers, let the order n {1,0,-1}-matrix D be given by diag(H_1,H_2,...,H_k,S), where the first k matrices are Hadamard matrices H_i of order r_i. Also, S is an order s matrix, and when s=1 or 2, S will also be a Hadamard matrix. If s=3, S will be a {1,-1}-matrix with determinant 4. A suggestive picture is:
| r_1 | r_2 |...|s|
1 1 1 1 . . . 1
1 1
1 1
1 1
. H_1 . 0
. .
. .
. .
1 1 1 1 . . . -1
1 1 .. 1
. .
. H_2 .
D = . .
0 1 1 ..-1
.
.
.
S
Note the only non-zero entries are in blocks along the
diagonal. As a result, det(D) is the product of the
determinants of H_i and S, which in general are
sqrt(r_i)^(r_i), and sqrt(s)^s. To make the discussion
below more uniform, I define c to be 1 when s is 0,
c = s when s is 1 or 2, and c = 16^(1/3) when s is 3.
So c "looks like" det(S)^(2/s).
I also let a = r_1/n < 1. I then have
n log n - 2*log(delta(n)) <= n log n - log(det(D)*det(D))
r_1 n r_k n s n
= n*[---log(---)+ ... + ---log(---) + -log(-)]
n r_1 n r_k n c
1 a r^(k-1) s n
<= n*[alog(-)+ ... + -------log(-------) + -log(-)],
a r^(k-1) a n c
As xlog(1/x) is increasing on the interval (0,1/e), the last
inequality is valid as long as a*e < r. I will have a be
at least 1/2, and it will appear that n > 127 allows the
assumption r > e.
For d a positive real number less than 1, the sum of -a*d^i log(a*d^i) for i ranging over the non-negative integers is -(a*log(a))/(1-d) - (a*d*log(d))/((1-d)^2). I use this to bound the first k terms of the sum above and get
2 a*r log(r) s n
log n - -*log(delta(n)) <= ---*[-log(a) + ------] + -log(-)
n r-1 r-1 n c
For sufficiently large n and some r>=2, one will find
decompositions such that (1-a)*(r-1) < a.
If I take r=2, I find the above is maximized when a= 1/2, in which case the term on the right hand side is {log(4) + (s/n)*log(n/c)}. This is not as good as the log(4/3) bound provided by Clements and Lindstroem. In order to provide a better bound, I must show that a larger r can be chosen.
Note that for any positive integer p <65 and any integer m > 1, there is a Hadamard matrix of order p*2^m, using well-known constructions. Thus for n larger than 128, one can find a sequence as above where (n-r_1)*32 is less than n and r>=32 as follows: Set n_0=n and i=0. If n_i>=128, produce p and m such that r_i= p*2^m, n_i>=r_i, p<64, and r_i is as large as possible, then add 1 to i. One has that (n_i - r_i) * 32 is less than r_i (consider the 6 most significant bits of the binary expansion of n_i). If n_i<128, set n_i= r_i +s where s is in {0,1,2,3}, r_i is a Hadamard number, and s is as small as possible.
We now have n decomposed as above, with r>=32. In particular, a is greater than 30/31. For n>=128, the sum above is smaller than 1/30 + 1/8 + 1/10, which is less than log (4/3). This ends the proof of the Lemma.
In the above, the situation a*e < r was handled because r > e was shown and a<1. For n between 44 and 128, one can use a decomposition of r_1 + s and the method above to get an epsilon less than log(4/3). For n less than 44 (especially when n is 3 mod 4), different constructions should be used to establish an epsilon less than log(4/3). However, the inequality of the lemma holds for all positive integers n.
One can also alter the construction of D to take advantage of a construction by Schmidt which allows the contribution by S and the smaller H_i to the product to be replaced by something larger (on the order of 2^(2s), for s on the order of log(n) and not just s<4). So the bound above is quite poor. The point of this note is to show a weak yet demonstrably improved lower bound for all n which are sufficiently large.
Of course, one can take advantage of more Hadamard matrices to reduce the constant even further. A bound of J. Seberry (Wallis) published in 1976 implies the existence of a Hadamard matrix of order q*p, where q is any odd number and p is a power of 2 less than q^3 and close to q^2; this bound can be used with the above method to show that (n^n)/(delta(n)^2) is less than e^(n^(2/3) * [1 + log(n)^2]) for all sufficiently large n. Ideally, the exponent above should be replaceable by a constant for all n.
Return to the main page for related material.