3
$\begingroup$

The Hadamard circulant conjecture states that there do not exist circulant Hadamard matrices with more than $4$ columns.

An $n$ by $n$ Hadamard matrix where the entries are chosen from $\{-1,1\}$ has determinant $\pm n^{n/2}$.

Does there exist a $c >1$ for which there exists an infinite number of positive integers $n$ such that there exists an $n$ by $n$ circulant $\{-1,1\}$-matrix with determinant at least $n^{n/c}$ (in absolute value)?

Despite searching the literature as far as possible I have not found this question discussed. What is its status? In particular, is it the case that:

  • It is known to be true.
  • It is conjectured to be true.
  • It is conjectured to be not true.
  • No one has ever considered the question.
  • Other.

Thank you very much for any help.

$\endgroup$
1
  • $\begingroup$ I do not know how it helps to answer, but determinant of a circulant matrix with first row $(c_0,c_1,\dots,c_{n-1})$, $c_{n-1}=\pm 1$, is $\pm \prod (x_i^n-1)$, where $x_1,\dots,x_{n-1}$ are the roots of the polynomial $c_0+c_1x+\dots +c_{n-1}x^{n-1}$. $\endgroup$ Commented Jan 10, 2016 at 12:20

1 Answer 1

1
$\begingroup$

I have not seen this question discussed in the literature either, but I will propose an answer here.

To begin with, I think that since $n^{n/2}$ is the maximum possible absolute value that the determinant of any $\{-1,1\}$-matrix can have (Hadamard upper bound), the constant $c$ in the question (if it exists) must necessarily be $\geq 2$.

I will now argue that any $c>2$ has the property described in the question. I will do that by sketching a derivation of the following lower bound for the largest $|\det A|$, which is stronger asymptotically for any $c>2$ than the bound $n^{n/c}$ suggested in the question.

Proposition:

There exists a real constant $\alpha > 0$, so that for any positive integer $n \geq 3$ there is at least one circulant matrix $A \in \{-1,1\}^{n \times n}$ that obeys $|\det A| > (\alpha n)^{n/2}$. Moreover, $\alpha = \sqrt2/{\rm e} \approx 0.52$ (and thus also any smaller $\alpha$) has this property.

The above proposition can be proved as follows. Using the same technique as described in this previous answer, it can be shown that the mean value of $|\det A|^2$ over all $n \times n$ circulant $\{-1,1\}$-matrices $A$ is bounded from below by $2^{\lfloor \frac{n-1}2 \rfloor} n!$, for any $n$ except $n=2$, where that mean value is zero. (In the previous answer, a lower bound $2^{-2n+\lfloor \frac{n-1}2 \rfloor} (n+1)!$ was derived for circulant $\{0,1\}$-matrices instead.)

Using Stirling's lower bound on $n!$ we then obtain the following sequence of lower bounds on the mean value of $|\det A|^2$: $$ 2^{\lfloor \frac{n-1}2 \rfloor} n! > 2^{\frac{n}2-1} \sqrt{2\pi n}\ \left(\frac{n}{\rm e}\right)^n > \left(\frac{\sqrt2}{\rm e} n \right)^n \ . $$ The last of these bounds implies that among these matrices $A$ there must be at least one with $|\det A| > (\alpha n)^{n/2}$, where $\alpha =\sqrt2/{\rm e}$, which concludes the proof.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .