Автоморфизм группы вручную. Можно ли более эффективно?

[B@R5uk]

Решил тут посчитать вручную (чтобы, так сказать, попробовать проблему на зуб) группу автоморфизмов группы

$$\mathbb{Z}_3^2=\left\langle\;a,\;b\;|\;a^3=b^3=[a,\;b]=e\;\right\rangle$$

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

$$\xymatrix{&*+[o]+[F]{a}\ar@{-}[dl]\ar@{-}[ddr]&&*+[o]+[F]{b}\ar@{-}[ddl]\ar@{-}[dr]&\\*+[o]+[F]{a^2}\ar@{-}[drr]&&&&*+[o]+[F]{b^2}\ar@{-}[dll]\\&&*+[o]+[F]{e}\ar@{-}[dll]\ar@{-}[ddl]\ar@{-}[ddr]\ar@{-}[drr]&&\\*+[o]+[F]{ab}\ar@{-}[dr]&&&&*+[o]+[F]{a^2b}\ar@{-}[dl]\\&*+[o]+[F]{a^2b^2}&&*+[o]+[F]{ab^2}&}$$

Как видно, все элементы группы имеют порядок 3, поэтому какую бы пару элементов мы не взяли в качестве образующих, первые два соотношения будут выполнены. Более того, группа абелева, поэтому третье соотношение тоже будет автоматически выполнено. Чтобы подстановка была обратима, а порождаемая новыми элементами группа — действительно исходная группа, образующие должны быть "линейно независимы", то есть принадлежать двум различным "лепесткам"-циклам на графе. В итоге имеется 8 способов выбрать первую образующую, а из оставшихся 7-ми нетривиальных элементов в качестве второй подойдёт 6. Получается 48 автоморфизмов, включая тривиальный. Замену обозначим следующим образом:

$$c=a^xb^y,\quad d=a^zb^v;\quad x,\;y,\;z,\;v\in\{0,1,2\}$$

Или в матричной форме:

$$\begin{pmatrix}c\\d\end{pmatrix}=\begin{pmatrix}a^xb^y\\a^zb^v\end{pmatrix}=\begin{pmatrix}x&y\\z&v\end{pmatrix}\begin{pmatrix}a\\b\end{pmatrix}$$

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

$$g=c^pd^q,\quad h=c^rd^s$$

$$\begin{pmatrix}g\\h\end{pmatrix}=\begin{pmatrix}c^pd^q\\c^rd^s\end{pmatrix}=\begin{pmatrix}p&q\\r&s\end{pmatrix}\begin{pmatrix}c\\d\end{pmatrix}=\begin{pmatrix}p&q\\r&s\end{pmatrix}\left[\begin{pmatrix}x&y\\z&v\end{pmatrix}\begin{pmatrix}a\\b\end{pmatrix}\right]=\begin{pmatrix}p&q\\r&s\end{pmatrix}\begin{pmatrix}a^xb^y\\a^zb^v\end{pmatrix}=$$

$$=\begin{pmatrix}(a^xb^y)^p\,(a^zb^v)^q\\(a^xb^y)^r\,(a^zb^v)^s\end{pmatrix}=\begin{pmatrix}a^{px+qz}\,b^{py+qv}\\a^{rx+sz}\,b^{ry+sv}\end{pmatrix}=\begin{pmatrix}px+qz&py+qv\\rx+sz&ry+sv\end{pmatrix}\begin{pmatrix}a\\b\end{pmatrix}=\left[\begin{pmatrix}p&q\\r&s\end{pmatrix}\begin{pmatrix}x&y\\z&v\end{pmatrix}\right]\begin{pmatrix}a\\b\end{pmatrix}$$

То есть при конкатенации подстановок матрицы соответствующих операторов перемножаются как обычные матрицы. Тут надо заметить, что "координаты" новой пары образующих находятся в строках (одна строка — одна образующая). Операция умножения матриц не коммутативна (то есть искомая группа не абелева), и порядок множителей важен. Так же, координаты являются числами 0, 1 и 2, а добавление/вычитание любого числа, кратного 3-ём ничего не меняет, так как образующая в такой степени равна нейтральному элементу. То есть, все вычислительные операции производятся по модулю 3. Другими словами, искомая группа автоморфизмов является группой обратимых матриц 2 на 2 с вычислениями по модулю 3. (Наверное, эта группа даже имеет какое-нибудь умное название и/или специальное обозначение).

Следующим этапом я записал все 48 матриц и проверил, что они действительно обратимы, то есть нашёл их обратные. Для матриц, содержащих в записи ноль обратная ищется довольно просто последовательным заполнением ячеек правильными цифрами в правильном порядке. Для случаев, когда нуля в записи нет, приходится прибегать к честному расчёту методом Гаусса, например:

$$\left(\begin{array}{cc|cc}2&2&1&0\\1&2&0&1\end{array}\right)\sim\left(\begin{array}{cc|cc}1&1&2&0\\0&1&1&1\end{array}\right)\sim\left(\begin{array}{cc|cc}1&0&1&2\\0&1&1&1\end{array}\right)$$

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

$$e=\begin{pmatrix}1&0\\0&1\end{pmatrix},\quad f=\begin{pmatrix}2&0\\0&2\end{pmatrix}\right$$

Умножение на 2-ю (с любой стороны) заменяет в любой матрице двойки на единицы и наоборот. Матрицы, обратные к которым совпадают с оригинальными, соответствуют элементам группы порядка 2 (кроме нейтрального).

Затем я посчитал квадраты всех остальных матриц (порядка больше 2). Те квадраты, что совпали с рассчитанными обратными, получались для матриц порядка 3. Далее осталось сопоставить какие квадраты имеют порядок 2, 3 и 4, чтобы получись список элементов искомой группы порядка 4, 6 и 8. Для упорядочивания элементов в циклы потребовалось ещё немного умножений (чтобы расположить в порядке возрастание степени порождающей матрицы). В итоге за приблизительно 3 на 48 матричных умножений я получил все подгруппы ранга 1 исходной группы (кольца).

Порядок 2 (13 элементов):

$$e=f^2=\begin{pmatrix}1&0\\0&2\end{pmatrix}^2=\begin{pmatrix}2&0\\0&1\end{pmatrix}^2=\begin{pmatrix}0&1\\1&0\end{pmatrix}^2=\begin{pmatrix}0&2\\2&0\end{pmatrix}^2=\begin{pmatrix}2&0\\1&1\end{pmatrix}^2=\begin{pmatrix}1&0\\2&2\end{pmatrix}^2=$$

$$=\begin{pmatrix}1&1\\0&2\end{pmatrix}^2=\begin{pmatrix}2&2\\0&1\end{pmatrix}^2=\begin{pmatrix}1&0\\1&2\end{pmatrix}^2=\begin{pmatrix}2&0\\2&1\end{pmatrix}^2=\begin{pmatrix}2&1\\0&1\end{pmatrix}^2=\begin{pmatrix}1&2\\0&2\end{pmatrix}^2$$

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

Порядок 3 (4 цикла, 8 элементов):

$$e-\begin{pmatrix}1&0\\1&1\end{pmatrix}-\begin{pmatrix}1&0\\2&1\end{pmatrix}-e-\begin{pmatrix}0&1\\2&2\end{pmatrix}-\begin{pmatrix}2&2\\1&0\end{pmatrix}-e-\begin{pmatrix}1&1\\0&1\end{pmatrix}-\begin{pmatrix}1&2\\0&1\end{pmatrix}-e-\begin{pmatrix}2&1\\2&0\end{pmatrix}-\begin{pmatrix}0&2\\1&2\end{pmatrix}-e$$

Порядок 4 (3 цикла, 6 элементов):

$$e-\begin{pmatrix}0&1\\2&0\end{pmatrix}-f-\begin{pmatrix}0&2\\1&0\end{pmatrix}-e$$

$$e-\begin{pmatrix}2&1\\1&1\end{pmatrix}-f-\begin{pmatrix}1&2\\2&2\end{pmatrix}-e$$

$$e-\begin{pmatrix}1&1\\1&2\end{pmatrix}-f-\begin{pmatrix}2&2\\2&1\end{pmatrix}-e$$

Порядок 6 (4 цикла, 8 элементов — вторые с краю):

$$e-\begin{pmatrix}2&0\\1&2\end{pmatrix}-\begin{pmatrix}1&0\\1&1\end{pmatrix}-f-\begin{pmatrix}1&0\\2&1\end{pmatrix}-\begin{pmatrix}2&0\\2&2\end{pmatrix}-e$$

$$e-\begin{pmatrix}1&1\\2&0\end{pmatrix}-\begin{pmatrix}0&1\\2&2\end{pmatrix}-f-\begin{pmatrix}2&2\\1&0\end{pmatrix}-\begin{pmatrix}0&2\\1&1\end{pmatrix}-e$$

$$e-\begin{pmatrix}2&1\\0&2\end{pmatrix}-\begin{pmatrix}1&1\\0&1\end{pmatrix}-f-\begin{pmatrix}1&2\\0&1\end{pmatrix}-\begin{pmatrix}2&2\\0&2\end{pmatrix}-e$$

$$e-\begin{pmatrix}0&1\\2&1\end{pmatrix}-\begin{pmatrix}2&1\\2&0\end{pmatrix}-f-\begin{pmatrix}0&2\\1&2\end{pmatrix}-\begin{pmatrix}1&2\\1&0\end{pmatrix}-e$$

Порядок 8 (3 цикла, 12 элементов — на нечётных позициях):

$$e-\begin{pmatrix}2&2\\1&2\end{pmatrix}-\begin{pmatrix}0&2\\1&0\end{pmatrix}-\begin{pmatrix}2&1\\2&2\end{pmatrix}-f-\begin{pmatrix}1&1\\2&1\end{pmatrix}-\begin{pmatrix}0&1\\2&0\end{pmatrix}-\begin{pmatrix}1&2\\1&1\end{pmatrix}-e$$

$$e-\begin{pmatrix}0&2\\2&1\end{pmatrix}-\begin{pmatrix}1&2\\2&2\end{pmatrix}-\begin{pmatrix}1&1\\1&0\end{pmatrix}-f-\begin{pmatrix}0&1\\1&2\end{pmatrix}-\begin{pmatrix}2&1\\1&1\end{pmatrix}-\begin{pmatrix}2&2\\2&0\end{pmatrix}-e$$

$$e-\begin{pmatrix}1&2\\2&0\end{pmatrix}-\begin{pmatrix}2&2\\2&1\end{pmatrix}-\begin{pmatrix}0&1\\1&1\end{pmatrix}-f-\begin{pmatrix}2&1\\1&0\end{pmatrix}-\begin{pmatrix}1&1\\1&2\end{pmatrix}-\begin{pmatrix}0&2\\2&2\end{pmatrix}-e$$

Здесь я, наверное, должен был сразу заметить, что циклов 4-го порядка три штуки и все они имеют общий элемент 2-го порядка, но это как-то проскользнуло мимо моего внимания. Вместо этого я пытался сопрягать элементы 8-го порядка элементами 3-го порядка и наоборот, а так же элементы 3-го порядка элементами 4-го в надежде получить прямую степень сопряжённого элемента, что указало бы на полупрямое произведение двух циклических групп. Вместо этого я всегда получал элементы из другого цикла. В итоге моё терпение закончилось и за "подглядел" в моей программулине, что искомая группа имеет вид

$$\mathrm{Q}_8\rtimes\mathrm{D}_6=\mathrm{Q}_8\rtimes\left(\mathbb{Z}_3\rtimes\mathbb{Z}_2\right)=\left(\mathrm{Q}_8\rtimes\mathbb{Z}_3\right)\rtimes\mathbb{Z}_2$$

Откуда ноги растут у группы кватернионов сразу стало очевидно, и для неё я выбрал такие образующие:

$$a=\begin{pmatrix}0&1\\2&0\end{pmatrix},\quad b=\begin{pmatrix}2&1\\1&1\end{pmatrix},\quad ab=\begin{pmatrix}0&1\\2&0\end{pmatrix}\begin{pmatrix}2&1\\1&1\end{pmatrix}=\begin{pmatrix}1&1\\1&2\end{pmatrix}$$

$$a^2=b^2=f,\;f^2=[a,\;f]=[b,\;f]=e$$

и непосредственным вычислением убедился что

$$bab^{-1}=\begin{pmatrix}2&1\\1&1\end{pmatrix}\begin{pmatrix}0&1\\2&0\end{pmatrix}\begin{pmatrix}1&2\\2&2\end{pmatrix}=\begin{pmatrix}0&2\\1&0\end{pmatrix}=a^{-1}$$

В качестве образующей 3-го порядка я выбрал такую, чтобы при сопряжении она заменяла первую образующую второй, а вторую — произведением:

$$c=\begin{pmatrix}1&0\\1&1\end{pmatrix}$$

$$cac^{-1}=\begin{pmatrix}1&0\\1&1\end{pmatrix}\begin{pmatrix}0&1\\2&0\end{pmatrix}\begin{pmatrix}1&0\\2&1\end{pmatrix}=\begin{pmatrix}0&1\\2&1\end{pmatrix}\begin{pmatrix}1&0\\2&1\end{pmatrix}=\begin{pmatrix}2&1\\1&1\end{pmatrix}=b$$

$$cbc^{-1}=\begin{pmatrix}1&0\\1&1\end{pmatrix}\begin{pmatrix}2&1\\1&1\end{pmatrix}\begin{pmatrix}1&0\\2&1\end{pmatrix}=\begin{pmatrix}2&1\\0&2\end{pmatrix}\begin{pmatrix}1&0\\2&1\end{pmatrix}=\begin{pmatrix}1&1\\1&2\end{pmatrix}=ab$$

$$[c,\;f]=cfc^{-1}f^{-1}=ca^2c^{-1}a^2=\left(cac^{-1}\right)^2a^2=(a^{-1})^2a^2=e$$

Ну и четвёртая образующая завершает группу:

$$d=\begin{pmatrix}1&0\\0&2\end{pmatrix}$$

$$dad^{-1}=dad=\begin{pmatrix}1&0\\0&2\end{pmatrix}\begin{pmatrix}0&1\\2&0\end{pmatrix}\begin{pmatrix}1&0\\0&2\end{pmatrix}=\begin{pmatrix}0&1\\1&0\end{pmatrix}\begin{pmatrix}1&0\\0&2\end{pmatrix}=\begin{pmatrix}0&2\\1&0\end{pmatrix}=a^3$$

$$dbd^{-1}=dbd=\begin{pmatrix}1&0\\0&2\end{pmatrix}\begin{pmatrix}2&1\\1&1\end{pmatrix}\begin{pmatrix}1&0\\0&2\end{pmatrix}=\begin{pmatrix}2&1\\2&2\end{pmatrix}\begin{pmatrix}1&0\\0&2\end{pmatrix}=\begin{pmatrix}2&2\\2&1\end{pmatrix}=a^3b$$

$$dcd^{-1}=dcd=\begin{pmatrix}1&0\\0&2\end{pmatrix}\begin{pmatrix}1&0\\1&1\end{pmatrix}\begin{pmatrix}1&0\\0&2\end{pmatrix}=\begin{pmatrix}1&0\\2&2\end{pmatrix}\begin{pmatrix}1&0\\0&2\end{pmatrix}=\begin{pmatrix}1&0\\2&1\end{pmatrix}=c^2$$

$$[d,\;f]=dfd^{-1}f^{-1}=da^2da^2=(dad)^2a^2=(a^3)^2a^2=e$$

$$(ad)^2=(cd)^2=e$$

Отсюда сразу видно, что искомая группа содержит группы диэдра порядка 6 и 8 в качестве подгрупп:

$$\mathrm{D}_8=\left\langle\;a,\;d\;|\;a^4=d^2=(ad)^2=e\;\right\rangle$$

$$\mathrm{D}_6=\left\langle\;c,\;d\;|\;c^3=d^2=(cd)^2=e\;\right\rangle$$

Более того, если в подгруппе

$$\mathrm{Q}_8\rtimes\mathbb{Z}_2=\left\langle\;a,\;b,\;d\;|\;a^4=d^2=(ad)^2=e,\;a^2=b^2,\;dbd=a^3b\;\right\rangle$$

сделать замену

$$h=bd=\begin{pmatrix}2&1\\1&1\end{pmatrix}\begin{pmatrix}1&0\\0&2\end{pmatrix}=\begin{pmatrix}2&2\\1&2\end{pmatrix}$$

$$dhd^{-1}=dhd=db=\begin{pmatrix}1&0\\0&2\end{pmatrix}\begin{pmatrix}2&1\\1&1\end{pmatrix}=\begin{pmatrix}2&1\\2&2\end{pmatrix}=h^3$$

$$h^4=f,\quad h^8=e$$

то становится понятно, что эта подгруппа имеет и другое представление:

$$\mathrm{Q}_8\rtimes\mathbb{Z}_2=\mathbb{Z}_8\overset{3}{\rtimes}\mathbb{Z}_2=\left\langle\;h,\;d\;|\;h^8=d^2=e,\;dhd^{-1}=h^3\;\right\rangle$$

Этих подгрупп в искомой группе автоморфизмов три, каждую можно получить из вышеприведённой сопрягая её с помощью степеней образующей c. Аналогично с подгруппами диэдра порядка 8. Моя программулина подсказывает мне, что подгрупп диэдра порядка 6 имеется значительно больше, чем казалось изначально, кроме того, тут есть также они и 12-го порядка, что я опять же проворонил. Хотя бы все 48 матриц удалось выразить в виде комбинации образующих в виде

$$a^xb^yc^zd^v,\quad x\in\{0,1,2,3\},\quad y,\;v\in\{0,1\},\quad c\in\{0,1,2\}$$

В общем вопрос более эффективного поиска структуры остаётся открытым. После получения матриц никаких свойств из линала привлечь мне не приметилось, кроме того, что матрицы с определителем 1 образуют подгруппу $\mathrm{Q}_8\rtimes\mathbb{Z}_3$ порядка 24 с образующими a, b и c. Были просто технические вычисления чтобы угадать и/или подтвердить искомые соотношения между образующими. Ну, хотя бы мне всю таблицу умножения целиком строить не понадобилось, это 2300+ матричных умножений. Я обошёлся значительно меньшим числом действий, чем требуется моей программулине (или даже для построения всей таблицы), но я не могу утверждать, что я нашёл решение и структуру вручную, только проверил её (потому что подсматривал). Кроме того, общего решения для автоморфизма групп вида $\mathbb{Z}_{mn}\times\mathbb{Z}_m$ или хотя бы $\mathbb{Z}_m^2$ из этого решения не просматривается.

[dgwuqtj]

B@R5uk в сообщении #1669247 писал(а):

Кроме того, общего решения для автоморфизма групп вида $\mathbb{Z}_{mn}\times\mathbb{Z}_m$ или хотя бы $\mathbb{Z}_m^2$ из этого решения не просматривается.

Смотря что вы называете решением... В случае $(\mathbb Z / m \mathbb Z)^2$ группа автоморфизмов — это $\mathrm{GL}(2, \mathbb Z / m \mathbb Z)$, практически по определению. Если $m = p_1^{k_1} \cdots p_l^{k_l}$ разложение на простые, то $\mathrm{GL}(2, \mathbb Z / m \mathbb Z) \cong \mathrm{GL}(2, \mathbb Z / p_1^{k_1}) \times \cdots \times \mathrm{GL}(2, \mathbb Z / p_l^{k_l})$, это китайская теорема об остатках. Далее, если $p$ простое и $k \geq 1$, то $\mathrm{GL}(2, \mathbb Z / p^k)$ имеет нормальную фильтрацию

$$1 \leq 1 + \mathrm M(2, p^{k - 1} \mathbb Z / p^k \mathbb Z) \leq \ldots \leq 1 + \mathrm M(2, p \mathbb Z / p^k \mathbb Z) \leq \mathrm{GL}(2, \mathbb Z / p^k \mathbb Z).$$

Факторы этой фильтрации — это $\mathbb F_p^4, \ldots, \mathbb F_p^4, \mathrm{GL}(2, \mathbb Z / p \mathbb Z)$. Наконец, $\mathrm{GL}(2, \mathbb Z / p \mathbb Z)$ имеет нормальную подгруппу $\mathrm{SL}(2, \mathbb F_p)$ с фактор-группой $\mathbb F_p^*$, центр $\mathrm{SL}(2, \mathbb F_p)$ — это группа скалярных матриц из $\pm 1$ (из двух элементов, кроме случая $p = 2$), а факторгруппа по ней проста при $p \geq 5$. Так что композиционные факторы найти довольно легко.

Вообще группа автоморфизмов абелевой группы $A$ — это группа обратимых элементов кольца $\mathrm{End}(A)$. Если у вас группа конечная, то есть примарное разложение $A = \bigoplus_p A_p$, ну и $\mathrm{End}(A) = \prod_p \mathrm{End}(A_p)$. Наконец, $A_p$ сами раскладываются в прямые суммы циклических групп, так что их группы автоморфизмов — это некие обобщённые матричные кольца.

[B@R5uk]

dgwuqtj в сообщении #1669250 писал(а):

Если $m = p_1^{k_1} \cdots p_l^{k_l}$ разложение на простые, то $\mathrm{GL}(2, \mathbb Z / m \mathbb Z) \cong \mathrm{GL}(2, \mathbb Z / p_1^{k_1}) \times \cdots \times \mathrm{GL}(2, \mathbb Z / p_l^{k_l})$, это китайская теорема об остатках.

Разве? На сколько я понимаю, КТоО утверждает, что

$$\mathbb{Z}_N\cong\mathbb{Z}_{a_1}\times\mathbb{Z}_{a_2}\times\ldots\times\mathbb{Z}_{a_k}$$

если

$$\gcd\left(a_i,a_j\right)=1,i\ne j,\quad N=a_1a_2\ldots a_k$$

Привлечение сюда автоморфизмов даёт куда более сильное утверждение связанное больше с функцией Эйлера, чем с КТоО. И структура даже абелевых групп сложнее, чем структура произведения взаимно простых чисел.

Что значит фильтрация группы?

[dgwuqtj]

Ну вот $\mathbb Z / N \mathbb Z \cong \prod_i \mathbb Z / a_i \mathbb Z$ как кольца, так что $\mathrm M(2, \mathbb Z / N \mathbb Z) \cong \prod_i \mathrm M(2, \mathbb Z / a_i \mathbb Z)$. Поэтому и группа обратимых матриц так раскладывается, и функция Эйлера мультипликативна.

А фильтрацией я почему-то назвал ряд подгрупп, то есть цепочку подгрупп $1 = H_0 \leq \ldots \leq H_n = G$. Ряд называется нормальным, если $H_i$ нормальны в $G$.

[B@R5uk]

Буквой M вы обозначаете множество матриц?

[dgwuqtj]

Да, $M(n, R)$ — это кольцо матриц $n \times n$ с элементами из $R$, а $M(n, m, R)$ — множество матриц $n \times m$ ($n$ строк, $m$ столбцов).