В теории групп, алгоритм Тодда — Коксетера, найденный Дж. А. Тоддом и Коксетером в 1936 году, является алгоритмом для решения проблемы перечисления смежных классов. Для конкретных задания группы и подгруппы в , алгоритм перечисляет смежные классы по и описывает представление перестановками на пространстве смежных классов.
Если порядок группы является относительно небольшим, и подгруппа является несложной (например, циклическая группа), то алгоритм может быть выполнен вручную и дает удобное описание группы . Используя свой алгоритм, Коксетер и Тодд показали, что конкретные системы соотношений между порождающими элементами некоторых известных групп полны, то есть составляют систему определяющих соотношений.
Алгоритм Тодда-Коксетера может быть применен к бесконечным группам и завершается после конечного числа шагов при условии, что индекс в конечен. С другой стороны, в общем случае для пары, состоящей из задания группы и подгруппы, количество его шагов не ограничено никакой вычислимой функцией индекса подгруппы и размера данных.
Выполнение алгоритма проходит следующим образом. Предположим это , где — множество образующих, — множество соотношений. Множество образующих и их инверсий обозначим . Пусть где — элементы . Есть три типа матриц, которые будут использоваться: смежный класс матриц, матрицы соотношения для каждого соотношения в , и матрицы подгруппы для каждого множества образующих от . Информация постепенно добавляется к этим матрицам, и как только они будут заполнены, все смежные классы будут перечислены, и алгоритм закончится. Смежный класс матриц используется, чтобы хранить соотношения между известными смежными классами при умножении множеством образующих. Это имеет ряды, представляющие смежные классы и колонки для каждого элемента . Пусть обозначает смежные классы -того ряда смежных классов матриц, и пусть обозначает множество образующих -той колонки. Ввод смежных классов матриц последователен, и определены так, чтобы было (если известно) , где — такое, что . Соотношения матриц используются, чтобы обнаружить, когда некоторые из смежных классов, которые мы нашли, фактически эквивалентны. Выполняется: одно соотношение матриц для каждого соотношения в . Пусть — соотношение в , где gni ОX' . матриц соотношения имеет ряды, представляющие смежных классов H, как в смежных классов матриц. Это имеет колонки, и ввод в -том ряду и -том колонке определен, чтобы быть (если известно) , где Ck=Cig1g2...gj. В частности i-тый вход - первоначально i, пока . Наконец, матрицы подгруппы подобны матрицам соотношения, за исключением того, что они держат след возможных соотношений множества образующих H. Для каждого множества образующих hn=gn1gn2...gnt из H, с gniОH', мы создаем матрицу подгруппы. Это имеет только один ряд, соответствуя смежным классам H непосредственно. Это имеет t колонки, и вход в j-той колонке определен (если известно), чтобы быть k, где . Когда ряд соотношения или матриц подгруппы закончен, новая информация найдена. Это известно как вычитание. От вычитания, мы можем быть в состоянии заполнить в дополнительных записях соотношения и матриц подгруппы, приводя к возможному дополнительному вычитанию. Мы можем заполниться в записях смежных классах матриц, соответствующего уравнениям и . Однако, заполняясь в смежных классах матриц, возможно, что мы можем уже иметь ввод для уравнения, но ввод имеет различную ценность. В этом случае, мы обнаружили, что два из наших смежных классов - фактически то же самое, известные как совпадение. Предположим , с . Мы заменяем все случаи j в матриц с i. Тогда, мы заполняем во всех возможных записях матриц, возможно приводя к большему количеству вычитания и совпадений. Если есть пустые записи в матрице после всего вычитания, и о совпадениях заботились, добавляем новый смежный класс к матрице и повторяем процесс. Мы удостоверяемся, что, добавляя смежный класс, если Hx - известный смежный класс, то Hxg будет добавлен в некоторый момент для всех . (Это необходимо, чтобы гарантировать, что алгоритм закончится обеспеченный конечен.) Когда все матрицы заполнены, алгоритм заканчивается. Мы получили всю информацию о действии G на смежные классы H.
| Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её. |
Алгоритм Тодда-Коксетера.