3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ I assume these matrices are all over the ring R of real numbers. Since they are full rank, row addition can make one row all the same coefficient with no change in determinant. Then subtracting multiples of this row can change all the other rows to y or -y (y some thing like (1-x)/2). Sometimes you can convert the remaining row to y -y without changing the determinant, but there is a computable factor c by which the new binary matrix determinant is c times the determinant of the original matrix. (c may depend on the matrix.) Gerhard "But Wait! There Is More!" Paseman, 2017.04.02 $\endgroup$ – Gerhard Paseman Apr 2 '17 at 21:12
  • $\begingroup$ Now you have the same situation as for 1,-1 order n matrices (which by a similar method is like 2^{n-1} times the determinant for 0,1 order n-1 matrices). Except for the cases where c is involved I don't see this as a problem different from the binary case, only differing in a scale factor like y^n. Gerhard "Numbers Are Just Symbols Anyway" Paseman, 2017.04.02. $\endgroup$ – Gerhard Paseman Apr 2 '17 at 21:16
  • $\begingroup$ I see. Those row operations may thus destroy the symmetries and create new ones, I suppose. Maybe I stick too much to 'nice' symmetries? $\endgroup$ – Wolfgang Apr 2 '17 at 21:20
  • $\begingroup$ Oh, and binary 0,1 matrices with maximal determinant are not always symmetric. I believe, but cannot refer you to a proof yet, that some of them are not symmetrizable. Gerhard "Consider Three Mod Four Orders" Paseman, 2017.04.02. $\endgroup$ – Gerhard Paseman Apr 2 '17 at 21:21
  • $\begingroup$ I don't know how much symmetries play in your study. While x=0 , x=1, and x=-1 will exhibit different behaviours, my point is that you do not need to consider any other values of x for your problem. By well understood transformations (most of them row additions and thus determinant preserving), your set is reducible to studying one of these three cases. Gerhard "That's How I See It" Paseman, 2017.04.02. $\endgroup$ – Gerhard Paseman Apr 2 '17 at 21:26

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.