Изменения

|statement=[[Определение матроида|Матроид]], двойственный к [[Примеры матроидов|матричному ]] над телом <tex>F</tex>, так же является матричным над телом <tex>F</tex>

: Пусть <tex> M = \langle X, \mathcal{I} \rangle</tex> {{- --}} произвольный матричный матроид над телом <tex>F</tex>, <tex>r</tex> {{- --}} его [[Ранговая функция, полумодулярность|ранговая функция]]. Рассмотрим сначала крайний случай тривиального и (двойственного к нему) полного матроида. :* Матроид <tex> M = \langle X, \mathcal{I} \rangle</tex> является тривиальным, если <tex>\mathcal{I} = \varnothing </tex>.:* Матроид <tex> M = \langle X, \mathcal{I} \rangle</tex> является полным, если <tex>\mathcal{I} = 2^X</tex>.:Они, очевидно, представимы над телом <tex>F</tex> нулевой и единичной матрицей соответственно. <br>

: Пусть теперь <tex>M</tex> {{- --}} произвольный нетривиальный и не полный матричный матроид. Тогда <tex>M</tex> изоморфен матроиду столбцов некоторой <tex>(t \times m)</tex>-матрицы <tex>P</tex> над телом <tex>F</tex>. Т.к. матроид нетривиален и несвободенне полный, то <tex>rank rg(P ) = r</tex> и <tex>0 < r < m </tex>. <br>

:: <tex>(1): PX=0</tex>. (1) <br>: По теореме Жордана для Для задания базиса ФСР этой системы нам [[wikipedia:ru:Решение систем линейных алгебраических уравнений|достаточно ]] <tex>m - r</tex> линейно независимых векторов. Пусть <br>:: <tex>(2): X_1, X_2,...\ldots, X_{m-r}</tex> (2) <br>:{{- --}} базис пространства решений системы (1). Составим из этих столбцов <tex>(m \times (m - r))</tex>-матрицу <tex>Q=(X_1, X_2, ...\ldots, 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,...\ldots, 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>(3): P_1Y=0</tex> (3)<br>

::<tex>(4): X=\alpha_1 X_1 + \alpha_2 X_2 + ... \ldots + \alpha_{m-r} X_{m-r}</tex> (4) <br>

::<tex>(5): X'_1, X'_2, ...\ldots, X'_{m-r}</tex> (5) <br>: из пространства <tex>F^{m-r}</tex>, полученные соответственно из столбцов <tex>X_1, X_2, ...\ldots, X_{m-r}</tex> отбрасыванием первых <tex>r</tex> компонент. Составим из этих "урезанных" столбцов <tex> ((m - r) \times (m - r))</tex>-матрицу <tex>Q_1 = (X'_1, X'_2, ...\ldots, X'_{m-r})</tex>. Матрица <tex>Q_1</tex> {{- --}} это квадратная матрица порядка <tex>m-r</tex>, которая является подматрицей матрицы <tex>Q</tex> и расположена внизу матрицы <tex>Q</tex>. Из равенства (4) следует, что <br>:: <tex>(6): 0=\alpha_1 X'_1 + \alpha_2 X'_2 + ... \ldots + \alpha_{m-r} X'_{m-r}</tex> (6) <br>

* ''Michel X. Goemans'' {{- --}} Advanced Combinatorial Optimization, lection 8: Mathroids.* ''Асанов М. О., Баранский В. А., Расин В. В.'' {{--- }} Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2''' <br>