[GAP Forum] Find rank-1 matrices in given subspace of matrices

[Alexander Hulpke]

Dear Benoit,

Ah — within a subspace will give you polynomial equations (all 2x2 subdeterminants=0) in the coefficients of a linear combination, and at least in principle this can be done with Groebner bases (i.e. you get rank <=1, but rank 0 is easily eliminated.)

For example (using the appended function) for the standard basis of Q^{3\times 4}:

gap> b:=BasisVectors(Basis(MatrixSpace(Rationals,3,4)));;
gap> e:=Rank1Equations(b);
[ x_1*x_6-x_2*x_5, x_1*x_7-x_3*x_5, x_1*x_8-x_4*x_5, x_2*x_7-x_3*x_6, 
  x_2*x_8-x_4*x_6, x_3*x_8-x_4*x_7, x_1*x_10-x_2*x_9, x_1*x_11-x_3*x_9, 
  x_1*x_12-x_4*x_9, x_2*x_11-x_3*x_10, x_2*x_12-x_4*x_10, x_3*x_12-x_4*x_11, 
  x_5*x_10-x_6*x_9, x_5*x_11-x_7*x_9, x_5*x_12-x_8*x_9, x_6*x_11-x_7*x_10, 
  x_6*x_12-x_8*x_10, x_7*x_12-x_8*x_11 ]
gap> ReducedGroebnerBasis(e,MonomialLexOrdering());
[ x_7*x_12-x_8*x_11, x_6*x_12-x_8*x_10, x_6*x_11-x_7*x_10, x_5*x_12-x_8*x_9, 
  x_5*x_11-x_7*x_9, x_5*x_10-x_6*x_9, x_3*x_12-x_4*x_11, x_3*x_8-x_4*x_7, 
  x_2*x_12-x_4*x_10, x_2*x_11-x_3*x_10, x_2*x_8-x_4*x_6, x_2*x_7-x_3*x_6, 
  x_1*x_12-x_4*x_9, x_1*x_11-x_3*x_9, x_1*x_10-x_2*x_9, x_1*x_8-x_4*x_5, 
  x_1*x_7-x_3*x_5, x_1*x_6-x_2*x_5 ]

So x_7 =x_8*x_11/x_12   (and case for x_12=0) etc. and you can build an (ugly) parameterization from these.

(Alternatively one could try to use \sum_c_i M_i=v\cdot w^T with v and w given by extra variables that are to be eliminated. This will yield the same  Groebner basi after variable elimination.)

Best,

  Alexander



Rank1Equations:=function(mats)
local l,f,r,vars,n,m,c,d,eqs;
  l:=Length(mats);
  f:=DefaultFieldOfMatrix(mats[1]);
  r:=PolynomialRing(f,l);
  vars:=IndeterminatesOfPolynomialRing(r);
  n:=Length(mats[1]);
  m:=Length(mats[1][1]);
  eqs:=[];
  for c in Combinations([1..n],2) do
    for d in Combinations([1..m],2) do
      Add(eqs,
          Sum([1..l],x->vars[x]*mats[x][c[1]][d[1]])
          *Sum([1..l],x->vars[x]*mats[x][c[2]][d[2]])
          -Sum([1..l],x->vars[x]*mats[x][c[1]][d[2]])
	  *Sum([1..l],x->vars[x]*mats[x][c[2]][d[1]]));
    od;
  od;
  return eqs;
end;