Кострикин. Курс алгебры, задачник

[xagiwo]

Вообще, я тут подумал, жалкий из меня помощник. Так что пойду-ка я отсюда... Мои извинения Sinoidу за то, что запутал его и всем, кому придётся распутывать его обратно.
Удачи!
кстати, если слишком долго застреваете на одной задаче, иногда это значит, что имеет смысл оставить её на потом и двигаться дальше

[Sinoid]

Так, пока ни о чем, на будущее. Вот, когда я с одним Курошом наперевес штурмовал задачник Фаддева, Сомнинского, по эпизодическим даже не упоминаниям, а вкраплениям слова редукция, я понял, что это метод решения задач, состоящий в переходе от данной задачи к некоторой соответствующей в некотором $\mathbb{Z}_{n}$. Вот эти слова:

nnosipov в сообщении #1001575 писал(а):

Ну как же ... Редуцируем коэффициенты по модулю $p$, после чего должна получится тривиальная линейная комбинация. Значит, все коэффициенты делились на $p$. Но они же были ... какими?

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

[nnosipov]

Sinoid в сообщении #1549066 писал(а):

или в математике это слово, имеющее несколько значений?

Разумеется, это слово многозначное, и не только в математике. Общий смысл: "редуцировать" --- это "свести" к чему-либо как-либо.

[Sinoid]

А, понятно. Спасиб большой.

[Sinoid]

Задача 8.12.
Пусть $A$ - целочисленная матрица и $d$- наименьший из модулей ее элементов. Доказать, что если при целочисленных элементарных преобразованиях строк и столбцов матрицы $A$ число $d$ не уменьшается, то $d$ делит все элементы матрицы $A$.
Вот, что сказано в указании:

Это же в самом начале хотели написать Если $d=\left|a_{ij}\right|$ , а везде, где $d$ взято в модуль, этого делать не следовало? А вместо формулы $b_{2}=dq+s$ нужно было написать формулу $b_{2p}=dq+s$, а еще лучше формулу $b_{2p}=dq_p+s_p$, где $2\leqslant p\leqslantколичества столбцов в матрице $A$?

-- 27.02.2022, 19:02 --

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

Sinoid в сообщении #1549634 писал(а):

$b_{2}=dq+s$ нужно было написать формулу $b_{2p}=dq+s$, а еще лучше формулу $b_{2p}=dq_p+s_p$,

в первом столбце этой строки стоит 0. Но это, вообще говоря, совершенно другие элементы, нежели стояли в исходной матрице $A$. И по делимости этих элементов на $d$ делается вывод о делимости на $d$ и элементов исходной матрицы $A$. Хоть убей, пока не могу понять этого и все тут!

[Sinoid]

Наверное, про $d$ следовало написать, что это не просто наименьший из модулей элементов матрицы $A$, а наименьший из модулей отличных от 0 элементов матрицы $A$?

[Sinoid]

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

Sinoid в сообщении #1549634 писал(а):

Это же в самом начале хотели написать Если $d=\left|a_{ij}\right|$ , а везде, где $d$ взято в модуль, этого делать не следовало? А вместо формулы $b_{2}=dq+s$ нужно было написать формулу $b_{2p}=dq+s$, а еще лучше формулу $b_{2p}=dq_p+s_p$, где $2\leqslant p\leqslantколичества столбцов в матрице $A$?

Это действительно некорректности или это я что-то неправильно понимаю?

[Sinoid]

Я тут несколько дней провозился вот с этим:

Sinoid в сообщении #1529154 писал(а):

У меня получается, что если некоторый целоисчисленный и с целыми элементами определитель делится на некоторое простое число $p$, то хотя бы к одной его строке (столбцу) можно прибавить такую целоисчисленную комбинацию остальных его строк (столбцов), что все элементы вновь полученной(-го) строки (столбца) будут делиться на это простое $p$. Но, как это доказать, я пока, к сожалению, не знаю. Вообще, это же верное утверждение?

Я понял, как нужно искать в определители ту строку, к которой нужно прибавлять целые кратные некоторых других строк, чтобы получилась строка, все элементы которой делятся на $p$ (в этой части объяснения и ниже в оффтопе будут действовать обозначения из приведенной выше цитаты в этом посте), я понял, как определять, какие строки и с какими коэффициентами нужно прибавлять к этой строке. Короче, я понял все!

(Оффтоп)

Оказалось, что для этого нужно заменить каждый элемент определителя соответствующим остатком от деления на $p$ этого элемента и начать рассматривать полученный определитель в поле $\mathbb{Z}_{p}$. В этом поле он равен 0. А известно, что вся теория определителей дословно переносится и на определители с элементами из этих полей. Получается, что между строками полученного таким образом определителя существует в $\mathbb{Z}_{p}$ линейная зависимость и задача сводится всего лишь к выявления этой зависимости. Ну, а это сделать проще-простого: я всего лишь начинал в $\mathbb{Z}_{p}$ замену в каких-либо столбцах, каких - смотрел, как удобно мне, всех его элементов, кроме одного, удобного мне, нулями и т. д., и т. п. Короче, на каком-то этапе эта зависимость становилась очевидной. В одном или двух случаях приходилось доходить до упора: оставалось 2 строки, которые, естественно, оказывались пропорциональными. Банальная зависимость между векторами. Записывал ее. А когда делал манипуляции со строками, после каждой манипуляции получал новый определитель. Так, когда получал зависимость между строками, с помощью формул, связывающих строки следующего определителя со строками предыдущего, отматывал все назад и назад, пока не получал линейную зависимость между строками исходного определителя, а потом уже становилось все очевидным.

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

[Sinoid]

Нет, все: бился, бился над задачей, что-то никак. Пора послушать умных людей. Итак, задача 8.13:
Доказать, что с помощью элементарных преобразований строк и столбцов над кольцом $\mathbb{Z}$ любую целочисленную матрицу можно привести к виду $\begin{pmatrix}A & 0\\ 0 & 0 \end{pmatrix}$, где $A=\mathrm{diag}\left\{ d_{1},\ldots,d_{r}\right\}$ и $d_{i}\mid d_{i+1}$, ($i=1,\,2,\ldots,\, r-1$).
Там ниже в другой задаче требуется вообще доказать, что такой вид, к которому приводится данная матрица, определен с точностью до знаков отличных от 0 элементов главной диагонали. Но это мне сейчас видится вообще как заклинание, доступное только для посвященных в высшие круги какого-нибудь ордена Итак, что удалось надумать? Допустим, у нас была целочисленная матрица $2\times 2$ и нам каким-то образом (каким - вопрос для меня еще не вполне отчетливо видимый, я вижу его лишь в общих чертах пока) удалось привести к эквивалентной целочисленной матрице $\begin{pmatrix}c_{1} & 0\\ 0 & c_{2} \end{pmatrix}$. Нужно доказать, что от этой матрице можно перейти при помощи названных в задаче преобразований к матрице указанного в задаче вида. Прежде всего сразу бросается в глаза, что заслуживает интереса для рассмотрения только тот случай, когда оба числа - $c_1$ и $c_2$ - отличны от нуля: иначе доказывать просто нечего. Пусть $e_{1}=\text{НОД}(c_{1},\, c_{2})$. Тогда существуют такие целые $u_1,\,u_2$, что $e_{1}=u_{1}c_{1}+u_{2}c_{2}$. Значит, прибавляя к первой строке (или отнимая от нее - в зависимости от знака $u_2$) вторую строку $\left|u_{2}\right|$ раз, а затем прибавляя ко второму столбцу (или отнимая от него - теперь уже в зависимости от знака $u_1$) первый столбец $\left|u_{1}\right|$ раз. получаем следующую последовательность эквивалентных матриц: $\begin{pmatrix}c_{1} & 0\\ 0 & c_{2} \end{pmatrix}\sim\begin{pmatrix}c_{1} & u_{2}c_{2}\\ 0 & c_{2} \end{pmatrix}\sim\begin{pmatrix}c_{1} & u_{1}c_{1}+u_{2}c_{2}\\ 0 & c_{2} \end{pmatrix}=\begin{pmatrix}c_{1} & e_1\\ 0 & c_{2} \end{pmatrix}$. Последняя матрица, т. к. $e_{1}\mid c_{1}$ и $e_{1}\mid c_{2}$, эквивалентна следующим: $\begin{pmatrix}0 & e_1\\ e_2 & 0 \end{pmatrix}\sim\begin{pmatrix}e_1 & 0\\ 0 & e_2 \end{pmatrix}$. Чтобы найти $e_2$, достаточно заметить, что на протяжении всех преобразований менялся от силы знак определителей матриц, ну, никак не модуль этих определителей, т. е., если я из уравнения $c_{1}c_{2}=e_{1}e_2$ напишу, что $e_{2}=\dfrac{c_{1}c_{2}}{e_{1}}=\dfrac{c_{1}c_{2}}{\text{НОД}(c_{1},\, c_{2})}=\text{НОК}(c_{1},\, c_{2}) $ и положу, что $d_{1}=e_{1}$ и $d_{2}=e_{2}$, то этим я построю матрицу, требующуюся построить для данной матрицы, лишь с точностью до знаков отличных от 0 элементов построенной матрицы, что, впрочем, вполне допустимо для задач такого типа. Итак, можно считать, что для матриц $2\times 2$ эта задача с горем пополам решена. Далее. Беру матрицу $3\times 3$: $\begin{pmatrix}c_{1} & 0 & 0\\ 0 & c_{2} & 0\\ 0 & 0 & c_{3} \end{pmatrix}$. Что тут приходит в голову? Прежде всего бросается в глаза, что, если $d_{1}=\text{НОД}(c_{1},\, c_{2},\, c_{3})$, а $d_{2}=\text{НОД}(c_{1},\, c_{2})$, то $d_{1}\mid d_{2}$. Далее. С помощью разрешенных в задаче преобразований можно получить, например, $d_1$ над $c_3$ и $d_2$ над $c_2$, но потом, даже при попытке преобразования полученной матрицы к диагональной матрице с диагональю $d_1,\,d_2,\,f_3$, вовсе неочевидно, что $f$ получится кратным $d_2$. Или это неочевидно только мне?

[vpb]

Насколько я помню, Вы проработали когда-то книжку Куроша. Загляните в главу 13, параграф 59, там такая задача для колец многочленов решается. Или "Основы линейной алгебры" Мальцева, там тоже есть (только книжки, или даже её файла, сейчас под рукой нет, так вышло). А как те рассуждения перенести на матрицы, элементы которых --- не многочлены с коэффициентами из поля, а целые числа ---сами подумайте.

[Sinoid]

vpb
Ой, большое спасибо, что откликнулись. Я уж думал, опять всем надоел до такой степени, что перестали со иной общаться. Вы знаете, я пока погожу подглядывать: вчера мне в голову пришла интересная идея: мне кажется я понял, как в целочисленной матрице с помощью элементарных преобразований над строками и столбцами получить НОД всех элементов этой матрицы. Поясню на примере $2\times 2$ матрицы. Ведь в ней в силу алгоритма Евклида кругами, кругами можно уменьшить исходно наименьший по модулю элемент до НОД всех элементов этой матрицы. Это как вот моется же рука об руку. Так и тут: строка об строку, столбец об столбец я буду последовательно все уменьшать и уменьшать этот наименьший по модулю элемент. И, таким образом, если, например, в исходной матрице этот наименьший по модулю элемент стоял во второй строке и первом столбце, а круг я начал по часовой стрелке, то уже после первого же уменьшения за счет первого и второго столбцов полученный уже уменьшенный наименьший элемент будет иметь вид $k_{11}a_{11}+k_{12}a_{12}+k_{21}a_{21}+k_{22}a_{22}$, где все $k$ - целые, а $a_{ij}$ - элементы исходной матрицы, и т. д., и т. д., а наименьший по модулю все меньше и меньше, а вид у него такой же. А тогда по теореме про НОД, доказанной в курсе Кострикина, я рано или поздно получу НОД всех элементов исходной матрицы, потом обнуляю все остальные элементы, стоящие в одной строке или одной матрицы с этим полученным НОД, а там уже и индукция начинает в дверь ломиться... Сейчас я хочу на конкретных матрицах пообкатывать это все. Хочу в Maple генерировать случайную матрицу и находить НОД всех ее элементов, и т. д. И так несколько раз. Да вот беда: не знаю, как в Maple получить список элементов матрицы. Вчера полчаса посидел, пособирал в мануале кирпичики для этого. Я так думаю. будет что-то через

for

Спасибо!

-- 10.03.2022, 16:45 --

Вот с однозначностью такого вида не знаю, что делать...

-- 10.03.2022, 16:48 --

vpb в сообщении #1550136 писал(а):

Насколько я помню, Вы проработали когда-то книжку Куроша.

Я там понял далеко не каждое доказательство.

[nnosipov]

Это называется нормальная форма Смита: https://en.wikipedia.org/wiki/Smith_normal_form Про нее можно также прочитать в книге: В. В. Прасолов. Задачи и теоремы линейной алгебры. М.: МЦНМО, 2015.

И еще одно место: см. п. D) на стр. 40-42 в книге: Л. С. Понтрягин. Непрерывные группы. М.: Наука, 1973.

И еще (про так называемые $\lambda$-матрицы): параграф 22 в книге: И. М. Гельфанд. Лекции по линейной алгебре. М.: МЦНМО, 1998.

[Sinoid]

nnosipov в сообщении #1550150 писал(а):

Это называется нормальная форма Смита: https://en.wikipedia.org/wiki/Smith_normal_form Про нее можно также прочитать в книге: В. В. Прасолов. Задачи и теоремы линейной алгебры. М.: МЦНМО, 2015.

И еще одно место: см. п. D) на стр. 40-42 в книге: Л. С. Понтрягин. Непрерывные группы. М.: Наука, 1973.

И еще (про так называемые $\lambda$-матрицы): параграф 22 в книге: И. М. Гельфанд. Лекции по линейной алгебре. М.: МЦНМО, 1998.

Так нет: я-то не хочу подглядывать готовые решения, я-то, если уж взялся, то хочу по возможности сам решать, ну, или с как можно минимальными подсказками.

-- 19.03.2022, 00:07 --

vpb в сообщении #1550136 писал(а):

Загляните в главу 13, параграф 59, там такая задача для колец многочленов решается. Или "Основы линейной алгебры" Мальцева, там тоже есть (только книжки, или даже её файла, сейчас под рукой нет, так вышло). А как те рассуждения перенести на матрицы, элементы которых --- не многочлены с коэффициентами из поля, а целые числа ---сами подумайте.

vpb
то же самое: это не будет называться сам решил - это будет подсмотрел, это будет неинтересно, это будет хуже для запоминания, это будет совсем никак!

-- 19.03.2022, 00:12 --

nnosipov в сообщении #1550150 писал(а):

Это называется нормальная форма Смита:

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

-- 19.03.2022, 00:47 --

Ну, вот с наименьшими по модулю понятно: если $a$-НОД целых чисел $a_{1},\, a_{2},\ldots,a_{n}$, то ни при каких целых $k_{1},\, k_{2},\ldots,k_{n}$ выражение $k_{1}a_{1}+k_{2}a_{2}+\ldots+k_{n}a_{n}$ не будет по модулю меньше $a$. А дальше же индукция по натуральному от 1 до минимума количества строк и столбцов в исходной матрице?

[vpb]

Sinoid в сообщении #1550696 писал(а):

о же самое: это не будет называться сам решил

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

[Sinoid]

vpb в сообщении #1550732 писал(а):

Понятно, что вам хочется решить задачу самостоятельно "из принципа".

Я далеко не с каждой задачей так делаю: я понимаю, что при цели решить абсолютно все самостоятельно у меня уйдет нереально много времени, потому что эти все знания копились поколениями и веками, поэтому очень часто я читаю указания к задаче. Но в подавляющем большинстве случаев это - максимальная подсказка, которую я себе позволяю. Не считая этого форума, конечно. Но это уже при безрезультативности подсказки в книге. А принцип тут совсем не причем, это вообще не оттуда у меня, поверьте.