主題
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 猜想

使用 探索

參考文獻

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.

在 中被引用

(0,1)-矩陣

請將此頁引用為

Weisstein, Eric W. "(0,1)-矩陣。" 來自 Web 資源。 https://mathworld.tw/01-Matrix.html

主題分類