"НОД" матриц

[zuj]

Доброго времени суток всем!

Что такое НОД двух полиномов вроде бы понятно. А вот что такое "НОД" двух матриц (одинаковых рамерностей)?

Буду благодарен любому иллюстрируещему примеру или ссылке на соответствующую литературу.

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

Ну, понятие НОДа вроде бы универсально и не зависит от того, какие объекты рассматриваются.

Определение. Пусть $A$ --- произвольное множество с заданным на нём отношением делимости $\mathbin{|}$ ($a \mathbin{|} b$ читается как "$a$ делит $b$"). Тогда для $a,b \in A$ элемент $c \in A$ называется наибольшим общим делителем элементов $a$ и $b$, если $c \mathbin{|} a$, $c \mathbin{|} b$ и для любого $d \in A$, такого что $d \mathbin{|} a$ и $d \mathbin{|} b$, справедливо $d \mathbin{|} c$.

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

[Brukvalub]

Профессор Снэйп, исходя из Вашего определения, в кольце целых чисел у каждой пары целых чисел есть не менее двух Н.О.Д. Странно....

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

Brukvalub писал(а):

Профессор Снэйп, исходя из Вашего определения, в кольце целых чисел у каждой пары целых чисел есть не менее двух Н.О.Д. Странно....

Нет, это не странно. Так оно и есть. НОД элементов в кольце определяется с точностью до умножения на единицу (то есть обратимый элемент, не путать с единичным элементом!) кольца. В кольце $\mathbb{Z}$ две единицы: $1$ и $-1$.

[TOTAL]

Всегда ли так определенный НОД существует?

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

TOTAL писал(а):

Всегда ли так определенный НОД существует?

Нет, конечно, не всегда.

Добавлю ещё несколько штрихов к картине. Пусть $A$ --- произвольное (коммутативное, ассоциативное, с единицей) кольцо. Тогда на $A$ можно ввести отношение делимости:

$$ a \mathbin{|} b \Leftrightarrow (\exists c \in A)(a \cdot c = b) $$

Отношение делимости --- это не то же самое, что операция деления. К примеру, в кольце $\mathbb{Z}$ число $0$ делит $0$, но спрашивать о том, чему равен результат деления --- бессмысленно

Так вот: это отношение --- оно рефлексивно (если кольцо с единицей) и транзитивно (в ассоциативных кольцах). То есть является предпорядком. С ним естественным образом ассоциируется частичный порядок. И вот наибольший общий делитель $a$ и $b$ --- это ни что иное, как инфимум элементов $[a]$ и $[b]$ в этом ЧУМе. Соответственно НОК --- супремум.

Когда говорят, что общий делитель "наибольший", то всегда подразумевают, что наибольший он относительно порядка по делимости, а не относительно какого-то другого порядка. В частности, в $\mathbb{Z}$ НОД двух нулей будет равен нулю, ибо ноль --- наибольший элемент в $\mathbb{Z}$ относительно делимости, хотя среди элементов $\mathbb{Z}$, делящих ноль, наибольшего элемента относительно естественного порядка нет.

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

Ну и продолжая отвечать на вопрос... Произвольный ЧУМ ведь не обязан быть нижней полурешёткой (то есть в нём не обязан существовать инфимум произвольного двухэлементного подмножества). Соответственно, когда порядок --- это делимость, то НОД у двух элементов тоже не всегда должен существовать.

[TOTAL]

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

Добавлю ещё несколько штрихов к картине.

Добавьте все это в Википедию. (Там только про целые и рац. числа.) Почему бы нет?

[zuj]

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

Матрицы в задаче, вероятно, не произвольные, а какого-то специального вида.

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

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

Остаётся только определить отношение делимости на матрицах и применить к нему это определение.

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

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

TOTAL писал(а):

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

Добавлю ещё несколько штрихов к картине.

Добавьте все это в Википедию. (Там только про целые и рац. числа.) Почему бы нет?

По двум причинам.

1) Я не умею туда что-то добавлять.

2) Добавлять что-то в Википедию --- слишком большая ответственность. Тех книжек, в которых я когда-то всё это прочитал, у меня сейчас нет. Если на форуме чуть-чуть наврать, то это не страшно, народ умный, разберётся, поправит, если что. А к энциклопедии же кто-то будет обращаться как к источнику знаний, обладающему непререкаемым авторитетом. Нет уж, я если что-то и буду туда добавлять, то только по своей узкой специальности.

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

zuj писал(а):

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

Матрицы в задаче, вероятно, не произвольные, а какого-то специального вида.

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

Замечу, что Вы сами себе противоречите. Сначала пишете, что в матрицах ничего специального нет, дескать, они произвольные, а потом тут же говорите, что их элементами являются многочлены (а не функции, к примеру, или какие-нибудь $p$-адические числа).

zuj писал(а):

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

К сожалению, ничего не могу Вам посоветовать. Подождите, может придёт кто-нибудь, кто лучше меня в алгебре шарит. Ну или поройтесь в справочниках. Ключевые слова: факториальные кольца, евклидовы кольца, кольца главных идеалов, наибольший общий делитель, алгоритм Евклида... Может, что-то ещё.

Единственное, что на ум сразу пришло и что, может быть, поможет. Произведение определителей равно определителю произведения. В Вашем же случае определители --- это как раз многочлены. И определитель НОДа матриц будет НОДом определителей. То есть, по крайней мере, из алгоритма Евклида для многочленов какую-то информацию Вы всё же извлечёте.

[zuj]

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

zuj писал(а):

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

Матрицы в задаче, вероятно, не произвольные, а какого-то специального вида.

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

Замечу, что Вы сами себе противоречите. Сначала пишете, что в матрицах ничего специального нет, дескать, они произвольные, а потом тут же говорите, что их элементами являются многочлены (а не функции, к примеру, или какие-нибудь $p$-адические числа).

Ок признаю, нужно было уточнить.

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

К сожалению, ничего не могу Вам посоветовать. Подождите, может придёт кто-нибудь, кто лучше меня в алгебре шарит.

Подождем а пока ...

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

Ну или поройтесь в справочниках. Ключевые слова: факториальные кольца, евклидовы кольца, кольца главных идеалов, наибольший общий делитель, алгоритм Евклида... Может, что-то ещё.

... пороемся .

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

Единственное, что на ум сразу пришло и что, может быть, поможет. Произведение определителей равно определителю произведения. В Вашем же случае определители --- это как раз многочлены. И определитель НОДа матриц будет НОДом определителей. То есть, по крайней мере, из алгоритма Евклида для многочленов какую-то информацию Вы всё же извлечёте.

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

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

zuj писал(а):

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

Может, Вы конкретно две матрицы выпишите, для которых надо НОД найти?

Кстати, смущает ещё то, что умножение матриц не коммутативно. Не возникнет ли вдруг такой ситуации, когда одна матрица делит другую матрицу слева и не делит справа?

[TOTAL]

zuj писал(а):

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

Поясните, пожалуйста. Вы сами придумали найти НОД матриц, но не придумали, что такое НОД для матриц?
Или кто-то дал Вам задание, а Вы не понимаете, что от Вас хотят?

[zuj]

TOTAL писал(а):

Или кто-то дал Вам задание, а Вы не понимаете, что от Вас хотят?

Нет задание мне никто не давал ... меня самого просто интересует какие алгоритмы существуют и существуют ли они вообще для поиска НОДа.

TOTAL писал(а):

zuj писал(а):

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

Поясните, пожалуйста. Вы сами придумали найти НОД матриц, но не придумали, что такое НОД для матриц?

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

Добавлено спустя 3 минуты 34 секунды:

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

zuj писал(а):

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

Кстати, смущает ещё то, что умножение матриц не коммутативно. Не возникнет ли вдруг такой ситуации, когда одна матрица делит другую матрицу слева и не делит справа?

так и будет ... нужно будет оговаривать с какой стороны ищется НОД

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

Может, Вы конкретно две матрицы выпишите, для которых надо НОД найти?

Ну к примеру такие матрицы:
A=\begin{bmatrix} x^2+1 & x\\ 1 & x-2 \end{bmatrix}
и
B=\begin{bmatrix} x^2 - x + 3 & x^2\\ x + 2 & x^3 - x + 2 \end{bmatrix}
Оговорим что НОД ищется слевой стороны.
Матрицы взял с потолка поэтому ничего не могу сказать есть ли у них вообще НОД или нет.

[TOTAL]

Кстати, можете записать свои матрицы так
$A=A_nx^n+A_{n-1}x^{n-1} + \hdots + A_1x+A_0$
$B=B_mx^m+B_{m-1}x^{m-1} + \hdots + B_1x+B_0$
и поступить как с многочленами.

[zuj]

TOTAL писал(а):

Кстати, можете записать свои матрицы так
$A=A_nx^n+A_{n-1}x^{n-1} + \hdots + A_1x+A_0$
$B=B_mx^m+B_{m-1}x^{m-1} + \hdots + B_1x+B_0$
и поступить как с многочленами.

Если поступить как Вы предлагаете, то матрицы $A$ и $B$ можно переписать как
A= \begin{bmatrix} 1 & 0\\ 0 & 0 \end{bmatrix}x^2+ \begin{bmatrix} 0 & 1\\ 0 & 1 \end{bmatrix}x+ \begin{bmatrix} 1 & 0\\ 1 & -2 \end{bmatrix}
и
B= \begin{bmatrix} 0 & 0\\ 0 & 1 \end{bmatrix}x^3+ \begin{bmatrix} 1 & 1\\ 0 & 0 \end{bmatrix}x^2+ \begin{bmatrix} -1 & 0\\ 1 & -1 \end{bmatrix}x+ \begin{bmatrix} 3 & 0\\ 2 & 2 \end{bmatrix}

Откровенно говоря мне неочевидно что делать дальше