(0,1)-Matrix (original) (raw)

Algebra Applied Mathematics Calculus and Analysis Discrete Mathematics Foundations of Mathematics Geometry History and Terminology Number Theory Probability and Statistics Recreational Mathematics Topology

Alphabetical Index New in MathWorld

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 forn=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." 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 (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. 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 (0,1)-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 (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." FromMathWorld--A Wolfram Resource. https://mathworld.wolfram.com/01-Matrix.html

Subject classifications