On Sun, 9 Aug 2015, Oleg Goldshmidt wrote:
Matan Ziv-Av <ma...@svgalib.org> writes:
On Sat, 8 Aug 2015, Omer Zak wrote:
What happens if you use the regular matrix inversion tool which works
on real numbers? (after rejecting, as singular over Z2, matrices
whose determinant modulo 2 is different from 1)
This will work if the inverse only has integer entries. It may also
work if your algorithm returns rational numbers, but will not work
with floating point numbers (there are no reals in a computer). You
cannot faithfully convert 1.1234 to an element of Z_2.
The original matrix contains zeros and ones, and you never need to
divide, just multiply and add modulo 2.
Please read what you reply to. The suggestion was to treat the matrix as
a real matrix, so the calculations will not be modulo 2.
If you take the, for example, matrix
[ [ 0, 0, 1, 1 ],
[ 0, 1, 0, 1 ],
[ 1, 0, 0, 1 ],
[ 1, 1, 1, 0 ] ]
The inverse, in floating point numbers, will be something like
[ [ -0.33333333333333331, -0.33333333333333331, 0.66666666666666663,
0.33333333333333331 ],
[ -0.33333333333333331, 0.66666666666666663, -0.33333333333333331,
0.33333333333333331 ],
[ 0.66666666666666663, -0.33333333333333331, -0.33333333333333331,
0.33333333333333331 ],
[ 0.33333333333333331, 0.33333333333333331, 0.33333333333333331,
-0.33333333333333331 ] ]
And you have no idea if 0.66666666666666663 should be 0 or 1 mod 2.
If you use rational numbers you get
[ [ -1/3, -1/3, 2/3, 1/3 ],
[ -1/3, 2/3, -1/3, 1/3 ],
[ 2/3, -1/3, -1/3, 1/3 ],
[ 1/3, 1/3, 1/3, -1/3 ] ]
Which is easy to convert (you ignore the denominators, which will all be
odd for an invertible matrix).
--
Matan.
_______________________________________________
Linux-il mailing list
Linux-il@cs.huji.ac.il
http://mailman.cs.huji.ac.il/mailman/listinfo/linux-il
