擬陣

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

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

定義

擬陣有很多等價的定義方式。

獨立集

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

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

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

基

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

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

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

環路

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

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

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

秩函數

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