- Пусть M=⟨X,I⟩ — произвольный матричный матроид над телом F, X={1,…,m}, r — его ранговая функция. Рассмотрим сначала крайний случай тривиального и (двойственного к нему) полного матроида.
- Матроид M=⟨X,I⟩ является тривиальным, если I=∅. r(I)=0
- Матроид M=⟨X,I⟩ является полным, если I=2X. r(I)=|X|
- Они, очевидно, представимы над телом F нулевой и единичной матрицей соответственно.
- Пусть теперь M — произвольный нетривиальный и не полный матричный матроид. Тогда M изоморфен матроиду столбцов некоторой (t×m)-матрицы P над телом F. Т.к. матроид нетривиален и не полный, то rg(P)=r и 0<r<m.
- Рассмотрим следующую однородную систему уравнений над пространством векторов-столбцов Fm:
- (1):PX=0.
- Для задания базиса ФСР этой системы нам достаточно[1] m−r линейно независимых векторов. Пусть
- (2):X1,X2,…,Xm−r
- — базис пространства решений системы (1). Составим из этих столбцов (m×(m−r))-матрицу Q=(X1,X2,…,Xm−r). Покажем, что матроид M∗ изоморфен матроиду строк матрицы Q над телом F. Для этого нам достаточно установить, что система каких-либо r столбцов матрицы P линейно независима тогда и только тогда, когда линейно независима дополняющая ее система m−r строк матрицы Q. Дополняющая система строк — это система строк, номера которых дополняют номера столбцов исходной системы столбцов до множества {1,…,m}.
- ⟹
- Возьмем произвольную систему из r столбцов матрицы P. Для простоты обозначений будем считать, что взяты первыеr столбцов (мы всегда можем переставить столбцы матрицы местами, не поменяв характера их линейной зависимости). Пусть P1(t×r) — подматрица матрицы P, составленная из взятых первых r столбцов. Рассмотрим однородную систему линейных уравнений над пространством векторов-столбцов Fr:
- (3):P1Y=0
- Пусть столбцы матрицы P1 линейно зависимы. Тогда система (3) имеет ненулевое решение Y. Добавим к нему снизу m−r нулей, получим ненулевое решение X системы (1). Выразим X через базис (2) пространства решений системы (1):
- (4):X=α1X1+α2X2+…+αm−rXm−r
- где среди коэффициентов есть хотя бы один ненулевой элемент из F. Введем в рассмотрение столбцы
- (5):X′1,X′2,…,X′m−r
- из пространства Fm−r, полученные соответственно из столбцов X1,X2,…,Xm−r отбрасыванием первых r компонент. Составим из этих "урезанных" столбцов ((m−r)×(m−r))-матрицу Q1=(X′1,X′2,…,X′m−r). Матрица Q1 — это квадратная матрица порядка m−r, которая является подматрицей матрицы Q и расположена внизу матрицы Q. Из равенства (4) следует, что
- (6):0=α1X′1+α2X′2+…+αm−rX′m−r
- т.е. система столбцов квадратной матрицы Q1 линейно зависима. Тогда линейно зависима и система строк этой матрицы, т.е. линейно зависима система из m−r последних строк матрицы Q. Что и требовалось доказать.
- ⟸
- Теперь докажем в обратную сторону. Пусть система каких-либо m−r строк матрицы Q линейно зависима. Для простоты обозначений будем считать, что эта система состоит из последних m−r строк матрицы Q. Тогда линейно зависима система (5) "урезанных" столбцов, составляющих матрицу Q1. Следовательно, некоторая нетривиальная линейная комбинация (6) "урезанных" столбцов равна 0. С помощью равенства (4) определим столбец X. Поскольку система столбцов (2) линейно независима, имеем X≠0. Столбец Х является решением системы (1), так как он равен линейной комбинации базиса пространства решений этой системы. Тогда столбец Y, полученный из столбца x отбрасыванием последних m - r нулевых компонент, является ненулевым решением системы (3). Следовательно, линейно зависима система из первых r столбцов матрицы P1, что и требовалось доказать.
|
