0

I am looking for effective algorithmic solutions for the following two problems:

Question 1: Is there a quick way to obtain for a given $n$ the list of all integer $n \times n$ matrices having only entries 0 and 1 that are invertible?

Question 2: Ditto, for given $n$ and $m$, matrices with largest entry $m$?

In the end I'm looking for a concrete implementation in GAP.

Community
  • 1
Mare
  • 2,332

1 Answers1

2

I do not think there is either function (nor indeed a non-brute force algorithm), though presumably asymptotically most matrices are invertible, so building matrices and testing invertibility would not be abysmal overkill.

Thus a very basic version (here for 0/1) is to take sets of possible rows (as combinations of different vectors) first (which saves on a factor of $n!$) before testing invertibility:

gap> n:=5;
gap> zeroone:=Combinations(Tuples([0,1],n),n);;Length(zeroone);
201376
gap> zeroone:=Filtered(zeroone,x->not IsZero(DeterminantMat(x)));;Length(zeroone);
104286

Then all matrices are obtained by permuting rows:

gap> sym:=SymmetricGroup(n);;
gap> all:=Concatenation(List(zeroone,x->Orbit(sym,x,Permuted)));;

which will get all 12514320 matrices.

ahulpke
  • 18,416
  • 1
  • 21
  • 38