34
правки
Изменения
м
Нет описания правки
|proof=
: Пусть <tex> M = \langle X, \mathcal{I} \rangle</tex> {{---}} произвольный матричный матроид над телом <tex>F</tex>, <tex> X = \{1,\ldots,m\} </tex>, <tex>r</tex> {{---}} его [[Ранговая функция, полумодулярность|ранговая функция]]. Рассмотрим сначала крайний случай тривиального и (двойственного к нему) полного матроида.
:* Матроид <tex> M = \langle X, \mathcal{I} \rangle</tex> является тривиальным, если <tex>\mathcal{I} = \varnothing </tex>. <tex>r(\mathcal{I}) = 0</tex>:* Матроид <tex> M = \langle X, \mathcal{I} \rangle</tex> является полным, если <tex>\mathcal{I} = 2^X</tex>. <tex>r(\mathcal{I}) = |X|</tex>
:Они, очевидно, представимы над телом <tex>F</tex> нулевой и единичной матрицей соответственно.
:<tex>\Longleftarrow</tex>
::Теперь докажем в обратную сторону. Пусть система каких-либо <tex>m - r</tex> строк матрицы <tex>Q</tex> линейно зависима. Для простоты обозначений будем считать, что эта система состоит из последних <tex> m - r </tex> строк матрицы <tex>Q</tex>. Тогда линейно зависима система (5) "урезанных" столбцов, составляющих матрицу <tex>Q_1</tex>. Следовательно, некоторая нетривиальная линейная комбинация (6) "урезанных" столбцов равна <tex>0</tex>. С помощью равенства (4) определим столбец <tex>X</tex>. Поскольку система столбцов (2) линейно независима, имеем <tex>X \ne 0</tex>. Столбец Х является решением системы (1), так как он равен линейной комбинации базиса пространства решений этой системы. Тогда столбец <tex>Y</tex>, полученный из столбца <tex>x</tex> отбрасыванием последних <tex>m - r >/tex> нулевых компонент, является ненулевым решением системы (3). Следовательно, линейно зависима система из первых <tex>r</tex> столбцов матрицы <tex>P_1</tex>, что и требовалось доказать.
}}
