マトロイドのコンピュータ上での表現

$M=(E,{\cal B})$を、基によって定義された マトロイドとする。

$|E|=m,\,\rank M=r$とする。 このとき$E=\{0,1,\ldots,m-1\}$としても一般性を失わない。

マトロイドに関する操作をコンピュータプログラムとして実現するためには、 部分集合に対する集合算を効率良く実行しなければならない。 一方で多くのプログラミング言語では$\{0,1\}$の列(ビット列)の論理演算が 予め用意されており、しかも高速に実行されることが期待される。

そこで $E$の部分集合を、以下のようにビット列として表現することにする。

$E$の部分集合$A$に対して、$\{\chi_A(i)\}_{0\le i < m}$を

\[
  \chi_A(i)=\left\{
    \begin{array}{ll}
      0 & (i \not\in A) \\ 
      1 & (i \in A)
    \end{array}
  \right.
\]

$n=|{\cal B}|$とし、${\cal B}=\{B_0,B_1,\ldots,B_{n-1}\}$であるとする。 $M$に対して第$p$行($0\le p < n$)が$\chi_{B_p}$であるような $n\times m$行列${\cal M}$が定まる。

命題

${\cal M}$は以下の条件をみたす。

1. 各行の成分の和は$r$。
2. 第$p,\,q$行をそれぞれ${\cal M}_p,\,{\cal M}_q$とし、 ${\cal M}_p$の第$j$成分が$1$であり、 それを$0$におきかえたビット列を${\cal M'}_p$とすると

   \[ {\cal M}_r\land ({\cal M'}_p\lor {\cal M}_q)={\cal M}_r \]
   

   をみたす行${\cal M}_r$が存在する。 ただし$\land$、$\lor$ はそれぞれビット列の論理積、論理和を表わす。

逆にこの条件をみたす行列から元のマトロイドを再構成することは容易である。 結局元数$m$の集合上の階数$r$のマトロイドは上の2条件をみたす$m$列の行列で表わされ、 さらに同型なマトロイドに対応する行列は、 行の置換および列の置換を施すことによって得られることがわかる。