How to get the binay matrix inverse

[MSAKARIM]

How can I get inverse of binary matrices ?
for example a=[0101 1111 0100
0001 1001 1000
1010 0111 0110]

 

[andre_luis]

I believe it is not possible to be performed with non-square matrices

 

[MSAKARIM]

I believe it is not possible to be performed with non-square matrices

so, how can i perform it for square one ?

 

[MSAKARIM]

Boolean matrix inverse

I need to find inverse of 4*4 byte binary matrix , when i searched i found some algorithm can be used to solve this problem but i don't know how to implement it . the algorithm is named " the extended Euclid algorithm"?

 

[vGoodtimes]

Re: Boolean matrix inverse

what do you mean by "4*4 byte binary matrix"?

a 4 x 4 matrix of integers in [-128, 127] where "+" is "+ mod 256" and "*" is "* mod 256"? This might not have an inverse.
a 4 x 4 matrix of integers in [0, 255] where "+" is "+ mod 256" and "*" is "* mod 256"? This might not have an inverse.
This is because some elements do not have inverses themselves. for example 1 = (2 * x) mod 256 has no solution if x must be an integer.

a 32 x 32 matrix of {0,1} where "+" is "xor" and "*" is "and"? This could have an inverse.
a 4 x 4 matrix of elements of a gf256? This could have an inverse.
These don't have numeric interpretations.

 

[MSAKARIM]

Re: Boolean matrix inverse

what do you mean by "4*4 byte binary matrix"?

a 4 x 4 matrix of integers in [-128, 127] where "+" is "+ mod 256" and "*" is "* mod 256"? This might not have an inverse.
a 4 x 4 matrix of integers in [0, 255] where "+" is "+ mod 256" and "*" is "* mod 256"? This might not have an inverse.
This is because some elements do not have inverses themselves. for example 1 = (2 * x) mod 256 has no solution if x must be an integer.

a 32 x 32 matrix of {0,1} where "+" is "xor" and "*" is "and"? This could have an inverse.
a 4 x 4 matrix of elements of a gf256? This could have an inverse.
These don't have numeric interpretations.

Example of 4*4byte matrix > i need to calculate its modular inverse

 

[vGoodtimes]

What part are you having trouble with? You may be having problems as 8b values can have 256 values, but 256 is not a prime number. As a result, not all bytes have a modular inverse.

 

[MSAKARIM]

What part are you having trouble with? You may be having problems as 8b values can have 256 values, but 256 is not a prime number. As a result, not all bytes have a modular inverse.

I need a general algorithm to apply it on any matrix like that in the previous image regardless its value ..

 

[andre_luis]

Did you take a look here ?
https://en.wikipedia.org/wiki/Invertible_matrix

 

[vGoodtimes]

I need a general algorithm to apply it on any matrix like that in the previous image regardless its value ..

If the binary values represent numbers, and addition/multiplication are done in the normal way, then you can't always solve for the inverse. 1 = (2*x) % 256 has no solution in integers -- even numbers don't have a multiplicative inverse. Thus [2,0,0;0,2,0;0,0,2] has no solution.

If the binary values represent numbers modulo a prime (eg, mod 251), and addition/multiplication are done modulo that prime, then you can invert any invertable matrix. however, 251, 252, 253, 254, and 255 are no longer valid values. Also addition/multiplication are done modulo 251, which can be annoying.

If the binary values represent non-numbers from a galois field, then you can invert any invertable matrix. However, addition and multiplication are weird and the binary values don't represent numbers.