Как найти обратную матрицу от бинарной?

[totor]

Здравствуйте, уважаемые форумчане.

Возникла необходимость найти обратную матрицу от бинарной, размером 8х8.
Стандартные скрипты считают ее десятичной и вычисляют совершенно не то.
Есть ли какие-то скрипты/формулы или хотя бы правила/методы из литературы для помощи в выполнении подобных задач?

Спасибо.

[Sonic86]

Считать так же, но по модулю 2 (для каждого числа брать остаток от деления на 2). Если у Вас обратная матрица целочисленная, можно взять ее элементы по модулю 2, получится то, что надо, иначе - нет.

-- Пт сен 17, 2010 16:18:57 --

Соответствующий скрипт мне не известен.
Ручками легко $8 \times 8$ сосчитать самому.

[Профессор Снэйп]

Sonic86 в сообщении #353383 писал(а):

Ручками легко $8 \times 8$ сосчитать самому.

Угу. Метод Гаусса над полем $\mathbb{Z}_2$, за полчаса легко программируется.

[totor]

Sonic86 в сообщении #353383 писал(а):

Считать так же, но по модулю 2

а если при вычислении мне надо что-то вычитать из чего-то - это нормально? Например, при попытке вычислить алгебраическое дополнение элемента получил (-1)+(-1) - надо их смело сложить по модулю 2 и получить ноль?

Sonic86 в сообщении #353383 писал(а):

Если у Вас обратная матрица целочисленная, можно взять ее элементы по модулю 2, получится то, что надо, иначе - нет.

Обратную пока так и не получил. то, что выдают скрипты - не целочисленное.
Брать все четные - 0, все нечетные - 1. Но если число меньше нуля, взять его модуль?

Sonic86 в сообщении #353383 писал(а):

Ручками легко $8 \times 8$ сосчитать самому.

А каким методом посоветуете?
Методом Гаусса - не получается чего-то. Да и строки надо складывать все по тому же модулю 2? перемножать их можно?
Через союзную матрицу - это надо посчитать 64 алгебраических дополнений (не назвал бы метод быстрым ). И определитель, если не равен нулю, то равен 1, так?


P.S. А если взять то, что выдает мне стандартный скрипт, считающий методом Гаусса, домножить матрицу настолько, чтобы она стала целочисленной и привести ее элементы к виду "по модулю два" - выгорит?

-- Пт сен 17, 2010 18:20:49 --

Профессор Снэйп в сообщении #353412 писал(а):

Sonic86 в сообщении #353383 писал(а):

Ручками легко $8 \times 8$ сосчитать самому.

Угу. Метод Гаусса над полем $\mathbb{Z}_2$, за полчаса легко программируется.

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

[Профессор Снэйп]

totor в сообщении #353414 писал(а):

Методом Гаусса - не получается чего-то.

Элементарно должно получаться. Если матрица, конечно, невырожденная

-- Пт сен 17, 2010 21:29:03 --

totor в сообщении #353414 писал(а):

Да и строки надо складывать все по тому же модулю 2?

Конечно, само собой!!!

Просто забудьте про другие числа, кроме $0$ и $1$. И дополнительное равенство $1 + 1 = 0$ имейте в виду. Вычитание и сложение --- одна и та же операция.

[totor]

Профессор Снэйп в сообщении #353419 писал(а):

totor в сообщении #353414 писал(а):

Методом Гаусса - не получается чего-то.

Элементарно должно получаться. Если матрица, конечно, невырожденная

Невырожденная. Вроде я пока не совсем умом тронулся.:)
Вообще суть метода Гаусса - крутить-вертеть и попытаться чуть ли не интуитивно получить единичную матрицу, или есть какой-то общий алгоритм? Я просто уже года 4, как за это не брал в руки этих шашек - забыл напрочь.

[Sonic86]

Профессор Снэйп писал(а):

Sonic86 писал(а):

Ручками легко $8 \times 8$ сосчитать самому.

Угу. Метод Гаусса над полем $\mathbb{Z}_2$, за полчаса легко программируется.

(Оффтоп)

Я просто не люблю программировать, тем более метод Гаусса там довольно много исключительных состояний.

totor писал(а):

а если при вычислении мне надо что-то вычитать из чего-то - это нормально? Например, при попытке вычислить алгебраическое дополнение элемента получил (-1)+(-1) - надо их смело сложить по модулю 2 и получить ноль?

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

totor писал(а):

А каким методом посоветуете?
Методом Гаусса - не получается чего-то. Да и строки надо складывать все по тому же модулю 2? перемножать их можно?

Метод Гаусса там лучше всего. Через алгебраические дополнения не надо, убиться можно.

totor писал(а):

P.S. А если взять то, что выдает мне стандартный скрипт, считающий методом Гаусса, домножить матрицу настолько, чтобы она стала целочисленной и привести ее элементы к виду "по модулю два" - выгорит?

Да, должно, если Вы ее умножаете на нечетное число (на него же потом поделить надо будет, а в $\mathbb{Z}_2$ это сделать нельзя)

Можете здесь попробовать написать от фонаря 0-1 матрицу $3 \times 3$ и обратить, а мы подскажем если что.

[totor]

Sonic86 в сообщении #353425 писал(а):

Да, должно, если Вы ее умножаете на нечетное число (на него же потом поделить надо будет, а в это сделать нельзя)

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

Sonic86 в сообщении #353425 писал(а):

Можете здесь попробовать написать от фонаря 0-1 матрицу и обратить, а мы подскажем если что.

Знаете, да. Действительно, надо просто поэкспериментировать. О результатах в понедельник, если получится, доложу. Спасибо.

[Профессор Снэйп]

totor в сообщении #353422 писал(а):

Вообще суть метода Гаусса - крутить-вертеть и попытаться чуть ли не интуитивно получить единичную матрицу, или есть какой-то общий алгоритм?

Конечно же, есть общий алгоритм

Элементарное преобразование --- домножение строки на ненулевое число, вычитание одной строки из другой.

Прямой ход --- приводим матрицу к верхнетреугольному виду с единицами по диагонали. Обратный ход --- к единичной матрице. Параллельно производите те же самые преобразования с единичной матрицей --- получаете обратную.

P. S. Какого-то Вы плохого мнения о Гауссе. Король математиков туфту не придумает

-- Сб сен 18, 2010 14:22:49 --

totor в сообщении #353435 писал(а):

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

Если изначальная матрица была невырожденной по модулю $2$, то определитель --- нечётное число, и на чётные умножать/делить не понадобится.

-- Сб сен 18, 2010 14:24:07 --

Sonic86 в сообщении #353425 писал(а):

Я просто не люблю программировать, тем более метод Гаусса там довольно много исключительных состояний.

Нету там никаких исключительных состояний! Если, конечно, с вырожденными матрицами не приходится возиться.

[ewert]

Sonic86 в сообщении #353425 писал(а):

Да, должно, если Вы ее умножаете на нечетное число (на него же потом поделить надо будет, а в $\mathbb{Z}_2$ это сделать нельзя)

Можно. Это ведь не только кольцо, но ещё и поле.

Мне кажется, что тут какая-то путаница в обсуждении... А-а Профессор Снэйп меня уже опередил:

Профессор Снэйп в сообщении #353632 писал(а):

Если изначальная матрица была невырожденной по модулю $2$, то определитель --- нечётное число, и на чётные умножать/делить не понадобится.

Только не "то", а "тогда и только тогда".

[Профессор Снэйп]

Кстати, такой естественный вопрос: сколько всего невырожденных бинарных матриц размера $n \times n$. Ясно, что

$$ (2^n - 1) \cdot (2^n - 2) \cdot (2^n - 4) \cdot \ldots \cdot (2^n - 2^{n-1}) $$

Как-нибудь к человеческому виду это произведение можно привести?

[EtCetera]

Профессор Снэйп

Профессор Снэйп в сообщении #353637 писал(а):

Как-нибудь к человеческому виду это произведение можно привести?

Разве что так: $\prod\limits_{k=1}^{n-1}(2^n-2^k)=(-1)^n\cdot 2^{\frac{n(n-1)}{2}}\cdot (2;2)_n$, где $(a;q)_k$ - q-Pochhammer symbol.

[Dandan]

метод Гаусса для бинарных матриц это вообще элементарщина. Нужно только складывать по модулю 2 и переставлять строки. Если матрицы не очень большие, то в C/C++ (да и других языках) можно использовать операцию XOR для побитового сложения по мод 2: a^b.
Т.е. алгоритм такой - строки матрицы кодируем целыми числами, а дальше используем XORы и перестановки в соответствии с методом Гаусса.

[ewert]

Dandan в сообщении #353661 писал(а):

можно использовать операцию XOR для побитового сложения по мод 2

Это так с точки зрения эффективности, но не очень наглядно -- в этом случае ещё маски придётся использовать и изменять.

[Профессор Снэйп]

Переставлять строки не обязательно, достаточно складывать