# Efficient method to determine if a set of vectors span a finite field with some constraints on the constants.

In a finite field $\{0,1,2\}^2$, given a set of vectors $[0\:1],[1\:0],[1\:1],[2\:2]$, we can have the linear combination, $c_1[1\:0]+c_2[0\:1]+c_3[1\:1]+c_4[2\:2] = [s_1\:s_2]\in\{0,1,2\}^2$, where $c_1,c_2,c_3,c_4\in \{0,1,2\}$.

The basis of this set of vectors is $\{[0\:1],[1\:0]\}$. The dimension of this basis is 2, hence this set of vectors span the entire finite field $\{0,1,2\}^2$.

However if the value each constant can take now changes to $c_1\in\{0,1\}, c_2\in\{0,1,2\}, c_3\in\{0,1\},c_4\in\{0,1\}$, is there a more efficient method to determine if these set of vectors still span the finite field $\{0,1,2\}^2$, without rigorously checking if each vector from the finite field $\{0,1,2\}^2$ can be achieved from the linear combination,

$c_1[1\:0]+c_2[0\:1]+c_3[1\:1]+c_4[2\:2] = [s_1\:s_2]\in\{0,1,2\}^2$, where $c_1\in\{0,1\}, c_2\in\{0,1,2\}, c_3\in\{0,1\}, c_4\in\{0,1\}$ ?

-
How is $\{0,1,2\}^2$ a finite field? Do you mean a 2-dimensional vector space over the field $F=\mathbb{Z}_3$ of three elements? For it to be a field you need to specify, how you multiply vectors. A minimal requirement is a rule $$[0\ 1][1\ 0]=[s_1\ s_2]$$ for some elements $s_1,s_2\in F$. The rest of the multiplication table then follows from the field axioms (but some care is needed in selecting $[s_1\ s_2]$ for otherwise you may get zero divisors or some such atrocities). –  Jyrki Lahtonen Aug 31 '12 at 9:57
@JyrkiLahtonen: I think that indeed the first sentence should read "In a vector space $\{0,1,2\}^2$ over a finite field $\{0,1,2\}$ ...", and that $\{0,1,2\}$ denotes $\mathbb Z/3\mathbb Z$. –  Marc van Leeuwen Aug 31 '12 at 12:57

Presumably $V=\{\overline{0},\overline{1},\overline{2}\}^2$ is just a vector space over the field $F=\mathbb{Z}_3=\{\overline{0},\overline{1},\overline{2}\}$. I use the overlines to enmphasize the fact that the elements are not just integers. They are residue classes modulo three.
The vectors $[\overline{0}\ \overline{1}]$ and $[\overline{1}\ \overline{0}]$ span the vector space $V$. The word span carries with itself the meaning that the set of multipliers is all of $F$.
But enough ranting. Your question is, whether we can easily determine, whether a subset of multipliers, separately handpicked for each generator, still gives all the vectors of the space as constrained linear combinations. I don't know of a general method to test that. Ad hoc techniques can be tried. For example in the concrete example that you listed, the multiplier of $[\overline{0}\ \overline{1}]$ was not constrained. That means that by using a term $c [\overline{0}\ \overline{1}]$ (for some $c\in F$) we can always adjust the second component to whatever value we please. Therefore it suffices to check that we can give the first component any value that we want. But all the possible values: $\overline{0},$ $\overline{1}$, and $\overline{2}$ appear, with multiplier one (that is apparently always allowed). As zero is also (apparently) always allowed as a multiplier, we can conclude that in this example case the answer is affirmative.