Решение системы линейных уравнений над бинарным полем

Мне нужно решить систему линейных уравнений над бинарным полем, а именно, у меня есть матрица M, и мне нужно найти вектор v такой, что M.v=0 (mod 2), где все элементы матрицы M и вектора v равны 0 или 1, а справа — вектор, все компоненты которого — четные числа. Есть ли хороший способ запрограммировать его в Mathematica или Matlab?


matlab wolfram-mathematica
person Mr. Gentleman    schedule 11.08.2014    source источник
comment
Это было задано [до] [1] в stackoverflow, поиск линейных соответствий: [1]: stackoverflow.com/questions/13339989/   -  person Bram    schedule 11.08.2014
comment
Какой размер у v? Возможен ли метод грубой силы?   -  person Luis Mendo    schedule 11.08.2014
comment
@Bram, спасибо, но этот алгоритм не применим к случаю с несколькими переменными.   -  person Mr. Gentleman    schedule 11.08.2014
comment
В Mathematica это сделает NullSpace[m, Modulus->2].   -  person Daniel Lichtblau    schedule 13.08.2014
comment
@DanielLichtblau: Большое спасибо!   -  person Mr. Gentleman    schedule 13.08.2014

Ответы (1)


arrow_upward
0
arrow_downward

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

M = [0 1 0 1; 1 0 0 1; 1 1 1 0]; %// example matrix M
V = (dec2bin(0:2^size(M,2)-1)-'0').'; %// all possible vectors v, as columns of V
ind = all(mod(M*V, 2)==0); %// index of solution vectors
solutions = V(:,ind); %// each column is a solution vector

В этом примере

solutions =
     0     1
     0     1
     0     0
     0     1
person Luis Mendo    schedule 11.08.2014
comment
Большое спасибо, но M и v обычно имеют несколько сотен записей... - person Mr. Gentleman; 11.08.2014
comment
Операция мода на RHS может потребовать грубой силы. - person Yvon; 11.08.2014