34
правки
Изменения
Добавлена теорема "двойственный к матричному матроид - матричный". Обновлен список источников.
*: <tex> A \in I^*_2 </tex> означает, что <tex> \exists B \in \mathcal B: \ A \cap B = \varnothing </tex>. Последнее можно записать иначе: <tex> A \subseteq \overline B </tex>.
*: Кроме того <tex> B \in \mathcal B \Rightarrow \overline B \in \mathcal B_1 </tex> по определению <tex> M^*_1 </tex>. Получили <tex> A \subseteq \overline B \in \mathcal B_1 </tex>, откуда следует <tex> A \in I^*_1 </tex>.
}}
{{Теорема
|statement=Матроид, двойственный к матричному над телом <tex>F</tex>, так же является матричным над телом <tex>F</tex>
|proof=
: Пусть <tex> M = \langle X, \mathcal{I} \rangle</tex> - произвольный матричный матроид над телом <tex>F</tex>, <tex>r</tex> - его ранговая функция. Рассмотрим сначала крайний случай тривиального и (двойственного к нему) полного матроида. Они, очевидно, представимы над телом <tex>F</tex> нулевой и единичной матрицей соответственно. <br>
: Пусть теперь <tex>M</tex> - произвольный нетривиальный и не полный матричный матроид. Тогда <tex>M</tex> изоморфен матроиду столбцов некоторой <tex>(t \times m)</tex>-матрицы <tex>P</tex> над телом <tex>F</tex>. Т.к. матроид нетривиален и несвободен, то <tex>rank P = r</tex> и <tex>0 < r < m </tex>. <br>
: Рассмотрим следующую однородную систему уравнений над пространством векторов-столбцов <tex>F^m</tex>: <br>
:: <tex>PX=0</tex>. (1) <br>
: По теореме Жордана для задания базиса ФСР этой системы нам достаточно <tex>m - r</tex> линейно независимых векторов. Пусть <br>
:: <tex>X_1, X_2,..., X_{m-r}</tex> (2) <br>
:- базис пространства решений системы (1). Составим из этих столбцов <tex>(m \times (m - r))</tex>-матрицу <tex>Q=(X_1, X_2, ..., X_{m-r})</tex>. Покажем, что матроид <tex>M^*</tex> изоморфен матроиду строк матрицы <tex>Q</tex> над телом <tex>F</tex>. Для этого нам достаточно установить, что система каких-либо <tex>r</tex> столбцов матрицы <tex>P</tex> линейно независима тогда и только тогда, когда линейно независима дополняющая ее система <tex>m - r</tex> строк матрицы <tex>Q</tex>. Дополняющая система строк - это система строк, номера которых дополняют номера столбцов исходной системы столбцов до множества <tex>\{1,..., m\}</tex>. <br>
:Возьмем произвольную систему из r cстолбцов матрицы <tex>P</tex>. Для простоты обозначений будем считать, что взяты первые<tex>r</tex> столбцов (мы всегда можем переставить столбцы матрицы местами, не поменяв характера их линейной зависимости). Пусть <tex>P_1(t\times r)</tex> - подматрица матрицы <tex>P</tex>, составленная из взятых первых <tex>r</tex> столбцов. Рассмотрим однородную систему линейных уравнений над пространством векторов-столбцов <tex>F^r</tex>: <br>
::<tex>P_1Y=0</tex> (3)<br>
: Пусть столбцы матрицы <tex>P_1</tex> линейно зависимы. Тогда система (3) имеет ненулевое решение <tex>Y</tex>. Добавим к нему снизу <tex>m - r</tex> нулей, получим ненулевое решение <tex>X</tex> системы (1). Выразим <tex>X</tex> через базис (2) пространства решений системы (1):<br>
::<tex>X=\alpha_1 X_1 + \alpha_2 X_2 + ... + \alpha_{m-r} X_{m-r}</tex> (4) <br>
: где среди коэффициентов есть хотя бы один ненулевой элемент из <tex>F</tex>. Введем в рассмотрение столбцы <br>
::<tex>X'_1, X'_2, ..., X'_{m-r}</tex> (5) <br>
: из пространства <tex>F^{m-r}</tex>, полученные соответственно из столбцов <tex>X_1, X_2, ..., X_{m-r}</tex> отбрасыванием первых <tex>r</tex> компонент. Составим из этих "урезанных" столбцов <tex> ((m - r) \times (m - r))</tex>-матрицу <tex>Q_1 = (X'_1, X'_2, ..., X'_{m-r})</tex>. Матрица <tex>Q_1</tex> - это квадратная матрица порядка <tex>m-r</tex>, которая является подматрицей матрицы <tex>Q</tex> и расположена внизу матрицы <tex>Q</tex>. Из равенства (4) следует, что <br>
:: <tex>0=\alpha_1 X'_1 + \alpha_2 X'_2 + ... + \alpha_{m-r} X'_{m-r}</tex> (6) <br>
: т.е. система столбцов квадратной матрицы <tex>Q_1</tex> линейно зависима. Тогда линейно зависима и система строк этой матрицы, т.е. линейно зависима система из <tex>m - r</tex> последних строк матрицы <tex>Q</tex>. Что и требовалось доказать. <br>
:Теперь докажем в обратную сторону. Пусть система каких-либо <tex>m - r</tex> строк матрицы <tex>Q</tex> линейно зависима. Для простоты обозначений будем считать, что эта система состоит из последних <tex> m - r </tex> строк матрицы <tex>Q</tex>. Тогда линейно зависима система (5) "урезанных" столбцов, составляющих матрицу <tex>Q_1</tex>. Следовательно, некоторая нетривиальная линейная комбинация (6) "урезанных" столбцов равна 0. С помощью равенства (4) определим столбец <tex>X</tex>. Поскольку система столбцов (2) линейно независима, имеем <tex>X \ne 0</tex>. Столбец Х является решением системы (1), так как он равен линейной комбинации базиса пространства решений этой системы. Тогда столбец <tex>Y</tex>, полученный из столбца <tex>x</tex> отбрасыванием последних m - r нулевых компонент, является ненулевым решением системы (3). Следовательно, линейно зависима система из первых <tex>r</tex> столбцов матрицы <tex>P_1</tex>, что и требовалось доказать.
}}
* [[wikipedia:ru:Матроид#Дополнительные_понятия | Википедия {{---}} Двойственный матроид]]
* [[wikipedia:en:Dual matroid | Wikipedia {{---}} Dual matroid]]
* ''Michel X. Goemans'' - Advanced Combinatorial Optimization, lection 8: Mathroids.
* ''Асанов М. О., Баранский В. А., Расин В. В.'' - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2''' <br>
[[Категория:Алгоритмы и структуры данных]]
[[Категория:Матроиды]]
[[Категория:Основные факты теории матроидов]]
