論理マトリックス

論理行列、二項行列、関係行列、ブール行列、または(0, 1)行列は、ブール領域 $B$ $= {0, 1}$ の要素を持つ行列です。このような行列は、有限集合のペア間の二項関係を表すために使用できます。これは、組合せ数学および理論計算機科学における重要なツールです。

関係の行列表現

R が有限インデックス集合XとYの間の2項関係（つまり $R$ $\subseteq$ $X$ $\times$ $Y$ ）である場合、 Rは、行と列のインデックスがそれぞれXとYの要素をインデックスする論理行列Mで表すことができ、 Mの要素は次のように定義されます。

m_{i,j}={\begin{cases}1&(x_{i},y_{j})\in R,\\0&(x_{i},y_{j})\not \in R.\end{cases}}

行列の行番号と列番号を指定するために、集合XとYは正の整数でインデックス付けされます。iは1からXの基数（サイズ）までの範囲、j は1からYの基数までの範囲です。詳細については、インデックス付き集合に関する記事を参照してください。

二項関係の論理行列の転置は逆関係に対応する。^[1] $R^{T}$ $R$

例

集合 ${1, 2, 3, 4}$ 上の二項関係Rは、 aがbを割り切れる場合、かつその場合に限りaRbが成立するように定義されます。例えば、2は4を割り切れるため2 R 4は成立しますが、3は4を割り切れるため3 R 4は成立しません。なぜなら、3は4を割り切れるため1が余るからです。次の集合は、関係Rが成立するペアの集合です。

{(1, 1)、(1, 2)、(1, 3)、(1, 4)、(2, 2)、(2, 4)、(3, 3)、(4, 4)}。

対応する論理行列の表現は

{\begin{pmatrix}1&1&1&1\\0&1&0&1\\0&0&1&0\\0&0&0&1\end{pmatrix}},

各数はそれ自身を割り切るので、対角線上に 1 が含まれます。

その他の例

順列行列は (0, 1) 行列であり、そのすべての列と行にはそれぞれ 1 つの非ゼロ要素が含まれます。
- コスタス配列は順列行列の特殊なケースです。
組合せ論と有限幾何学における接続行列には、幾何学の点 (または頂点) と線、ブロック設計のブロック、またはグラフのエッジの間の接続を示すものがあります。
分散分析における設計行列は、行の合計が一定である (0, 1) 行列です。
論理行列はグラフ理論における隣接行列を表すことができます。非対称行列は有向グラフに対応し、対称行列は通常のグラフに対応し、対角線上の 1 は対応する頂点のループに対応します。
単純な無向二部グラフの隣接行列は(0, 1) 行列であり、任意の (0, 1) 行列はこのようにして生じます。
m 個の平方自由でn 個の滑らかな数からなるリストの素因数は、 m × π ( n ) (0, 1) 行列として記述できます。ここで、π は素数計算関数であり、a _ijはj番目の素数がi番目の数を割り切る場合にのみ 1 となります。この表現は、二次ふるい分解アルゴリズムで有用です。
2 色のみのピクセルを含むビットマップイメージは、ゼロが 1 色のピクセルを表し、1 が他の色のピクセルを表す (0, 1) 行列として表すことができます。
バイナリマトリックスは囲碁のゲームルールを確認するために使用することができます。^[2]
2 ビットの 4 値ロジックは、2 × 2 論理マトリックスによって変換され、遷移システムを形成します。
再帰プロットとその変種は、位相空間内でどの点のペアが特定の近傍閾値よりも近いかを示す行列です。

いくつかのプロパティ

有限集合上の等式関係の行列表現は単位行列 $I$ 、つまり対角要素がすべて 1 で、その他がすべて 0 である行列です。より一般的には、関係 $Rが$ $I \subseteq R を$ 満たす場合 $、$ $R$ は反射関係です。

ブール領域を半環とみなし、加算が論理和、乗算が論理積に対応するとすると、2つの関係の合成を表す行列表現は、これらの関係の行列表現の行列積に等しくなります。この積は、期待時間O( n ² )で計算できます。 ^[3]

二元行列の演算は、しばしばモジュラー演算mod 2で定義されます。つまり、要素はガロア体の要素として扱われます。これらは様々な表現で現れ、より限定された特殊形式もいくつか存在します。これらは、例えば XOR 充足可能性などに適用されます。 ${\mathbf {GF}}(2)=\mathbb {Z} _{2}$

異なるm行n列のバイナリ行列の数は2 ^mnに等しく、したがって有限です。

格子

nとmが与えられ、Uがすべての論理m×n行列の集合を表すとする。このとき、Uは次式で表される半順序を持つ。

\forall A,B\in U,\quad A\leq B\quad {\text{when}}\quad \forall i,j\quad A_{ij}=1\implies B_{ij}=1.

実際、U は、2 つの行列間のand とorの演算を要素ごとに適用したブール代数を形成します。論理行列の補行列は、すべての 0 と 1 をその反対の要素と交換することで得られます。

すべての論理行列 $A = (A ij)$ には転置行列 $A T = (A ji) が存在する。A$ が、どの列もどの行もゼロでない論理行列であるとする。この場合、ブール演算を用いた行列積はm × m の単位行列を含み、積はn × n の単位行列を含む。 $A^{\operatorname {T} }A$ $AA^{\operatorname {T} }$

数学的構造として、ブール代数Uは包含によって順序付けられた格子を形成します。さらに、行列の乗算により乗法格子になります。

U内の各論理行列は二項関係に対応する。U に対するこれらの演算と順序付けは関係の計算に対応し、行列の乗算は関係の合成を表す。[ 4 ^]

論理ベクトル

グループのような構造
	合計	連想	身元	分割可能	可換性
部分的なマグマ	不要	不要	不要	不要	不要
半群体	不要	必須	不要	不要	不要
小規模カテゴリ	不要	必須	必須	不要	不要
群体	不要	必須	必須	必須	不要
マグマ	必須	不要	不要	不要	不要
準群	必須	不要	不要	必須	不要
ユニタルマグマ	必須	不要	必須	不要	不要
ループ	必須	不要	必須	必須	不要
セミグループ	必須	必須	不要	不要	不要
モノイド	必須	必須	必須	不要	不要
グループ	必須	必須	必須	必須	不要
アーベル群	必須	必須	必須	必須	必須

mまたはnが1 の場合、 m × n論理行列 ( m _ij ) は論理ベクトルまたはビット文字列です。m = 1の場合、ベクトルは行ベクトル、n = 1 の場合、ベクトルは列ベクトルです。いずれの場合も、ベクトルの表記から添え字の 1 は省略されます。

とが2つの論理ベクトルであるとする。PとQの外積はm × nの直交関係となる。 $(P_{i}),\,i=1,2,\ldots ,m$ $(Q_{j}),\,j=1,2,\ldots ,n$

m_{ij}=P_{i}\land Q_{j}.

このような行列の行と列を並べ替えると、すべての1を行列の長方形の部分にまとめることができます。^[5]

hをすべて 1 のベクトルとする。v を任意の論理ベクトルとすると、関係R = vh T^はvによって定まる定数行を持つ。関係の計算において、このようなRはベクトルと呼ばれる。^[5]特別な例として、普遍関係がある。 $hh^{\operatorname {T} }$

与えられた関係Rに対して、 Rに含まれる最大の直交関係はRにおける概念と呼ばれる。関係は概念に分解し、誘導された概念束に注目することで研究することができる。

群のような構造の表を考えてみましょう。ここで、「不要」は0、「必要」は1で表され、論理行列を形成します。の要素を計算するには、この行列の行にある論理ベクトルのペアの論理内積を使用する必要があります。この内積が0の場合、行は直交します。実際、小カテゴリは準群に直交し、群はマグマに直交します。したがって、にはゼロが存在し、普遍的な関係にはなり得ません。 $R.$ $RR^{\operatorname {T} }$ $RR^{\operatorname {T} }$

行と列の合計

論理行列内のすべての1を合計する方法は2つあります。まず行を合計する方法と、まず列を合計する方法です。行の合計を合計すると、列の合計を合計した場合と同じになります。接続幾何学では、この行列は接続行列として解釈され、行は「点」、列は「ブロック」（点からなる線を一般化したもの）に対応します。行の合計は点次数と呼ばれ、列の合計はブロック次数と呼ばれます。点次数の合計はブロック次数の合計に等しくなります。^[6]

この分野における初期の問題は、「与えられた点次数とブロック次数を持つ接続構造が存在するための必要かつ十分な条件を見つけること、あるいは行列言語で言えば、与えられた行と列の和を持つv × b型の(0, 1)行列が存在するための必要かつ十分な条件を見つけること」であった。^{[6]この問題は}ゲール・ライザーの定理によって解決される。

参照

注記

^ アーヴィング・M・コピロウィッシュ（1948年12月）「関係計算の行列展開」、記号論理ジャーナル13（4）：193–203 Jstorリンク
^ Petersen、Kjeld (2013 年 2 月 8 日)。「ビンマトリックス」。2017 年8 月 11 日に取得。
^ O'Neil, Patrick E.; O'Neil, Elizabeth J. (1973). 「ブール行列乗算と推移閉包のための高速期待時間アルゴリズム」.情報制御. 22 (2): 132–8 . doi :10.1016/s0019-9958(73)90228-3.— このアルゴリズムは加算がべき等であることを前提としています。134 ページ (下部) を参照してください。
^ コピロウィッシュ、アーヴィング（1948年12月）「関係計算の行列展開」『記号論理学ジャーナル』13 (4): 193–203 . doi :10.2307/2267134. JSTOR 2267134.
^ ab Schmidt, Gunther (2013). 「6: 関係とベクトル」.関係数学. ケンブリッジ大学出版局. p. 91. doi :10.1017/CBO9780511778810. ISBN 978-0-511-77881-0。
^ ab 例えば、Beth, Thomas、Jungnickel, Dieter、Lenz, Hanfried (1999). 「I. 例と基本定義」.デザイン理論.数学とその応用百科事典. 第69巻（第2版）. Cambridge University Press . p. 18. doi :10.1017/CBO9780511549533.001. ISBNを参照 978-0-521-44432-3。

参考文献

Brualdi, Richard A. (2006). 「組合せ行列クラス」.数学とその応用百科事典. 第108巻. ケンブリッジ大学出版局. doi :10.1017/CBO9780511721182. ISBN 978-0-521-86565-4。
Brualdi, Richard A.; Ryser, Herbert J. (1991). 「組合せ行列理論」.数学とその応用百科事典. 第39巻. Cambridge University Press. doi :10.1017/CBO9781107325708. ISBN 0-521-32265-0。
Botha, JD (2013)、「31. 有限体上の行列 §31.3 二元行列」、Hogben, Leslie (編) 『線形代数ハンドブック（離散数学とその応用）』（第2版）、Chapman & Hall/CRC、doi :10.1201/b16113、ISBN 978-0-429-18553-3
キム・キハン（1982）『ブール行列理論とその応用』デッカー、ISBN 978-0-8247-1788-9
ライザー, HJ (1957). 「0と1からなる行列の組合せ的性質」. Canadian Journal of Mathematics . 9 : 371–7 . doi :10.4153/CJM-1957-044-3.
ライザー, HJ (1960). 「0と1の行列のトレース」.カナダ数学ジャーナル. 12 : 463–476 . doi :10.4153/CJM-1960-040-0.
Ryser, HJ (1960). 「0と1の行列」(PDF) .アメリカ数学会報. 66 (6): 442– 464. doi :10.1090/S0002-9904-1960-10494-6.
フルカーソン, DR (1960). 「零点トレースを持つ零一行列」(PDF) .パシフィック・ジャーナル・オブ・マスマティクス. 10 (3): 831–6 . doi :10.2140/pjm.1960.10.831.
フルカーソン, DR; ライザー, HJ (1961). 「(0, 1)-行列の幅と高さ」.カナダ数学ジャーナル. 13 : 239–255 . doi :10.4153/CJM-1961-020-3.
フォード・ジュニア、LR、フルカーソン、DR (2016) [1962]. 「II. 実現可能性定理と組合せ論的応用 §2.12 0と1からなる行列」.ネットワークにおけるフロー.プリンストン大学出版局. pp. 79– 91. doi :10.1515/9781400875184-004. ISBN 9781400875184. MR 0159700。

外部リンク

「論理行列」、数学百科事典、EMSプレス、2001 [1994]

[1] アーヴィング・M・コピロウィッシュ（1948年12月）「関係計算の行列展開」、記号論理ジャーナル13（4）：193–203 Jstorリンク

[2] Petersen、Kjeld (2013 年 2 月 8 日)。「ビンマトリックス」。2017 年8 月 11 日に取得。

[3] O'Neil, Patrick E.; O'Neil, Elizabeth J. (1973). 「ブール行列乗算と推移閉包のための高速期待時間アルゴリズム」.情報制御. 22 (2): 132–8 . doi :10.1016/s0019-9958(73)90228-3.— このアルゴリズムは加算がべき等であることを前提としています。134 ページ (下部) を参照してください。

[4] コピロウィッシュ、アーヴィング（1948年12月）「関係計算の行列展開」『記号論理学ジャーナル』13 (4): 193–203 . doi :10.2307/2267134. JSTOR 2267134.

[GS-5] Schmidt, Gunther (2013). 「6: 関係とベクトル」.関係数学. ケンブリッジ大学出版局. p. 91. doi :10.1017/CBO9780511778810. ISBN 978-0-511-77881-0。

[BJL-6] 例えば、Beth, Thomas、Jungnickel, Dieter、Lenz, Hanfried (1999). 「I. 例と基本定義」.デザイン理論.数学とその応用百科事典. 第69巻（第2版）. Cambridge University Press . p. 18. doi :10.1017/CBO9780511549533.001. ISBNを参照 978-0-521-44432-3。

v t e 行列クラス
明示的に制約されたエントリ	交代反対角線反エルミート反対称矢じりバンド双対角線左右対称ブロック対角線ブロックブロック三角対角線ブール値コーシー中心対称会議複素アダマール共陽性対角線優位対角線離散フーリエ変換小学校同等フロベニウス一般化順列アダマールハンケルエルミートヘッセンベルク中空整数論理的マトリックスユニットメッツラームーア非負五角形順列非対称多項式四元数サイン歪エルミート歪対称スカイラインまばらシルベスター対称的トゥープリッツ三角三角線ヴァンダーモンドウォルシュ Z
絶え間ない	交換ヒルベルト身元レーマー 1つのうちパスカルパウリレッドヘファーシフトゼロ
固有値または固有ベクトルの条件	仲間収束欠陥品明確対角化可能ハーウィッツ安定正定値スティルチェス
積または逆行列の条件を満たす	合同な冪等性または射影反転可能内向的な零位普通直交ユニモジュラー単能性ユニタリー完全にユニモジュラー計量
特定のアプリケーション	アジュゲート交互記号拡張ベズージャボチンスキーカルタン巡回員補因子減刑混乱コクセター距離重複と削除ユークリッド距離基礎方程式（線形微分方程式）ジェネレータグラムヘッセン世帯主ヤコビアン一瞬精算選ぶランダム回転ラウス・ハーウィッツザイフェルト剪断類似性シンプレクティック完全にポジティブ変換
統計で使用される	センタリング相関共分散デザイン二重確率論フィッシャー情報帽子精度確率論的遷移
グラフ理論で使用される	隣接性隣接性程度エドモンズ入射ラプラシアンザイデル隣接性トゥッテ
科学技術で使用される	カビボ・小林・益川密度基礎（コンピュータービジョン）あいまい連想ガンマゲルマンハミルトニアン不規則な重複 S 状態遷移代替 Z（化学）
関連用語	ジョルダン正規形線形独立性行列指数円錐曲線の行列表現完璧なマトリックス擬似逆行列列階段形式ヴロンスキアン
数学ポータル行列のリストカテゴリ:行列（数学）