Таблица Кэли

Таблица Кэли

12.11.2020

Таблица Кэли — таблица, которая описывает структуру конечных алгебраических систем путём расположения результатов операции в таблице, напоминающей таблицу умножения. Названа в честь английского математика Артура Кэли. Таблица имеет важное значение в дискретной математике, в частности, в теории групп. Таблица позволяет выяснить некоторые свойства группы, например, является ли группа абелевой, найти центр группы и обратные элементы элементов группы.

В высшей алгебре таблицы Кэли могут также использоваться для определения бинарных операций в полях, кольцах и других алгебраических структурах.

Простой пример таблицы Кэли для группы {1, −1} с обычным умножением:

История

Таблицы Кэли впервые появились в статье Кэли «On The Theory of Groups, as depending on the symbolic equation θ n = 1» в 1854 году. В этой статье это были просто таблицы, используемые в иллюстративных целях. Называть таблицами Кэли их стали позже в честь их создателя.

Структура

Поскольку многие таблицы Кэли описывают группы, не являющиеся абелевыми, произведение ab не обязательно равно произведению ba для всех a и b в группе. Чтобы избежать путаницы, принимается, что множитель, соответствующий строкам, идёт первым, а множитель, соответствующий столбцам — вторым. Например, пересечение строки a и столбца b — это ab, а не ba, что показано в следующем примере:

Кэли в своей работе в первой строке и первом столбце размещал нейтральный элемент, что позволяло ему не выделять отдельных строки и столбца с указанием элементов, как это видно в примере выше. Например, та же самая таблица представлялась в виде:

В этом примере циклической группы Z3 элемент a является нейтральным элементом, и он появляется в верхнем левом углу таблицы. Легко видеть, например, что b2 = c и что cb = a. Вопреки этому большинство современных текстов, включая и эту статью, включают заголовочные строку и столбец для большей ясности.

Свойства и использование

Коммутативность

Таблица Кэли показывает нам, является ли группа абелевой. Поскольку групповая операция в абелевой группе коммутативна, группа является абелевой в том и только в том случае, когда её таблица Кэли симметрична (относительно диагонали). Циклическая группа порядка 3 выше, а также {1, −1} по обычному умножению, обе являются примерами абелевых групп, и симметрия их таблиц Кэли доказывает это. А вот наименьшая неабелева диэдральная группа шестого порядка не имеет симметрии в таблице Кэли.

Ассоциативность

Поскольку ассоциативность в группах присутствует по определению, часто она предполагается и в таблицах Кэли. Однако таблицы Кэли можно использовать для описания операций в квазигруппах, в которых ассоциативность не требуется (более того, таблицы Кэли можно использовать для описания операции в любой конечной магме). К сожалению, в общем случае невозможно простым обзором таблицы определить, ассоциативна операция или нет, в отличие от коммутативности. Это обусловлено тем, что ассоциативность зависит от трёх элементов в равенстве, ( a b ) c = a ( b c ) {displaystyle (ab)c=a(bc)} , в то время как таблица Кэли показывает произведения двух элементов. Тем не менее, тест ассоциативности Лайта может определить ассоциативность с меньшими усилиями, чем грубый перебор.

Перестановки

Поскольку сокращение для групп выполняется (более того, выполняется даже для квазигрупп), никакая строка или столбец таблицы Кэли не может содержать один элемент дважды. Таким образом, каждая строка и столбец таблицы является перестановкой элементов группы.

Чтобы увидеть, почему строки и столбцы не могут содержать одинаковых элементов, положим a, x и y — элементы группы, при этом x и y различны. Теперь в строке, соответствующей элементу a, и столбце, соответствующем элементу x, будет находиться произведение ax. Аналогично в столбце, соответствующем y, будет находиться ay. Пусть два произведения равны, то есть строка a содержит элемент дважды. По правилу сокращения мы из ax = ay можем заключить, что x = y, что противоречит выбору x и y. Точно те же рассуждения верны и для столбцов. Ввиду конечности группы по принципу Дирихле каждый элемент группы будет представлен в точности по одному разу в каждой строке и в каждом столбце.

То есть таблица Кэли для группы является примером латинского квадрата.

Построение таблиц Кэли для групп

Используя структуру групп, часто можно «заполнить» таблицы Кэли, которые имеют незаполненные поля, даже не зная ничего об операции группы. Например, поскольку каждая строка и каждый столбец должны содержать все элементы группы, один отсутствующий элемент в строке (или столбце) можно заполнить, совершенно не зная ничего о группе. Это показывает, что это свойство и некоторые другие свойства групп дают возможность построения таблиц Кэли, даже если мы мало что знаем о группе.

«Скелет нейтральных элементов» конечной группы

Поскольку в любой группе, даже не в абелевой, любой элемент перестановочен со своим обратным, распределение нейтральных элементов в таблице Кэли симметрично относительно диагонали. Нейтральные элементы, лежащие на диагонали, соответствуют элементам, совпадающим со своими обратными.

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

Теперь для конечной группы некоторого порядка легко определить «скелет нейтральных элементов», названный так по той причине, что нейтральные элементы либо лежат на главной диагонали, либо рядом с ней.

Относительно легко доказать, что группы с различными скелетами не могут быть изоморфны, однако обратное неверно (например, циклическая группа C8 и группа кватерионов Q не изоморфны, хотя и имеют одинаковые скелеты).

Пусть имеется шесть элементов группы e, a, b, c, d и f. Пусть e — нейтральный элемент. Поскольку нейтральный элемент совпадает со своим обратным, а обратный элемент единственен, должен быть, по крайней мере, ещё один элемент, совпадающий со своим обратным. Таким образом, получаем следующие возможные скелеты:

  • все элементы совпадают со своими обратными,
  • все элементы, за исключением d и f, совпадают со своими обратными, а эти два обратны друг другу,
  • a совпадает со своим обратным, b и c обратны, d и f обратны.

В нашем случае не существует группы первого типа порядка 6. Более того, из того, что скелет возможен, совсем не следует, что существует группа, у которой скелет совпадает с ним.

Заслуживает внимание факт (и его легко доказать) что любая группа, в которой любой элемент совпадает с его обратным, абелева.

Заполнение таблицы по скелету нейтральных элементов

Если задан скелет нейтральных элементов, можно приступить к заполнению таблицы Кэли. Например, выберем второй скелет группы порядка 6 из описанных выше:

Очевидно, что строка e и столбец e могут быть заполнены немедленно. Как только это сделано, может оказаться необходимым (и это необходимо в нашем случае) сделать предположение, которое впоследствии может привести к противоречию, что будет означать, что предположение неверно. Мы предположим, что ab = c. Тогда:

Умножая ab = c слева на a, получим b = ac. Умножение справа на c даёт bc = a. Умножение ab = c справа на b даёт a = cb. Умножение bc = a слева на b даёт c = ba, а умножение справа на a даёт ca = b. После заполнения этих произведений в таблице мы обнаружим, что ad и af остаются незаполненными в строке a. Поскольку каждый элемент должен появиться в строке ровно один раз, получим, что ad должен быть либо d, либо f. Однако этот элемент не может равняться d, поскольку в противном случае a был бы равен e, в то время как мы знаем, что эти два элемента различны. Таким образом, ad = f и af = d.

Теперь, поскольку обратный элементу d есть f, умножение ad = f справа на f даёт a = f2. Умножение слева на d даёт da = f. Умножив справа на a, мы получим d = fa.

После внесения всех этих произведений таблица Кэли примет вид:

Поскольку каждый элемент группы должен появиться в каждой строке ровно один раз, легко заметить, что две пустые ячейки таблицы в строке b должны быть заняты либо d, либо f. Однако в соответствующих столбцах уже присутствуют d и f . Таким образом, что бы мы ни поставили в эти поля, получим повторение в столбцах, что показывает, что наше начальное предположение ab = c было неверным. Однако мы теперь знаем, что abc.

Осталось две возможности — либо ab = d, либо ab = f. Поскольку d and f взаимно обратны и выбор букв произволен, следует ожидать, что результат будет одинаковым с точностью до изоморфизма. Без потери общности можно считать, что ab = d. Если мы теперь получим противоречие, нам придётся признать, что для этого скелета нет соответствующей группы.

Получаем новую таблицу Кэли:

Умножая ab = d слева на a, мы получаем b = ad. Умножение справа на f даёт bf = a, а умножение слева на b даёт f = ba. Умножив справа на a, мы получим fa = b, а умножив слева на d, получим a = db. Внеся результаты в таблицу Кэли, получим (новые элементы выделены красным):

В строке a отсутствуют c и f, но поскольку af не может равняться f (иначе a будет равен e), мы можем заключить, что af = c. Умножение слева на a даёт f = ac, и это мы можем умножить справа на c, что даёт fc = a. Умножение последнего на d слева даёт c = da, что мы можем умножить справа на a и получить ca = d. Таким же образом, умножая af = c справа на d, получим a = cd. Обновим таблицу (последние изменения выделены синим):

Поскольку в строке b отсутствуют c и d, а bc не может равняться c, мы выводим, что bc = d, а потому произведение bd должно быть равно c. Умножение справа на f даёт нам b = cf, что можно преобразовать в cb = f умножением на c слева. Рассуждая аналогично, можно вывести, что c = fb и dc = b. Вносим изменения в таблицу (внесённые элементы выделены зелёным цветом):

В строке d отсутствует только f, так что d2 = f. Таким же образом получаем, что f2 = d. Мы заполнили всю таблицу и не пришли к противоречию. Таким образом, мы нашли группу порядка 6, соответствующую скелету. Просмотр таблицы показывает, что она не абелева. Фактически это наименьшая неабелева группа, диэдрическая группа D3:

Генерация матрицы перестановок

В стандартной форме таблицы Кэли порядок строк и столбцов совпадает. Другим способом упорядочения является расстановка столбцов таким образом, чтобы n-ый столбец соответствовал обратным элементам n-ой строки. В нашем примере для D3 нам необходимо только переставить два последних столбца, поскольку только f и d не являются обратными себе, зато являются обратными друг другу.

В нашем примере можно создать шесть перестановочных матриц (все элементы равны 1 или 0, по одной единице в каждой строке и каждом столбце). 6x6 матрица содержит единицу, если метка столбца совпадает с меткой строки, и нули во всех остальных полях, символ Кронекера для метки. (Заметим, что для строки e получим единичную матрицу.) Например, для a получим перестановочную матрицу.

Это показывает, что любая группа порядка n является подгруппой группы перестановок Sn порядка n!.

Обобщения

Описанные выше свойства зависят от некоторых аксиом для групп. Естественно распространить таблицы Кэли на некоторые другие алгебраические структуры, такие как полугруппы, квазигруппы и магмы, но для них некоторые выше указанные свойства выполняться не будут.