Две задачки для школьников.

[Коровьев]

Простая для разминки.
1. Найти все матрицы второго порядка кубы которых равны единице.

Потруднее.
2. Пусть :
$P$ - простое число.
$A$ - целочисленная матрица /можно и рациональная/, отличная от единичной.
Доказать, что если $A^P=1$, то порядок матрицы не ниже $P-1$

[Профессор Снэйп]

Коровьев писал(а):

2. Пусть :
$P$ - простое число.
$A$ - целочисленная матрица /можно и рациональная/
Доказать, что если $A^P=1$, то порядок матрицы не ниже $P-1$

Что-то я не въехал. Берём единичную квадратную матрицу любого размера, возводим в любую натуральную степень, получаем единичную матрицу. И где тут прикол? Или под порядком матрицы понимается что-то такое особенное, что равно $P-1$ для любого простого $P$ и любой единичной матрицы?

[worm2]

Цитата:

1. Найти все матрицы второго порядка кубы которых равны единице.

У меня получилось вот что:
1) единичная
2)

$$\left(\begin{array}{cc}x&y\\-\frac{x^2+x+1}{y} &-1-x\end{array}\right)$$

,
где x, y --- произвольные комплексные числа, y --- ненулевое.
3)

$$\left(\begin{array}{cc}x_1&y\\0 &x_2\end{array}\right)$$

4)

$$\left(\begin{array}{cc}x_1&0\\y &x_2\end{array}\right)$$

,
где $x_1$ и $x_2$ --- два различных кубических корня из единицы, комплексно сопряжённых друг другу (т.е. $-\frac{1}{2}\pm i\frac{\sqrt{3}}{2}$), y --- любое.
При сильном желании можно объявить 3) и 4) частными случаями формулы 2).

[Коровьев]

Профессор Снэйп писал(а):

Коровьев писал(а):

2. Пусть :
$P$ - простое число.
$A$ - целочисленная матрица /можно и рациональная/
Доказать, что если $A^P=1$, то порядок матрицы не ниже $P-1$

Что-то я не въехал. Берём единичную квадратную матрицу любого размера, возводим в любую натуральную степень, получаем единичную матрицу. И где тут прикол? Или под порядком матрицы понимается что-то такое особенное, что равно $P-1$ для любого простого $P$ и любой единичной матрицы?

Виноват.
Естественно имеется ввиду
Матрица $A$ отлична от единичной.
Добавлено в исходный пост.

Добавлено спустя 45 минут 38 секунд:

Указание к задаче 2.
Воспользоваться следующим, безусловно верным, утверждением из теории алгебраических чисел:
Алгебраическое число

\[\alpha = \sum\limits_{n = 0}^{p - 2} {a_n } \varepsilon ^n \]

где:
$P$ - простое число,

\[\varepsilon = Cos\frac{{2\pi }}{P} + \iota Sin\frac{{2\pi }}{P}\]

- первообразный корень $P$-ой степени из единицы
$a_n$ - рациональные,
равно нулю тогда и только тогда, когда все $a_n$равны нулю.

[Really]

Многочлен $x^p-1$ аннулирует матрицу $A$, $p$ - простое число.
$x^p-1=(x-1)\cdot g(x)$, где $g(x)=x^{p-1}+x^{p-2}+\ldots+1$. Многочлен $g$
неприводим над полем $\mathbb Q$ (этот факт надо еще доказать, но я уверен,
что это так). Отсюда следует, что минимальный аннулирующий многочлен
матрицы принадлежит мн-ву $\{ x-1, x^p-1, g(x) \}$. Если это $x-1$, то матрица
единичная, если нет, то размер матрицы не меньше чем $p-1$. Действительно
пусть $A$ - матрица размера $n \times n$. Тогда $A$ обязательно
имеет аннулирующий многочлен степени не большей $n$ - это ее характеристический
многочлен. Если степень минимального многочлена $p-1$, то размер матрицы
не меньше $p-1$.

Вроде бы так.

Добавлено спустя 40 минут 20 секунд:

Ну да. Теорема, которую привел Коровьев и есть доказательство неприводимости
многочлена $g$ над полем $Q$. Ни один многочлен с рациональными коэффициентами
степени меньше $p-1$ не имеет своими корнями корни $g(x)$ - те самые первообразные
корни.

[Коровьев]

Really писал(а):

Многочлен $x^p-1$ аннулирует матрицу $A$, $p$ - простое число.
$x^p-1=(x-1)\cdot g(x)$, где $g(x)=x^{p-1}+x^{p-2}+\ldots+1$. Многочлен $g$
неприводим над полем $\mathbb Q$ (этот факт надо еще доказать, но я уверен,
что это так). Отсюда следует, что минимальный аннулирующий многочлен
матрицы принадлежит мн-ву $\{ x-1, x^p-1, g(x) \}$. Если это $x-1$, то матрица
единичная, если нет, то размер матрицы не меньше чем $p-1$. Действительно
пусть $A$ - матрица размера $n \times n$. Тогда $A$ обязательно
имеет аннулирующий многочлен степени не большей $n$ - это ее характеристический
многочлен. Если степень минимального многочлена $p-1$, то размер матрицы
не меньше $p-1$.

Вроде бы так.

Согласен. Так даже проще. Многочлен $g(x)$ действительно неприводим над полем рациональных чисел и доказательство этого факта также принадлежит теории алгебраических чисел.
Но приведу и "своё" решение.

\[ A^P = E \]

\[ A^P - E = (A - E)\prod\limits_{n = 1}^{p - 1} {(A - \varepsilon ^n } E) = 0 \]

где

\[\varepsilon = Cos\frac{{2\pi }}{P} + \iota Sin\frac{{2\pi }}{P}\]

- первообразный корень $P$-ой степени из единицы
Переходя к определителям получим

\[ \left\| {A^P - E} \right\| = \left\| {(A - E)} \right\|\prod\limits_{n = 1}^{p - 1} {\left\| {(A - \varepsilon ^n E)} \right\|} = 0 \]

Так как $A$ не единичная матрица, то отсюда следует, что многочлен

\[f(\varepsilon ^k)= \left\| {(A - \varepsilon ^k E)} \right\| = 0 \]

при некотором $k$ и имеет степень относительно $\varepsilon ^k $ равную порядку матрицы $A$.
Так как $\varepsilon ^k $ - есть первобразный корень из единицы при любом $k$ не кратном $P$, то этот многочлен при порядке матрицы меньше P-1 может быть равен нулю только если все его коэффициенты равны нулю. Но коэффициент при старшем члене уже равен = +/- 1.
Следовательно исходное равенство при порядке матрицы меньше P-1 невозможно.

[Коровьев]

Доказать, что каждая целочисленная матрица /с целыми элементами/ с определителем равным

\[ \pm 1 \]

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

[ewert]

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

[Коровьев]

Вот ещё сугубо эмпирический факт.
*****
Множество целочисленных матриц одинакового порядка с одинаковым определителем разобьём на классы.
Объединим в один класс все матрицы полученные из одной умножением слева на унимодулярную матрицу.
Доказать.
1.В качестве образующёй класса можно взять любой элемент из этого класса.
2.Если два класса имеют хотя бы один общий элемент, то они совпадают.
3.Число классов конечно.

[Коровьев]

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

Доказать.
1.В качестве образующёй класса можно взять любой элемент из этого класса.
2.Если два класса имеют хотя бы один общий элемент, то они совпадают.
3.Число классов конечно.
***
1.В качестве образующёй класса можно взять любой элемент из этого класса.
Это тривиально.
$U$ - унимодулярная матрица.
$A_1=UA$
$A={U^_{-1}} A_1$
$C=U_1A=U_1{U^_{-1}} A_1=U_2A_1$

2.Если два класса имеют хотя бы один общий элемент, то они совпадают.
Это тоже.
Пусть для класса $A$ и $B$ для некоторых представителей выполняется
$U_1A=U_2B$
Тогда для любого элемента класса $A$ имеем
$U_3A=U_3U_1^{-1}(U_1A)=U_3U_1^{-1}(U_2B)=U_4B$

3.Число классов конечно.
Это чуть сложнее.
Любую целочисленную матрицу можно представить ввиде произведения унимодулярной матрицы на треугольную, у которой все элементы, лежащие ниже главной диагонали, равны нулю, диагональные элементы положительны, а элементы, лежащие выше главной диагонали неотрицательны и меньше диагональных элементов того же столбца.
Для первокурсников, измученных нарзаном и методом Гаусса, это не представляет труда.
Можно показать,
-что для всех элементов одного класса такая треугольная матрица одна и только одна.
То есть, из равенства
$U_1T1=U_2T_2$
следует
$T_1=T_2$
$U_1=U_2$
-разные классы имеют разные треугольные матрицы с перчисленными выше условиями.
Далее.
Поскольку максимальный элемент таких матриц лежит на главной диагонали и ограничен,/он не может быть больше значения определителя рассматриваемых матриц/ конечно число таких матриц, а вместе с тем конечно и число классов.

[ewert]

Коровьев писал(а):

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

Доказать.
1.В качестве образующёй класса можно взять любой элемент из этого класса.
2.Если два класса имеют хотя бы один общий элемент, то они совпадают.
3.Число классов конечно.
***
1.В качестве образующёй класса можно взять любой элемент из этого класса.
Это тривиально.
$U$ - унимодулярная матрица.
$A_1=UA$
$A={U^_{-1}} A_1$
$C=U_1A=U_1{U^_{-1}} A_1=U_2A_1$

2.Если два класса имеют хотя бы один общий элемент, то они совпадают.
Это тоже.
Пусть для класса $A$ и $B$ для некоторых представителей выполняется
$U_1A=U_2B$
Тогда для любого элемента класса $A$ имеем
$U_3A=U_3U_1^{-1}(U_1A)=U_3U_1^{-1}(U_2B)=U_4B$

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

Тогда п.п. 1 и 2 просто отпадают.

---------------------------------------------------------------------
Да, а вот, кстати, в этой связи задачка, решение которой хотя и очень просто, но почему-то кажется мне всё же не совсем тривиальным. Совпадают ли отношения правой и левой эквивалентности?

[Коровьев]

ewert писал(а):

Коровьев писал(а):

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

Доказать.
1.В качестве образующёй класса можно взять любой элемент из этого класса.
2.Если два класса имеют хотя бы один общий элемент, то они совпадают.
3.Число классов конечно.
***
1.В качестве образующёй класса можно взять любой элемент из этого класса.
Это тривиально.
$U$ - унимодулярная матрица.
$A_1=UA$
$A={U^_{-1}} A_1$
$C=U_1A=U_1{U^_{-1}} A_1=U_2A_1$

2.Если два класса имеют хотя бы один общий элемент, то они совпадают.
Это тоже.
Пусть для класса $A$ и $B$ для некоторых представителей выполняется
$U_1A=U_2B$
Тогда для любого элемента класса $A$ имеем
$U_3A=U_3U_1^{-1}(U_1A)=U_3U_1^{-1}(U_2B)=U_4B$

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

Тогда п.п. 1 и 2 просто отпадают.

---------------------------------------------------------------------
Да, а вот, кстати, в этой связи задачка, решение которой хотя и очень просто, но почему-то кажется мне всё же не совсем тривиальным. Совпадают ли отношения правой и левой эквивалентности?

***
Ну, задача и выражения целиком взяты из Фаддеева/два "д"/. Сборник задач по высшей алгебре.
Насчёт правой и левой - надо подумать.

[Коровьев]

Произвольно от отрезка отрезали отрезки:
1) Два
2)N
Какова вероятность в каждом случае, что сумма длин отрезков будет меньше половины первоначального отрезка?

[TOTAL]

Коровьев писал(а):

Произвольно от отрезка отрезали отрезки:
1) Два
2)N
Какова вероятность в каждом случае, что сумма длин отрезков будет меньше половины первоначального отрезка?

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

[Коровьев]

А пусть как брёвна на дрова в деревне пилят - последовательно от одного конца. Хотя мне разницы не видно с намеченными точками разреза, допустим, от одного конца.