Нахождение обратной матрицы с элементами поля Галуа.

[lomaxe]

Здравствуйте.
Надеюсь, что написал в правильный раздел. Остальные разделы вроде бы не подходят для данного вопроса.
В общем, решая задачу, связанную с кодированием информации помехозащитными кодами, столкнулся с такой проблемой. Есть уравнение, записано в виде произведения матриц, элементами которой являются элементы поля Галуа GF(8).
$\begin{bmatrix}\alpha^5&\alpha^6\\ \alpha^3&\alpha^5$\end{bmatrix}\begin{bmatrix}e_1\\e_2\end{bmatrix}=\begin{bmatrix}\alpha^6\\ \alpha^0\end{bmatrix}

Таблица сложения для поля Галуа GF(8):

$\setcounter{MaxMatrixCols}{20} \begin{matrix}&\alpha^0&\alpha^1&\alpha^2&\alpha^3&\alpha^4&\alpha^5&\alpha^6&\\\alpha^0&0&\alpha^3&\alpha^6&\alpha^1&\alpha^5&\alpha^4&\alpha^2\\\alpha^1&\alpha^3&0&\alpha^4&\alpha^0&\alpha^2&\alpha^6&\alpha^5\\\alpha^2&\alpha^6&\alpha^4&0&\alpha^5&\alpha^1&\alpha^3&\alpha^0\\\alpha^3&\alpha^1&\alpha^0&\alpha^5&0&\alpha^6&\alpha^2&\alpha^4\\\alpha^4&\alpha^5&\alpha^2&\alpha^1&\alpha^6&0&\alpha^0&\alpha^3\\\alpha^5&\alpha^4&\alpha^6&\alpha^3&\alpha^2&\alpha^0&0&\alpha^1\\\alpha^6&\alpha^2&\alpha^5&\alpha^0&\alpha^4&\alpha^3&\alpha^1&0\end{matrix}$

Таблица умножения для поля Галуа GF(8):

$\setcounter{MaxMatrixCols}{20} \begin{matrix}&\alpha^0&\alpha^1&\alpha^2&\alpha^3&\alpha^4&\alpha^5&\alpha^6&\\\alpha^0&\alpha^0&\alpha^1&\alpha^2&\alpha^3&\alpha^4&\alpha^5&\alpha^6\\\alpha^1&\alpha^1&\alpha^2&\alpha^3&\alpha^4&\alpha^5&\alpha^6&\alpha^0\\\alpha^2&\alpha^2&\alpha^3&\alpha^4&\alpha^5&\alpha^6&\alpha^0&\alpha^1\\\alpha^3&\alpha^3&\alpha^4&\alpha^5&\alpha^6&\alpha^0&\alpha^1&\alpha^2\\\alpha^4&\alpha^4&\alpha^5&\alpha^6&\alpha^0&\alpha^1&\alpha^2&\alpha^3\\\alpha^5&\alpha^5&\alpha^6&\alpha^0&\alpha^1&\alpha^2&\alpha^3&\alpha^4\\\alpha^6&\alpha^6&\alpha^0&\alpha^1&\alpha^2&\alpha^3&\alpha^4&\alpha^5\end{matrix}$

Пытаюсь решить это уравнение матричным способом. Соответсвтенно:

$\begin{bmatrix}e_1\\e_2\end{bmatrix}=\begin{bmatrix}\alpha^6\\ \alpha^0\end{bmatrix}\begin{bmatrix}\alpha^5&\alpha^6\\ \alpha^3&\alpha^5$\end{bmatrix}^{-1}

И вот тут то вот и возникают проблемы при нахождении обратной матрицы стандартным способом:

$\begin{vmatrix}A\end{vmatrix}^{-1}=\frac{cofactor\begin{vmatrix}A\end{vmatrix}}{det\begin{vmatrix}A\end{vmatrix}};$ $cofactor\begin{bmatrix}\alpha^5&\alpha^6\\ \alpha^3&\alpha^5$\end{bmatrix}=\begin{bmatrix}\alpha^5&\alpha^3\\ \alpha^6&\alpha^5$\end{bmatrix};$ $det\begin{bmatrix}\alpha^5&\alpha^6\\ \alpha^3&\alpha^5$\end{bmatrix}=\alpha^5\alpha^5-\alpha^3\alpha^6=\alpha^{10}+\alpha^9=\alpha^3+\alpha^5=\alpha^5;$

$\begin{bmatrix}\alpha^5&\alpha^6\\ \alpha^3&\alpha^5$\end{bmatrix}^{-1}=\frac{\begin{bmatrix}\alpha^5&\alpha^3\\ \alpha^6&\alpha^5$\end{bmatrix}}{\alpha^5}=\alpha^{-5}{\begin{bmatrix}\alpha^5&\alpha^3\\ \alpha^6&\alpha^5$\end{bmatrix}}=\alpha^2{\begin{bmatrix}\alpha^5&\alpha^3\\ \alpha^6&\alpha^5$\end{bmatrix}}={\begin{bmatrix}\alpha^7&\alpha^5\\ \alpha^8&\alpha^7$\end{bmatrix}}=$

$=\begin{bmatrix}\alpha^0&\alpha^5\\ \alpha^1&\alpha^0$\end{bmatrix} ;$
Делаем проверку. Если обратную матрицу нашли правильно, то должно выполняться условие:

$\begin{vmatrix}A\end{vmatrix}\begin{vmatrix}A\end{vmatrix}^{-1}=\begin{vmatrix}E\end{vmatrix}$ где $\begin{vmatrix}E\end{vmatrix}$ - единичная матрица;
Умножим исходную матрицу на "обратную":

$\begin{bmatrix}\alpha^5&\alpha^6\\ \alpha^3&\alpha^5$\end{bmatrix}{\begin{bmatrix}\alpha^0&\alpha^5\\ \alpha^1&\alpha^0$\end{bmatrix}}={\begin{bmatrix}\alpha^5+\alpha^7&\alpha^{10}+\alpha^6\\ \alpha^3+\alpha^6&\alpha^8+\alpha^5$\end{bmatrix}}=\begin{bmatrix}\alpha^{12}&\alpha^{16}\\ \alpha^9&\alpha^{13}$\end{bmatrix}=\begin{bmatrix}\alpha^4&\alpha^2\\ \alpha^2&\alpha^6$\end{bmatrix}$

Как видим, обратную матрицу мы нашли неправильно. Возьмём, к примеру, другую матрицу:

$\begin{bmatrix}\alpha^3&\alpha^5\\ \alpha^5&\alpha^6$\end{bmatrix};$ $cofactor\begin{bmatrix}\alpha^3&\alpha^5\\ \alpha^5&\alpha^6$\end{bmatrix}=\begin{bmatrix}\alpha^6&\alpha^5\\ \alpha^5&\alpha^3$\end{bmatrix};$ $det\begin{bmatrix}\alpha^3&\alpha^5\\ \alpha^6&\alpha^6$\end{bmatrix}=\alpha^3\alpha^6-\alpha^5\alpha^5=\alpha^9+\alpha^{10}=\alpha^5+\alpha^3=\alpha^5;$

Обратная матрица будет:

$\begin{bmatrix}\alpha^3&\alpha^5\\ \alpha^5&\alpha^6$\end{bmatrix}^{-1}=\frac{\begin{bmatrix}\alpha^6&\alpha^5\\ \alpha^5&\alpha^3$\end{bmatrix}}{\alpha^5}=\alpha^{-5}{\begin{bmatrix}\alpha^6&\alpha^5\\ \alpha^5&\alpha^3$\end{bmatrix}}=\alpha^2{\begin{bmatrix}\alpha^6&\alpha^5\\ \alpha^5&\alpha^3$\end{bmatrix}}={\begin{bmatrix}\alpha^8&\alpha^7\\ \alpha^7&\alpha^5$\end{bmatrix}}=$

$=\begin{bmatrix}\alpha^1&\alpha^0\\ \alpha^0&\alpha^5$\end{bmatrix} ;$

Производим проверку:

$\begin{bmatrix}\alpha^3&\alpha^5\\ \alpha^5&\alpha^6$\end{bmatrix}\begin{bmatrix}\alpha^1&\alpha^0\\ \alpha^0&\alpha^5$\end{bmatrix}=\begin{bmatrix}\alpha^4+\alpha^5&\alpha^3+\alpha^{10}\\ \alpha^6+\alpha^6&\alpha^5+\alpha^{11}$\end{bmatrix}=\begin{bmatrix}1&0\\ 0&1\end{bmatrix};$ Тут всё получилось.

И вот я ломаю голову. Почему в первом примере не выходит обратная матрица, как не крути. А во втором получается, хотя и там и там применён алгоритм нахождения обратной матрицы.
Я вообще, путём нехитрых логических выводов нашёл обратную матрицу для первого примера:

$\begin{bmatrix}\alpha^0&\alpha^6\\ \alpha^5&\alpha^0$\end{bmatrix}$

Но вопрос, почему алгоритм не работает???
Помогите пожалуйста разобраться.

[Xaositect]

Если я правильно понял, что cofactor это adjoint, она же присоединенная матрица, то ее надо транспонировать.

[lomaxe]

Xaositect в сообщении #380989 писал(а):

Если я правильно понял, что cofactor это adjoint, она же присоединенная матрица, то ее надо транспонировать.

cofactor - это матрица, состоящая из миноров соответствующих элементов.

Ну, допустим, я транспонирую матрицу в первом и во втором примере. Допустим, это поможем мне найти обратную матрицу в первом примере. Но тогда поменяется матрица во втором примере, и уже там будет найдена неверно обратная матрица. поправьте меня, если я не прав.

[Xaositect]

lomaxe в сообщении #380992 писал(а):

Но тогда поменяется матрица во втором примере

Посмотрите внимательно, как она поменяется при транспонировании :)

[Leox]

просто интересно - как у вас получились таблицы умножения для GF(8) - переписали из книжки или сами реализовали поле профакторизовав по неприводимому многочлену третьей степени?

[lomaxe]

Xaositect в сообщении #380998 писал(а):

Посмотрите внимательно, как она поменяется при транспонировании :)

Да, я посмотрел внимательно. Что получается. Для первого примера:

$\begin{bmatrix}\alpha^0&\alpha^5\\\alpha^1&\alpha^0\end{bmatrix}^T=\begin{bmatrix}\alpha^0&\alpha^1\\\alpha^5&\alpha^0\end{bmatrix}$

$\begin{bmatrix}\alpha^0&\alpha^5\\\alpha^1&\alpha^0\end{bmatrix}\begin{bmatrix}\alpha^0&\alpha^1\\\alpha^5&\alpha^0\end{bmatrix}=\begin{bmatrix}\alpha^5+\alpha^11&\alpha^6+\alpha^6\\\alpha^3+\alpha^{10}&\alpha^4+\alpha^5\end{bmatrix}=$\begin{bmatrix}\alpha^0&0\\0&\alpha^0\end{bmatrix}=$\begin{bmatrix}1&0\\0&1\end{bmatrix}$

Для второго примера:

$\begin{bmatrix}\alpha^1&\alpha^0\\\alpha^0&\alpha^5\end{bmatrix}^T=\begin{bmatrix}\alpha^1&\alpha^0\\\alpha^0&\alpha^5\end{bmatrix}$

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

http://mathem.h1.ru/examples/example.html?3

-- Сб ноя 27, 2010 12:40:42 --

Leox в сообщении #381059 писал(а):

просто интересно - как у вас получились таблицы умножения для GF(8) - переписали из книжки или сами реализовали поле профакторизовав по неприводимому многочлену третьей степени?

Эту таблицу передрал из книжки. Хотя, сам реализовывал таблицу и умножения и сложения для поля GF(16). Таблицу умножения реализовывал путём умножения элементов поля Галуа, складывая их степени по модулю $2^m-1$. В случае поля GF(16), по модулю 15
Таблицу сложения несколько другим способом.

[Xaositect]

lomaxe в сообщении #381060 писал(а):

И всё-таки, это не даёт ответ на мой вопрос. Почему же так выходит? В первом примере нужно делать транспонирование, а во втором не нужно.

Во втором тоже нужно, но присоединенная матрица симметрична, и поэтому оно ничего не меняет.

lomaxe в сообщении #381060 писал(а):

Допустим, транспонирование должно делаться в любом случае, но я вот ради интереса нашёл в интернете алгоритм нахождения обратной матрицы. Про транспонирование там ничего нет:

http://mathem.h1.ru/examples/example.html?3

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

[Someone]

lomaxe в сообщении #380992 писал(а):

cofactor - это матрица, состоящая из миноров соответствующих элементов.

Точно из миноров? А не из алгебраических дополнений? (Хотя в $GF(2^n)$ это одно и то же).

[lomaxe]

Someone в сообщении #381144 писал(а):

lomaxe в сообщении #380992 писал(а):

cofactor - это матрица, состоящая из миноров соответствующих элементов.

Точно из миноров? А не из алгебраических дополнений? (Хотя в $GF(2^n)$ это одно и то же).

Ну да, извиняюсь за неточность. Cofactor - это матрица, состоящая из алгебраический дополнений. Просто не обратил внимания, так как в полях Галуа это не имеет значения. Хотя, тут есть один интересный момент, который ввёл меня несколько в ступор.
Дело в том, что я, вместо того, чтобы повторить действия над матрицами в каком-нибудь учебнике по математике, просто посмотрел пару примеров в той технической книге, которую читаю, ну и по примеру начал делать. А там в одном примере попалась матрица, как можно увидеть выше, что транспонированная от неё матрица имеет тот же вид. Ну, я и не транспонировал матрицу в той задаче, из которой взял пример выше.
А техническая книга, которую я читаю, - на английском. Я именно в этой книге столкнулся с термином cofactor. Особо не задумывался, что он значит. Просто посмотрел пример и как бы сам дошёл.
А теперь вот начал разбираться и стало интересно. Не знаю, то ли это недостаток это й технической книги. В книге написано:

$Inv\begin{bmatrix}A\end{bmatrix}=\frac{cofactor\begin{bmatrix}A\end{bmatrix}}{det\begin{bmatrix}A\end{bmatrix}}$

Я тут порылся, нашёл информацию про то, что такое cofactor:

Cofactor Matrix
Matrix of Cofactors
A matrix with elements that are the cofactors, term-by-term, of a given square matrix.

Example: Find the cofactor matrix of A given that A=$\begin{bmatrix}1&2&3\\0&4&5\\1&0&6\end{bmatrix}$

Solution: First find the cofactor of each element.

$A_{11}=\begin{bmatrix}4&5\\0&6\end{bmatrix}=24\quad A_{12}=\begin{bmatrix}0&5\\1&6\end{bmatrix}=5\quad A_{13}=\begin{bmatrix}0&4\\1&0\end{bmatrix}=-4$

$A_{21}=\begin{bmatrix}2&3\\0&6\end{bmatrix}=-12\quad A_{22}=\begin{bmatrix}1&3\\1&6\end{bmatrix}=3\quad A_{23}=\begin{bmatrix}1&2\\1&0\end{bmatrix}=2$

$A_{31}=\begin{bmatrix}2&3\\4&5\end{bmatrix}=-2\quad A_{32}=\begin{bmatrix}1&3\\0&5\end{bmatrix}=-5\quad A_{33}=\begin{bmatrix}1&2\\0&4\end{bmatrix}=-4$

The cofactor matrix is thus:

$\begin{bmatrix}24&5&-4\\-12&3&2\\-2&-5&4\end{bmatrix}$

Cofactor
The determinant obtained by deleting the row and column of a given element of a matrix or determinant. The cofactor is preceded by a + or – sign depending whether the element is in a + or – position.

+ and - positions in a 4x4 determina: $\begin{bmatrix}+&-&+&-\\-&+&-&+\\+&-&+&-\\-&+&-&+\end{bmatrix}$

Original determinant: $\begin{bmatrix}1&2&3&4\\0&5&\fbox{6}&7\\0&8&9&10\\0&0&0&11\end{bmatrix}$ Cofactor of the circled element $-\begin{bmatrix}1&2&4\\-0&8&10\\0&0&11\end{bmatrix}=-88$

В общем, получается, что cofactor, это матрица, состоящая из алгебраических дополнений, но не транспонированная. И согласно той формуле в книге, по которой находится обратная матрица, cofactor матрицы не транспонируется (хотя в другом примере, данным в книге, видно, что матрицу транспонируют). Получается, что это уже промах данной книги. Хотя удивительно для такой недешёвой книги, что они такое допустили.

-- Вс ноя 28, 2010 00:15:01 --

Но в любом случае, всем большое спасибо за помощь. Особенно Xaositect. Так бы ещё долго голову ломал бы, выясняя, в чём дело.