論理行列

R が有限の添字付き集合 X と Y の間の二項関係である（すなわち R ⊆ X ×Y）とき、R は、その行添字と列添字がそれぞれ X と Y の要素を添字づける論理行列 M によって表されうる。ここで M の成分は次のように定義される。

${\displaystyle 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 の濃度までの範囲をとる。詳細は添字付き集合の項を参照。

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

• 置換行列は、その列と行の各々がちょうど一つの非零成分を持つ (0, 1)-行列である。
  • コスタス配列は置換行列の特殊な場合である。
• 組合せ論と有限幾何学における接続行列は、点（ないし頂点）と、幾何の直線、ブロックデザインのブロック、ないしグラフの辺との間の接続を示すために 1 を持つ。
• 分散分析における計画行列は、行和が一定の (0, 1)-行列である。
• 論理行列はグラフ理論における隣接行列を表しうる。すなわち、非対称行列は有向グラフに、対称行列は通常のグラフに対応し、対角上の 1 は対応する頂点におけるループに対応する。
• 単純な無向二部グラフの二部隣接行列は (0, 1)-行列であり、任意の (0, 1)-行列はこの仕方で生じる。
• m 個の平方因子をもたないn-なめらかな数のリストの素因数は、m × π(n) の (0, 1)-行列として記述されうる。ここで π は素数計数関数であり、a_ij は j 番目の素数が i 番目の数を割り切るとき、かつそのときに限り 1 である。この表現は二次ふるい法の因数分解アルゴリズムにおいて有用である。
• わずか二色のみのピクセルを含むビットマップ画像は、0 が一方の色のピクセルを、1 が他方の色のピクセルを表す (0, 1)-行列として表現されうる。
• 二進行列は、囲碁のゲームにおいてゲームのルールを確認するために用いられうる^[2]。
• 2 ビットの四値論理は、2 × 2 の論理行列によって変換され、遷移系をなす。
• 再帰プロットとその変種は、位相空間においてどの点の対が一定の近傍閾値より近いかを示す行列である。

有限集合上の相等関係の行列表現は単位行列 I、すなわち対角上の成分がすべて 1 で他がすべて 0 である行列である。より一般に、関係 R が I ⊆ R を満たすならば、R は反射関係である。

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

しばしば、二進行列に対する演算は 2 を法とするモジュラー算術の観点から定義される。すなわち、成分はガロア体 ${\displaystyle {\mathbf {GF}}(2)=\mathbb {Z} _{2}}$ の要素として扱われる。それらはさまざまな表現において生じ、いくつかのより制限された特殊形を持つ。例えばXOR充足可能性において応用される。

相異なる m × n 二進行列の数は 2^mn に等しく、それゆえ有限である。

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

${\displaystyle \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 は、二つの行列の間の論理積（and）と論理和（or）を成分ごとに適用する演算をもってブール代数をなす。論理行列の補は、すべての 0 と 1 をその反対と入れ替えることによって得られる。

すべての論理行列 A = (A_ij) は転置 A^T = (A_ji) を持つ。A が、恒等的に零である列も行も持たない論理行列であるとする。すると、ブール算術を用いた行列の積 ${\displaystyle A^{\operatorname {T} }A}$ は m × m の単位行列を含み、積 ${\displaystyle AA^{\operatorname {T} }}$ は n × n の単位行列を含む。

数学的構造として、ブール代数 U は包含によって順序づけられた束をなす。加えて、行列の乗法ゆえにそれは乗法的束である。

U のすべての論理行列は二項関係に対応する。U 上のこれらの列挙された演算と順序づけは、行列の乗法が関係の合成を表す関係計算に対応する^[4]。

m ないし n が 1 に等しいならば、m × n の論理行列 (m_ij) は論理ベクトルないしビット列である。m = 1 ならばベクトルは行ベクトルであり、n = 1 ならば列ベクトルである。いずれの場合も、1 に等しい添字はベクトルの表記から省かれる。

${\displaystyle (P_{i}),\,i=1,2,\ldots ,m}$ と ${\displaystyle (Q_{j}),\,j=1,2,\ldots ,n}$ を二つの論理ベクトルとする。P と Q の外積は m × n の矩形関係をもたらす。

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

そのような行列の行と列の並べ替えは、すべての 1 を行列の矩形部分へと集めることができる^[5]。

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

与えられた関係 R について、R に含まれる極大な矩形関係は R における概念（concept）と呼ばれる。関係は、概念へと分解し、次に誘導される概念束に着目することによって研究されうる。

群様構造の表を考える。ここで「不要」を 0、「必要」を 1 と表記し、論理行列 ${\displaystyle R}$ を形成する。${\displaystyle RR^{\operatorname {T} }}$ の要素を計算するには、この行列の行における論理ベクトルの対の論理内積を用いる必要がある。この内積が 0 であれば、行は直交する。実のところ、小さい圏は擬群に直交し、亜群はマグマに直交する。その結果、${\displaystyle RR^{\operatorname {T} }}$ には零があり、それは普遍関係であることに失敗する。

論理行列におけるすべての 1 を加え合わせることは、二つの方法で達成されうる。まず行を和すか、まず列を和すかである。行和を加えるとき、その和は列和を加えるときと同じである。接続幾何学においては、行列は、行が「点」に、列が「ブロック」（点からなる直線を一般化したもの）に対応する接続行列として解釈される。行和はその点次数と呼ばれ、列和はブロック次数である。点次数の和はブロック次数の和に等しい^[6]。

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

• 行列の一覧
• ビナトリックス（二進のデ・ブラウイントーラス）
• ビット配列
• 選言行列
• レドヘッファー行列
• 真理値表
• 三値論理