可表示擬陣

可表示擬陣(representable matroid)亦稱可坐標化擬陣，是一種組合構形，它是與有限域GF(q)上的矩陣擬陣M(A)有一一對應關係的擬陣M(E)，稱M(A)為擬陣M(E)的表示，矩陣A為擬陣的表示矩陣。

基本介紹

• 中文名：可表示擬陣
• 外文名：representable matroid
• 所屬學科：數學
• 別名：可坐標化擬陣
• 所屬問題：離散數學（組合序）
• 簡介：一種組合構形

基本介紹

定義1 設M是個擬陣，若存在某個域F，及域F上的一個矩陣A使得MM_F[A]，則稱M是個F-可線性表示擬陣(F-representable matroid)，或(在不強調F的時候)稱M為一個可線性表示擬陣(representable matroid)(也常簡稱為F-可表示擬陣或可表示擬陣)；而矩陣A則稱為M的一個F-線性表示(F-representation)(或簡稱為F-表示)，有時也稱A為M在F上的一個坐標化(F-coordinatization)。若存在某個圖G，使得MM(G)，則稱M為可圖擬陣(graphicmatroid)。

例如，在完全圖K₄上的圖擬陣M(K₄)在二元域GF(2)上是可表示的；但是，均勻擬陣U_2，4在二元域GF(2)上卻是不可表示的，儘管它在其他域上是可表示的(見圖1和表1)。可表示擬陣的對偶擬陣、子擬陣亦均為可表示的。這是可表示擬陣的優越性所在。

表1

圖1

特別地，把能夠在二元域GF(2)上表示的擬陣稱為二元擬陣。均勻擬陣U_2，3為二元擬陣。因為對於三元素集E={a，b，c}，其任意真子集都是U_2，3的獨立集，而E為相關集。相應的表示向量為α(a)=(1，0)，α(b)=(0，1)，α(c)=(1，1)。均勻擬陣U_2，4卻不是二元擬陣。二元擬陣包含了單模擬陣和圖擬陣等重要擬陣。在擬陣的表示理論中，二元擬陣是研究較早的一類。

相關介紹

定義2對於給定的兩個擬陣M₁(Z₁，)和M₂(Z₂，)，若映射：E₁→E₂滿足以下的條件：

(i)：E₁→E₂是一個一一對應，

(ii)對任意子集X∈若且唯若(X)∈，

則稱：E₁→E₂為從M₁到M₂的一個同構。若這樣的存在，稱M₁與M₂同構，記作M₁M₂。對每個擬陣M，易見全體從M到M的同構在映射的複合下構成一個群Aut(M)(稱為M的自同構群)。

作為例子，如下（1），（2），若且是(1)中的矩陣而G是(2)中的圖，則M[A](M(G)，其同構映射就是。

(1)考慮實數域R上的矩陣

令a_i(1≤i≤4)代表A的第i個列向量的標號i，又令為A的列向量的標號集合。要確定所有獨立集的集族，我們要找出所有的子集I⊆E₁，使得由I中元素所標號的向量組在V(3，R)中線性無關。從線性代數中我們知道，任何一個線性無關向量組都被一個極大線性無關向量組所包含。因此我們只要找出A的列向量中的全體極大線性無關向量組。不難看出，A的全體極大線性無關向量組由E₁的這些子集所標號

因此

(2)考慮圖G

其邊集為。我們要確定所有無圈子圖的邊集的集族。由於每一個無圈子圖都是一個支撐樹的子圖，因此我們只要找出G的所有的支撐樹。不難看出G的全體支撐樹對應的邊子集是

因此，

進一步的觀察可以看出，(1)與(2)這兩個例子，除了一個從矩陣出發得到，另一個從圖得到以外，它們有互相對應的獨立子集族，因而它們的獨立結構沒有什麼本質的區別，為此我們有同構的定義。