Karim BELABAS on Tue, 7 Jan 2003 01:26:51 +0100 (MET)

 Re: inverse of a modulo 2 matrix

```On Tue, 7 Jan 2003, Ramón Casero Cañas wrote:
> Hi, I'm Ramón, rcasero@tsc.uc3m.es; our mail server has been down for the
> whole Christmas, so I have to use this address meanwhile.
>
>> 1) To inverse a matrix, use A^-1 or 1/A.
>>
>> 2) If A is invertible, you should rather use matsolve() than
>matinverseimage().
>>
>> 3) matsolve(A,X) is faster than computing A^-1, but not much, so you are
>right,
>> it is best to compute A^-1 if you have many vectors X.
>
> Thanks, Bill. I tried this in GP, and it worked. I actually did this
>
> -----------------------------------
>
> ? a=[Mod(0,2),Mod(1,2); Mod(1,2),Mod(1,2)]
> %2 =
> [Mod(0, 2) Mod(1, 2)]
>
> [Mod(1, 2) Mod(1, 2)]
>
> ? a^(-1)
> %3 =
> [Mod(1, 2) Mod(1, 2)]
>
> [Mod(1, 2) Mod(0, 2)]
[...]
> Why? Because I want to invert a modulo 2 matrix, and then use it to span
> modulo 2 vectors. I know that I can work with reals and do
>
> a^(-1) = inv(a) * det(a)
>
> but I would like to stay in {0, 1}. Maybe pari can do this, and this is the
> reason of my interest in inversing a matrix. But I would like to do this
> with a function, using the C interface, not the gp program. The inversion
> function is what I cannot find in the documentation (I did find the data
> type for the modulo 2 symbols).

Use ginv().

Cheers,

Karim.

P.S: In recent development versions (2.2.4 onward, or so), you can also use

GEN u_FpM_inv(GEN x, ulong p)

where x is a t_MAT, whose columns are t_VECSMALL [ entries are ordinary
C longs, here assumed reduced mod p ].

[ undocumented, use at your own risk, ** stability not guaranteed ** ]

You can write the above example as

GEN smallcol(long a, long b) {
GEN z = cgetg(3, t_VECSMALL;
z[1] = a;
z[2] = b; return z;
}

a = cgetg(3, t_MAT);
a[1] = (long)smallcol(0, 1);
a[2] = (long)smallcol(1, 1);
return u_FpM_inv(a, 2);

[ untested. Should be about ten times faster than straight t_INTMODs + ginv;
and much more memory efficient as dimension increases ]

--
Karim Belabas                    Tel: (+33) (0)1 69 15 57 48
Dép. de Mathématiques, Bât. 425  Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud             Email: Karim.Belabas@math.u-psud.fr
F-91405 Orsay (France)           http://www.math.u-psud.fr/~belabas/
--