(0,1)-Matrix

A -matrix is an integer matrix in which each element is a 0 or 1. It is also called a logical matrix, binary matrix, relation matrix, or Boolean matrix. The number of binary matrices is , so the number of square binary matrices is which, for , 2, ..., gives 2, 16, 512, 65536, 33554432, ... (OEIS A002416).

The numbers of positive eigenvalued -matrices for , 2, ... are 1, 3, 25, 543, 29281, ... (OEIS A003024). Weisstein's conjecture proposed that these matrices were in one-to-one correspondence with labeled acyclic digraphs on nodes, and this was subsequently proved by McKay et al. (2003, 2004). Counts of both are therefore given by the beautiful recurrence equation

with (Harary and Palmer 1973, p. 19; Robinson 1973, pp. 239-273).

The numbers of binary matrices with no adjacent 1s (in either columns or rows) for , 2, ..., are given by 2, 7, 63, 1234, ... (OEIS A006506). For example, the binary matrices with no adjacent 1s are

These numbers are closely related to the hard square entropy constant. The numbers of binary matrices with no three adjacent 1s for , 2, ..., are given by 2, 16, 265, 16561, ... (OEIS A050974).

For an -matrix, the largest possible determinants (Hadamard's maximum determinant problem) for , 2, ... are 1, 1, 2, 3, 5, 9, 32, 56, 144, 320, 1458, 3645, 9477, ... (OEIS A003432). The numbers of distinct binary matrices having the largest possible determinant are 1, 3, 3, 60, 3600, 529200, 75600, 195955200, 13716864000, ... (OEIS A051752).

Wilf (1997) considers the complexity of transforming an binary matrix into a triangular matrix by permutations of the rows and columns of , and concludes that the problem falls in difficulty between a known easy case and a known hard case of the general NP-complete problem.