17
$\begingroup$

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?

$\endgroup$
16
  • 4
    $\begingroup$ A simple observation is that your class of matrices is stable for sign change of a column, so if there exist a matrix with determinant $D$, it also exist a matrix with determinant $-D$. In other words, in your motivating question you can ask for determinant precisely 27. $\endgroup$ Apr 17, 2022 at 22:45
  • 3
    $\begingroup$ Last observation, and then I'll go XD if $a, b$ are possible determinants of size $n, m$ then $ab$ is a possible determinant for size $nm$, since your class is stable for tensor of matrices! $\endgroup$ Apr 17, 2022 at 23:02
  • 5
    $\begingroup$ This could be relevant: arxiv.org/abs/2006.04701 $\endgroup$ Apr 18, 2022 at 14:09
  • 4
    $\begingroup$ In trying $10^6$ random such matrices, I got $|\det|=27$ in 990 cases... $\endgroup$
    – YCor
    Apr 18, 2022 at 17:14
  • 3
    $\begingroup$ For $n=6$ using random generation of such matrices, I obtained (absolute value of det of $\{\pm 1,0\}$-valued matrices): (a) all odd numbers from 1 to 95, plus 99, 105 and 125; (b) all numbers in $2\mathbf{Z}$ from 0 to 116, plus 120, 128, 130, 132, 136, 144, 160 (160 is the maximum possible, cf my previous comment). Did I miss any number? I particular, can one get any of 97, 101, 118, 124, 152? $\endgroup$
    – YCor
    Apr 20, 2022 at 9:26

4 Answers 4

27
$\begingroup$

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.)

$\endgroup$
3
  • 2
    $\begingroup$ Very nice. It reminds me of a construction by Kim, Lee, and Seol that I mentioned in another MO answer, although they were considering permanents rather than determinants. $\endgroup$ Apr 20, 2022 at 10:13
  • $\begingroup$ Brute force checking shows that the possible (absolute values of) determinants of $4\times 4$ matrices additionally include 9, 10, 12 and 16. Perhaps with Andrea Marino's answer one can do much more. $\endgroup$ Apr 20, 2022 at 13:52
  • $\begingroup$ I believe far more determinants are possible, but I'm not aware of any constructions. In particular, Tao and Vu in this paper prove $|det(M)|\in[\sqrt{n!}\,2^{-n^{0.51}},\sqrt{n!}\,n^{1.1}]$ with high probability for M with random $\pm1$ entries. I would therefore guess that there at least $\sqrt{n!}\sim 2^{O(n\log n/2)}$ possible values of the det. $\endgroup$
    – rikhavshah
    Apr 21, 2022 at 2:02
17
$\begingroup$

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.

$\endgroup$
1
  • 3
    $\begingroup$ It seems that the $\{0,\pm1\}$ analogue of A013588 is not in the OEIS. Maybe someone should add such a sequence, if it looks interesting. $\endgroup$ Apr 18, 2022 at 17:16
5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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