擬陣

擬陣是組合數學中的一個結構，是對向量空間中線性獨立這一概念的概括與歸納。擬陣有許多等價的定義，其中最主要的幾個定義分別是基於獨立集、基底、環路、閉集、平坦、閉包算子和秩函數。

擬陣理論從線性代數和圖論中借用了大量術語，主要是因為它是對這些領域中很多重要的核心概念的概括。擬陣理論在幾何、拓撲學、組合優化、網絡理論和編碼理論中都有應用。

定義

擬陣有很多等價的定義方式^[1]。

獨立集

就獨立集來說, 一個有限的擬陣 ${\displaystyle M}$ 是一個二元組 ${\displaystyle (E,{\mathcal {I}})}$, 其中 ${\displaystyle E}$ 是一個 有限集 (稱之為 基礎集) ，${\displaystyle {\mathcal {I}}}$ 是一個由${\displaystyle E}$的子集構成的 集族 (稱之為 獨立集) 它需要滿足下面的條件:^[2]

1. 空集 是獨立的, 也就是說, ${\displaystyle \emptyset \in {\mathcal {I}}}$. 換個說法就是, 至少有一個 ${\displaystyle E}$的子集是獨立的, 即：${\displaystyle {\mathcal {I}}\neq \emptyset }$.
2. 每個獨立集的子集是獨立的, 即： 對於每個子集 ${\displaystyle A'\subset A\subset E}$, 如果 ${\displaystyle A\in {\mathcal {I}}}$ 則 ${\displaystyle A'\in {\mathcal {I}}}$. 有時我們稱之為 遺傳特性.
3. 如果 ${\displaystyle A}$ 和 ${\displaystyle B}$ 是 ${\displaystyle {\mathcal {I}}}$ 的兩個獨立子集,${\displaystyle A}$ 比${\displaystyle B}$有更多的元素, 則在${\displaystyle A}$中存在一個元素，當其加入 ${\displaystyle B}$時得到一個比${\displaystyle B}$更大獨立子集. 有時我們稱之為 擴充特性 或者叫 獨立集交換特性.

頭兩個特性定義了一個公認的組合結構，叫做獨立系統。

基

對於有限擬陣 ${\displaystyle M}$，若其基礎集${\displaystyle E}$的子集${\displaystyle B}$是一個極大的獨立集（即添加任何一個新的元素得到的子集都不是獨立集），則將${\displaystyle B}$稱為一個基底（英文：basis）。擬陣的一種等價定義為二元組${\displaystyle (E,{\mathcal {B}})}$，其中${\displaystyle E}$ 是一個有限集，${\displaystyle {\mathcal {B}}}$ 是一個由基底構成的${\displaystyle E}$的子集族，稱為${\displaystyle M}$的基，滿足以下條件:^[1]

1. ${\displaystyle {\mathcal {B}}\neq \emptyset }$;（即至少存在一個基底）
2. 對於${\displaystyle {\mathcal {B}}}$中不同的集合${\displaystyle A,B}$以及任一元素${\displaystyle a\in A-B}$，存在元素${\displaystyle b\in B-A}$使得${\displaystyle A\cup \{b\}-\{a\}\in {\mathcal {B}}}$。（該條件被稱為交換公理）

可以證明，一個有限擬陣的所有基底的元素個數都相同，這個數被稱為擬陣的秩。

環路

對於有限擬陣 ${\displaystyle M}$，若其基礎集${\displaystyle E}$的子集${\displaystyle C}$是一個極小的非獨立集（即去掉其中任一元素得到的子集都是獨立集），則將${\displaystyle C}$稱為一個環路（英文：circuit）。擬陣的一種等價定義為二元組${\displaystyle (E,{\mathcal {C}})}$，其中${\displaystyle E}$ 是一個有限集，${\displaystyle {\mathcal {C}}}$ 是一個由環路構成的${\displaystyle E}$的子集族，稱為${\displaystyle M}$的環路集，滿足以下條件:^[1]

1. ${\displaystyle \emptyset \notin {\mathcal {C}}}$；
2. 如果${\displaystyle C_{1},C_{2}\in {\mathcal {C}}}$且${\displaystyle C_{1}\subseteq C_{2}}$，則${\displaystyle C_{1}=C_{2}}$；
3. 對於${\displaystyle {\mathcal {C}}}$中不同的集合${\displaystyle C_{1},C_{2}}$以及元素${\displaystyle a\in C_{1}\cap C_{2}}$，存在${\displaystyle C_{3}\in {\mathcal {C}}}$使得${\displaystyle C_{3}\subseteq C_{1}\cup C_{2}-\{a\}}$。

可以證明，基礎集的一個子集是獨立集若且唯若它不包含任一環路作為子集。

秩函數

類似線性代數基底的性質，擬陣的基底具有類似的性質：${\displaystyle M}$的任意兩個基底具有相同的元素個數。這個數字被稱為擬陣${\displaystyle M}$的秩。

閉包