Matrix inversion tool

[Matan Ziv-Av]

On Sun, 9 Aug 2015, Oleg Goldshmidt wrote:

> Matan Ziv-Av <matan at 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.