6
$\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$
  • $\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$ – Fedor Petrov Jan 10 '16 at 12:20
2
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.