Изменения

[[Файл:Vamos_matroid_N.png|thumb|300px200px|right]]'''Матроид Вамоса''' или '''куб Вамоса''' {{---}} это [[ Определение_матроида | матроид ]] над восьми элементным восьмиэлементным множеством, который не изоморфен матричному ни над каким полем. Он назван в честь английского математика '''Питера Вамоса''' ('''Peter Vámos'''), который первым описал его в неопубликованной рукописи в 1968.

Пусть <tex> E = \{1, 2, 3, 4, 5, 6, 7, 8\}</tex>. Матроид Вамоса <tex>V</tex> удобно задать, назвав все его '''[[Определение_матроида | зависимые''' ]] множества: это все подмножества <tex>E</tex>, в которых не менее пяти элементов, а также <tex>\{1, 2, 5, 6\}, \{1, 2, 7, 8\}, \{3, 4, 5, 6\}, \{3, 4, 7, 8\}, \{5, 6, 7, 8\}</tex>.

{{Теорема|statement== Доказательство матроидной природы =Заданная конструкция является матроидом. |proof= Сначала убедимся в том, что перед нами действительно матроидВыполнение первых двух аксиом очевидно. Фактически В проверке нуждается в проверке лишь тот факт, что если <tex>A</tex> и <tex>B</tex> независимые множества и <tex>|B| = 3</tex>, <tex>|A| = 4</tex>, то в <tex>A</tex> найдется такой элемент <tex>e</tex>, что <tex>B \cup \{e\}</tex> {{---}} независимое множество. Когда <tex>B \subset A</tex>, это очевидно. В противном же случае множество <tex> A \setminus B</tex> содержит по меньшей мере два различных элемента. Обозначим их через <tex>e1e_1</tex> и <tex>e2e_2</tex>. Теперь осталось заметить, что из множеств <tex>B \cup \{e1e_1\}</tex> и <tex>B \cup \{e2e_2\}</tex> хотя бы одно независимое, так как по условию нет двух зависимых множеств изчетырtх четырех элементов, отличающихся одним элементом.}}

* Все циклы матроида Вамоса имеют размер по меньшей мере равный его [[Определение_матроида| рангу]](максимальный размер независимого множества).* Матроид Вамоса [[Определение_матроида | изоморфен ]] своему [[Двойственный_матроид | двойственному матроиду]]. Однако он не самодвойственен, так как это требует нетривиальную перестановку элементов.* Матроид Вамоса не представим ни над каким полем. Это значит, что не существует векторного пространства и системы из восьми векторов в нем, таких что матроид линейной независимости этих векторов изоморфен матроиду Вамоса. То есть матроид Вамоса не является [[Примеры_матроидов#.D0.9C.D0.B0.D1.82.D1.80.D0.B8.D1.87.D0.BD.D1.8B.D0.B9_.D0.BC.D0.B0.D1.82.D1.80.D0.BE.D0.B8.D0.B4|матричным]].

Предположим, что существует изоморфный V векторный матроид <tex>M = \langle E, J begin{vmatrix} a_{53} & a_{54} \\ a_{63} & a_{64} \rangleend{vmatrix} = 0 </tex>, где  то есть векторы <tex>E = \{x1, x2, {{...}} , x8}z_5</tex>, и для каждого <tex>iz_6</tex> линейно зависимы. Заметим, что вектор <tex>x_iz_5</tex> соответствует элементу ненулевой (иначе были бы линейно зависимыми векторы <tex>ix_1, x_2, x_5</tex>, а у нас любые три вектора линейно независимые) . Поэтому для некоторого скаляра (то есть элемента числового поля, над которым рассматривается линейное пространство) <tex> \mu </tex> имеет место равенство <tex>z_6 = \mu z_5</tex> матроида Вамоса. Множество Точно так же из линейной зависимости четвёрок векторов <tex>\{x1x_1, x_2, x_7, x_8\}, \{x_3, x2x_4, x3x_5, x4x_6\}, \{x_3, x_4, x_7, x_8\}</tex> является базисом получаем соответственно равенства <tex>Mz_8 = \beta z_7, y_6 = \lambda y_5, y_8 = \alpha y_7</tex>, где греческими буквами обозначены некоторые скаляры. Запишем координаты каждого вектора в  Наконец, используем линейную зависимость векторов <tex>x_5, x_6, x_7, x_8</tex>. С помощью найденных соотношений будем преобразовывать определитель, составленный из координат этих векторов (при этом базисевместо строк определителя длянаглядности записываем поначалу соответствующие векторы):  <tex> \begin{vmatrix} x_5 \\ x_6 \\ x_7 \\ x_8 \end{vmatrix} = \begin{vmatrix} y_5+z_5 \\ y_6+z_6 \\ y_7+z_7 \\ y_8+z_8 \end{vmatrix} = \begin{vmatrix} y_5+z_5 \\ \lambda y_5+ \mu z_5 \\ y_7+z_7 \\ \alpha y_7+ \beta z_7 \end{vmatrix} = \begin{vmatrix} y_5 \\ \mu z_5 \\ y_7 \\ \beta z_7 \end{vmatrix} + \begin{vmatrix} y_5 \\ \mu z_5 \\ z_7 \\ \alpha y_7 \end{vmatrix} + \begin{vmatrix} z_5 \\ \lambda y_5 \\ y_7 \\ \beta z_7 \end{vmatrix} + \begin{vmatrix} z_5 \\ \lambda y_5 \\ z_7 \\ \alpha y_7 \end{vmatrix} = </tex><tex>x_i \mu (\beta - \alpha) \begin{vmatrix} y_5 \\ z_5 \\ y_7 \\ z_7 \end{vmatrix} - \lambda ( \beta- \alpha) \begin{vmatrix} y_5 \\ z_5 \\ y_7 \\ z_7 \end{vmatrix} = (\mu - \lambda)( \beta- \alpha) \begin{vmatrix} a_{51} & a_{i152}, & 0 & 0 \\ 0 & 0 & a_{53} & a_{54} \\ a_{71} & a_{i272}, & 0 & 0 \\ 0 & 0 & a_{i373}, & a_{i474} \end{vmatrix}= </tex><tex>( \mu - \lambda)( \beta- \alpha) \begin{vmatrix} a_{51} & a_{52} \\ a_{71} & a_{72} \end{vmatrix} \begin{vmatrix} a_{53} & a_{54} \\ a_{73} & a_{74} \end{vmatrix} = 0</tex>. Для дальнейшего нам понадобятся также  Теперь заметим, что <tex> \mu \ne \lambda</tex> (в противном случае линейно зависимыми будут векторы <tex>y_i x_5 = (a_i1, a_i2, 0, 0)y_5 + z_5</tex> и <tex>z_i x_6 = \lambda y_5 + \mu z_5)</tex> , а <tex> \alpha \ne \beta</tex> (0, 0, a_i3, a_i4иначе линейно зависимы векторы <tex>x_7</tex> и <tex>x_8</tex>). Поэтому равен нулю один из определителей <tex>\begin{vmatrix} a_{51} & a_{52} \\ a_{71} & a_{72} \end{vmatrix}</tex> или <tex>\begin{vmatrix} a_{53} & a_{54} \\ a_{73} & a_{74} \end{vmatrix} </tex>, где например - первый из них. Но тогда <tex>i \begin{vmatrix} x_3 \\ x_4 \\ x_5 \\ x_7 \end{vmatrix} = \begin{vmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1, 2, \\ a_{51} & a_{52} & a_{53} & a_{54} \\ a_{71} & a_{72} & a_{73} & a_{74} \end{vmatrix} = \begin{vmatrix} a_{51} & a_{...52} \\ a_{71}& a_{72} , 8\end{vmatrix} =0 </tex>. Ввиду линейной зависимости векторов то есть векторы <tex>x1x_3, x2x_4, x5x_5, x6x_7</tex> получаем равенство нулю определителя линейно зависимы, составленного из координат этих векторов:что противоречит условию.}} ==См. также==* [[Определение матроида]]* [[Примеры матроидов]]* [[Двойственный матроид]]

*[http://en.wikipedia.org/wiki/V%C3%A1mos_matroid Wikipedia {{---}} Vámos matroid, wikipedia]