Определитель целочисленной матрицы по модулю простого числа

[Zealint]

Вопрос к специалистам по линейной алгебре.

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

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

[Mathusic]

Zealint в сообщении #393436 писал(а):

Обычный метод Гаусса в этом случае не работает.

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

[bot]

Zealint в сообщении #393436 писал(а):

Обычный метод Гаусса в этом случае не работает.

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

[Zealint]

Цитата:

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

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

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

[Mathusic]

Zealint в сообщении #393443 писал(а):

Этот метод даёт неправильные ответы.

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

[Zealint]

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

$$ 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?

[Mathusic]

Да, перестановкой первых двух строк ваша конечная матрица приводится к виду

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

$|A'|=3$, значит $|A|=-3 \equiv 2 \pmod 5.$