Jump to content

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

(Перенаправлено с Линейного матроида )

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

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

Определения

[ редактировать ]

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

В более общем смысле, если — любой матроид, то представление может быть определена как функция это отображает в векторное пространство , обладающий тем свойством, что подмножество из независим тогда и только тогда, когда является инъективным и линейно независима. Матроид с представлением называется линейным матроидом, и если является векторным пространством над полем F , то матроид называется F -линейным матроидом. Таким образом, линейные матроиды — это в точности матроиды, изоморфные матроидам, определенным из множеств или мультимножеств векторов. Функция будет взаимно однозначным тогда и только тогда, когда базовый матроид прост (не имеет двухэлементных зависимых множеств). Представления матроида также могут быть описаны более конкретно с использованием матриц над полем F , с одним столбцом на элемент матроида и с набором элементов, независимых в матроиде тогда и только тогда, когда соответствующий набор столбцов матрицы линейно независим. Функция ранга линейного матроида задается матричным рангом подматриц этой матрицы или, что то же самое, размерностью линейной оболочки подмножеств векторов. [3]

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

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

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

Бинарные матроиды — это матроиды, которые могут быть представлены в конечном поле GF(2) ; это именно те матроиды, у которых нет единого матроида как несовершеннолетний . [5] Унимодулярные или регулярные матроиды — это матроиды, которые могут быть представлены во всех полях; [6] их можно охарактеризовать как матроидов, у которых нет ни одного , плоскость Фано (двоичный матроид с семью элементами) или двойственный матроид плоскости Фано как миноры. [5] [7] Альтернативно, матроид является регулярным тогда и только тогда, когда его можно представить полностью унимодулярной матрицей . [8]

Гипотеза Роты утверждает, что для каждого конечного поля 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 -линейной.

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

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

Подобно однородным матроидам и матроидам разбиения, гаммоиды , матроиды, представляющие достижимость в ориентированных графах , линейны в каждом достаточно большом поле. Точнее, гаммоид с элементы могут быть представлены в каждом поле, имеющем хотя бы элементы. [24]

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

  1. ^ Оксли, Джеймс Г. (2006), Теория матроидов , Тексты для выпускников Оксфорда по математике, том. 3, Издательство Оксфордского университета, с. 8, ISBN  9780199202508 . О ранговой функции см. с. 26.
  2. ^ Уэлш, DJA (2010), Теория Матроидов , Courier Dover Publications, стр. 10, ISBN  9780486474397 .
  3. ^ Оксли (2006) , с. 12.
  4. ^ Оксли (2006) , стр. 170–172, 196.
  5. ^ Jump up to: а б с Тутте, В.Т. (1958), «Гомотопическая теорема для матроидов. I, II», Труды Американского математического общества , 88 : 144–174, doi : 10.2307/1993244 , MR   0101526 .
  6. ^ Белый (1987) стр.2
  7. ^ Белый (1987) стр.12
  8. ^ Jump up to: а б Тутте, WT (1965), «Лекции по матроидам» , Журнал исследований Национального бюро стандартов , 69B : 1–47, doi : 10.6028/jres.069b.001 , MR   0179781 .
  9. ^ Рота, Джан-Карло (1971), «Комбинаторная теория, старая и новая», Труды Международного конгресса математиков (Ницца, 1970), Том 3 , Париж: Готье-Виллар, стр. 229–233, МР   0505646 .
  10. ^ Биксби, Роберт Э. (1979), «О характеристике Ридом троичных матроидов», Журнал комбинаторной теории , серия B, 26 (2): 174–204, doi : 10.1016/0095-8956(79)90056-X , МР   0532587 .
  11. ^ Сеймур, П.Д. (1979), «Матроидное представление над GF(3)», Журнал комбинаторной теории , серия B, 26 (2): 159–173, doi : 10.1016/0095-8956(79)90055-8 , MR   0532586 .
  12. ^ Гилен, Дж. Ф. ; Джерардс, AMH; Капур, А. (2000), «Исключенные миноры для GF(4)-представимых матроидов» (PDF) , Journal of Combinatorial Theory , Series 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 , МР   0518224 .
  14. ^ Уайт, Нил, изд. (1987), Комбинаторная геометрия , Энциклопедия математики и ее приложений, том. 29, Кембридж: Издательство Кембриджского университета , с. 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 }», Discrete Mathematics , 242 (1–3): 175–185, doi : 10.1016/S0012-365X(00)00466-0 , hdl : 10092/13245 , МР   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, vol. 197, Провиденс, Род-Айленд: Американское математическое общество, стр. 171–311, doi : 10.1090/conm/197/02540 , MR   1411692 .
  24. ^ Линдстрем, Бернт (1973), «О векторных представлениях индуцированных матроидов», Бюллетень Лондонского математического общества , 5 : 85–90, doi : 10.1112/blms/5.1.85 , MR   0335313 .
  25. ^ Инглтон, AW (1971), «Представление матроидов», Комбинаторная математика и ее приложения (Proc. Conf., Oxford, 1969) , Лондон: Academic Press, стр. 149–167, MR   0278974 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: b15dcbfd3f84e29ddf4acdf6f309451d__1691916960
URL1:https://arc.ask3.ru/arc/aa/b1/1d/b15dcbfd3f84e29ddf4acdf6f309451d.html
Заголовок, (Title) документа по адресу, URL1:
Matroid representation - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)