Possible values of the determinant for matrices with elements $\{1, 0, -1\}$

Question

For matrices with elements $\{-1, 1\}$ it is known from here that the possible absolute values of determinants of $n \times n$, $n \leq 6$ matrices with entries $\{-1, 1\}$ are as follows:

n=1: 1  

n=2: 0,2

n=3: 0,4

n=4: 0,8,16

n=5: 0,16,32,48

n=6: 0,32,64,96,128,160

Are there any known such results for matrices with elements $\{-1, 0, 1\}$?

I have found the following resource here, but unfortunately, it does not go beyond $n=5$. I am interested in such results and methods for $n>5$.

One motivating question I am trying to answer is the following: is there a $\{1, 0, -1\}$ matrix of order $6$ with the absolute value of the determinant equal to 27?

Answer 1

Here's a large subset of possible determinants, which may be enough for your application. With $n\times n$ matrices, one can achieve any integral determinant in the interval $[-2^{n-1},2^{n-1}]$.

Specifically, as @nathaniel-johnston notes, the answer to your example question is yes. There's actually straightforward way to construct the matrix (without a computer search). Consider matrices of the form $$M_b= \begin{bmatrix} b_0& 1& 1& 1& 1& 1 \\ b_1& -1& 1& 1& 1& 1 \\ b_2& 0& -1& 1& 1& 1 \\ b_3& 0& 0& -1& 1& 1 \\ b_4& 0& 0& 0& -1& 1 \\ b_5& 0& 0& 0& 0& -1 \end{bmatrix}. $$ Then $-\det(M_b)=b_0+b_1+2b_2+4b_3+8b_4+16b_5$. By picking $b_j\in\{0,1\}$ and using binary, one can get $\det(M_b)$ to be any integer in $[-32, 32]$. So concretely for your example, $$\det\left(\begin{bmatrix} 1& 1& 1& 1& 1& 1 \\ 0& -1& 1& 1& 1& 1 \\ 1& 0& -1& 1& 1& 1 \\ 0& 0& 0& -1& 1& 1 \\ 1& 0& 0& 0& -1& 1 \\ 1& 0& 0& 0& 0& -1 \end{bmatrix}\right)=-27.$$

This technique generalizes to any size matrix. Place $-1$s on the diagonal, $1$s above the diagonal, $0$s below the diagonal, then replace the first column with the binary expansion of your target determinant. The proof of this fact notes that the first row of the inverse of $M_{10\cdots 0}$ are the powers of two, then the cofactor expansion of the determinant along the first column means you get to sum powers of two to obtain possible determinants.

An almost identical proof is given in more detail in this paper (shameless plug of my own work, which is was also linked to by @sandeep in the comments of your post.)

Answer 2

I don't know of an answer to your general question of "what determinants are possible for $\{-1,0,1\}$ matrices", but I can answer "is there a {1,0,−1} matrix of order 6 with the absolute value of the determinant equal to 27?" in the affirmative: $$ \begin{bmatrix} 0 & 1 & 1 & 0 & 1 &-1\\ -1 &-1 & 1 & 0 & 1 &-1\\ 0 &-1 &-1 & 1 &-1 &-1\\ -1 &-1 & 0 & 1 & 1 &-1\\ 1 & 0 & 1 & 1 & 1 & 1\\ -1 & 1 & 1 & 1 & 0 & 1 \end{bmatrix} $$ This was found via random trial-and-error fairly quickly (about 1000 trials of random $\{-1,0,1\}$ matrices). I'd expect you can similarly generate matrices with determinant below the Hadamard bound fairly quickly as long as the size is not too large.

Answer 3

Too long to comment.

Since the set of matrices is also stable under block matrix construction (with [-1,0,1] matrices), one can obtain results such as the following.

Consider the matrices $A = \begin{bmatrix}1 & -1\\1 & 0\end{bmatrix}$, $B=\begin{bmatrix}1 & 0\\0 & 1\end{bmatrix}$ and $C=\begin{bmatrix}1 & -1\\1 & 1\end{bmatrix}$. Construct the matrix $D=\begin{bmatrix}A & B & 0\\B & A&0\\0&0&C\end{bmatrix}$. With that $\det(D) = \det(A-B)\det(A+B)\det(C)=1\cdot3\cdot2 = 6$. Similarly, one can construct matrices of dimension $4n+2m$ which has a determinant of $3^n2^m$.

I'm not sure if such constructs exist for every integer though.

Answer 4

Since we are collecting some constructive criteria in the comments, I thought it would be nice to find a way to constrain the possible determinants.

Let $S$ be the set $\{-1, 0,1\}$, but the criterion holds for any set which is invariant for sign change. Unless otherwise specified, all the vectors and coefficients are in $S$. Let's denote by $\textrm{Det}_S(n)$ the set of integers that are achieved as determinants of $n\times n$ matrices with coefficients in $S$. Then we have the following

CRITERION We have that $d \in \textrm{Det}_S(n+1), d \neq 0$ if and only if there exist $0 \neq d_1 , \ldots, d_{n+1} \in \textrm{Det}_S(n)$, $v_1, \ldots, v_{n+1} \in S^n$ and $c_1, \ldots c_{n+1} \in S$ such that $$ \sum_i (-1)^i d_i v_i = 0$$ $$ \det(v_2| \ldots | v_n) = d_1 $$ $$ \sum_i (-1)^i d_i c_i = d$$

Proof. If $d \in \textrm{Det}_S(n+1)$, by Laplace expanding in the first row you get numbers $c_1, \ldots, c_{n+1} \in S$ and determinants $d_1, \ldots, d_{n+1} \in \textrm{Det}_S(n)$ such that $$ d = \sum (-1)^{i} c_i d_i $$ Also, the $d_i$ satisfy the following condition: there exists $v_1, \ldots,v_{n+1}$ such that $$ d_i = \det( v_1 | \ldots | \hat{v}_i | \ldots | v_{n+1} ) $$ Suppose WLOG that $d_1 \neq 0$. Otherwise, up to signs, you can rearrange the columns and get $d_1 \neq 0$.We want to show that the $n+1$ determinant conditions are equivalent to the first condition plus $$ \sum_i (-1)^i d_i v_i = 0$$ If the determinant condition holds, since the determinant of $v_2, \ldots, v_{n+1}$ is not zero, they are a basis. Write $$ v_1 = \sum_{i \ge 2} (-1)^i \lambda_i v_i $$ For some $\lambda_i$. Substituting into the $i$-th determinant condition we get $$ d_i = \det ( (-1)^i \lambda_i v_i | v_2 | \ldots | \hat{v}_i | \ldots | v_{n+1} ) = (-1)^i \lambda_i \det (v_i | v_2 | \ldots | \hat{v}_i | \ldots | v_{n+1} ) = \lambda_i d_1 $$ From which we get $\lambda_i = d_i/d_1$. We used that the contributions along, for example, $v_2$, does not contribute to the determinant since $v_2$ is a column of the matrix. Subsstituiting into the expression for $v$ we get $$ v_1 = \sum_{i \ge 2} (-1)^i \frac{d_i}{d_1} v_i$$ From which we get the desired constraint.

On the other hand, if the constraint hold and the first determinant is correct, the determinants containing $v_1$ can be computed using the expression for $v_1$ exactly as above, yielding the correct value $d_i$ for the $i$-th condition.

EXAMPLES.

$\textrm{Det}_S(3)$. Starting from $\textrm{Det}_S(2) = \{-2, \ldots, 2\}$, let's see for example that the maximum of $\textrm{Det}_S(3)$ is $4$. Indeed, the tuple $222$ is impossible, since $$ 2v_1-2v_2+2v_3 = 0$$ Implies $$ v_1 = v_3-v_2$$ But the only pairs of vectors with determinant two are in $(\pm 1, \pm 1) $. This implies that $v_1$ has even entries, but the only possible even entry is zero. We conclude that $v_1-v_3 =0$, a contradiction.

The tuple $221$ is impossible too, since $$ 2v_1-2v_2+v_3 = 0$$ Implies modulo 2 that $v_3=0$, a contradiction. 220 is possible and realized by $ (1, 1), (1, -1), (1, -1) $.

$\textrm{Det}_S(4)$. Going one step further, this explains why 15 does not show up in $\textrm{Det}(4) $. Indeed, the only possible tuple that would determine $15$ is $ 4443$, and this is not possible, since $$ 4v_1-4v_2+4v_3-3v_4=0$$ Implies modulo 2 that $v_4=0$,which is a contradiction.

Similarly, $14$ is not possible, since the two candidate tuples are $4433$ and $4442$. The latter implies $$ 4v_1-4v_2+4v_3-2v_4 = 0$$ Dividing by $2$ and analyzing modulo $2$ we get $v_4 = 0$, which is impossible. The tuple $4433$ gives $$ 4v_1-4v_2+3v_3-3v_4 = 0$$ Modulo $4$ we have $v_3 = v_4$, which implies $v_3 = v_4$, a contradiction (since $4 = \det(v_2 | v_3 | v_4)=0$).

Corollary criterion. A nonzero candidate tuple cannot have only one odd number, nor only two equal numbers $a \neq 0 \pmod{m}$ numbers for $ m/ \textrm{gcd}(a,m) \ge 3$.

Proof. If there is just one odd number, modulo $2$ we get a zero vector, which is impossible. If there are only two equal numbers $a \neq 0 \pmod{m}$ we get modulo $m$ that $$a v_i \equiv a v_j \pmod{m}$$ $$v_i \equiv v_j \pmod{\frac{m}{\textrm{gcd}(a,m)} }$$ which implies $v_i = v_j$, a contradiction.