Таблица Кэли

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

× 1 −1
1 1 −1
−1 −1 1

История[править | править вики-текст]

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

Структура[править | править вики-текст]

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

* a b c
a a2 ab ac
b ba b2 bc
c ca cb c2

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

a b c
b c a
c a b

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

Свойства и использование[править | править вики-текст]

Коммутативность[править | править вики-текст]

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

Ассоциативность[править | править вики-текст]

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

Перестановки[править | править вики-текст]

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

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

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

Построение таблиц Кэли[править | править вики-текст]

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

"Скелет нейтральных элементов" конечной группы[править | править вики-текст]

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

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

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

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

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

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

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

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

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

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

e a b c d f
e e
a e
b e
c e
d e
f e

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

e a b c d f
e e a b c d f
a a e c
b b e
c c e
d d e
f f e

Умножая 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.

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

e a b c d f
e e a b c d f
a a e c b f d
b b c e a
c c b a e
d d f e
f f d e a

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

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

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

e a b c d f
e e a b c d f
a a e d
b b e
c c e
d d e
f f e

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

e a b c d f
e e a b c d f
a a e d b
b b f e a
c c e
d d a e
f f b e

В строке 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. Обновим таблицу (последние изменения выделены синим):

e a b c d f
e e a b c d f
a a e d f b c
b b f e a
c c d e a
d d c a e
f f b a e

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

e a b c d f
e e a b c d f
a a e d f b c
b b f e d c a
c c d f e a b
d d c a b e
f f b c a e

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

* e a b c d f
e e a b c d f
a a e d f b c
b b f e d c a
c c d f e a b
d d c a b f e
f f b c a e d

Генерация матрицы перестановок[править | править вики-текст]

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

e a b c f=d−1 d=f−1
e e a b c f d
a a e d f c b
b b f e d a c
c c d f e b a
d d c a b e f
f f b c a d e

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

e a b c f d
e 0 1 0 0 0 0
a 1 0 0 0 0 0
b 0 0 0 0 1 0
c 0 0 0 0 0 1
d 0 0 1 0 0 0
f 0 0 0 1 0 0

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

Обобщения[править | править вики-текст]

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

Смотрите также[править | править вики-текст]

Ссылки[править | править вики-текст]