Войти
В математической теории матроидов представление матроида - это семейство векторов, отношение линейной независимости которых такое же, как у данного матроида. Представления матроидов аналогичны представлениям групп ; оба типа представления обеспечивают абстрактные алгебраические структуры (матроиды и группы соответственно) с конкретными описаниями в терминах линейной алгебры.
Линейный матроид является матроидом, что имеет представление, и F - линейный матроид (для поля F) является матроидом, что имеет представление, используя векторное пространство над F. Теория представлений матроидов изучает существование представлений и свойства линейных матроидов.
(Конечный) матроид определяется конечным набором (элементами матроида) и непустым семейством подмножеств, называемых независимыми наборами матроида. Требуется удовлетворить свойства, заключающиеся в том, что каждое подмножество независимого набора само по себе является независимым, и что если один независимый набор больше, чем второй независимый набор, то существует элемент, который может быть добавлен для формирования большего независимого набора. Одним из ключевых мотивирующих примеров в формулировке матроидов было понятие линейной независимости векторов в векторном пространстве : если - конечное множество или мультимножество векторов, и является семейством линейно независимых подмножеств, то является матроидом.
В более общем смысле, если какой - либо матроид, то представление может быть определена как функция, которая отображает на векторном пространство, со свойством, что подмножество из не зависит тогда и только тогда, когда инъективно и является линейно независимым. Матроид с представлением называется линейным матроидом, а если это векторное пространство над полем F, то матроид называется F -линейным матроидом. Таким образом, линейные матроиды - это в точности те матроиды, которые изоморфны матроидам, определенным из наборов или мультимножеств векторов. Функция будет взаимно однозначной тогда и только тогда, когда лежащий в основе матроид простой (не имеющий двухэлементных зависимых наборов). Представления матроидов также могут быть описаны более конкретно с использованием матриц над полем F, с одним столбцом на каждый элемент матроида и с набором элементов, независимым в матроиде тогда и только тогда, когда соответствующий набор столбцов матрицы является линейно независимым. Оценка функция линейной матроиды задаются матрица ранг подматриц этой матрицы, или, что эквивалентно по размеру в линейной оболочке подмножеств векторов.
Vámos матроид, а не линейное над любым полем 
Конфигурации Perles, линейные над полем вещественных чисел, но не рациональные числа Не каждый матроид является линейным; Восьмиэлементная Vámos матроидом является одним из самых маленьких матроидов, что является непредставимо по всем полям. Если матроид является линейным, он может быть представлен в некоторых, но не во всех полях. Например, матроид третьего ранга, состоящий из девяти элементов, определенный конфигурацией Перлеса, может быть представлен действительными числами, но не рациональными числами.
Бинарные матроиды - это матроиды, которые могут быть представлены над конечным полем GF (2) ; это как раз те матроиды, у которых нет однородного матроида в качестве младшего. Унимодулярные или регулярные матроиды - это матроиды, которые могут быть представлены во всех полях; их можно охарактеризовать как матроиды, не имеющие ни одного из, плоскость Фано (бинарный матроид с семью элементами) или двойственный матроид плоскости Фано в качестве миноров. С другой стороны, матроид является правильным тогда и только тогда, когда он может быть представлен полностью унимодулярной матрицей.
Гипотеза Рота утверждает, что для любого конечного поля F, то F -линейных матроиды можно охарактеризовать конечным множеством запрещенных несовершеннолетними, сходны с характеристиками описанных выше для бинарных и регулярных матроидов. По состоянию на 2012 год это было доказано только для полей из четырех или менее элементов. Для бесконечных полей (таких как поле действительных чисел ) такая характеризация невозможна.
Для каждого поля алгебраических чисел и любого конечного поля F существует матроид M, для которого F является минимальным подполе его алгебраического замыкания над которой М можно представить: M может быть взята из 3 -го ранга.
Набор характеристик линейного матроида определяется как набор характеристик полей, по которым он является линейным. Для каждого простого числа p существует бесконечно много матроидов, характеристическим множеством которых является одноэлементное множество { p }, и для каждого конечного множества простых чисел существует матроид, характеристическим множеством которого является данное конечное множество.
Если характеристический набор матроида бесконечен, он содержит ноль; а если он содержит ноль, то он содержит все, кроме конечного числа простых чисел. Следовательно, единственно возможные характеристические множества - это конечные множества, не содержащие нуля, и кофинитные множества, содержащие ноль. Действительно, все такие множества встречаются.
У однородного матроида есть элементы, а его независимые множества состоят из всех подмножеств до элементов. Равномерные матроиды могут быть представлены наборами векторов общего положения в -мерном векторном пространстве. Поле представления должно быть достаточно большим, чтобы в этом векторном пространстве существовали векторы общего положения, поэтому однородные матроиды F- линейны для всех полей F, кроме конечного числа. То же самое верно и для матроидов разбиения, прямых сумм однородных матроидов, поскольку прямая сумма любых двух F- линейных матроидов сама по себе F- линейна.
График матроидом является матроидом определяется от краев к неориентированного графа путем определения набора ребер, чтобы быть независимым, если и только если он не содержит цикл. Каждый графический матроид регулярно, и, таким образом, является F -линейным для каждого поля F.
В жесткости матроиды описывают степени свободы механических связей, образованных жестких стержней, соединенных на их концах с помощью гибких петель. Связь этого типа может быть описана как граф с ребром для каждого стержня и вершиной для каждого шарнира, а для одномерных связей матроиды жесткости являются в точности графическими матроидами. Матроиды жесткости более высокой размерности могут быть определены с использованием матриц действительных чисел со структурой, аналогичной структуре матрицы инцидентности нижележащего графа, и, следовательно, являются -линейными.
Подобно однородным матроидам и матроидам разбиения, гаммоиды, матроиды, представляющие достижимость в ориентированных графах, линейны по каждому достаточно большому полю. Более конкретно, гаммоид с элементами может быть представлен по каждому полю, которое имеет по крайней мере элементы.
В алгебраических матроидах являются матроидами, определенные из наборов элементов расширения поля, используя понятие алгебраической независимости. Каждый линейный матроид является алгебраическим, и для полей с нулевой характеристикой (например, действительных чисел) линейные и алгебраические матроиды совпадают, но для других полей могут существовать нелинейные алгебраические матроиды.
