Message Boards Message Boards

0
|
2918 Views
|
3 Replies
|
0 Total Likes
View groups...
Share
Share this post:

Multiplication in GF(2) of rectangular matrices hanging indefinitely

Posted 3 years ago

I have been attempting to execute the following matrix multiplication over GF(2) using the FiniteFields package with (17 x 18) x (18 x 17) rectangular matrices, but Mathematica (version 12.1.1.0, Mac OS) is hanging indefinitely (I killed the kernel after waiting a few minutes):

<< FiniteFields`
m = {{GF[2][{1}], GF[2][{1}], GF[2][{1}], GF[2][{0}], GF[2][{1}], 
   GF[2][{1}], GF[2][{1}], GF[2][{1}], GF[2][{1}], GF[2][{1}], 
   GF[2][{0}], GF[2][{0}], GF[2][{1}], GF[2][{0}], GF[2][{0}], 
   GF[2][{1}], GF[2][{0}]}, {GF[2][{1}], GF[2][{0}], GF[2][{1}], 
   GF[2][{1}], GF[2][{0}], GF[2][{0}], GF[2][{1}], GF[2][{1}], 
   GF[2][{0}], GF[2][{1}], GF[2][{1}], GF[2][{0}], GF[2][{0}], 
   GF[2][{1}], GF[2][{1}], GF[2][{0}], GF[2][{1}]}, {GF[2][{0}], 
   GF[2][{0}], GF[2][{0}], GF[2][{1}], GF[2][{1}], GF[2][{1}], 
   GF[2][{0}], GF[2][{0}], GF[2][{1}], GF[2][{0}], GF[2][{1}], 
   GF[2][{1}], GF[2][{1}], GF[2][{0}], GF[2][{0}], GF[2][{0}], 
   GF[2][{0}]}, {GF[2][{0}], GF[2][{1}], GF[2][{0}], GF[2][{0}], 
   GF[2][{1}], GF[2][{1}], GF[2][{1}], GF[2][{0}], GF[2][{1}], 
   GF[2][{1}], GF[2][{1}], GF[2][{1}], GF[2][{1}], GF[2][{1}], 
   GF[2][{0}], GF[2][{0}], GF[2][{0}]}, {GF[2][{0}], GF[2][{0}], 
   GF[2][{1}], GF[2][{0}], GF[2][{1}], GF[2][{0}], GF[2][{1}], 
   GF[2][{0}], GF[2][{0}], GF[2][{0}], GF[2][{1}], GF[2][{0}], 
   GF[2][{0}], GF[2][{1}], GF[2][{1}], GF[2][{0}], 
   GF[2][{1}]}, {GF[2][{0}], GF[2][{0}], GF[2][{1}], GF[2][{0}], 
   GF[2][{0}], GF[2][{1}], GF[2][{0}], GF[2][{1}], GF[2][{0}], 
   GF[2][{0}], GF[2][{0}], GF[2][{1}], GF[2][{0}], GF[2][{1}], 
   GF[2][{0}], GF[2][{1}], GF[2][{1}]}, {GF[2][{0}], GF[2][{0}], 
   GF[2][{1}], GF[2][{1}], GF[2][{0}], GF[2][{0}], GF[2][{0}], 
   GF[2][{0}], GF[2][{0}], GF[2][{1}], GF[2][{1}], GF[2][{1}], 
   GF[2][{0}], GF[2][{0}], GF[2][{1}], GF[2][{1}], 
   GF[2][{0}]}, {GF[2][{1}], GF[2][{1}], GF[2][{0}], GF[2][{0}], 
   GF[2][{1}], GF[2][{0}], GF[2][{0}], GF[2][{1}], GF[2][{1}], 
   GF[2][{1}], GF[2][{1}], GF[2][{1}], GF[2][{1}], GF[2][{1}], 
   GF[2][{1}], GF[2][{0}], GF[2][{0}]}, {GF[2][{1}], GF[2][{0}], 
   GF[2][{0}], GF[2][{0}], GF[2][{1}], GF[2][{0}], GF[2][{1}], 
   GF[2][{1}], GF[2][{1}], GF[2][{0}], GF[2][{1}], GF[2][{0}], 
   GF[2][{0}], GF[2][{1}], GF[2][{1}], GF[2][{0}], 
   GF[2][{0}]}, {GF[2][{1}], GF[2][{1}], GF[2][{1}], GF[2][{0}], 
   GF[2][{0}], GF[2][{1}], GF[2][{0}], GF[2][{0}], GF[2][{1}], 
   GF[2][{0}], GF[2][{0}], GF[2][{1}], GF[2][{1}], GF[2][{1}], 
   GF[2][{1}], GF[2][{1}], GF[2][{0}]}, {GF[2][{1}], GF[2][{1}], 
   GF[2][{0}], GF[2][{1}], GF[2][{1}], GF[2][{1}], GF[2][{1}], 
   GF[2][{1}], GF[2][{1}], GF[2][{1}], GF[2][{1}], GF[2][{0}], 
   GF[2][{0}], GF[2][{0}], GF[2][{0}], GF[2][{1}], 
   GF[2][{1}]}, {GF[2][{0}], GF[2][{0}], GF[2][{0}], GF[2][{0}], 
   GF[2][{1}], GF[2][{0}], GF[2][{0}], GF[2][{0}], GF[2][{1}], 
   GF[2][{1}], GF[2][{1}], GF[2][{0}], GF[2][{0}], GF[2][{0}], 
   GF[2][{0}], GF[2][{0}], GF[2][{0}]}, {GF[2][{0}], GF[2][{0}], 
   GF[2][{1}], GF[2][{0}], GF[2][{1}], GF[2][{0}], GF[2][{1}], 
   GF[2][{1}], GF[2][{0}], GF[2][{1}], GF[2][{1}], GF[2][{1}], 
   GF[2][{1}], GF[2][{1}], GF[2][{1}], GF[2][{0}], 
   GF[2][{0}]}, {GF[2][{0}], GF[2][{0}], GF[2][{0}], GF[2][{1}], 
   GF[2][{0}], GF[2][{0}], GF[2][{0}], GF[2][{1}], GF[2][{1}], 
   GF[2][{1}], GF[2][{1}], GF[2][{0}], GF[2][{1}], GF[2][{1}], 
   GF[2][{1}], GF[2][{0}], GF[2][{0}]}, {GF[2][{1}], GF[2][{0}], 
   GF[2][{0}], GF[2][{1}], GF[2][{1}], GF[2][{0}], GF[2][{1}], 
   GF[2][{0}], GF[2][{1}], GF[2][{0}], GF[2][{1}], GF[2][{0}], 
   GF[2][{0}], GF[2][{1}], GF[2][{0}], GF[2][{1}], 
   GF[2][{1}]}, {GF[2][{1}], GF[2][{0}], GF[2][{1}], GF[2][{1}], 
   GF[2][{0}], GF[2][{1}], GF[2][{1}], GF[2][{1}], GF[2][{1}], 
   GF[2][{0}], GF[2][{1}], GF[2][{0}], GF[2][{0}], GF[2][{1}], 
   GF[2][{0}], GF[2][{1}], GF[2][{1}]}, {GF[2][{0}], GF[2][{0}], 
   GF[2][{0}], GF[2][{1}], GF[2][{1}], GF[2][{1}], GF[2][{0}], 
   GF[2][{0}], GF[2][{0}], GF[2][{0}], GF[2][{1}], GF[2][{1}], 
   GF[2][{0}], GF[2][{1}], GF[2][{1}], GF[2][{0}], 
   GF[2][{1}]}, {GF[2][{1}], GF[2][{1}], GF[2][{1}], GF[2][{0}], 
   GF[2][{0}], GF[2][{0}], GF[2][{1}], GF[2][{1}], GF[2][{1}], 
   GF[2][{1}], GF[2][{1}], GF[2][{0}], GF[2][{0}], GF[2][{0}], 
   GF[2][{1}], GF[2][{1}], GF[2][{0}]}}
Transpose[m] . m

A very small (3 x 2) x (2 x 3) rectangular example however works immediately:

<< FiniteFields`
x = {{GF[2][{1}], GF[2][{1}], GF[2][{1}]}, {GF[2][{1}], GF[2][{0}], 
   GF[2][{1}]}}
Transpose[x] . x

Any ideas? Also of note, the smaller example produces "0" instead of "{0}_2", but I've seen other calculations keep the idea that the zero is in GF(2):

GF[2][{1}] * GF[2][{0}]

produces "{0}_2", but

GF[2][{1}] + GF[2][{1}]

produces "0" which is odd.

POSTED BY: Jeff Johnson
3 Replies

I would recommend just using Dot on integer (0-1) matrices, and then taking the result mod 2.

POSTED BY: Daniel Lichtblau
Posted 3 years ago

Unfortunately that approach in general can't work for me, as I need this to also work for GF(2^n) where n > 1, and am using this as part of finding a left inverse of a rectangular matrix if it exists via (A^t A)^-1 A^t.

POSTED BY: Jeff Johnson

Okay, you can do as follows.

(1) Represent the field elements using a polynomial to define the extension.

(2) Take the usual dot product. Use PolynomialReduce to reduce mod 2 and that defining polynomial.

(3) Use ResourceFunction["LinearAlgebraMod"][...,"Inverse"] to find the matrix inverse.

(4) Use that dot product and reduction again.

If I find time I might add "Dot" to the LinearAlgebraMod repertoire. "Det" was also a latecomer...I should have added Dot when I put in dat Det.

POSTED BY: Daniel Lichtblau
Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract