◐ Shell
clean mode source ↗

(0,1)-Matrix

Weisstein, Eric W.

A (0,1)-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 m×n binary matrices is 2^(mn), so the number of square n×n binary matrices is 2^(n^2) which, for n=1, 2, ..., gives 2, 16, 512, 65536, 33554432, ... (OEIS A002416).

The numbers of positive eigenvalued n×n (0,1)-matrices for n=1, 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 n nodes, and this was subsequently proved by McKay et al. (2003, 2004). Counts of both are therefore given by the beautiful recurrence equation

a_n=sum_(k=1)^n(-1)^(k-1)(n; k)2^(k(n-k))a_(n-k)

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

The numbers of n×n binary matrices with no adjacent 1s (in either columns or rows) for n=1, 2, ..., are given by 2, 7, 63, 1234, ... (OEIS A006506). For example, the 2×2 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].

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

For an n×n (0,1)-matrix, the largest possible determinants (Hadamard's maximum determinant problem) for n=1, 2, ... are 1, 1, 2, 3, 5, 9, 32, 56, 144, 320, 1458, 3645, 9477, ... (OEIS A003432). The numbers of distinct n×n 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 m×n binary matrix A into a triangular matrix by permutations of the rows and columns of A, and concludes that the problem falls in difficulty between a known easy case and a known hard case of the general NP-complete problem.

See also

Adjacency Matrix, Frobenius-König Theorem, Gale-Ryser Theorem, Hadamard's Maximum Determinant Problem, Hard Square Entropy Constant, Identity Matrix, Incidence Matrix, Integer Matrix, Lam's Problem, Permutation Matrix, Positive Eigenvalued Matrix, Redheffer Matrix, s-Cluster, s-Run, Weisstein's Conjecture

Explore with Wolfram|Alpha

References

Brualdi, R. A. and Shen, J. "Discrepancy of Matrices of Zeros and Ones." Elec. J. Combin. 6, No. 1, R15, 1-12, 1999. https://doi.org/10.37236/1447.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 (0,1)-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 (0,1)-Matrices." 28 Oct 2003. https://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 (0,1)-Matrices." J. Integer Sequences 7, Article 04.3.3, 1-5, 2004. https://cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html.Metropolis, N. and Stein, P. R. "On a Class of (0,1) 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.

Referenced on Wolfram|Alpha

(0,1)-Matrix

Cite this as:

Weisstein, Eric W. "(0,1)-Matrix." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/01-Matrix.html

Subject classifications