10.6. Представимость матроидов

Пусть М — матроид на множестве S. Пусть

— соответствующая кобаза М. Напомним, что где базисный цикл элемента . Аналогично где — базисный коцикл элемента Как и в случае неориентированных графов (гл. 6), мы можем сейчас определить базисную цикломатическую матрицу D и базисную коцикломатическую матрицу матроида М по отношению к базе В. Очевидно, что обе эти матрицы будут иметь вид , где U — единичная матрица, столбцы которой соответствуют элементам В. Матрица такого вида называется стандартным представлением матроида М по отношению к базе В.

Рассмотрим граф G. Присвоим произвольным образом ориентацию ребрам графа G, получив в результате ориентированный граф G. Тогда по теореме 6.9 усеченная матрица инциденций G есть представление циклического матроида М (G) над произвольным полем F. Можно заметить также (теорема 6.10), что любая базисная матрица разрезающих множеств G является стандартным представлением М (G) над произвольным полем F. Далее, по теореме 6.11 любая базисная цикломатическая матрица G является стандартным представлением циклического матроида М (G) над произвольным полем F. Таким образом, приходим к следующему утверждению:

Теорема 10.23. Циклический матроид и матроид разрезов графа представимы над произвольным полем

Сейчас мы докажем основной результат этого раздела.

Теорема 10.24. Если матроид М на представим над полем F, тогда двойственный матроид М на S также представим над

Доказательство. Допустим, М имеет ранг и содержит элементов. Пусть матрица А порядка является представлением М над

Пусть X — множество всех таких векторов-столбцовчто Величина X называется нуль-пространством матрицы А. Из линейнои алгебры известно, что размерность X равна Выберем теперь из X множество из линейно независимых векторов-столбцов и образуем из эти векторов, как из столбцов, матрицу В порядка Заметим, что

Покажем сейчас, что является представлением над F двойственного матроида М. Для этого докажем, что произвольные столбцов матрицы А линейно независимы тогда и только тогда, когда дополняющее множество из столбцов линейно независимо. Выберем первые столбцов матрицы А. Очевидно, что такой выбор не влечет потери общности.

Первые столбцов матрицы А линейно зависимы тогда и только тогда, когда существует ненулевой вектор-столбец принадлежащий X. Такой вектор в свою очередь, существует тогда и только тогда, когда существует вектор-столбец такой размерности что , где имеет порядок легко видеть, что . Поскольку , то вырожденная матрица. Таким образом, строки , а следовательно, и последние столбцов В зависимы, что доказывает теорему.

Легким следствием этой теоремы является следующий результат:

Следствие 10.24.1. Пусть М — матроид ранга на множестве Если М имеет стандартное представление

то M имеет стандартное представление

где — единичная матрица порядка

Из этого следствия легко получается выражение (6.13), связывающее базисную цикломатическую матрицу с базисной матрицей разрезающих множеств.

Дальнейшее обсуждение проблемы представимости матроидов можно найти в работе [10.4].