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).
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.
Brualdi, R. A. and Shen, J. "Discrepancy of Matrices of Zeros and Ones." Electronic J. Combinatorics6, No. 1,
R15, 1-12, 1999. http://www.combinatorics.org/Volume_6/Abstracts/v6i1r15.html.Ehrlich,
H. "Determinantenabschätzungen für binäre Matrizen." Math.
Z.83, 123-132, 1964.Ehrlich, H. and Zeller, K. "Binäre
Matrizen." Z. angew. Math. Mechanik42, T20-21, 1962.Harary,
F. and Palmer, E. M. Graphical
Enumeration. New York: Academic Press, 1973.Komlós, J.
"On the Determinant of -Matrices."
Studia Math. Hungarica2, 7-21 1967.McKay, B. D.;
Oggier, F. E.; Royle, G. F.; Sloane, N. J. A.; Wanless, I. M.;
and Wilf, H. "Acyclic Digraphs and Eigenvalues of -Matrices." 28 Oct 2003. http://arxiv.org/abs/math/0310423.McKay,
B. D.; Royle, G. F.; Wanless, I. M.; Oggier, F. E.; Sloane, N. J. A.;
and Wilf, H. "Acyclic Digraphs and Eigenvalues of -Matrices." J. Integer Sequences7,
Article 04.3.3, 1-5, 2004. http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html.Metropolis,
N. and Stein, P. R. "On a Class of Matrices with Vanishing Determinants." J. Combin
Th.3, 191-198, 1967.Robinson, R. W. "Counting
Labeled Acyclic Digraphs." In New
Directions in Graph Theory (Ed. F. Harary). New York: Academic Press,
1973.Ryser, H. J. "Combinatorial Properties of Matrices of
Zeros and Ones." Canad. J. Math.9, 371-377, 1957.Sloane,
N. J. A. Sequences A002416, A003024/M3113,
A003432/M0720, A006506/M1816,
A050974, and A051752
in "The On-Line Encyclopedia of Integer Sequences."Wilf, H.
"On Crossing Numbers, and Some Unsolved Problems." In Combinatorics,
Geometry, and Probability: A Tribute to Paul Erdős. Papers from the Conference
in Honor of Erdős' 80th Birthday Held at Trinity College, Cambridge, March 1993
(Ed. B. Bollobás and A. Thomason). Cambridge, England: Cambridge
University Press, pp. 557-562, 1997.Williamson, J. "Determinants
Whose Elements Are 0 and 1." Amer. Math. Monthly53, 427-434,
1946.