(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
![[0 0; 0 0],[0 0; 0 1],[0 0; 1 0],[0 1; 0 0],[0 1; 1 0],[1 0; 0 0],[1 0; 0 1].](/National_Library/im_/https://mathworld.wolfram.com/images/equations/01-Matrix/NumberedEquation2.gif) |
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. Combinatorics 6, 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. Mechanik 42, 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. Hungarica 2, 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 Sequences 7, 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. Monthly 53, 427-434, 1946.
Weisstein, Eric W. "(0,1)-Matrix." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/01-Matrix.html
Contact the MathWorld Team
arcsin 2
