Таблица Кэли

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

Например, таблица Кэли для стандартной операции умножения $\times$ на множестве $\{1,-1\}$ имеет вид:

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

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

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

История

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

Структура

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

*	a	b	c
a	a²	ab	ac
b	ba	b²	bc
c	ca	cb	c²

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

a	b	c
b	c	a
c	a	b

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Группы с различными скелетами не могут быть изоморфны, однако обратное неверно (например, циклическая группа C₈ и группа кватернионов 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 = f². Умножение слева на 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 было неверным. Однако мы теперь знаем, что ab ≠ c.

Осталось две возможности — либо 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, так что d² = f. Таким же образом получаем, что f² = d. Мы заполнили всю таблицу и не пришли к противоречию. Таким образом, мы нашли группу порядка 6, соответствующую скелету. Просмотр таблицы показывает, что она не абелева. Фактически это наименьшая неабелева группа, диэдрическая группа D₃:

*	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-ой строки. В нашем примере для D₃ нам необходимо только переставить два последних столбца, поскольку только f и d не являются обратными себе, зато являются обратными друг другу.

	e	a	b	c	f=d⁻¹	d=f⁻¹
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 является подгруппой группы перестановок S_n порядка n!.

Обобщения

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

См. также

Ссылки

Cayley, Arthur. «On the theory of groups, as depending on the symbolic equation θⁿ = 1», Philosophical Magazine, Vol. 7 (1854), pp. 40-47. Available on-line at Google Books as part of his collected works.
Cayley, Arthur. «On the Theory of Groups», American Journal of Mathematics, Vol. 11, No. 2 (Jan 1889), pp. 139—157. Available at JSTOR.