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

В математической теории матроидов — представление матроида это семейство векторов которых , линейное отношение независимости такое же, как и у данного матроида. Представления матроидов аналогичны представлениям групп ; оба типа представления предоставляют абстрактные алгебраические структуры (матроиды и группы соответственно) с конкретным описанием в терминах линейной алгебры .

Линейный матроид — это матроид, имеющий представление, а F - линейный матроид (для поля F — это матроид, имеющий представление с использованием векторного пространства над F. ) Теория представлений матроидов изучает существование представлений и свойства линейных матроидов.

Определения

(Конечный) матроид $(E,{\mathcal {I}})$ определяется конечным множеством $E$ (элементы матроида) и непустое семейство ${\mathcal {I}}$ из подмножеств $E$, называемые независимыми множествами матроида. Требуется удовлетворить свойства, согласно которым каждое подмножество независимого множества само по себе является независимым и что если одно независимое множество $A$ больше, чем второй независимый набор $B$ тогда существует элемент $x\in A\setminus B$ что можно добавить в $B$ чтобы сформировать более крупный независимый набор. Одним из ключевых мотивирующих примеров при формулировке матроидов было понятие линейной независимости векторов в векторном пространстве : если $E$ представляет собой конечное множество или мультимножество векторов, а ${\mathcal {I}}$ — семейство линейно независимых подмножеств $E$, затем $(E,{\mathcal {I}})$ это матроид.

В более общем смысле, если $(E,{\mathcal {I}})$ — любой матроид, то представление $(E,{\mathcal {I}})$ может быть определена как функция $f$ это отображает $E$ в векторное пространство $V$, обладающий тем свойством, что подмножество $A$ из $E$ независим тогда и только тогда, когда $f|_{A}$ является инъективным и $f(A)$ линейно независима. Матроид с представлением называется линейным матроидом, и если $V$ является векторным пространством над полем F , то матроид называется F -линейным матроидом. Таким образом, линейные матроиды — это в точности матроиды, изоморфные матроидам, определенным из множеств или мультимножеств векторов. Функция $f$ будет взаимно однозначным тогда и только тогда, когда базовый матроид прост (не имеет двухэлементных зависимых множеств). Представления матроида также могут быть описаны более конкретно с использованием матриц над полем F , с одним столбцом на элемент матроида и с набором элементов, независимых в матроиде тогда и только тогда, когда соответствующий набор столбцов матрицы линейно независим. Функция ранга линейного матроида задается матричным рангом подматриц этой матрицы или, что то же самое, размерностью линейной оболочки подмножеств векторов.

Характеристика линейных матроидов

Матроид Вамоса , не линейный ни в каком поле.

, Конфигурация Перля линейная по действительным, но не рациональным числам.

Не каждый матроид линеен; восьмиэлементный матроид Вамоса — один из самых маленьких матроидов, который непредставим во всех полях. Если матроид линеен, его можно представить в некоторых, но не во всех полях.Например, девятиэлементный матроид третьего ранга, определенный конфигурацией Перля, представим в действительных числах , но не в рациональных числах .

Бинарные матроиды — это матроиды, которые могут быть представлены в конечном поле GF(2) ; это именно те матроиды, у которых нет единого матроида $U{}_{4}^{2}$ как несовершеннолетний . Унимодулярные или регулярные матроиды — это матроиды, которые могут быть представлены во всех полях; их можно охарактеризовать как матроидов, у которых нет ни одного из $U{}_{4}^{2}$, плоскость Фано (двоичный матроид с семью элементами) или двойственный матроид плоскости Фано как миноры. Альтернативно, матроид является регулярным тогда и только тогда, когда его можно представить полностью унимодулярной матрицей .

Гипотеза Роты утверждает, что для каждого конечного поля F F -линейные матроиды могут характеризоваться конечным набором запрещенных миноров, аналогично описанным выше характеристикам для бинарных и регулярных матроидов. По состоянию на 2012 год это было доказано только для полей из четырех и менее элементов. Для бесконечных полей (таких как поле действительных чисел ) такая характеристика невозможна.

Область определения

Для каждого поля алгебраических чисел и каждого конечного поля F существует матроид M, для которого F является минимальным подполем его алгебраического замыкания, над которым M может быть представлено: M можно взять ранга 3.

Набор характеристик

Характеристический набор линейного матроида определяется как набор характеристик полей, над которыми он линеен. Для каждого простого числа p существует бесконечно много матроидов, характеристическим набором которых является одноэлементный набор { p }, и для каждого конечного набора простых чисел существует матроид, характеристическое множество которого является заданным конечным множеством.

Если характеристическое множество матроида бесконечно, оно содержит ноль; и если оно содержит ноль, то оно содержит все простые числа, кроме конечного числа. Следовательно, единственными возможными характеристическими множествами являются конечные множества, не содержащие нуля, и коконитные множества, содержащие ноль. Действительно, все такие множества встречаются.

Родственные классы матроидов

матроида Униформа $U{}_{n}^{r}$ имеет $n$ элементов, а его независимые множества состоят из всех подмножеств размером до $r$ элементов. Однородные матроиды могут быть представлены наборами векторов общего положения в $r$-мерное векторное пространство. Поле репрезентации должно быть достаточно большим, чтобы существовало $n$ векторы общего положения в этом векторном пространстве, поэтому равномерные матроиды F кроме конечного числа -линейны для всех полей F, . То же самое верно и для матроидов разбиения , прямых сумм однородных матроидов, поскольку прямая сумма любых двух F -линейных матроидов сама по себе является F -линейной.

Графический матроид — это матроид, определенный из ребер неориентированного графа путем определения набора ребер, которые будут независимыми тогда и только тогда, когда он не содержит цикла . Каждый графический матроид является регулярным и, следовательно, - линейным для любого поля F. F

Матроиды жесткости описывают степени свободы механических связей, образованных жесткими стержнями, соединенными на концах гибкими шарнирами. Связь этого типа можно описать как граф с ребром для каждого стержня и вершиной для каждого шарнира, а для одномерных связей матроиды жесткости являются в точности графическими матроидами. Матроиды жесткости более высокой размерности могут быть определены с использованием матриц действительных чисел со структурой, аналогичной структуре матрицы инцидентности основного графа, и, следовательно, являются $\mathbb {R}$-линейный.

Подобно однородным матроидам и матроидам разбиения, гаммоиды , матроиды, представляющие достижимость в ориентированных графах , линейны в каждом достаточно большом поле. Точнее, гаммоид с $n$ элементы могут быть представлены в каждом поле, имеющем хотя бы $2^{n}$ элементы.

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