Mátrixmatroid

A matematika által vizsgált egyik struktúratípus a matroid. A mátrixmatroid (vagy lineáris matroid, illetve reprezentálható matroid) olyan matroidot jelent, melyben az alaphalmaz/univerzum egy adott test feletti nem azonosan nulla mátrix oszlopainak halmaza, maga a struktúra pedig ennek részhalmazaiból áll, tehát az oszlopok halmazának hatványhalmazának egy részhalmazából; mégpedig pontosan azon oszlopokból, melyek (lineárisan) függetlenek, röviden függetlenek (azaz őket mint vektorokat akármilyen skalárokkal szorozva is adjuk össze, ha véletlenül nullvektort kapnánk, akkor az összes skalár nulla volt).

A matroidaxiómák teljesülése mátrixmatroidokra

A mátrixmatroid valóban a matroidok egy példája, mivel olyan halmazrendszer, mely nem üres, leszálló és elemei kölcsönösen bővíthetőek (vagy másképp, bármely oszlophalmazra az ebben lévő független oszlophalmazok azonos elemszámúak).

Ugyanis nem üres, mert van legalább egy olyan oszlopa, amely a mátrix nem nullmátrixsága miatt nem nullvektor. Ez az egy oszlop pedig biztosan lineárisan független. Vagy másképp biztosan tartalmazza az üres oszlophalmazt, ami „triviálisan” lineárisan független, hiszen tetszőleges üres oszloprendszerre teljesül, hogy ha „lineárisan kikeverjük” belőle a nullvektort, akkor minden együttható nulla. Nem tudunk ugyanis ellenpéldát mutatni (megjegyezzük: az üres oszloprendszerek egyben lineárisan összefüggőek is, de ez ne zavarjon, az üres vektorrendszerek az egyetlen egyszerre függő és független rendszerek).

A mátrixmatroid leszálló halmazrendszer, azaz ha egy oszlophalmaz az eleme, akkor annak minden részhalmaza is. Ugyanis ha egy oszlophalmaz lineárisan független, akkor minden részhalmaza is az, mert vagy üres, és ekkor az előbbi okok miatt, vagy (indirekte) lenne egy függő része, amelynek egyik nem-pusztán nulla együtthatókból álló kombinációja (mondjuk $\alpha _{i}$) nulla(vektor) lenne, ekkor a maradék részt 0 együtthatókkal szorozva és az eddigiekhez hozzáadva, még mindig a nullavektort kapnánk, de lenne egy nem nulla együttható ($\alpha _{i}$), így az egész rendszer is összefüggő lenne.

Lényegében egy elemi lineáris algebrai tételből következik, hogy a „bővíthetőségi” matroidaxióma is teljesül. Ez azonban enélkül is belátható.

Példa

Legyen $M={\begin{bmatrix}1&1&0&0\\1&0&1&0\\1&0&0&1\\0&0&0&0\end{bmatrix}}$ egy 4×4-es mátrix. Az i-edik oszlopát jelölje $o_{i}$. Az alaphalmaz tehát $U=\left\{\ o_{1},o_{2},o_{3},o_{4}\ \right\}$.

Ekkor az M-ből készített mátrixmatroid a következő: ${\mathcal {F}}(M)=\left\{\left\{o_{1},o_{2},o_{3}\right\},\left\{o_{1},o_{2},o_{4}\right\},\left\{o_{1},o_{3},o_{4}\right\},\left\{o_{2},o_{3},o_{4}\right\},\left\{o_{1},o_{2}\right\},\left\{o_{1},o_{3}\right\},\left\{o_{1},o_{4}\right\},\left\{o_{2},o_{3}\right\},\left\{o_{2},o_{4}\right\},\left\{o_{3},o_{4}\right\},\left\{o_{1}\right\},\left\{o_{2}\right\},\left\{o_{3}\right\},\left\{o_{4}\right\},\emptyset \right\}$ . Pontosabban ez csak a független halmazok halmaza, mert magát a matroidot a ${\mathcal {M}}(M)=\left(U,{\mathcal {F}}(M)\right)$ párként definiáljuk.

Tehát lényegében bármely oszlophalmaza lineárisan független, kivéve magát az összes oszlopot tartalmazó univerzumot, ugyanis $1\cdot o_{1}-1\cdot o_{2}-1\cdot o_{3}-1\cdot o_{4}={\overline {0}}$ miatt ez nem lineárisan független.