Matrix of finite field

[Craig McQueen]

I've seen some recent discussion about Matrices of e.g.
sympy.polys.domains. I'm very interested, because I'd like to be able
to add, multiply and (most usefully to me) invert matrices of Galois
(finite) fields with modulo 2.

This relates to a question I asked on StackOverflow, originally about
numpy:
http://stackoverflow.com/questions/5578172/can-i-use-my-own-python-class-with-numpy-or-some-other-matrix-library

Originally I planned to do a Galois class myself, and hoped to use it
in numpy or some generic matrix library; but I see sympy provides
sympy.polys.domains.FF so I can do GF2 = sympy.polys.domains.FF(2).
Now all I need is a matrix class that can use elements of that type,
including doing matrix inversion.

I saw some posts started by Sherjil Ozair discussing possibilities.
What's the current status? Is there some code somewhere that can be
downloaded and tried?

[SherjilOzair]

On Jun 21, 4:45 am, Craig McQueen <googlegro...@craig.mcqueen.id.au>
wrote:

> I've seen some recent discussion about Matrices of e.g.
> sympy.polys.domains. I'm very interested, because I'd like to be able
> to add, multiply and (most usefully to me) invert matrices of Galois
> (finite) fields with modulo 2.
>
> This relates to a question I asked on StackOverflow, originally about

> numpy:http://stackoverflow.com/questions/5578172/can-i-use-my-own-python-cl...

>
> Originally I planned to do a Galois class myself, and hoped to use it
> in numpy or some generic matrix library; but I see sympy provides
> sympy.polys.domains.FF so I can do GF2 = sympy.polys.domains.FF(2).
> Now all I need is a matrix class that can use elements of that type,
> including doing matrix inversion.
>
> I saw some posts started by Sherjil Ozair discussing possibilities.
> What's the current status? Is there some code somewhere that can be
> downloaded and tried?

Hello Craig,
As you know correctly, part of my project involves making Sympy
matrices work for any odd python class.
The class will need to have a few things implemented in it, like
__add__, __mul__.
No, it has not been done as yet. I'm still on phase 1 of my project
which is writing sparse matrix algorithms for sympy's symbolic
matrices.

In a few days however, I'd be releasing two new Matrix class, based on
the List of List and the Dict of Keys representations.
You would find the work in progress code here [1]. There are two
classes, the LILMatrix and the DOKMatrix, which can take in elements
of any type.
I will be adding a commit shortly which will allow you to set the
'type' of the matrix.

So, you will be able to get a matrix with elements of GaloisField.

But, according to my understanding and what a mentor has told me,
regular algorithms do not apply to matrices over finite field. As yet,
algorithms in the Matrix class, and in my DOKMatrix and LILmatrix
class, assume (implictly) that the elements belong to the
characteristic 0 fields.

So, currently sympy doesn't solve matrices over finite fields or is
expected to do anytime soon.
Matrices over arbitrary dtypes is still possible, and the code will be
finished by the end of this month.

Still, its worth a shot. If you could post example code, as to what
you want to be done, and what you expect the results to be, I'll see
if the current algorithms work can be modified to work on it or not.

Regards,
Sherjil Ozair


[1] https://github.com/sherjilozair/sympy/tree/lilmatrix

[SherjilOzair]

Hello again,

Good news !

I tried to find the inverse of a Matrix over Galois field, and I was
successful. To what degree, I don't know.

Check this out. https://gist.github.com/1037126

The Matrix classes yet still don't have a complete set of fundamental
operators, so I had to use .toMatrix a lot.

I think this implies that matrix over finite fields can be solved for
certain or all cases.

Will update if I have more good news.

Sherjil Ozair

[SherjilOzair]

https://github.com/sympy/sympy/pull/444