Построение обратимых матриц большого порядка

[Pavel2015]

Добрый день. Требуется построить обратимую квадратную матрицу размером 9 на 9 над полем GF(2). В этой матрице третий столбец должен состоять только из нулей. Какие подходы могут быть использованы для построения такой матрицы?

[nnosipov]

Pavel2015 в сообщении #924422 писал(а):

Требуется построить обратимую квадратную матрицу размером 9 на 9 над полем GF(2). В этой матрице третий столбец должен состоять только из нулей.

Здесь наука бессильна, надо к колдунам обращаться.

[Brukvalub]

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

[Pavel2015]

Ой, это же опечатка. Условие задачи формулируется следующим образом. Требуется построить обратимую матрицу над GF(2) размера 9 на 9. Эта матрица, а также обратная к ней матрица, должны иметь следующий вид:

$ a_{1,1}, a_{1,2}, 0, a_{1,4}, a_{1,5}, a_{1,6}, a_{1,7}, a_{1,8}, a_{1,9} $
$ a_{2,1}, a_{2,2}, 0, a_{2,4}, a_{2,5}, a_{2,6}, a_{2,7}, a_{2,8}, a_{2,9} $
$ a_{3,1}, a_{3,2}, 1, a_{3,4}, a_{3,5}, a_{3,6}, a_{3,7}, a_{3,8}, a_{3,9} $
$ a_{4,1}, a_{4,2}, a_{4,3}, a_{4,4}, a_{4,5}, 0, a_{4,7}, a_{4,8}, a_{4,9} $
$ a_{5,1}, a_{5,2}, a_{5,3}, a_{5,4}, a_{5,5}, 0, a_{5,7}, a_{5,8}, a_{5,9} $
$ a_{6,1}, a_{6,2}, a_{6,3}, a_{6,4}, a_{6,5}, 1, a_{6,7}, a_{6,8}, a_{6,9} $
$ a_{7,1}, a_{7,2}, a_{7,3}, a_{7,4}, a_{7,5}, a_{7,6}, a_{7,7}, a_{7,8}, 0 $
$ a_{8,1}, a_{8,2}, a_{8,3}, a_{8,4}, a_{8,5}, a_{8,6}, a_{8,7}, a_{8,8}, 0 $
$ a_{9,1}, a_{9,2}, a_{9,3}, a_{9,4}, a_{9,5}, a_{9,6}, a_{9,7}, a_{9,8}, 1 $

То есть в обоих матрицах девять битов должны быть одинаковыми и иметь значения, которые указаны ваше. Есть ли какой-то алгоритм, который можно использовать для построения такой матрицы?

-- 31.10.2014, 14:03 --

Остальные значения могут как совпадать, так и не совпадать. Это не имеет значения.

[Sender]

А вот сможете навскидку назвать какую-нибудь обратимую матрицу 9-го порядка?

[Pavel2015]

Да, единичная матрица.

-- 31.10.2014, 15:08 --

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

[patzer2097]

Pavel2015 в сообщении #924738 писал(а):

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

а что, Вам не хватит полиномиального времени, чтобы построить единичную матрицу $9\times9$?