I want to implement a program to calculate the Inverse of a matrix in F(2) (only 0 and 1) . Please let me know if you can think of any algorithm or just simple algo for inverse of Matrix.
+1
A:
Matrix inverse is understandable. You can use Gaussian elimination for that. Or, if you prefer, you can use LU or QR decomposition and build up the inverse by cycling through unit vectors on the right hand side.
Inverse of a matrix in F(2) (only 0 and 1)
I have no idea what this means. Perhaps you can clarify.
duffymo
2010-07-22 01:38:50
GF(2), i.e. each element of the matrix is a single bit. The Gaussian elimination algorithm still works with a few modifications. http://en.wikipedia.org/wiki/GF%282%29
GregS
2010-07-22 01:41:45
Thank you, GregS. I didn't know.
duffymo
2010-07-22 01:51:44
F(2) is field of {0, 1} - ie all arithmetic is modulo 2
Kelly
2010-07-22 01:52:00
A:
There is method of four russians (m4ri) with works in $O(n^3 / log(n))$ time.
It is implemented in, for example, this library: http://m4ri.sagemath.org/
falagar
2010-07-23 11:52:59