Матроид Вамоса — различия между версиями
(→Матроид Вамоса не представим ни над каким полем) |
м (rollbackEdits.php mass rollback) |
||
(не показано 14 промежуточных версий 4 участников) | |||
Строка 4: | Строка 4: | ||
== Задание матроида == | == Задание матроида == | ||
− | Пусть <tex> E = \{1, 2, 3, 4, 5, 6, 7, 8\}</tex>. Матроид Вамоса <tex>V</tex> удобно задать, назвав все его [[Определение_матроида | | + | Пусть <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>. |
{{Теорема | {{Теорема | ||
Строка 20: | Строка 20: | ||
== Матроид Вамоса не представим ни над каким полем == | == Матроид Вамоса не представим ни над каким полем == | ||
{{Теорема | {{Теорема | ||
− | |statement=Матроид Вамоса не представим ни над каким полем. | + | |statement=Матроид Вамоса не [[ Примеры_матроидов#.D0.91.D0.B8.D0.BD.D0.B0.D1.80.D0.BD.D1.8B.D0.B9_.D0.BC.D0.B0.D1.82.D1.80.D0.BE.D0.B8.D0.B4 | представим]] ни над каким полем. |
|proof= | |proof= | ||
+ | Это значит, что не существует векторного пространства и системы из восьми векторов в нем, таких что матроид линейной независимости этих векторов изоморфен матроиду Вамоса. | ||
− | Предположим, что существует изоморфный <tex>V</tex> векторный матроид <tex>M = \langle E, J \rangle</tex>, где <tex>E = \{ | + | Предположим, что существует изоморфный <tex>V</tex> векторный матроид <tex>M = \langle E, J \rangle</tex>, где <tex>E = \{x_1, x_2, {{...}} , x_8 \}</tex>, и для каждого <tex>i</tex> вектор <tex>x_i</tex> соответствует элементу <tex>i</tex> матроида Вамоса. |
− | Множество <tex>\{ | + | Множество <tex>\{x_1, x_2, x_3, x_4\}</tex> является базисом <tex>M</tex> (так как <tex>\{1, 2, 3, 4\}</tex> {{---}} независимое множество в матроиде Вамоса). Запишем координаты каждого вектора в этом базисе: <tex>x_i = (a_{i1}, a_{i2}, a_{i3}, a_{i4})</tex>. Для дальнейшего нам понадобятся также векторы <tex>y_i = (a_{i1}, a_{i2}, 0, 0)</tex> и <tex>z_i = (0, 0, a_{i3}, a_{i4})</tex>, где <tex>i = 1, 2, {{...}} , 8</tex>. |
− | Ввиду линейной зависимости векторов <tex> | + | Ввиду линейной зависимости векторов <tex>x_1, x_2, x_5, x_6</tex> (соответствуют зависимому множеству в матроиде Вамоса) получаем равенство нулю определителя, составленного из координат этих векторов: |
<tex> \begin{vmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ a_{51} & a_{52} & a_{53} & a_{54} \\ a_{61} & a_{62} & a_{63} & a_{64} \end{vmatrix} = 0 </tex> | <tex> \begin{vmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ a_{51} & a_{52} & a_{53} & a_{54} \\ a_{61} & a_{62} & a_{63} & a_{64} \end{vmatrix} = 0 </tex> | ||
Строка 39: | Строка 40: | ||
<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> \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> | + | <tex> \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_{52} & 0 & 0 \\ 0 & 0 & a_{53} & a_{54} \\ a_{71} & a_{72} & 0 & 0 \\ 0 & 0 & a_{73} & a_{74} \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 - \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> | ||
Строка 46: | Строка 47: | ||
<tex> \begin{vmatrix} x_3 \\ x_4 \\ x_5 \\ x_7 \end{vmatrix} = \begin{vmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 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} \end{vmatrix} =0 </tex> | <tex> \begin{vmatrix} x_3 \\ x_4 \\ x_5 \\ x_7 \end{vmatrix} = \begin{vmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ 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} \end{vmatrix} =0 </tex> | ||
− | то есть векторы <tex> | + | то есть векторы <tex>x_3, x_4, x_5, x_7</tex> линейно зависимы, что противоречит условию. |
}} | }} | ||
+ | |||
+ | ==См. также== | ||
+ | * [[Определение матроида]] | ||
+ | * [[Примеры матроидов]] | ||
+ | * [[Двойственный матроид]] | ||
== Источники информации == | == Источники информации == | ||
*[http://en.wikipedia.org/wiki/V%C3%A1mos_matroid Wikipedia {{---}} Vámos matroid] | *[http://en.wikipedia.org/wiki/V%C3%A1mos_matroid Wikipedia {{---}} Vámos matroid] | ||
*[http://www.lib.susu.ac.ru/ftd?base=SUSU_METHOD&key=000305409&dtype=F&etype=.pdf Элементарное введение в матроиды] | *[http://www.lib.susu.ac.ru/ftd?base=SUSU_METHOD&key=000305409&dtype=F&etype=.pdf Элементарное введение в матроиды] | ||
− | |||
[[Категория:Дискретная математика и алгоритмы]] | [[Категория:Дискретная математика и алгоритмы]] | ||
[[Категория:Матроиды]] | [[Категория:Матроиды]] | ||
+ | [[Категория:Основные факты теории матроидов]] |
Текущая версия на 19:13, 4 сентября 2022
Матроид Вамоса или куб Вамоса — это матроид над восьмиэлементным множеством, который не изоморфен матричному ни над каким полем. Он назван в честь английского математика Питера Вамоса (Peter Vámos), который первым описал его в неопубликованной рукописи в 1968.
Задание матроида
Пусть зависимые множества: это все подмножества , в которых не менее пяти элементов, а также .
. Матроид Вамоса удобно задать, назвав все егоТеорема: |
Заданная конструкция является матроидом. |
Доказательство: |
Выполнение первых двух аксиом очевидно. В проверке нуждается лишь тот факт, что если | и независимые множества и , , то в найдется такой элемент , что — независимое множество. Когда , это очевидно. В противном же случае множество содержит по меньшей мере два различных элемента. Обозначим их через и . Теперь осталось заметить, что из множеств и хотя бы одно независимое, так как по условию нет двух зависимых множеств из четырех элементов, отличающихся одним элементом.
Свойства
- Все циклы матроида Вамоса имеют размер по меньшей мере равный его рангу (максимальный размер независимого множества).
- Матроид Вамоса изоморфен своему двойственному матроиду. Однако он не самодвойственен, так как это требует нетривиальную перестановку элементов.
- Многочлен Татта матроида Вамоса равен
- Матроид Вамоса не является матричным.
Матроид Вамоса не представим ни над каким полем
Теорема: |
Матроид Вамоса не представим ни над каким полем. |
Доказательство: |
Это значит, что не существует векторного пространства и системы из восьми векторов в нем, таких что матроид линейной независимости этих векторов изоморфен матроиду Вамоса. Предположим, что существует изоморфный векторный матроид , где , и для каждого вектор соответствует элементу матроида Вамоса. Множество является базисом (так как — независимое множество в матроиде Вамоса). Запишем координаты каждого вектора в этом базисе: . Для дальнейшего нам понадобятся также векторы и , где . Ввиду линейной зависимости векторов (соответствуют зависимому множеству в матроиде Вамоса) получаем равенство нулю определителя, составленного из координат этих векторов:
отсюда
то есть векторы и линейно зависимы. Заметим, что вектор ненулевой (иначе были бы линейно зависимыми векторы , а у нас любые три вектора линейно независимые) . Поэтому для некоторого скаляра (то есть элемента числового поля, над которым рассматривается линейное пространство) имеет место равенство . Точно так же из линейной зависимости четвёрок векторов получаем соответственно равенства , где греческими буквами обозначены некоторые скаляры.Наконец, используем линейную зависимость векторов . С помощью найденных соотношений будем преобразовывать определитель, составленный из координат этих векторов (при этом вместо строк определителя для наглядности записываем поначалу соответствующие векторы):
Теперь заметим, что то есть векторы (в противном случае линейно зависимыми будут векторы и , а (иначе линейно зависимы векторы и ) . Поэтому равен нулю один из определителей или , например - первый из них. Но тогда линейно зависимы, что противоречит условию. |