# Size of a boolean vectorial subspace

We know that a boolean vectorial space of dimension n is defined by all posible n-tuples formed by 0 or 1 in each position (note this set is finite), and adding to this set the operations of:

• Multiply by an scalar (also 0 or 1) -> Boolean multiplication to all its components by this scalar.
• Add 2 vectors -> Boolean sum component by component.

When we select a set of m independent vectors (note this can be writen as a boolean matrix nxm where m<=n of rank m) we can see it as the basis of a boolean subspace from the main one of dimension n. This vectorial subspace is formed by all possible linear combinations of its basis (note its size is, of course, also finite).

I am interested in getting any kind of relationship among the size of a boolean vectorial subspace and any parameter that define it (dimension, orthogonality of its vectors,...).

My main issue comes from that I am not really familiar with specific tools to be used in finite vectorial spaces.

• Mathematicians denote $\{0,1\}$ as $F=GF(2)$ (Galois Field with two elements) and you are working with the cartesian product $F^n$ which is a vector space over $F$. These notations will help you to have access to a vast litterature. See for example math.stackexchange.com/q/34042. Are you accustomed with the very precise meaning of the word "field" in algebra ? – Jean Marie Apr 7 at 14:41
• Thanks for this, really appreciated. I will try right now. – 24th_moonshine Apr 7 at 14:46
• @JeanMarie: That was what I thought, too, but the OP doesn't seem to be talking about a vector space over a field at all. For instance, in a BVS, we would have $v+v=v$ for all vectors $v,$ whereas in a vector space over $GF(2),$ we instead have $v+v=0$ for all vectors $v.$ – Cameron Buie Apr 7 at 14:51
• I think the issue is that you have to choose between addition $1+1=0$ (which is a "xor" addition) which is the framework permitting to speak about vector subspaces, etc... or the addition rule $1+1=1$ which is much "closed on itself" (I wrote at first "algebraicaly poor") without rich algebraic structures... Abandon in this case subspaces and the like... – Jean Marie Apr 7 at 14:52
• @CameronBuie is right I am not using GF(2) as it uses AND and XOR as product and sum rules, but usual boolean algebra rules AND and OR. – 24th_moonshine Apr 7 at 14:53