Unimodular Symmetric Logic Matrix – When is it Invertible?

Question

I am currently interested in invertible symmetric logical matrices, or, $(0,1)$-matrices, i.e., $n \times n$ matrices whose entries are either $0$ or $1$ (integers). I noticed that many invertible symmetric logical matrices that arise naturally from other fields of mathematics have determinant $\pm 1$, i.e., they are unimodular matrices.

Question: when is an invertible symmetric logic matrix unimodular?

Equivalent Question: can we find a property P such that "P + invertible + symmetric + Logical Matrix" implies "determinant = $\pm 1$?

Surprisingly, I find this question quite hard. For example, one of the property $P$ is the Lemma 2.1 in this article, which is very restrictive. I am wondering whether there are less restrictive conditions. There are many researches concerning logical matrices, and many concerns unimodular matrices. However, there are very few results on there intersections.

Answer 1

Edit because the title and question have changed to something specific: All invertible unimodular logical matrices belong to the group $GL_n(\mathbb{Z}_2)$, also written $GL(n, 2)$ by definition of the group. This group has an order of:

$$\prod_{j=0}^{n-1}(2^n-2^k)$$

It is a finite lie group under multiplication, so it is well known that given two of it's generating elements you may calculate the entire group. This paper here has formulas for the generators of any $GL(n, p)$ group, and since ours is one of those, it will work well. When you have this group, you may then pick the elements out of it that are symmetric and $0$-$1$ matrices. If you just want matrices with determinant $1$, the group is called $SL_n(\mathbb{Z}_2)$, or $SL(n,2)$ (I believe they are equivalent but I am not sure). Good luck.

I suppose you could use this in combination with a non full rank matrix to determine when a matrix has $0$, $1$, or $-1$ determinant, but you cannot really tell the difference between $1$ and $-1$ unless you want to calculate both $GL(n,2)$ and $SL(n,2)$.

Pre edit: At the time of writing, the question was for logical matrices with determinant $0, 1, $ or $-1$.

Generally, there are no strict rules on when we can look at a matrix and tell if it's determinant is $0,1,-1$ or any other number (and to the very best of my knowledge most people aren't concerned with $\pm 1$ and are more concerned with $0$ so there is less research there), so I believe the answer to your question will be no. However, there are many instances from which we can find whether or not a logical matrix has a determinant of $0,1, -1$, but each is restrictive. Denote $M$ to be our logical $0-1$ matrix, then off the top of my head:

• If a matrix $M$ is upper triangular with all of the elements in the upper triangle equal to $1$. Then, if $m_{12} = m_{12} = \ldots = m_{n-1n}= 0$, $\det(M) = 1$, otherwise $\det(M) = 0$.
• If the any two columns or rows of $M$ are all $1$ or $0$,or copies of each other, then $\det(B) = 0$.
• An interesting one (but not nessecarily useful) is that if we consider $M$ to be the anti-adjacency matrix of a directed graph $G$, then if $G$ is acyclic, and has a Hamiltonian path $\det(M) = 1$, if it is just acyclic $\det(M) = 0$.

An interesting note about this last point is $1$) Any symmetric logical matrix can be considered as the adjacency matrix of a graph, and 2) any logical matrix can be considered as the adjacency matrix of a directed graph. So, if you were so inclined you could find patterns in graphs that affect matrices and also there determinants and go from there, or you could view every logical matrix as a graph, find things about the graph, and then see if this translates into anything about it's determinant. Moving on:

• By Schur's formula, if we choose to represent $M$ as a block matrix such that (if $A$ is $p \times p$, $B$ is $p \times q$, $C$ are $q \times p$, and $D$ is $q \times q$ matrices: $$M = \begin{pmatrix} A & B \\ C & D \end{pmatrix} $$ Then,$\det(M) = \det(A) \det(D - CA^{-1}B)$ if $A$ is invertible, or $\det(M) = \det(D) \det(A - CD^{-1}B)$ is $D$ is invertible. So, if one is invertible and one is not, then our determinant is $0$.

Outside of these tidbits, you may find the following papers interesting (again no general rules in them):

• Determinants Whose Elements Are $0$ and $1$ by John Williamson. Available here
• Note on best possible bounds for determinants of matrices close to the identity matrix by Richard P. Brent et al. Available here
• Wikipedia Logical Matrices by whoever writes wikipedia. Available here. (While not a paper, it does show the alternate names of a logical matrix which may be of interest to you).

To conclude: no. We do not have general rules about determinants of matrices because they are really really hard to make. Instead, we have tiny cases where the determinant is $0$ or $\pm 1$.