マトロイド表現

マトロイドの数学的理論では、マトロイド表現は、与えられたマトロイドと同じ線形独立関係を持つベクトルの族です。マトロイド表現はグループ表現に類似しており、どちらのタイプの表現も、線形代数の観点から具体的な記述を伴う抽象的な代数構造 (それぞれマトロイドとグループ) を提供します。

線形マトロイドは表現を持つマトロイドであり、F線形マトロイド(体 Fの場合) はF上のベクトル空間を使用して表現を持つマトロイドです。マトロイド表現理論は、表現の存在と線形マトロイドの特性を研究します。

（有限）マトロイドは、 有限集合（マトロイドの要素）と、マトロイドの独立集合と呼ばれるの部分集合の空でない族によって定義されます。独立集合のすべての部分集合はそれ自体が独立であるという特性と、1 つの独立集合が2 番目の独立集合より大きい場合、に追加してより大きな独立集合を形成できる要素が存在するという特性を満たす必要があります。マトロイドの定式化における重要な動機付けの例の 1 つは、ベクトル空間におけるベクトルの線形独立性の概念でした。 が有限集合またはベクトルの多重集合であり、 がの線形独立部分集合の族である場合、 はマトロイドです。^{[1] [2]}${\displaystyle (E,{\mathcal {I}})}$ ${\displaystyle E}$ ${\displaystyle {\mathcal {I}}}$${\displaystyle E}$${\displaystyle A}$${\displaystyle B}$${\displaystyle x\in A\setminus B}$${\displaystyle B}$${\displaystyle E}$${\displaystyle {\mathcal {I}}}$${\displaystyle E}$${\displaystyle (E,{\mathcal {I}})}$

より一般的には、 が任意のマトロイドである場合、 の表現はベクトル空間 にマップする関数として定義でき、のサブセットが独立であるためには が単射であり線型独立である場合に限ります。 表現を持つマトロイドは線型マトロイドと呼ばれ、 が体F上のベクトル空間である場合、マトロイドはF線型マトロイドと呼ばれます。 したがって、線型マトロイドは、ベクトルの集合または多重集合から定義されるマトロイドと同型のマトロイドです。 関数が1 対 1となるのは、基礎となるマトロイドが単純である（2 つの要素の従属集合を持たない）場合のみです。 マトロイド表現は、体F上の行列を使用してより具体的に記述することもできます。この場合、マトロイド要素ごとに 1 つの列があり、マトロイド内の要素の集合が独立しているのは、対応する行列の列の集合が線型独立である場合に限ります。線形マトロイドのランク関数は、この行列の部分行列の行列ランク、またはベクトルの部分集合の線形スパンの次元によって与えられます。^[3]${\displaystyle (E,{\mathcal {I}})}$${\displaystyle (E,{\mathcal {I}})}$${\displaystyle f}$${\displaystyle E}$${\displaystyle V}$${\displaystyle A}$${\displaystyle E}$${\displaystyle f|_{A}}$${\displaystyle f(A)}$${\displaystyle V}$${\displaystyle f}$

すべてのマトロイドが線形というわけではありません。8要素のヴァモスマトロイドは、すべての体で表現できない最小のマトロイドの1つです。 ^{[4]マトロイドが線形の場合、一部の体では表現できますが、すべての体では表現できません。たとえば、} Perles構成で定義される9要素のランク3マトロイドは、実数では表現できますが、有理数では表現できません。

バイナリマトロイドは、有限体 GF(2)上で表現できるマトロイドです。つまり、一様マトロイドを マイナーとして持たないマトロイドです。^[5]ユニモジュラマトロイドまたは正則マトロイドは、すべての体上で表現できるマトロイドです。^[6]これらは、マイナーとして、ファノ平面（7つの要素を持つバイナリマトロイド）、またはファノ平面の双対マトロイドのいずれも持たないマトロイドとして特徴付けることができます。 ^{[5] [7]あるいは、マトロイドが正則であるためには、}完全にユニモジュラな行列 で表現できる必要があります。^[8]${\displaystyle U{}_{4}^{2}}$${\displaystyle U{}_{4}^{2}}$

ロータの予想は、任意の有限体Fに対して、F線型マトロイドは、上記の二元マトロイドおよび正則マトロイドの特徴付けと同様に、禁制小数の有限集合によって特徴付けられるというものである。^[9] 2012年現在、この予想は4つ以下の要素を持つ体に対してのみ証明されている。^{[5] [10] [11] [12]無限体（}実数体など）に対しては、このような特徴付けは不可能である。^[13]

あらゆる代数体とあらゆる有限体 Fに対して、 Fがその代数閉包の最小部分体となりMを表現できるようなマトロイドMが存在する。Mは階数3であるとすることができる。^[14]

線形マトロイドの特性集合は、それが線形である体の特性集合として定義される。 ^[15] すべての素数 pに対して、特性集合が単集合{ p }であるマトロイドが無限に存在する。^{[16]すべての素数の}有限集合に対して、特性集合が与えられた有限集合であるマトロイドが存在する。^[17]

マトロイドの特性集合が無限である場合、それはゼロを含みます。そして、それがゼロを含む場合、それは有限個以外のすべての素数を含みます。^[18] したがって、唯一の可能な特性集合は、ゼロを含まない有限集合と、ゼロを含むコ有限集合です。^[19] 確かに、そのような集合はすべて存在します。^[20]

一様マトロイドは 個の要素を持ち、その独立集合は 個の要素の最大 個の部分集合から構成される。一様マトロイドは、 次元ベクトル空間における一般的な位置にあるベクトルの集合によって表される。表現体は、このベクトル空間における一般的な位置にあるベクトルが存在するのに十分な大きさでなければならないため、一様マトロイドは有限個の体F を除くすべての体に対してF線形である。^[21]一様マトロイドの直和である分割マトロイドについても同じことが言え、任意の 2 つのF線形マトロイドの直和はそれ自体がF線形である。 ${\displaystyle U{}_{n}^{r}}$${\displaystyle n}$${\displaystyle r}$${\displaystyle r}$${\displaystyle n}$

グラフィックマトロイドは、無向グラフの辺から、サイクルを含まない場合にのみ辺の集合が独立であると定義することによって定義されるマトロイドである。すべてのグラフィックマトロイドは正則であり、したがってすべての体Fに対してF線形である。^[8]

剛性マトロイドは、柔軟なヒンジによって両端が接続された剛性バーによって形成される機械的リンクの自由度を表します。このタイプのリンクは、各バーに辺、各ヒンジに頂点を持つグラフとして記述することができ、1次元リンクの場合、剛性マトロイドはまさにグラフィックマトロイドです。高次元の剛性マトロイドは、基礎となるグラフの接続行列に似た構造を持つ実数行列を使用して定義できるため、-線形です。^{[22] [23]}${\displaystyle \mathbb {R} }$

一様マトロイドや分割マトロイドと同様に、有向グラフの到達可能性を表すマトロイドであるガモイドは、十分に大きな体すべてにわたって線形である。より具体的には、要素を持つガモイドは、少なくとも要素を持つすべての体で表現できる。^[24]${\displaystyle n}$${\displaystyle 2^{n}}$

代数マトロイドは、代数的独立性の概念を用いて体の拡大の要素の集合から定義されるマトロイドである。すべての線形マトロイドは代数的であり、特性がゼロの体（実数など）では線形マトロイドと代数マトロイドは一致するが、他の体では線形ではない代数マトロイドが存在する可能性がある。^[25]