Define $\mathcal M_n$ as the set of all $n\times n$ matrices of full rank with each entry either 1 or $x$. I am interested in how big the determinant of such a matrix can be. For this, we define in a straightforward way 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$.
Then my main question is:
What can be said about the matrices in $\mathcal M_n$ whose determinant dominates all the others?
We will identify matrices that only differ by a combination of row/column permutations and/or transposition, as the determinant doesn't change up to sign. Moreover, we always assume that the leading coefficient $f_n$ is positive (otherwise just switch two lines).
For $x\to1$, the matrices of $\mathcal M_n$ degenerate to the all-1-matrix of rank $1$ instead of $n$. From this it is easy to see that for $M\in\mathcal M_n$, we have $$\det(M)=(x-1)^{n-1}(ax+b).$$ We'll refer to this linear form $ax+b$ (wlog $a>0$) as the remainder of $M$. For given $n$, denote the dominant remainder by $a_nx+b_n$.
The sequence $(a_n)$ is well-known (see below).
What can be said about $b_n$ (other than $b_n\le a_n$)?
For each line or column of a matrix $M\in\mathcal M_n$, we define its weight as the number of $x$'s occurring in it. The signature of $M$ is the set of the two vectors of row weights and column weights, wlog both in non-increasing order. (And wlog we'll reorder the rows and columns accordingly.)
Matrices of different signatures can have the same determinant. Intuitively, I would conjecture though that for the extremal ones, the signature is unique and that the matrices can be arranged in a fairly symmetrical way. Signatures can help to identify certain symmetries of such matrices which have been found experimentally.
Extensive (but for $n\ge7$ not exhaustive) computations seem to show that the extremal matrices always can be written (by performing row/column permutations) as symmetric ones, meaning in particular that rows and columns have the same signature. Intuitively, this is no surprise, but:
Can that be proven, maybe by some extremal principle?
Some examples :
$n=3$: best remainder is $2x+1$, e.g. $M=\begin{pmatrix} 1&x&x\\ x&1&x\\ x&x&1\\ \end{pmatrix}$ with signature $(222,222) $
$n=4$: best remainder is $3x+2$, e.g. $M=\begin{pmatrix} 1&x&x&x\\ x&x&1&1\\ x&1&x&1\\ x&1&1&x\\ \end{pmatrix}$ with signature $(3222,3222) $
$n=5$: best is $5x+4$ for $M=\begin{pmatrix} x&x&1&1&x\\ x&x&1&x&1\\ 1&1&x&x&x\\ 1&x&x&1&1\\ x&1&x&1&1\\ \end{pmatrix}$ with signature $(33322,33322)$
$n=6$: best is $9x+9$ with $M=\begin{pmatrix} \color{blue}x&\color{blue}1&x&x&1&1\\ \color{blue}1&\color{blue}x&x&x&1&1\\ 1&1&\color{blue}x&\color{blue}1&x&x\\ 1&1&\color{blue}1&\color{blue}x&x&x\\ x&x&1&1&\color{blue}x&\color{blue}1\\ x&x&1&1&\color{blue}1&\color{blue}x\\ \end{pmatrix}$ and signature $(3_6,3_6)$. Note the circulant block structure of the $2\times2$ blocks, which will be referred to below.
$n=7$: very probably best is $32x+24$ with, e.g.,
$M=\begin{pmatrix}
x&1&1&\color{blue}x&1&x&x\\
1&x&1&\color{blue}x&x&1&x\\
1&1&x&\color{blue}x&x&x&1\\
\color{blue}x&\color{blue}x&\color{blue}x&\color{blue}x&\color{blue}1&\color{blue}1&\color{blue}1\\
1&x&x&\color{blue}1&1&x&x\\
x&1&x&\color{blue}1&x&1&x\\
x&x&1&\color{blue}1&x&x&1\\
\end{pmatrix}$ or $M=\begin{pmatrix}
x&x&x&1&x&1&1\\
1&x&x&x&1&x&1\\
1&1&x&x&x&1&x\\
x&1&1&x&x&x&1\\
1&x&1&1&x&x&x\\
x&1&x&1&1&x&x\\
x&x&1&x&1&1&x
\end{pmatrix}$,
which both have signature $(4_7,4_7) $. Note the symmetry of the first one and the $3\times3$ blocks in the 4 corners. The second one is not symmetric, but circulant. BTW the question whether both matrices are essentially the same (i.e. obtainable from one another by suitable permutations of rows and columns) has motivated this question.
$n=8$: best so far is $56x+40$ with $M=\begin{pmatrix} 1&x&x&x&1&x&\color{blue}1&\color{blue}x\\ x&1&x&x&x&1&\color{blue}1&\color{blue}x\\ x&x&1&x&x&x&\color{blue}1&\color{blue}1\\ x&x&x&1&x&x&\color{blue}1&\color{blue}1\\ 1&x&x&x&x&1&\color{blue}x&\color{blue}1\\ x&1&x&x&1&x&\color{blue}x&\color{blue}1\\ \color{blue}1&\color{blue}1&\color{blue}1&\color{blue}1&\color{blue}x&\color{blue}x&\color{blue}x&\color{blue}x\\ \color{blue}x&\color{blue}x&\color{blue}1&\color{blue}1&\color{blue}1&\color{blue}1&\color{blue}x&\color{blue}x\\ \end{pmatrix}$ and signature $(5_64_2,5_64_2) $. Look again at the $2\times2$ blocks.
The sequence $2,3,5,9,32,56...$ of the $a_n$'s is the same as A003432, which is the largest determinant of a {0,1}-matrix of order n. This is clear from the following argument: If $M\in\mathcal M_n$ with $\det(M)=f(x)=(x-1)^{n-1}(ax+b)$ and $M^\sim$ is defined by swapping the $1$'s with the $x$'s, we have $f^\sim:=\det(M^\sim)=x^nf(\frac1x)=(x-1)^{n-1}(bx+a)$, so by letting $x\to\infty$ in $M$ we get for the leading coefficient $f_n=f^\sim(0)=a$, while on the other hand putting $x=0$ in $M^\sim$ yields a {0,1}-matrix with determinant $a$. Further, all these steps can be reversed.
Now I am also wondering what is the link with the "Hadamard maximal determinant problem", which asks when a matrix of a given order with entries -1 and +1 has the largest possible determinant. The relationship between $\pm1$-matrices and 0-1-matrices is vaguely explained on the dedicated site as "a consequence of a mapping between binary and sign matrices" (which is supposedly bijective). But e.g. for $n=6$ the extremal $\pm1$-matrix \begin{pmatrix} -&+&+&+&+&+\\ +&-&+&+&+&+\\ +&+&-&+&+&+\\ -&-&-&-&+&+\\ -&-&-&+&-&+\\ -&-&-&+&+&-\\ \end{pmatrix} (essentially unique, up to permutations and negations of rows and columns) has obviously symmetries corresponding to $3\times3$ blocks, while the symmetries of the (also essentially unique) extremal 0-x-matrix above correspond to $2\times2$ blocks. The intriguing thing is further that Hadamard matrices only seem to encapsulate the $a_n$'s of the 1-x-matrices, but not the $b_n$'s. Well, it all may depend on the mapping.
Any insights about a reasonable such mapping?
