# Span of a set of vectors over a given field

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.

-
I think an example with inputs and outputs could be nice ... – Dr. belisarius Aug 14 '12 at 15:18
RowReduce[S, Modulus->q] followed by removing the all zero rows. – Daniel Lichtblau Aug 14 '12 at 15:30
@DanielLichtblau What is F? – Dr. belisarius Aug 14 '12 at 16:06
I assume you are asking what is the field in question. In my example it is the prime field integers modulo q (where q is prime). – Daniel Lichtblau Aug 14 '12 at 17:15

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.

-
Usually when someone asks for the span of a set of vectors, they don't want the entire set of all of them, but rather a basis. – murray Aug 15 '12 at 21:08

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.

-

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]


   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}};

Because it is not necessary for $q$ to be prime (it can be any prime power), it would be interesting to see a more general solution. – whuber Aug 14 '12 at 17:54
It's probably more efficient to treat the given vectors as rows and then use the method suggested by @Daniel Lichtbau. In any event, RowReduce is a bit of overkill: one doesn't need a reduced row echelon form, just a row echelon form, to identify the rows/columns forming the span. Unfortunately, there's nothing unique about such a row echelon form, and there's no Mathematica function that gives one except for the reduced form. – murray Aug 14 '12 at 19:19