2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему
 
 Определитель целочисленной матрицы по модулю простого числа
Сообщение29.12.2010, 19:40 


26/01/10
959
Вопрос к специалистам по линейной алгебре.

Имеется матрица $A$, составленная из неотрицательных целых чисел. Требуется отыскать определитель матрицы по модулю некоторого простого числа $p$.

Обычный метод Гаусса в этом случае не работает. Решается ли такая задача за кубическое время? Каким методом?

 Профиль  
                  
 
 Re: Определитель целочисленной матрицы по модулю простого числа
Сообщение29.12.2010, 19:43 
Аватара пользователя


14/08/09
1140
Zealint в сообщении #393436 писал(а):
Обычный метод Гаусса в этом случае не работает.

Хм... А что значит "обычный"?
Метод Гаусса работает и здесь, только оперировать нужно будет над полем вычетов $\mathbb{Z}_p.$

 Профиль  
                  
 
 Re: Определитель целочисленной матрицы по модулю простого числа
Сообщение29.12.2010, 19:45 
Заслуженный участник
Аватара пользователя


21/12/05
5931
Новосибирск
Zealint в сообщении #393436 писал(а):
Обычный метод Гаусса в этом случае не работает.

С чего бы это? Метод Гаусса работает в любом поле, в том числе и в $\mathbb Z/p\mathbb Z$

 Профиль  
                  
 
 Re: Определитель целочисленной матрицы по модулю простого числа
Сообщение29.12.2010, 19:51 


26/01/10
959
Цитата:
Хм... А что значит "обычный"?
Метод Гаусса работает и здесь, только оперировать нужно будет над полем вычетов $\mathbb{Z}_p.$

Ну, обычный, это в моём понимании следующий.

Для строки $k=1,\ldots,n$ выбираем ведущий элемент и выполняем относительно него преобразование Жордана --- Гаусса. Параллельно с этим считаем произведение ведущих элементов. Отличие только в том, что вместо деления на ведущий элемент выполняем умножение на обратное по модулю число. Этот метод даёт неправильные ответы.

 Профиль  
                  
 
 Re: Определитель целочисленной матрицы по модулю простого числа
Сообщение29.12.2010, 19:59 
Аватара пользователя


14/08/09
1140
Zealint в сообщении #393443 писал(а):
Этот метод даёт неправильные ответы.

Правильная реализация метода Гаусса должна давать верный ответ.
Возможно, вам стоит лучше ознакомиться с арифметикой конечных полей (здесь - полей вычетов).

 Профиль  
                  
 
 Re: Определитель целочисленной матрицы по модулю простого числа
Сообщение29.12.2010, 20:08 


26/01/10
959
Пример привожу. Может, я что-то неправильно понимаю?

$$
A=\begin{pmatrix}
0&1&2 \\ 
1&2&6 \\ 
2&6&14 \\ 
\end{pmatrix}, \qquad p = 5.
$$
Если считать не по модулю, то получим $|A|=2$.

Теперь считаем, как в школе учили, только все операции по модулю 5. Для начала все элементы возьмём по модулю 5. В квадратике ведущий элемент.

$$
A=\begin{pmatrix}
0&\fbox{1}&2 \\ 
1&2&1 \\ 
2&1&4 \\ 
\end{pmatrix}
$$

Проводим преобразование: ко второй строке добавим первую, умноженную на 3, к третьей добавим первую, умноженную на 4 (все операции сразу выполняем по модулю 5) ---

$$
A=\begin{pmatrix}
0&1&2 \\ 
\fbox{1}&0&2 \\ 
2&0&2 \\ 
\end{pmatrix}
$$

Теперь к третьей строке добавим вторую, домноженную на 3:


$$
A=\begin{pmatrix}
0&1&2 \\ 
1&0&2 \\ 
0&0&3 \\ 
\end{pmatrix}
$$

Теперь у меня получается 3 в конце. Это значит, что определитель равен 3? Или из-за того, что сейчас перестановка строк имеет нечётное число инверсий я должен взять дополнение тройки до 5?

 Профиль  
                  
 
 Re: Определитель целочисленной матрицы по модулю простого числа
Сообщение29.12.2010, 20:18 
Аватара пользователя


14/08/09
1140
Да, перестановкой первых двух строк ваша конечная матрица приводится к виду $$A'=\begin{pmatrix}
1&0&2 \\
0&1&2 \\  
0&0&3 \\ 
\end{pmatrix}
$$
$|A'|=3$, значит $|A|=-3 \equiv 2 \pmod 5.$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

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



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

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


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

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