2014 dxdy logo

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

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




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

 
 
 
 Re: Построение обратимых матриц большого порядка
Сообщение30.10.2014, 13:22 
Pavel2015 в сообщении #924422 писал(а):
Требуется построить обратимую квадратную матрицу размером 9 на 9 над полем GF(2). В этой матрице третий столбец должен состоять только из нулей.
Здесь наука бессильна, надо к колдунам обращаться.

 
 
 
 Re: Построение обратимых матриц большого порядка
Сообщение30.10.2014, 16:52 
Аватара пользователя
Определитель матрицы с нулевым столбцом равен нулю, а у обратимой матрицы так не бывает.

 
 
 
 Re: Построение обратимых матриц большого порядка
Сообщение31.10.2014, 13:02 
Ой, это же опечатка. Условие задачи формулируется следующим образом. Требуется построить обратимую матрицу над 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 --

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

 
 
 
 Re: Построение обратимых матриц большого порядка
Сообщение31.10.2014, 13:36 
А вот сможете навскидку назвать какую-нибудь обратимую матрицу 9-го порядка?

 
 
 
 Re: Построение обратимых матриц большого порядка
Сообщение31.10.2014, 14:07 
Да, единичная матрица.

-- 31.10.2014, 15:08 --

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

 
 
 
 Re: Построение обратимых матриц большого порядка
Сообщение31.10.2014, 18:04 
Pavel2015 в сообщении #924738 писал(а):
Да, единичная матрица.
Задача состоит не в том, чтобы угадать матрицу, а в том, чтобы построить ее за полиномиальное время.
а что, Вам не хватит полиномиального времени, чтобы построить единичную матрицу $9\times9$? :lol1:

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group