Матроид Вамоса — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Матроид Вамоса не представим ни над каким полем)
м (rollbackEdits.php mass rollback)
 
(не показано 15 промежуточных версий 4 участников)
Строка 4: Строка 4:
 
== Задание матроида ==
 
== Задание матроида ==
  
Пусть <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>.
+
Пусть <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 = \{x1, x2, {{...}} , x8 \}</tex>, и для каждого <tex>i</tex> вектор <tex>x_i</tex> соответствует элементу <tex>i</tex> матроида Вамоса.  
+
Предположим, что существует изоморфный <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>\{x1, x2, x3, x4\}</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>\{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>x1, x2, x5, x6</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> = \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 (\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>\{x3, x4, x5, x7\}</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

Vamos matroid N.png

Матроид Вамоса или куб Вамоса — это матроид над восьмиэлементным множеством, который не изоморфен матричному ни над каким полем. Он назван в честь английского математика Питера Вамоса (Peter Vámos), который первым описал его в неопубликованной рукописи в 1968.

Задание матроида

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

Теорема:
Заданная конструкция является матроидом.
Доказательство:
[math]\triangleright[/math]
Выполнение первых двух аксиом очевидно. В проверке нуждается лишь тот факт, что если [math]A[/math] и [math]B[/math] независимые множества и [math]|B| = 3[/math], [math]|A| = 4[/math], то в [math]A[/math] найдется такой элемент [math]e[/math], что [math]B \cup \{e\}[/math] — независимое множество. Когда [math]B \subset A[/math], это очевидно. В противном же случае множество [math] A \setminus B[/math] содержит по меньшей мере два различных элемента. Обозначим их через [math]e_1[/math] и [math]e_2[/math]. Теперь осталось заметить, что из множеств [math]B \cup \{e_1\}[/math] и [math]B \cup \{e_2\}[/math] хотя бы одно независимое, так как по условию нет двух зависимых множеств из четырех элементов, отличающихся одним элементом.
[math]\triangleleft[/math]

Свойства

  • Все циклы матроида Вамоса имеют размер по меньшей мере равный его рангу (максимальный размер независимого множества).
  • Матроид Вамоса изоморфен своему двойственному матроиду. Однако он не самодвойственен, так как это требует нетривиальную перестановку элементов.
  • Многочлен Татта матроида Вамоса равен [math]x^4+4x^3+10x^2+15x+5xy+15y+10y^2+4y^3+y^4.[/math]
  • Матроид Вамоса не является матричным.

Матроид Вамоса не представим ни над каким полем

Теорема:
Матроид Вамоса не представим ни над каким полем.
Доказательство:
[math]\triangleright[/math]

Это значит, что не существует векторного пространства и системы из восьми векторов в нем, таких что матроид линейной независимости этих векторов изоморфен матроиду Вамоса.

Предположим, что существует изоморфный [math]V[/math] векторный матроид [math]M = \langle E, J \rangle[/math], где [math]E = \{x_1, x_2, {{...}} , x_8 \}[/math], и для каждого [math]i[/math] вектор [math]x_i[/math] соответствует элементу [math]i[/math] матроида Вамоса. Множество [math]\{x_1, x_2, x_3, x_4\}[/math] является базисом [math]M[/math] (так как [math]\{1, 2, 3, 4\}[/math] — независимое множество в матроиде Вамоса). Запишем координаты каждого вектора в этом базисе: [math]x_i = (a_{i1}, a_{i2}, a_{i3}, a_{i4})[/math]. Для дальнейшего нам понадобятся также векторы [math]y_i = (a_{i1}, a_{i2}, 0, 0)[/math] и [math]z_i = (0, 0, a_{i3}, a_{i4})[/math], где [math]i = 1, 2, {{...}} , 8[/math]. Ввиду линейной зависимости векторов [math]x_1, x_2, x_5, x_6[/math] (соответствуют зависимому множеству в матроиде Вамоса) получаем равенство нулю определителя, составленного из координат этих векторов:

[math] \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 [/math]

отсюда

[math] \begin{vmatrix} a_{53} & a_{54} \\ a_{63} & a_{64} \end{vmatrix} = 0 [/math]

то есть векторы [math]z_5[/math] и [math]z_6[/math] линейно зависимы. Заметим, что вектор [math]z_5[/math] ненулевой (иначе были бы линейно зависимыми векторы [math]x_1, x_2, x_5[/math], а у нас любые три вектора линейно независимые) . Поэтому для некоторого скаляра (то есть элемента числового поля, над которым рассматривается линейное пространство) [math] \mu [/math] имеет место равенство [math]z_6 = \mu z_5[/math]. Точно так же из линейной зависимости четвёрок векторов [math]\{x_1, x_2, x_7, x_8\}, \{x_3, x_4, x_5, x_6\}, \{x_3, x_4, x_7, x_8\}[/math] получаем соответственно равенства [math]z_8 = \beta z_7, y_6 = \lambda y_5, y_8 = \alpha y_7[/math], где греческими буквами обозначены некоторые скаляры.

Наконец, используем линейную зависимость векторов [math]x_5, x_6, x_7, x_8[/math]. С помощью найденных соотношений будем преобразовывать определитель, составленный из координат этих векторов (при этом вместо строк определителя для наглядности записываем поначалу соответствующие векторы):

[math] \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} = [/math] [math] \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} = [/math] [math]( \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[/math]

Теперь заметим, что [math] \mu \ne \lambda[/math] (в противном случае линейно зависимыми будут векторы [math]x_5 = y_5 + z_5[/math] и [math]x_6 = \lambda y_5 + \mu z_5)[/math] , а [math] \alpha \ne \beta[/math] (иначе линейно зависимы векторы [math]x_7[/math] и [math]x_8[/math]) . Поэтому равен нулю один из определителей [math]\begin{vmatrix} a_{51} & a_{52} \\ a_{71} & a_{72} \end{vmatrix}[/math] или [math]\begin{vmatrix} a_{53} & a_{54} \\ a_{73} & a_{74} \end{vmatrix} [/math], например - первый из них. Но тогда [math] \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 [/math]

то есть векторы [math]x_3, x_4, x_5, x_7[/math] линейно зависимы, что противоречит условию.
[math]\triangleleft[/math]

См. также

Источники информации