Функция Эйлера для матриц

[Руст]

Рассмотрим матрицы фиксированного порядка $k^2$ с целыми элементами. Естественно определить взаимную простоту матрицы $A$ и числа $n$ как взаимную простоту определителя $A$ с $n$.
1. Обобщим определение функции Эйлера на матрицы как количество взаимно простых с $n$ матриц элементы которых от $0$ до $n-1$ (вычеты по модулю $n$). Верно ли что эта функция мультипликативна (т.е. значение для произведения $n=ml, \ (m,l)=1$ равно произведению)?
2. Верно ли что для любой взаимно простой с $n$ матрицы его соответствующая степень равна $1$ с точностью до делящихся на $n$?
3. Вычислить функцию Эйлера для матриц.

[V.V.]

Вроде, Арнольд на эту тему статью писал...

[Руст]

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

[V.V.]

Руст писал(а):

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

А можно примеры ошибок и тривиальных гипотез?

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

[Руст]

Эти вопросы рассматриваются в брошюрах Арнольда "Группы Эйлера и арифметика геометрических прогрессий" и "Задачи семинара". Я как то выделил в первой брошюре 12 ошибок. В качестве примера приведу одно: на стр.13 он доказывает явно неверное утверждение:

$$(1+p)^k=(1+pk_0)(1+p^2k_1)...(1+p^ak_{a-1})\pmod {p^{a+1}},\ k=k_0+k_1p+k_2p^2+...$$

Очевидный контрпример $a=2,p=3,k=5. $
В этих книжках он вводит глупые классы и экспериментально их изучает и выдвигает разные гипотезы. Некоторые из них элементарно можно доказать, а некоторые легко опровергнуть, причём я гипотезы не перечислял в число указанных ошибок, даже если они опровергаются.

[V.V.]

Руст писал(а):

Эти вопросы рассматриваются в брошюрах Арнольда "Группы Эйлера и арифметика геометрических прогрессий" и "Задачи семинара". Я как то выделил в первой брошюре 12 ошибок.

...

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

Может быть, Вы напишите о всех ошибках и тривиальных гипотезах на форуме?

[Руст]

О всех ошибках вряд ли стоит писать на форуме. Большинства ошибок довольно просты и любой заметит, например на стр. 4 "Поскольку сократимости на разные простые числа $p$ очевидно независимы, вероятность полной несократимости равна

$$p=\prod_p \frac{1}{1-\frac{1}{p^m}} $$

".
Многие "гипотезы" тривиальны и они легко доказываются если знать китайскую теорему об остатках, которую вводя обозначения для колец вычетов $Z_n=Z/nZ$ можно записать в виде: Существует кольцевой изоморфизм: $Z_{mn}=Z_m*Z_n,(m,n)=1$ для взаимно простых чисел $m$ и $n$. Отсюда легко получается вычисление периода для $a,(a,n)=1$:

$$per(a,n)=lcm(per,p_i^{k_i}),n=\prod_i p_i^{k_i} $$

. Соответственно станет понятно, что лучше вводить классы индекса $N$ не относительно функции Эйлера от $n$, а относительно максимального порядка циклической группы, равной:
$c(n)=lcm(c(p_i^{k_i}),c(2^k)=2^{k-2},k>2,c(2)=1,$$c(4)=2,c(p^k)=(p-1)p^{k-1},p\ge 3. $

[bot]

Неоднократно видел, как большие люди попадают впросак, когда вторгаются в новую для себя область. То они дурацкую проблему поднимут, то сочтут интересной какую-нибудь банальность.
В моей практике был случай - писал в ревьюс однострочное доказательство проблемы, которую поставил "большой автор" (иностранный) и в статье из страниц эдак 15-20, получил значительное продвижение в её решении.
С нашими тоже бывало, хотя до такой степени курьёзности не доходило.

[незваный гость]

Руст писал(а):

2. Верно ли что для любой взаимно простой с n матрицы его соответствующая степень равна 1 с точностью до делящихся на n?

$\left( \begin{array}{cc} 1 & 1 & 0 & 1 & \end{array} \right)$ взаимно проста с любым $n$, однако ее любая степень не $1$ (если только вопрос не имеет в виду, что $\left( \begin{array}{cc} 1 & n & 0 & 1 & \end{array} \right) = 1$).

[Руст]

Именно последнее имеется в виду. И для чисел $a^{p-1}=1 (mod \ p)$ а не сама степень равно 1.

[незваный гость]

Рассмотрим $A$, $(\det(A),n) = 1$. Тогда ${(\det A)}^{\varphi(n)} \equiv 1 (\!\!\!\!\mod n)$. Рассмотрим $A^{m \varphi(n)}, m = 1,...$. Поскольку по модулю $n$ мы имеем не более $n^{k^2}$ матриц, существуют $m_1, m_2: A^{m_1 \varphi(n)} \equiv A^{m_2 \varphi(n)} (\!\!\!\!\mod n)$. Откеле выводим ${A^{(m_1-m_2) \varphi(n)}} \equiv I (\!\!\!\!\mod n)$ (для обоснования деления достаточно вспомнить, что определитель равен 1).

[Руст]

На самом деле матрицы взаимно простые с $n$ образуют мультипликативную группу по модулю $n$. Действительно если определитель равен $m, (m,n)=1$, то существует $l: lm=1 \pmod n$. Умножив исходную матрицу на матрицу с $l$ на первой строке главной диагонали, а остальные 1 получаем матрицу с определителем $1$ по модулю $n$ а соответственно найдём обратную матрицу по модулю $n$. Группа эта конечная, соответственно по теореме Лагранжа для любого элемента степень кратная порядку группы даст $1$ (по модулю $n$). Так что эта часть тривиальная и известна ещё Лагранжу. Здесь главное структура этой группы, так как группа не коммутативная то содержит много интересного.

[lofar]

Если я верно понял, то задача состоит в отыскании мощности группы обратимых матриц размера $k\times k$ над кольцом $\mathbb Z_n$.

I. Пусть $R$ и $S$ --- кольца и $T=R\times S$ их прямое произведение. Тогда кольцо матриц $M_k(T)$ изоморфно прямому произведению $M_k(R)\times M_k(S)$. Значит имеет место изоморфизм групп обратимых элементов: $M_k(T)^*\cong M_k(R)^*\times M_k(S)^*$.

В частности, если $n=p_1^{a_1}\ldots p_s^{a_s}$, то $\mathbb Z_{n}\cong\mathbb Z_{p_1^{a_1}}\times\ldots\times\mathbb Z_{p_s^{a_s}}}$ и следовательно $M_k(\mathbb Z_{n})^*\cong M_k(\mathbb Z_{p_1^{a_1}})^*\times\ldots\times M_k(\mathbb Z_{p_s^{a_s}}})^*$. Отсюда следует мультипликативность изучаемой величины. Для получения конечной формулы остается вычислить мощность $M_k(\mathbb Z_{p^a})^*$.

II. $\mathbb Z_{p^a}$ --- локальное кольцо с радикалом $p\mathbb Z_{p^a}$. Рассмотрим канонический эпиморфизм $\mathbb Z_{p^a}\to\mathbb Z_{p^a}/p\mathbb Z_{p^a}\cong\mathbb Z_{p}$ определяемый соотношением $x\mapsto \overline x = x+p\mathbb Z_{p^a}$. Этот эпиморфизм естественным образом индуцирует эпиморфизм колец матриц

$$ \varphi\colon M_k(\mathbb Z_{p^a})\to M_k(\mathbb Z_{p}),\;\;\varphi\colon (x_{ij})\mapsto (\overline {x_{ij}}). $$

Ядро $Ker(\varphi)$ является нильпотентным идеалом в $M_k(\mathbb Z_{p^a})$ ($Ker(\varphi)^a=0$). Поэтому $x\in M_k(\mathbb Z_{p^a})^*\Leftrightarrow\varphi(x)\in M_k(\mathbb Z_{p})^*$. Значит

$$ |M_k(\mathbb Z_{p^a})^*| = |M_k(\mathbb Z_{p})^*|\cdot|Ker(\varphi)| $$

Хорошо известно, что $|M_k(\mathbb Z_{p})^*|=p^{k(k-1)/2}(p^k-1)(p^{k-1}-1)\ldots (p-1)$. Также ясно, что $|Ker(\varphi)|=|p\mathbb Z_{p^a}|^{k^2}=p^{(a-1)k^2}$. Значит, окончательно,

$$ |M_k(\mathbb Z_{p^a})^*| = p^{k(k-1)/2+(a-1)k^2}(p^k-1)(p^{k-1}-1)\ldots (p-1). $$

[Руст]

Всё правильно. Для непосвящённых количество обратимых матриц взаимно простых с простым $p$ вычисляется как набор из $k$ векторов. Первый можно взять любой кроме 0 (всего $p^k-1$), каждому выбору первого вектора соответствует $p^k-p$ возможных выборов второго вектора (не принадлежащих одномерному подпространву порождённым первым вектором) и т.д., что даёт всего

$$\prod_{i=0}^{k-1} (p^k-p^i)=p^{k(k-1)/2}\prod_{i=1}^k (p^i-1). $$

Вообще то Арнольд интересуется и структурой этой группы, в частности тем, чему равен максимальный порядок циклической группы $c(n)$, образованной такой матрицы. Из того, что имеется мультипликативность значение $c(n)$ как и для чисел будет вычисляться как НОК по примарным разложениям. Однако, примарные разложения не являются циклическими группами как для чисел и поэтому вычисление $c(n)$ не такое простое для степеней простых чисел. Тем не менее оно вычисляется и предлагаю это сделать другим.

[Руст]

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

$$c(n),n=\prod_i p_i^{m_i},c(n)=lcm (c(p_i^{m_i}),c(p_i^{m_i})=p_i^{m_i-1}c(p_i),c(p_i)=p_i^k lcm (p_i-1,p_i^2-1,...,p_i^k-1).$$