Note that this work is not completed. Thus you run the risk of acheiving dissatisfaction after perusing this page.
In what follows, several notions of equivalence are used. Since the subject concerns determinants of 0-1 matrices, I will use symmetries implied by the determinant function to reduce the number of cases to be examined. Such symmetries include row permutation, column permutation, matrix transpose, multiplication of rows by scalars, and adding the scalar multiple of one row to another row. These operations preserve the order of the matrix, and certain combinations of them will preserve the property that all the matrix entries lie in {0,1}, or lie in {0,1,-1}. Except when context clearly dictates otherwise, I will assume that if B is equivalent to a 0-1 matrix A by the operations above, then B is also a 0-1 matrix.
As I will usually work with matrices of order larger than 1, I remark that for every such matrix A with det d, there is another matrix, gotten by permuting the last two rows of A, which has determinant -d. Thus I will often talk about one determinant being equivalent to another; in this case this means that the determinants have the same absolute value, so d and -d are equivalent in this sense. Thus all the operations listed above do not change the equivalence class of a determinant of a matrix, with the exception of multiplication by scalars other than 1 and -1. In most of what follows, all operations used preserve this determinant equivalence.
In the case of order 1, the determinant spectrum of all 0-1 matrices of this order is the set {0,1}, and does not enjoy a symmetrical distribution about 0 which is clearly possessed by the sets of all higher orders.
Since I will be computing determinants using Laplace's method of expanding by cofactors, I will use equivalence in another sense between matrices of different orders. For example, A and B are considered equivalent in this last sense when A is a matrix and B is A augmented by a certain special row and column which have all zero entries except for the common entry of 1, i.e. B is
0 ... 0 1
0
.
A .
.
0
Note that det(A) is not necessarily the same as det(B), but they
are necessarily equivalent. A is not equivalent to B
in any of the earlier senses since they have different orders.
So equivalence of A and B here should be interpreted
to mean equivalence of det(A) and det(B).
Theorem: Let d = det(A), where A is a 7x7 0-1 matrix. Then
abs(d) \in {0,1,...,17,18,20,24,32}.
The theorem above depends on several parts, some of which are listed below:
Lemma: There is a set of matrices G_n such that: a) G_n is an nxn 0-1 matrix; b) det(G_n) = 2*fib(n-1) - 1 where fib(m) is the mth Fibonacci number; c) For each positive integer i less than det(G_n) there is a 0-1 matrix H_i with det(H_i) = i and such that (G_n - H_i) is an nxn 0-1 matrix with at most n ones all in one row.
Lemma: There are 7x7 0-1 matrices with first row having only two ones and whose determinants are 16, 17, and 18 respectively.
Lemma C: Let A be a 6x6 0-1 matrix which is not equivalent to a 0-1 matrix with a row or column that has two ones. This means: a) every row has precisely 3 or 4 ones. b) For every two distinct rows of A, their dot product is 2, unless the rows each have exactly three ones, in which case their dot product is 1. Then abs(det(A)) is a multiple of 8.
Lemma D: Let A be an nxn 0-1 matrix, and let r and s be positive integers such that s>r>1, and r+s=n+1. Assume A satisfies the following properties concerning r and s: a) There are no rows with fewer than r or greater than s ones b) There is at least one row with either exactly r or exactly s rows. Then A is equivalent to a matrix B which satisfies the two properties above and an additional property: c) Let m_r be the number of rows of B with exactly r ones and m_s the number of rows of B with exactly s ones. Then m_r + m_s <=n and s*m_s <= r*m_r
Lemma E: The maximum determinant for any 6x6 0-1 matrix is 9.
For the proof of the first Lemmas please go to Lemmas.html.
Proof of Lemma C:
Use Lemma D to eliminate rows of lengths 5 and 6, as well as 2 and 1, and to produce a row of 1-content 3. Assume this row is the first row and the ones are in the first three columns.
Now note the following: each of the remaining rows has precisely two ones in the last column (otherwise the matrix is reducible to one with two or fewer ones.) Further, one cannot have three rows with the same pattern of ones in the last three columns (otherwise there is a column with only two ones.) I can thus rearrange it so that the columns look as follows, which lead by a row operation to the fact that the determinant of the original matrix is a multiple of two:
1 1 1 0 0 0 1 1 1 0 0 0 * * * 1 0 1 * * * 1 0 0 * * * 1 0 1 --> * * * 1 0 0 * * * 0 1 1 * * * 0 1 0 * * * 0 1 1 * * * 0 1 0 * * * 1 1 0 * * * 1 1 (-2)Now, investigating the second and third rows, I note the original matrix is equivalent to the matrix below, as otherwise the matrix is reducible to a matrix with two ones:
1 1 1 0 0 0 1 0 0 1 0 0 0 1 1 1 0 0 * * * 0 1 0 * * * 0 1 0 * * * 1 1 (-2)One can similarly argue for the fourth and fifth rows and use row operations to get that the determinant of the original matrix is equivalent to either
1 1 1 1 1 1 2 * det - 1 1 or 2 * det - 1 1 1 - 1 - 1 1thus giving that the original determinant is a multiple of 8.
Proof of Lemma D.
I will use the following technique, which I refer to as XOR by a row, which preserves equivalence classes of determinants and preserves the {0,1} character of a 0-1 matrix. For purposes of illustration, I apply it to a particular row of a certain matrix, although the method is much more general.
I use row addition and multiplications by the scalar -1 on columns and the chosen row to affect a particular matrix. Specifically, I take a chosen row, subtract it from all other rows, multiply the chosen row by -1, and multiply all affected columns by -1. As a simple demonstration, take
1 1 1 0 0 0 0 0 * * 0 1 0 * * 1 1 0 * *Using - to represent -1, I transform the matrix according to the following sequence, where the * entries remain unchanged:
(subtract (negate (negate
1 1 1 0 0 1st 1 1 1 0 0 1st - - - 0 0 some 1 1 1 0 0
0 0 0 * * row) - - - * * row) - - - * * cols) 1 1 1 * *
0 1 0 * * --> - 0 - * * --> - 0 - * * --> 1 0 1 * *
1 1 0 * * 0 0 - * * 0 0 - * * 0 0 1 * *
Note that the starred entries remain unaffected by the process, that
the result yields a 0-1 matrix, that the process can be applied
to non-square matrices, and that it is composed of operations
which preserve determinant equivalence. Similar operations
can be defined based on the column of a matrix. The only
difficulty is proving that a 0-1 matrix results, and this follows
from the fact that the first two operations affect a submatrix
of the same number of rows by chaning it from a {0,1}submatrix
to an almost complementary {0,-1} submatrix. I thank George
Bergman for bringing this to my attention.
Now with this operation in hand, I note that for any matrix and any column of that matrix chosen, the operation affects the number of ones in a row by either preserving it (if the row has a 0 in that column), or by changing the number of ones from r to s where r+s=n+1, and where n is the number of columns of the matrix.
It should now be clear that any matrix with properties (a) and (b) of the Lemma should have these properties preserved when XORed by one of its columns. For property (c), consider any column C of the matrix such that there is a row with s ones or a row with r ones which has a 1 in that column. XORing by that column will change, say, C_s rows having s ones to rows with r ones, and C_r rows with r ones to s ones. If C_s>C_r, then we can reduce the number of rows with s ones in them, and then consider the transformed matrix. So assume for all columns C that C_r>=C_s. Then the sum of C_s as C ranges over all the columns is s*m_s, and the sum of C_r as C ranges over all the columns is r*m_r, and one has s*m_s<=r*m_r.
That m_r + m_s is <= n is trivial. Thus Lemma D is established.
A significant application of the technique of XORing is to find equivalent matrices with smaller numbers of ones. The technique is used in Lemma E to expand the range of symmetries and reduce the number of cases investigated.
For the proof of Lemma E, please go to LemmaE.html.
Now the proof of the theorem goes as follows: Use the first two Lemmas to help establish the consecutive part of the spectrum. Use Lemmas D and E to establish that any 7x7 0-1 matrices with determinant > 18 (=2*9) must have all rows (and all columns) with 3,4, or 5 ones.
Use Lemma D again to establish that it suffices to look at those matrices with at most two rows with 5 ones. Then utilize the combinatorics of the situation to find that it suffices to consider only matrices with rows with three or four ones, and observe the duality present in the situation.
For example, consider all possible combinations of rows with four ones which do not reduce to a case of one row with two or fewer ones. This means that if there are three such rows, they can be arranged up to symmetry in only one of two ways:
1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 1 1 1 1 0Further, if a fourth row is added to either configuration, one see that the matrix is permuation equivalent to one in which the first three rows may be arranged as in the first of the two ways shown above.
Similarly, the case of investigating possible combinations of rows with three ones which are also not reducible to a case with a row of two ones leads to examining the complementary matrices above. In particular, I note that at most three rows of three ones in such a configuration will have a column in common in which each row has a 1 in this column.
With this observation, I now state:
Proposition: Any 7x7 matrix with two or fewer rows containing five ones is equivalent to one with no rows of five ones.
To prove this, consider the case that the matrix has at least one row of five ones. Such a row must have a dot product of two with every row of three ones. Suppose there are at least two such rows of five ones. Note that every row of three ones must have a one in a column which does not have a 1 possessed by either of the two rows with five ones. Also, the two rows of five ones must have a dot product of three, otherwise the matrix reduces to a previously considered case. The picture is
1 0 1 0 0 0 1 0 0 1 1 1 1 1 1 1 1 1 1 0 0for an equivalent submatrix containing the three rows mentioned.
Considering the middle three columns above, they can possess at most five ones belonging to rows which have three ones ( since each row of three ones contributes at most one 1 to these columns), thus there is some column of these three which has at most one 1. Doing the XOR operation of Lemma D with this column gives us a matrix with at least one fewer row of five ones.
If there is exactly one row of five ones, then by the observation above, there are at most four rows of three ones allowed which have dot product of two with this row. (Otherwise we can reduce to a case involving a row of two ones.) The allowable configuration up to symmetry is
1 0 1 1 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 1 0 1 0 0 0 1 1 1 1 1.Notice that in this instance, as well as in other instances with fewer rows of three ones, any non-reducible configuration leaves a column available which has a 1 contributed by the row of five ones, and no ones contributed by any rows of three ones. Thus doing an XOR on this column allows us to remove the row of five ones. This settles the proposition.
Now we can assume there are only rows with three ones and with four ones. Note that the dot product of any pair of the rows of four ones must be two, of any pair of the rows of three ones must be 1, and of any row of four ones and any row of three ones must be 1 or 2. Suppose there are four rows of four ones. Then, as above, the allowable configurations up to symmetry are few in number.
1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 1 1 0 0 1 1 1 1 0Note that the configurations have many symmetries. In the first configuration, I can find a transformation which takes any of the last 6 columns to any other, and then I can permute the rows to restore the configuration. In the second configuration I can similarly interchange any two of the columns of three rows or any two of the columns of three ones, and restore the original configuration by a row permutation. This symmetry allows me to consider a smaller number of cases.
Now consider the first configuration above, and assume that the matrix has also three rows of three ones, and that there is a column in which these three rows each have a one in that column. I can assume that this is column number 2, by symmetry and by avoiding a dispensible transpose. I can also use the observation above to note that each remaining column has exactly one 1 from any of the three rows. I can then use symmetry to assume placement of a ones, and then find that the positions of the remaining ones in that row are determined by the restriction that no dispensible configuration results. Then the transpose is seen to have determinant less than 19. The transition is below:
1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 * 1 * * * * * 1 1 * * * * * 1 1 0 0 0 0 1 * 1 * * * * * * 1 * * * * * 0 1 * * * * 0 * 1 * * * * * * 1 * * * * * 0 1 * * * * 0
Now suppose the three rows of three do not share such a column. of ones. Then they share a column of 0's, and that must be in the first column (otherwise the result gives a column with two ones in it.) By symmetry, we can assume that the second column has four ones in it. Then the last column has at most one three ones in it (otherwise the transpose has two rows of four with dot product 1, or the amtrix has two rows of thhree with dot product two. By symmetry, we can assume the matrix is as below
1 1 1 1 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1 0 1 * * * * 1 0 1 * * * * 0 0 0 * * * * 0
Note that the symmetries present in this matrix allow us to interchange the columns 3 through 6. Then I can assume that column 3 has two ones as shown below. This determines the last two rows (as now the third one in the sixth row can go in only one place, thus limiting determining the seventh row) and the picture becomes (with a = 0 or 1, and a+b=1)
1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 0 0 1 0 1 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 0 0 1 1 0 1 0 * * * 1 0 1 0 a b 0 1 0 2 0 1 b 0 1 0 1 1 * * * 0 0 1 1 0 0 1 0 0 1 2 0 0 1 0 0 0 1 * * * 0 0 0 1 1 1 0 0 0 0 1 2 1 0 0By doing appropriate column operations (involving subtracting column 1 from columns 2,3, and 4), we find that the matrix has determinant equivalent to 18.
Now we assume again that the matrix has four rows with four ones, and three rows with three ones, but this time the four rows are as in the second configuration. If the three rows of three ones each share a column, it must be the last column if the determinant must be greater than 18. We can use symmetry considerations to assume the appearance of column 5, and then of columns 4 and 3. This then limits the appearance (up to symmetry) of the rest of the matrix. The sequence of matrices is :
1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 * * * * 1 * 1 0 0 0 1 1 0 1 0 0 0 1 1 0 1 * * * * 0 * 1 * * 1 0 0 * 1 0 1 1 0 0 0 1 * * * * 0 * 1 * * 0 0 0 * 1 1 0 0 0 0 1 1This last matrix has a determinant of 18.
Now we turn to the case that the three rows of three ones share a column of zeroes. Avoiding a reducible case and symmetry allow me to assume that this column is first, and the last column has two ones shared by two of the last three rows. Then consideration of that row in the last three with two zeros indicates it must have two ones in the second column, else a reducible case occurs. The picture is:
1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 * * * * * 0 0 1 * * * * 0 0 * * * * * 1 0 1 * * * * 1 0 * * * * * 1 0 0 * * * * 1Now as I can use symmetry to swap columns 3 and 5 and 4 and 6, the remaining cases concern the placement of two more ones in either column 3 or 4. In this case, column 5 will have four ones in it, and must have dot product of two with column 2. This determines column 6, which then determines column 5. When that is done, the remaining possibilities are quickly narrowed. Given that a is 0 or 1, and that a+b=1, these cases are
1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 * * * 0 0 0 1 * * 1 0 0 0 1 b a 1 0 0 0 1 * * * 0 1 0 1 * * 0 0 1 0 1 a b 0 0 1 0 0 * * 0 1 1 0 0 * * 0 1 1 0 0 b a 0 1 1both of which have det 18. This takes care of all cases in which the matrix has exactly four rows of four ones.
If the matrix has five rows of four ones, then up to symmetry, the matrix looks like
1 1 1 1 0 0 0 1 1 0 0 1 1 0 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 1 1By adding rows 3 and 2 to 1, and by adding rows 3 and 4 to 5, one gets two rows with entries of 0 and 2, and thus establishes that the determinant of the matrix is a multiple of 4. Since there are rows with three ones in them, this limits the determinant to a number less than 28, so the allowable determinants are equivalent to 24, 20, or some smaller multiple of 4. This part of the analysis is not yet done.