主题
Search

(0,1)-矩阵


一个 (0,1)-矩阵是一个整数矩阵,其中每个元素是 0 或 1。它也被称为逻辑矩阵、二元矩阵、关系矩阵或布尔矩阵。m×n 二元矩阵的数量是 2^(mn),因此 n×n 方阵二元矩阵的数量是 2^(n^2),当 n=1, 2, ... 时,得到 2, 16, 512, 65536, 33554432, ... (OEIS A002416)。

n×n n×n (0,1)-正特征值矩阵的数量,当 n=1, 2, ... 时,分别为 1, 3, 25, 543, 29281, ... (OEIS A003024)。Weisstein 猜想提出,这些矩阵与 n 个节点上的标记无环有向图存在一一对应关系,随后 McKay等人 (2003, 2004) 证明了这一点。因此,两者的计数都由优美的递推方程给出

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

其中 a_0=1 (Harary 和 Palmer 1973, p. 19; Robinson 1973, pp. 239-273)。

n×n n×n 二元矩阵(在列或行中都没有相邻的 1)的数量,当 n=1, 2, ... 时,分别为 2, 7, 63, 1234, ... (OEIS A006506)。例如,没有相邻 1 的 2×2 二元矩阵有

 [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].

这些数字与硬方格熵常数密切相关。n×n n×n 二元矩阵(没有三个相邻的 1)的数量,当 n=1, 2, ... 时,分别为 2, 16, 265, 16561, ... (OEIS A050974)。

对于一个 n×n n×n (0,1)-矩阵,当 n=1, 2, ... 时,可能的最大行列式(Hadamard 最大行列式问题)分别为 1, 1, 2, 3, 5, 9, 32, 56, 144, 320, 1458, 3645, 9477, ... (OEIS A003432)。具有最大可能行列式的不同 n×n n×n 二元矩阵的数量分别为 1, 3, 3, 60, 3600, 529200, 75600, 195955200, 13716864000, ... (OEIS A051752)。

Wilf (1997) 考虑了通过置换 m×n m×n 二元矩阵 A 的行和列将其转换为三角矩阵的复杂性,并得出结论,该问题的难度介于已知的简单情况和一般的 NP 完全问题的已知困难情况之间。


另请参阅

邻接矩阵, Frobenius-König 定理, Gale-Ryser 定理, Hadamard 最大行列式问题, 硬方格熵常数, 单位矩阵, 关联矩阵, 整数矩阵, Lam 问题, 置换矩阵, 正特征值矩阵, Redheffer 矩阵, s-簇, s-游程, Weisstein 猜想

使用 Wolfram|Alpha 探索

参考文献

Brualdi, R. A. 和 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. 和 Zeller, K. "二元矩阵 (Binäre Matrizen)." Z. angew. Math. Mechanik 42, T20-21, 1962.Harary, F. 和 Palmer, E. M. 图形计数 (Graphical Enumeration). New York: Academic Press, 1973.Komlós, J. "(0,1)-矩阵的行列式 (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.; 和 Wilf, H. "(0,1)-矩阵的无环有向图和特征值 (Acyclic Digraphs and Eigenvalues of (0,1)-Matrices)." 2003 年 10 月 28 日. http://arxiv.org/abs/math/0310423.McKay, B. D.; Royle, G. F.; Wanless, I. M.; Oggier, F. E.; Sloane, N. J. A.; 和 Wilf, H. "(0,1)-矩阵的无环有向图和特征值 (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. 和 Stein, P. R. "一类行列式为零的 (0,1) 矩阵 (On a Class of (0,1) Matrices with Vanishing Determinants)." J. Combin Th. 3, 191-198, 1967.Robinson, R. W. "标记无环有向图的计数 (Counting Labeled Acyclic Digraphs)." 收录于 图论新方向 (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. 序列 A002416, A003024/M3113, A003432/M0720, A006506/M1816, A050974, 和 A051752,出自 "整数序列在线大全 (The On-Line Encyclopedia of Integer Sequences)"。Wilf, H. "关于交叉数和一些未解决的问题 (On Crossing Numbers, and Some Unsolved Problems)." 收录于 组合学、几何学和概率论:致敬 Paul Erdős。1993 年 3 月在剑桥三一学院举行的纪念 Erdős 80 岁生日会议论文集 (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 和 A. Thomason)。Cambridge, England: Cambridge University Press, pp. 557-562, 1997。Williamson, J. "元素为 0 和 1 的行列式 (Determinants Whose Elements Are 0 and 1)." Amer. Math. Monthly 53, 427-434, 1946.

在 Wolfram|Alpha 中被引用

(0,1)-矩阵

请将此页引用为

Weisstein, Eric W. "(0,1)-矩阵。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/01-Matrix.html

主题分类