§ 19. Изоморфизм матроидов

Пусть M1=(E1, β1) и М2 = (E2, β2) — два матроида с множествами баз β1 и β2, φ: Е1→Е2 — биекция. Для ХЕ1 положим φ(Х) = { φ(x): хХ}. Если для любого XE1 имеем φ(Х) β2 тогда и только тогда, когда Xβ1 , то биекция φ называется изоморфизмом матроида М1 на матроид M2.

В этой ситуации будем писать

φ: M1→M2. (1)

Для изоморфизма φ существует обратная биекция φ^-1, причем очевидно, что для любого YЕ2 имеем φ^-1 (Y) β1 тогда и только тогда, когда Yβ2. Следова­тельно, если (1) —изоморфизм матроидов, то и φ^-1: M2→M1 – также изоморфизм.

Если существует изоморфизм (1), то будем называть матроиды М1 и M2 изоморфными и писать М1M2.

Утверждение 19.1. Если φ: M1→M2 — изомор­физм матроидов, то:

1. φ (Х)—независимое множество матроида M2 тогда и только тогда, когда X является независимым множеством матроида М1;

2. φ (Х)—цикл матроида M2 тогда и только тогда, когда X является циклом матроида М1;

3. φ (Х)—кобаза матроида M2 тогда и только тогда, когда X является кобазой матроида M1;

4. φ (X) — коцикл матроида M2 тогда и только тогда, когда X является коциклом в М1.

> 1) Пусть X — независимое множество матроида М1. Тогда X содержится в некоторой базе Вβ1. Множество (X) содержится в базе φ(B) β2 и потому независимо в матроиде M2. Поскольку множество φ (Х) отображается на X обратным изоморфизмом φ^-1, то из независимости множества φ (Х) в свою очередь следует независимость множества X.

2. Пусть X — цикл матроида М1, т. е. минимальное относительно включения зависимое множество. Применяя уже доказанное утверждение 1), заключаем, что φ (Х) –минимальное относительно включения зависимое множество матроида М2.

3. Положим =Е\Х. Множество_Х — кобаза матроида М1 тогда и только тогда, когда — база М1, т. е. когда φ ()—база матроида М2. Последнее равносильно тому, что — кобаза в М2. Но = φ(Х).

4. Коциклы матроида — это минимальные козависимые множества. Подмножество X элементов матроида М1 козависимо тогда и только тогда, когда оно пересекается

с любой базой этого матроида. Последнее равносильно тому, что множество φ(Х) пересекается с любой базой матроида М2, т. е. φ(Х) козависимо в матроиде М2. <

Из предыдущего утверждения непосредственно вытекает

Следствие 19.2. Если матроиды изоморфны, то двойственные матроиды также изоморфны, т. е. если φ: M1→M2 — изоморфизм матроидов, то φ: M*1→M*2 так­же является изоморфизмом матроидов.

Итак, изоморфные матроиды «одинаково устроены», что дает основание их не различать. Поэтому любой матроид, изоморфный векторному, также назовем векторным. Матроид назовем графическим, если он изомор­фен матроиду циклов M(G) некоторого графа G, и кографическим, если он изоморфен матроиду разрезов

На рис. 19.1 изображены два графа G и H, цикличе­ские матроиды которых изоморфны.

§ 20. Представление матроида

Стремление понять строение тех матроидов, которые близки к векторным, т. е. если и не являются векторны­ми, то отличаются от последних лишь незначительно, приводит к понятию представления матроида, в опреде­ленном смысле близкому к понятию изоморфизма.

Пусть М — матроид с множеством элементов Е, Fⁿ — линейное пространство столбцов высоты п над полем F. Отображение φ: E→Fⁿ называется представлением мат­роида М над полем F, если оно удовлетворяет следующе­му условию: для любого подмножества Х = {е1, е2, ... ..., ek} множества Е система векторов φ (е1), φ (е2), ... ..., φ (еk) линейно независима над полем F тогда и толь­ко тогда, когда X является независимым множеством матроида М.

Пусть φ: E→Fⁿ — представление матроида М, Е={е1,e2, ..., еm}. Построим n X m-матрицу

φ (E)=[ φ (е1), φ (е2), ... ..., φ (еm)],

столбцами которой являются образы элементов матрои­да М в представлении φ. Эта матрица также называется представлением матроида М.

Утверждение 20.1. Пусть М — матроид с мно­жеством элементов Е={е1,e2, ..., еm}, А — произвольная п X т-матрица над полем F. Для того чтобы матрица А была представлением матроида М, необходимо и доста­точно выполгнение следующих двух условий:

1. rank A = ρ(M);

2. система любых ρ = ρ(M) столбцов матрицы А с но­мерами i1, i2, ..., iρ линейно независима тогда и только тогда, когда множество [еi1, еi2, .. . ,eiρ} является базой матроида М.

> Очевидно, что А= ρ(E) удовлетворяет условиям 1) и 2). С другой стороны, пусть п X m-матрица А удов­летворяет этим условиям и пусть А1, А2, ..., Аm — ее столбцы. Тогда, положив φ(е1) = A1, получим представ­ление φ: E→Fⁿ матроида М. <

Матроид называется представимым над полем F, если он имеет представление над F. Как подтверждают сле­дующие примеры, одни матроиды представимы над лю­бым полем, другие — не над любым.

Пусть М — матроид с множеством элементов E = {1, 2, 3}, базами которого служат все двухэлементные под­множества множества Е. Очевидно, что этот матроид представим над произвольным полем, поскольку матрица

служит представлением матроида М.

С другой стороны, возьмем в качестве М матроид с множеством элементов E = {1, 2, 3, 4}, базами которого, как и выше, служат все двухэлементные подмножества множества Е. Пусть матрица А является представлением этого матроида над полем F из двух элементов. Тогда rank A = 2 и, следовательно, столбцы этой матрицы при­надлежат двумерному линейному пространству над F. Двумерное линейное пространство над полем из двух элементов — это четырехэлементное множество {а, Ь, a+Ь, 0). Следовательно, столбцами матрицы А являются a, b, а + b, 0. Но поскольку любое двухэлементное под­множество множества Е является базой матроида М, то любые два столбца матрицы А должны быть линейно независимы. Полученное противоречие доказывает, что матроид М не представим над полем из двух элементов.

Если же F — произвольное поле, содержащее более двух элементов, то, например, матрица

является представлением матроида М над F. Итак, рассматриваемый матроид представим над любым полем, кроме поля из двух элементов.

Очевидно, что свободный матроид представим над лю­бым полем — его представлением служит, например, еди­ничная матрица. Двойственный ему тривиальный матроид также представим, его представление — нулевая матрица.

Заметим, что существуют матроиды, не представимые ни над каким полем.

Из определения представления вытекает, что оно дей­ствует инъективно на каждом независимом множестве элементов матроида. Однако в целом оно может оказать­ся и не инъективным. Рассмотрим, например, матроид М = (Е, β) с множеством элементов E = {1, 2, 3, 4, 5} и множеством баз β = {{3, 4}, {3, 5), {4, 5}}. Его цикла­ми служат множества {1}, {2} и {3, 4, 5}. Положив

получим представление φ матроида М над произвольным полем. Это представление не является инъективным. Очевидно, что рассматриваемый матроид не имеет инъективных представлений ни над каким полем, поскольку φ(1) = φ(2) = 0 для любого представления φ этого мат­роида.

Легко понять, что матроид, для которого существует инъективное представление, является векторным. В са­мом деле, для произвольного представления φ некоторого матроида М = (Е, β) рассмотрим множество столбцов {φ(е): eE}. Это множество порождает векторный мат­роид, который обозначим через φ(М). Если отображение φ инъективно, то оно естественно индуцирует изомор­физм φ` матроидов М и φ (М): φ`(е) = φ(е) для любого элемента е матроида М. Итак, верно

Утверждение 20.2. Если представление φ мат­роида М инъективно, то М φ(М).

С другой стороны, пусть L — n-мерное линейное про­странство над произвольным полем F, E  L — конечное непустое подмножество, М — векторный матроид, порожденный множеством векторов Е. Зафиксируем в простран­стве L произвольный базис. Поставив в соответствие каж­дому вектору из Е его координатный столбец в отмечен­ном базисе, получим представление Е→Fⁿ матроида М, являющееся инъективным.

Итак, инъективные представления существуют у всех векторных матроидов и только у них.

Теорема 20.3. Если матроид представим над полем F, то двойственный ему матроид также представим над F.

> Для свободного и тривиального матроидов утверж­дение теоремы очевидно. Пусть М — нетривиальный мат­роид, не являющийся свободным, ρ = ρ(M), п X m-матрица А — представление над полем F матроида М. Тогда rank А = ρ , 0 < ρ < т.

Рассмотрим однородную систему

AХ = 0 (1)

линейных уравнений с матрицей А (здесь X — столбец неизвестных х1, x2, ..., хm, 0 — нулевой столбец высоты п). Пусть Y — множество всех столбцов из F^m, являю­щихся решениями системы (1). Как известно из алгебры, Y — подпространство пространства F^m размерности т — ρ. Выберем какой-либо базис

Y1, Y2, … , Ym-ρ (2)

подпространства Y и составим из столбцов (2) т Х (m- ρ)-матрицу B = [Y1, Y2, … , Ym-ρ].

Теперь докажем, что транспонированная матрица В^Т является представлением матроида M*, для чего исполь­зуем утверждение 20.1. Имеем

rank В^T = rank В = m — ρ = ρ (М*).

Далее вспомним, что базами матроида М* являются до­полнения до баз матроида М. Поэтому достаточно уста­новить следующее: система каких-либо ρ столбцов мат­рицы А линейно независима тогда и только тогда, когда линейно независима дополняющая система т — p столб­цов матрицы В^T (или строк матрицы В). Слово «допол­няющая» означает, что номера столбцов второй системы отличны от номеров столбцов первой.

Выделим какую-либо систему ρ столбцов матрицы А. Пусть, для определенности, это первые ρ столбцов, и пусть С — подматрица в А, составленная из взятых столбцов. Теперь рассмотрим однородную систему линей­ных уравнений

CZ = 0 (3)

с матрицей С (Z — столбец неизвестных z1, z2,…, zρ). Если столбцы матрицы С линейно зависимы, то си­стема (3) имеет ненулевое решение Z. Рассмотрим стол­бец

высоты т, полученный добавлением m — ρ нулей к столб­цу Z. Очевидно, что U— решение системы (1), т. е. UY. Поскольку (2) — базис пространства Y, то

U = α1Y1 + α2Y2 +... + αm-ρYm-ρ. (4)

Введем столбцы

Y`1, Y`2, … , Y`m-ρ (5)

высоты m — ρ, отбросив из каждого столбца (2) первые ρ координат, и рассмотрим матрицу D = [Y`1, Y`2, … , Y`m-ρ], столбцами которой являются векторы (5). Это квадратная матрица, строки которой суть последние m — ρ строк матрицы В. Из равенства (4) следует

Среди коэффициентов αi в последнем равенстве есть от­личные от нуля, поскольку U ≠ 0. Следовательно, систе­ма столбцов (5) линейно зависима.

Обратно, пусть система каких-либо, например, послед­них m — ρ строк матрицы В линейно зависима. Тогда (5) — линейно зависимая система векторов, и потому вер­но равенство вида (6), среди коэффициентов αi которого есть отличные от нуля. Определим столбец U формулой (4). Поскольку система векторов (2) линейно независи­ма, то U ≠ 0, и U — решение системы (1). Итак, система (1) имеет ненулевое решение вида U. Но тогда столбец Z, который получается из U в результате удаления по­следних m — ρ координат, является ненулевым решением системы (3). Следовательно, столбцы матрицы С линей­но зависимы.

Доказано, что из линейной зависимости каких-либо т — ρ строк матрицы В вытекает линейная зависимость дополняющей системы ρ столбцов матрицы А. Тем самым доказана теорема. <