В математической теории матроидов представление матроида - это семейство векторов , отношение линейной независимости которых такое же, как у данного матроида. Представления матроидов аналогичны представлениям групп ; оба типа представления обеспечивают абстрактные алгебраические структуры (матроиды и группы соответственно) с конкретными описаниями в терминах линейной алгебры .
Линейный матроид является матроидом , что имеет представление, и F - линейный матроид (для поля F ) является матроидом , что имеет представление , используя векторное пространство над F . Теория представлений матроидов изучает существование представлений и свойства линейных матроидов.
Определения
(Конечный) матроид определяется конечным множеством (элементы матроида) и непустое семейство из подмножеств , называемые независимыми множествами матроида. Требуется удовлетворить свойства, заключающиеся в том, что каждое подмножество независимого набора само по себе является независимым, и что если один независимый набор больше, чем второй независимый набор тогда существует элемент что можно добавить к чтобы сформировать более крупный независимый набор. Одним из ключевых мотивирующих примеров при формулировании матроидов было понятие линейной независимости векторов в векторном пространстве : если конечное множество или мультимножество векторов, и семейство линейно независимых подмножеств , тогда это матроид. [1] [2]
В более общем смысле, если любой матроид, то представление можно определить как функцию что отображает в векторное пространство , со свойством, что подмножество из является независимым тогда и только тогда, когда инъективен и линейно независима. Матроид с представлением называется линейным матроидом, и еслиявляется векторным пространством над полем F, то матроид называется F -линейным матроидом. Таким образом, линейные матроиды - это в точности матроиды, которые изоморфны матроидам, определенным из наборов или мультимножеств векторов. Функциябудет взаимно однозначным тогда и только тогда, когда лежащий в основе матроид простой (не имеющий двухэлементных зависимых наборов). Представления матроидов также могут быть описаны более конкретно с использованием матриц над полем F , с одним столбцом на каждый элемент матроида и с набором элементов, независимым в матроиде тогда и только тогда, когда соответствующий набор столбцов матрицы является линейно независимым. Оценка функция линейной матроиды задаются матрица ранг подматриц этой матрицы, или , что эквивалентно по размеру в линейной оболочке подмножеств векторов. [3]
Характеристика линейных матроидов
Не каждый матроид является линейным; Восьмиэлементная Vámos матроидом является одним из самых маленьких матроидов , что является непредставимо по всем полям. [4] Если матроид является линейным, он может быть представлен в некоторых, но не во всех полях. Например, матроид третьего ранга из девяти элементов, определенный конфигурацией Перлеса, может быть представлен в виде действительных чисел, но не в виде рациональных чисел .
Бинарные матроиды - это матроиды, которые могут быть представлены над конечным полем GF (2) ; это именно те матроиды, у которых нет однородного матроида как несовершеннолетний . [5] Унимодулярные или регулярные матроиды - это матроиды, которые могут быть представлены во всех полях; [6] их можно охарактеризовать как матроидов, не имеющих, плоскость Фано (бинарный матроид с семью элементами) или двойственный матроид плоскости Фано в качестве миноров. [5] [7] В качестве альтернативы, матроид является правильным тогда и только тогда, когда он может быть представлен полностью унимодулярной матрицей . [8]
Гипотеза Рота утверждает , что для любого конечного поля F , то F -линейных матроиды можно охарактеризовать конечным множеством запрещенных несовершеннолетними, сходны с характеристиками описанных выше для бинарных и регулярных матроидов. [9] По состоянию на 2012 год это было доказано только для полей из четырех или менее элементов. [5] [10] [11] [12] Для бесконечных полей (таких как поле действительных чисел ) такая характеризация невозможна. [13]
Поле определения
Для каждого поля алгебраических чисел и любого конечного поля F существует матроид М , для которых F является минимальным подполе его алгебраического замыкания , над которой М может быть представлена: М может быть взята ранга 3. [14]
Набор характеристик
Набор характеристик линейного матроида определяется как набор характеристик полей, по которым он является линейным. [15] Для каждого простого числа p существует бесконечно много матроидов, характеристическим множеством которых является одноэлементное множество { p }, [16] и для каждого конечного множества простых чисел существует матроид, характеристическим множеством которого является данное конечное множество. [17]
Если характеристический набор матроида бесконечен, он содержит ноль; а если он содержит ноль, то он содержит все, кроме конечного числа простых чисел. [18] Следовательно, единственными возможными характеристическими множествами являются конечные множества, не содержащие нуля, и кофинитные множества, содержащие ноль. [19] Действительно, все такие множества встречаются. [20]
Родственные классы матроидов
Равномерный матроид имеет элементов, а его независимые множества состоят из всех подмножеств до элементов. Однородные матроиды могут быть представлены наборами векторов общего положения в-мерное векторное пространство. Поле представления должно быть достаточно большим, чтобы оно могло существовать.векторов общего положения в этом векторном пространстве, поэтому однородные матроиды являются F- линейными для всех полей F, кроме конечного числа . [21] То же самое верно и для матроидов разбиений , прямых сумм однородных матроидов, поскольку прямая сумма любых двух F- линейных матроидов сама является F- линейной.
График матроидом является матроидом определяется от краев к неориентированного графа путем определения набора ребер , чтобы быть независимым , если и только если он не содержит цикл . Каждый графический матроид регулярно, и , таким образом , является F -линейным для каждого поля F . [8]
В жесткости матроиды описывают степени свободы механических связей , образованных жестких стержней , соединенных на их концах с помощью гибких петель. Связь этого типа может быть описана как граф с ребром для каждого стержня и вершиной для каждого шарнира, а для одномерных связей матроиды жесткости являются в точности графическими матроидами. Матроиды жесткости более высокой размерности могут быть определены с использованием матриц действительных чисел со структурой, аналогичной структуре матрицы инцидентности нижележащего графа, и, следовательно, являются-линейный. [22] [23]
Подобно однородным матроидам и матроидам разбиения, гаммоиды , матроиды, представляющие достижимость в ориентированных графах , линейны по каждому достаточно большому полю. В частности, гаммоид с элементы могут быть представлены в каждом поле, которое имеет не менее элементы. [24]
В алгебраических матроидах являются матроидами , определенные из наборов элементов расширения поля , используя понятие алгебраической независимости . Каждый линейный матроид является алгебраическим, и для полей с нулевой характеристикой (например, действительных чисел) линейные и алгебраические матроиды совпадают, но для других полей могут существовать нелинейные алгебраические матроиды. [25]
Рекомендации
- ^ Оксли, Джеймс Г. (2006), Теория матроидов , Тексты для выпускников Оксфорда по математике, 3 , Oxford University Press, стр. 8, ISBN 9780199202508. Относительно функции ранга см. Стр. 26.
- ^ Валлийский, DJA (2010), Теория матроидов , Courier Dover Publications, стр. 10, ISBN 9780486474397.
- ^ Оксли (2006) , стр. 12.
- Перейти ↑ Oxley (2006) , pp. 170–172, 196.
- ^ а б в Tutte, WT (1958), "Гомотопия теорема для матроидов I, II.", Труды Американского математического общества , 88 : 144-174, DOI : 10,2307 / 1993244 , MR 0101526.
- ↑ Белый (1987) стр.2
- ^ White (1987) с.12
- ^ а б Tutte, WT (1965), "Лекция по матроидам" , Журнал исследований Национального бюро стандартов , 6 : 1-47, DOI : 10,6028 / jres.069b.001 , MR 0179781.
- ^ Рота, Джан-Карло (1971), «Комбинаторная теория, старая и новая», Actes du Congrès International des Mathématiciens (Ницца, 1970), Том 3 , Париж: Готье-Виллар, стр. 229–233, MR 0505646.
- ^ Биксби, Роберт Е. (1979), "О характеризации Рейда тройных матроидов", Журнал комбинаторной теории , серии B, 26 (2): 174-204, DOI : 10.1016 / 0095-8956 (79) 90056-X , Руководство по ремонту 0532587.
- ^ Seymour, PD (1979), "матроида представление над GF (3)", Журнал комбинаторной теории , Series B, 26 (2): 159-173, DOI : 10,1016 / 0095-8956 (79) 90055-8 , МР 0532586.
- ^ Geelen, JF ; Джерардс, AMH; Капур, A. (2000), "Исключенные несовершеннолетних для GF (4) -представимых матроиды" (PDF) , Журнал комбинаторной теории , серии B, 79 (2): 247-299, DOI : 10,1006 / jctb.2000.1963 , MR 1769191 , архивировано из оригинала (PDF) 24 сентября 2010 г..
- ^ Вамос П. (1978), «Недостающая аксиома теории матроидов потеряна навсегда», Журнал Лондонского математического общества , вторая серия, 18 (3): 403–408, doi : 10.1112 / jlms / s2-18.3.403 , MR 0518224.
- ^ Уайт, Нил, изд. (1987), Комбинаторные геометрии , Энциклопедия математики и ее приложений, 29 , Кембридж: Издательство Кембриджского университета , стр. 18 , ISBN 0-521-33339-3, Zbl 0626,00007
- ^ Инглтон, AW (1971), «Представление матроидов», на валлийском языке, DJA (ред.), Комбинаторная математика и ее приложения. Proceedings, Oxford, 1969 , Academic Press, стр. 149–167, ISBN 0-12-743350-3, Zbl 0222,05025
- ^ Оксли, Джеймс; Семпл, Чарльз; Вертиган, Дирк; Уиттл, Джефф (2002), «Бесконечные антицепи матроидов с характеристическим набором { p }», Дискретная математика , 242 (1–3): 175–185, DOI : 10.1016 / S0012-365X (00) 00466-0 , hdl : 10092/13245 , Руководство по ремонту 1874763.
- ^ Кан, Джефф (1982), "Характерные наборы матроидов", журнал Лондонского математического общества , вторая серия, 26 (2): 207-217, DOI : 10,1112 / jlms / s2-26.2.207 , MR 0675165 , Zbl 0468,05020.
- ^ Оксли (2006) , стр. 225.
- ^ Оксли (2006) , стр. 226.
- ^ Оксли (2006) , стр. 228.
- ^ Оксли (2006) , стр. 100.
- ^ Гравер, Джек Е. (1991), "Жесткость матроиды", SIAM журнал по дискретной математике , 4 (3): 355-368, DOI : 10,1137 / 0404032 , МР 1105942.
- ^ Whiteley, Вальтер (1996), "Некоторые матроиды из дискретной прикладной геометрии", матроидных теории (Сиэтл, Вашингтон, 1995) , Современная математика, 197 , Providence, RI: Американское математическое общество, стр 171-311,. Дои : 10,1090 / conm / 197/02540 , Руководство по ремонту 1411692.
- ^ Линдстр, Бернт (1973), «О векторных представлениях , индуцированные матроидов», Бюллетень Лондонского математического общества , 5 : 85-90, DOI : 10,1112 / БЛХ / 5.1.85 , МР 0335313.
- ^ Инглтон, AW (1971), "Представление матроидов", Комбинаторная математика и ее приложения (Proc. Conf., Oxford, 1969) , Лондон: Academic Press, стр. 149–167, MR 0278974.