I previously asked a similar question to this but noticed that the formulation was slightly different than what I am interested in, therefore I ask for any useful information on this problem (by any useful information I mean any mention of this problem in literature, lower bounds to complexity, complexity analysis and even intuitions on how to efficiently approach this problem).
The formulation of the problem I am interested in is as follows (pay attention that any information on a more general version of this problem is also welcome, such as by considering a generic field instead of GF(2)):
Let $X \subseteq \{0,1\}^n$ be a nonempty set of vectors of length $n \geq 1$ with binary components such that the zero vector $\vec{0}$ having all components equal to $0$ belongs to $X$. Along with the sum $\oplus$ defined as the component-wise xor (modulo 2 sum) of two vectors (i.e. consider the usual GF(2) field), i.e. let $x_i, y_i$ be the $i$-th component of $\vec{x}, \vec{j}$ respectively, then $$ (\vec{x} \oplus \vec{y})_i :=\quad x_i + y_i\quad\text{(mod 2)} $$
Find: a subset of $X$ which is a vector space and has maximum size (in terms of cardinality, or equivalently, dimension).
A few things to note:
- The existence of a solution is trivial, since the set $X$ is finite and the vector space $\{\vec{0}\}$ is contained in $X$.
- There might be multiple subsets which have the same maximal cardinality (i.e. the solution might not be unique), if that is the case, picking any such set is enough.
One approach to giving a lower bound to the solutions' size is by observing that whenever $|X| \geq 2$ then any solution $S$ is such that $|S| \geq 2$, since at least one vector space with dimension 1 is guaranteed to be contained in $X$. This approach can probably be extended to a general bound but I feel this gives a very loose lower bound on the size of the solution.
My belief is that this problem might be NP-hard, I tried to find a reduction from some known problems (CLIQUE, SAT) but with no success. I also find it strange that while the "dual" problem asking for the smallest vector space containing a given set is well known in literature, this one has no mentions (afaik).
As a final remark on how this problem differs from the previous one, intuitively, one subset of $X$ might be such that it cannot be "expanded' with any new element of $X$, but still have a cardinality smaller than some other subset which constitutes a vector space, that is, is maximal in terms of set inclusion, but not in terms of dimension.