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

Vectors with given pattern of independence

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

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

Определения

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

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

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

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

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

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

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

Гипотеза Роты утверждает, что для любого конечного поля F F -линейные матроиды могут быть охарактеризованы конечным набором запрещённых миноров, аналогично характеристикам, описанным выше для бинарных и регулярных матроидов. ^[9] По состоянию на 2012 год это было доказано только для полей из четырёх или менее элементов. [ ^{5] [10] [11] [12]} Для бесконечных полей (таких как поле действительных чисел ) такая характеристика невозможна. ^[13]

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

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

Характерный набор

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

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

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

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

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

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

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

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

Ссылки

1. Оксли, Джеймс Г. (2006), Теория матроидов , Oxford Graduate Texts in Mathematics, т. 3, Oxford University Press, стр. 8, ISBN 9780199202508. О ранговой функции см. стр. 26.
2. Валлийский, DJA (2010), Теория Матроидов , Courier Dover Publications, стр. 10, ISBN 9780486474397.
3. Оксли (2006), стр. 12.
4. Оксли (2006), стр. 170–172, 196.
5. Tutte, WT (1958), «Гомотопическая теорема для матроидов. I, II», Transactions of the American Mathematical Society , 88 (1): 144–174, doi :10.2307/1993244, JSTOR  1993244, MR  0101526.
6. Уайт (1987) стр.2
7. Уайт (1987) стр.12
8. Tutte, WT (1965), «Лекции о матроидах», Журнал исследований Национального бюро стандартов , 69B : 1–47, doi : 10.6028/jres.069b.001 , MR  0179781.
9. Рота, Джан-Карло (1971), «Комбинаторная теория, старая и новая», Actes du Congrès International des Mathématiciens (Ницца, 1970), Том 3 , Париж: Готье-Виллар, стр. 229–233, MR  0505646.
10. Биксби, Роберт Э. (1979), «О характеристике тернарных матроидов по Риду», Журнал комбинаторной теории , Серия B, 26 (2): 174–204, doi : 10.1016/0095-8956(79)90056-X , MR  0532587.
11. Сеймур, PD (1979), «Представление матроида над GF(3)», Журнал комбинаторной теории , Серия B, 26 (2): 159–173, doi : 10.1016/0095-8956(79)90055-8 , MR  0532586.
12. Geelen, JF ; Gerards, AMH; Kapoor, A. (2000), «Исключенные миноры для GF(4)-представимых матроидов» (PDF) , Журнал комбинаторной теории , Серия B, 79 (2): 247–299, doi :10.1006/jctb.2000.1963, MR  1769191, архивировано из оригинала (PDF) 24 сентября 2010 г..
13. Вамос, П. (1978), «Отсутствующая аксиома теории матроидов утеряна навсегда», Журнал Лондонского математического общества , Вторая серия, 18 (3): 403–408, doi :10.1112/jlms/s2-18.3.403, MR  0518224.
14. Уайт, Нил, ред. (1987), Комбинаторные геометрии, Энциклопедия математики и ее приложений, т. 29, Кембридж: Cambridge University Press , стр. 18, ISBN 0-521-33339-3, ЗБЛ  0626.00007
15. Инглтон, AW (1971), "Представление матроидов", на валлийском, DJA (ред.), Комбинаторная математика и ее приложения. Труды, Оксфорд, 1969 , Academic Press, стр. 149–167, ISBN 0-12-743350-3, ЗБЛ  0222.05025
16. Оксли, Джеймс; Семпл, Чарльз; Вертиган, Дирк; Уиттл, Джефф (2002), «Бесконечные антицепи матроидов с характеристическим множеством { p }», Дискретная математика , 242 (1–3): 175–185, doi :10.1016/S0012-365X(00)00466-0, hdl : 10092/13245 , MR  1874763.
17. Кан, Джефф (1982), «Характерные множества матроидов», Журнал Лондонского математического общества , Вторая серия, 26 (2): 207–217, doi :10.1112/jlms/s2-26.2.207, MR  0675165, Zbl  0468.05020.
18. Оксли (2006), стр. 225.
19. Оксли (2006), стр. 226.
20. Оксли (2006), стр. 228.
21. Оксли (2006), стр. 100.
22. Грейвер, Джек Э. (1991), «Жесткие матроиды», SIAM Journal on Discrete Mathematics , 4 (3): 355–368, doi :10.1137/0404032, MR  1105942.
23. Уайтли, Уолтер (1996), «Некоторые матроиды из дискретной прикладной геометрии», Теория матроидов (Сиэтл, Вашингтон, 1995) , Contemporary Mathematics, т. 197, Провиденс, Род-Айленд: Американское математическое общество, стр. 171–311, doi : 10.1090/conm/197/02540 , ISBN 978-0-8218-0508-4, г-н  1411692.
24. Линдстрём, Бернт (1973), «О векторных представлениях индуцированных матроидов», Бюллетень Лондонского математического общества , 5 : 85–90, doi :10.1112/blms/5.1.85, MR  0335313.
25. Инглтон, AW (1971), «Представление матроидов», Комбинаторная математика и ее приложения (Proc. Conf., Оксфорд, 1969) , Лондон: Academic Press, стр. 149–167, MR  0278974.