Span of a set of vectors over a given field

Question

Could anyone help me find a function that takes as inputs:

a set $S$ of vectors and an integer $q$

and outputs:

the Span of $S$, where $Span[S]$ is a vector space over the field $F_q$.

If its simpler, could someone tell a method for $q=2$ (binary vectors) case.

Thanks.

Answer 1

You said "field", so presumably you want q to be a prime. Try the following. I've changed the name from Span to columnSpace because the former is a reserved Mathematica name.

The vectors here are the columns of a given matrix (the typical situation); if you want to make them rows instead, the changes are fairly obvious.

The key is to use RowReduce with its Modulus option, to locate the pivot columns of the resulting matrix, and then pick out the corresponding columns of the original matrix.

   columnSpace[mat_,p_] := Module[{reduced = RowReduce[mat,Modulus->p]},    
      Transpose@Pick[Transpose @ mat, markPivotColumns @ reduced,1]]

   isolateLeading1[vec_?VectorQ] := Module[{v = vec, i , n = Length[vec]}, 
          i= First @ Flatten @ Position[N[vec ~Append~ 1], 1.];
          v[[i + Range[n - i]]] = 0; 
          v]

   markPivotColumns[mat_] := Apply[Plus, Map[isolateLeading1, mat]]

Test case:

   a = {{1,2,0,3,4,1},{3,6,1,17,18,0},{4,8,0,12,16,2},{3,6,0,9,12,1}};
   columnSpace[a,5]
{{1,0,1},{3,1,0},{4,0,2},{3,0,1}}

Answer 2

For finite fields that are nontrivial powers of primes in size one can use GroebnerBasis to emulate row reduction. I think the main ideas are indicated in the notebook available from http://library.wolfram.com/infocenter/Conferences/325/ See the section "Linear algebra in a Galois field".

In any case here is a specific example. I work in the field G(16) generated by an irreducible of degree 5 over Z_2.

Our extension defining polynomial:

r = x^5 + x^2 + 1;

Show it is in fact irreducible:

Factor[r, Modulus -> 2]

(* Out[270]= 1 + x^2 + x^5 *)

We define functions to create a random element in this Galois field and a random linear polynomial comprised of such elements (as coefficients) times the given linear variables.

randomElem[ext_, x_, mod_] := With[
  {deg = Exponent[ext, x]},
  RandomInteger[{0, mod - 1}, deg].x^Range[0, deg - 1]
  ]
randomLinearPoly[vars_List, ext_, evar_, mod_] := 
 vars.Table[randomElem[ext, x, mod], {Length[vars]}]

I'll use four linear variables and three polynomials in those variables.

vars = {s, t, u, v};
SeedRandom[11111];
linpolys = Table[randomLinearPoly[vars, r, x, 2], {Length[vars] - 1}]

(* Out[276]= {s*x + u*x^3 + v*x^3 + t*(x + x^2 + x^3), 
 s*(1 + x^3) + u*(1 + x + x^4) + 
     v*(x + x^3 + x^4) + t*(1 + x + x^3 + x^4), 
 v*x^2 + s*(1 + x + x^3) + 
     u*(x^2 + x^3) + t*(1 + x + x^4)} *)

Here is the function to do the row reduction.

rowReduce[linpolys_, vars_, ext_, mod_] := With[
  {evar = Variables[ext][[1]]},
  Select[GroebnerBasis[Join[linpolys, {ext}], Join[vars, {evar}]], 
   Variables[#] =!= {evar} &]]

Our example:

rowReduce[linpolys, vars, r, 2]

(* Out[278]= {4013*u + 1680*v + 639*v*x + 497*v*x^2 + 2647*v*x^3 + 
  670*v*x^4, 
   4013*t + 1292*v + 1552*v*x + 1653*v*x^2 - 611*v*x^3 + 993*v*x^4, 
   4013*s + 1737*v - 1181*v*x + 865*v*x^2 - 1570*v*x^3 - 2532*v*x^4} *)

Not surprisingly (since we used random inputs) there are no null rows, that is, we have full rank of three generators.

Answer 3

The wikipedia definition for span(S):

http://en.wikipedia.org/wiki/Linear_span#Definition

So for doing the sum, we can first make a list of all possible coefficients. For the binary case (q = 2), it will be all possible n-tuples containing 0 and 1. So that is just: Tuples[{0,1},n] where n is the number of vectors in S.

Now to find the span, we need to add the basis vectors with different choices for the coefficients. Each possible choice is an element from Tuples[{0,1},n] . So, we just have to do a vector dot product of an element from this set and S. This will give one possible linear combination. Similarly, we can do all the linear combinations.

span[S_] := (coef = Tuples[{0, 1}, Length[S]]; Map[Mod[#1, 2] &, Table[coef[[i]].S, {i, 1, Length[coef]}], {2}]);

Just one small issue was that the dot product will produce vectors with integer (numbers other than 0 and 1) components. But then finally we can replace every such component to itself Mod 2. That was the purpose of putting the Map function.

For the case of general (non-binary) fields, we have coef defined as:

coef = Tuples[Range[0,q-1],Length[S]]

where $F_q$ is a field ($q$ is a prime power). Hence the argument to the Map function will change accordingly.

span[S_,q_] := (coef = Tuples[Range[0,q-1], Length[S]]; Map[Mod[#1, q] &, Table[coef[[i]].S, {i, 1, Length[coef]}], {2}]);

Hope this is a simple solution. Here is a output for $q = 2$ case:

In[46]:= span[S_, q_] := (coef = Tuples[Range[0, q - 1], Length[S]]; Map[Mod[#1, q] &, Table[coef[[i]].S, {i, 1, Length[coef]}], {2}])

In[51]:= BAS

Out[51]= {{1, 0, 0, 0, 0, 0, 1}, {0, 1, 0, 0, 0, 1, 0}, {0, 1, 0, 0, 1, 0, 0}, {1, 1, 0, 1, 0, 0, 0}, {1, 0, 1, 0, 0, 0, 0}}

In[50]:= span[BAS, 2]

Out[50]= {{0, 0, 0, 0, 0, 0, 0}, {1, 0, 1, 0, 0, 0, 0}, {1, 1, 0, 1, 0, 0, 0}, {0, 1, 1, 1, 0, 0, 0}, {0, 1, 0, 0, 1, 0, 0}, {1, 1, 1, 0, 1, 0, 0}, {1, 0, 0, 1, 1, 0, 0}, {0, 0, 1, 1, 1, 0, 0}, {0, 1, 0, 0, 0, 1, 0}, {1, 1, 1, 0, 0, 1, 0}, {1, 0, 0, 1, 0, 1, 0}, {0, 0, 1, 1, 0, 1, 0}, {0, 0, 0, 0, 1, 1, 0}, {1, 0, 1, 0, 1, 1, 0}, {1, 1, 0, 1, 1, 1, 0}, {0, 1, 1, 1, 1, 1, 0}, {1, 0, 0, 0, 0, 0, 1}, {0, 0, 1, 0, 0, 0, 1}, {0, 1, 0, 1, 0, 0, 1}, {1, 1, 1, 1, 0, 0, 1}, {1, 1, 0, 0, 1, 0, 1}, {0, 1, 1, 0, 1, 0, 1}, {0, 0, 0, 1, 1, 0, 1}, {1, 0, 1, 1, 1, 0, 1}, {1, 1, 0, 0, 0, 1, 1}, {0, 1, 1, 0, 0, 1, 1}, {0, 0, 0, 1, 0, 1, 1}, {1, 0, 1, 1, 0, 1, 1}, {1, 0, 0, 0, 1, 1, 1}, {0, 0, 1, 0, 1, 1, 1}, {0, 1, 0, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1}}

It works for $q = 3$ with the same basis set BAS. But, sorry, the output is fairly long to paste it here.