2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 "НОД" матриц
Сообщение04.07.2008, 09:36 


11/11/07
80
Доброго времени суток всем!

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

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

 Профиль  
                  
 
 
Сообщение04.07.2008, 09:45 
Заморожен
Аватара пользователя


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

Определение. Пусть $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$.

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

 Профиль  
                  
 
 
Сообщение04.07.2008, 10:04 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение04.07.2008, 10:13 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Brukvalub писал(а):
Профессор Снэйп, исходя из Вашего определения, в кольце целых чисел у каждой пары целых чисел есть не менее двух Н.О.Д. Странно....


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

 Профиль  
                  
 
 
Сообщение04.07.2008, 10:18 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Всегда ли так определенный НОД существует?

 Профиль  
                  
 
 
Сообщение04.07.2008, 10:38 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
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}$, делящих ноль, наибольшего элемента относительно естественного порядка нет.

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

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

 Профиль  
                  
 
 
Сообщение04.07.2008, 10:54 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Профессор Снэйп писал(а):
Добавлю ещё несколько штрихов к картине.
Добавьте все это в Википедию. (Там только про целые и рац. числа.) Почему бы нет?

 Профиль  
                  
 
 
Сообщение04.07.2008, 10:58 


11/11/07
80
Профессор Снэйп писал(а):
Матрицы в задаче, вероятно, не произвольные, а какого-то специального вида.

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

Профессор Снэйп писал(а):
Остаётся только определить отношение делимости на матрицах и применить к нему это определение.

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

 Профиль  
                  
 
 
Сообщение04.07.2008, 11:12 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
TOTAL писал(а):
Профессор Снэйп писал(а):
Добавлю ещё несколько штрихов к картине.
Добавьте все это в Википедию. (Там только про целые и рац. числа.) Почему бы нет?


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

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

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

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

zuj писал(а):
Профессор Снэйп писал(а):
Матрицы в задаче, вероятно, не произвольные, а какого-то специального вида.

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


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

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


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

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

 Профиль  
                  
 
 
Сообщение04.07.2008, 11:20 


11/11/07
80
Профессор Снэйп писал(а):
zuj писал(а):
Профессор Снэйп писал(а):
Матрицы в задаче, вероятно, не произвольные, а какого-то специального вида.

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


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


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

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

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

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

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

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

 Профиль  
                  
 
 
Сообщение04.07.2008, 11:25 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
zuj писал(а):
так то оно так только меня интересует сама матрица, а не ее определитель, то есть интересно как будет выглядеть матрица.


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

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

 Профиль  
                  
 
 
Сообщение04.07.2008, 11:26 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
zuj писал(а):
так то оно так только меня интересует сама матрица, а не ее определитель, то есть интересно как будет выглядеть матрица.
Поясните, пожалуйста. Вы сами придумали найти НОД матриц, но не придумали, что такое НОД для матриц?
Или кто-то дал Вам задание, а Вы не понимаете, что от Вас хотят?

 Профиль  
                  
 
 
Сообщение04.07.2008, 11:41 


11/11/07
80
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}
Оговорим что НОД ищется слевой стороны.
Матрицы взял с потолка поэтому ничего не могу сказать есть ли у них вообще НОД или нет.

 Профиль  
                  
 
 
Сообщение04.07.2008, 11:43 
Заслуженный участник
Аватара пользователя


23/08/07
5420
Нов-ск
Кстати, можете записать свои матрицы так
$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$
и поступить как с многочленами.

 Профиль  
                  
 
 
Сообщение04.07.2008, 12:00 


11/11/07
80
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}

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 29 ]  На страницу 1, 2  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group