Re: inverse of a modulo 2 matrix

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

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/
--
PARI/GP Home Page: http://www.parigp-home.de/