4
$\begingroup$

Define an antisymmetric 1-x-matrix as an $n\times n$ matrix $M=(m_{ij})$ with $m_{ii}=0$ and $\{m_{ij},m_{ji}\}=\{1,x\}$ for all $1\le i<j\le n$. Call their set $\mathcal A_n$.
The setup is as here: I am interested in how big the determinant of such a matrix can be.

For this, we define again the following:

For polynomials $f(x)=f_nx^n+\cdots+f_0$ and $g(x)=g_mx^m+\cdots+g_0$ with $f_n,g_m>0$, we say that $f$ dominates $g$ if either $n>m$ or $(f_n,\dots,f_0) \succ (g_m, \dots,g_0)$ in lexical order. Equivalently, $f(x)\geqslant g(x)$ for large $x>x_0$.

The matrices of $\mathcal A_n$ are in fact essentially the same as tournaments (i.e. complete graphs with oriented edges): Label the vertices $1,\dots,n$ and give for $i\ne j$ the edge $(i,j)$ the orientation $i\to j$ iff $m_{ij}=x$. Now in the existing literature, tournaments are usually examined in terms of paths, cycles etc... I couldn't find anything related to the following I found experimentally:

Conjecture: For a prime $n=4k-1$, the dominant determinant for a matrix of $\mathcal A_n$ is $$(2k-1)(x+1)[kx^2-(2k-1)x+k]^{2k-1}$$ and is attained by a matrix which can be written after suitable line and column permutations in a unique way (up to transposition $1\leftrightarrow x$) as a circulant matrix.

E.g. for $n=7$, the circulant matrix

$$M=M_7=[0, x, x, 1, x, 1, 1]=\begin{pmatrix} 0&x&x&1&x&1&1\\ 1&0&x&x&1&x&1\\ 1&1&0&x&x&1&x\\ x&1&1&0&x&x&1\\ 1&x&1&1&0&x&x\\ x&1&x&1&1&0&x\\ x&x&1&x&1&1& 0\end{pmatrix} $$

is extremal in $\mathcal A_7$ with determinant $3(x + 1)( 2x^2 - 3x + 2)^3$. The first extremal matrices are

$M_{3}=[0, \ \ x, \ \ 1] $

$M_{7}=[0, \ \ x, x, 1, \ \ x, 1, 1] $

$M_{11}=[0, \ \ x, 1, x, x, x,\ \ 1, 1, 1, x, 1] $

$M_{19}=[0, \ \ x, 1, 1, x, x, x, x, 1, x, \ \ 1, x, 1, 1, 1, 1, x, x, 1]$

$M_{23}=[0, \ \ x, x, x, x, 1, x, 1, x, x, 1, 1, \ \ x, x, 1, 1, x, 1, x, 1, 1, 1, 1]$

$M_{31}=[0, \ \ x,x,1,x,x,1,x,x,x,x,1,1,1,x,1, \ \ x,1,x,x,x,1,1,1,1,x,1,1,x,1,1]$

(written with spaces to display the anti-symmetry of the generating arrays).

If this conjecture is true, it would mean for example that each prime $p\equiv3\pmod4$ triggers a unique number defined by the corresponding binary code (just put $x=0$ and drop the anti-symmetric half of the array). E.g. $p=11$ yields $01000_2=8$, or $p=19$ yields $011000010_2=194$.
Or, even before that: What about the 2-adic valuation (number of 1's in the first half of the array) for a given $p$?

Does this have number-theoretic implications?

By curiosity, I have also computed some extremal matrices for small composite $n$ :

$n=4: \begin{pmatrix} 0&x&x&1\\ 1&0&x&1\\ 1&1&0&x\\ x&x&1&0\\ \end{pmatrix}$ with irreducible determinant $x^4 + x^3 - x^2 + x + 1$

$n=5: \begin{pmatrix} 0&x&x&x&1\\ 1&0&x&1&x\\ 1&1&0&x&x\\ 1&x&1&0&x\\ x&1&1&1&0\\ \end{pmatrix}$ with determinant $(x + 1)( x^2 - x + 1)( 3x^2 - 4x + 3)$

$n=6:\ \quad \begin{pmatrix} \color{blue}0&\color{blue}x&\color{blue}1&1&x&x\\ \color{blue}1&\color{blue}0&\color{blue}x&x&1&x\\ \color{blue}x&\color{blue}1&\color{blue}0&x&x&1\\ x&1&1&\color{blue}0&\color{blue}1&\color{blue}x\\ 1&x&1&\color{blue}x&\color{blue}0&\color{blue}1\\ 1&1&x&\color{blue}1&\color{blue}x&\color{blue}0\\ \end{pmatrix}$ with determinant $ (x^2 + 3x + 1)( 2x^2 - 3x + 2)^2$

$n=8: \begin{pmatrix} 0&1&1&1&x&x&x&1\\ x&\color{blue}0&\color{blue}x&\color{blue}1&x&1&1&1\\ x&\color{blue}1&\color{blue}0&\color{blue}x&1&x&1&1\\ x&\color{blue}x&\color{blue}1&\color{blue}0&1&1&x&1\\ 1&1&x&x&\color{blue}0&\color{blue}1&\color{blue}x&x\\ 1&x&1&x&\color{blue}x&\color{blue}0&\color{blue}1&x\\ 1&x&x&1&\color{blue}1&\color{blue}x&\color{blue}0&x\\ x&x&x&x&1&1&1&0\\ \end{pmatrix}\ \ $ or $\ \ \begin{pmatrix} 0&x&x&1&x&x&1&1\\ 1&0&x&x&x&1&x&1\\ 1&1&0&x&x&x&1&x\\ x&1&1&0&x&x&x&1\\ 1&1&1&1&0&x&x&x\\ 1&x&1&1&1&0&x&x\\ x&1&x&1&1&1&0&x\\ x&x&1&x&1&1&1&0 \end{pmatrix}\ \ $

both with determinant $ (2x^2 - 3x + 2)^ 2(6x^4 + 2x^3 - 9x^2 + 2x + 6)$. Note in the first one the central $6\times6$ square with a structure of $3\times3$ blocks very similar (in a sense, "dual") to the $n=6$ matrix given just before. Moreover, the anti-symmetry implies that its two extremal entries $m_{18}$ and $m_{81}$ can be swapped without altering the determinant! The second given matrix is non isomorphic to the first one (because it has a different incidence structure) and 'almost circulant'. For even $n$, tournaments cannot be circulant (what would $m_{1,\frac n2+1}$ be?), but this one comes closest possible to it $-$ an argument for its extremality in the light of my conjecture?

$n=9:$ supposedly best $\begin{pmatrix} 0&x&1&x&x&1&1&x&x\\ 1&0&x&x&1&x&1&x&x\\ x&1&0&x&x&x&1&1&1\\ 1&1&1&0&x&x&x&x&1\\ 1&x&1&1&0&x&x&1&x\\ x&1&1&1&1&0&x&x&x\\ x&x&x&1&1&1&0&x&1\\ 1&1&x&1&x&1&1&0&x\\ 1&1&x&x&1&1&x&1&0\\ \end{pmatrix}$ with determinant $ (x + 1)( 5x^4 - 15x^3 + 21x^2 - 15x + 5)( 19x^4 - 58x^3 + 82x^2 - 58x + 19)$. Note that the matrix can be (and has been here) written as symmetric w.r.t. the secondary diagonal. I don't know if it can be written in a 'more circulant' way as for $n=8$ and $n=10$ (supposedly yes), having done all the line and column swapping by hand in order to find the IMHO most beautiful shapes.

$n=10:$ supposedly best $\begin{pmatrix} 0&x&1&x&x&x&1&1&1&x\\ 1&0&x&1&x&x&x&1&x&1\\ x&1&0&x&1&x&x&x&1&1\\ 1&x&1&0&x&1&x&x&x&1\\ 1&1&x&1&0&x&1&x&x&x\\ 1&1&1&x&1&0&x&1&x&x\\ x&1&1&1&x&1&0&x&1&x\\ x&x&1&1&1&x&1&0&x&1\\ x&1&x&1&1&1&x&1&0&x\\ 1&x&x&x&1&1&1&x&1&0\\ \end{pmatrix}$ with determinant $ (x + 1)(3x^2 - 5x + 3)^ 3(32x^4 - 99x^3 + 139x^2 - 99x + 32)$. Again like for $n=9$ the matrix here is symmetric w.r.t. the secondary diagonal and again like for $n=8$ very close to being circulant.

Last question, based on these examples:

If $n$ is composite, is it possible that an extremal matrix is a Toeplitz matrix (i.e. each diagonal is constant)?

Being Toeplitz is a condition weaker than being circulant, but from the numerical experiments I would still expect a negative answer.

In the previous thread, I had asked for a relationship with Hadamard matrices. But here I won't insist, especially as circulant Hadamard matrices seem to be rather a no-go.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.