Finding a maximal vector space in a finite set

Question

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)} $$

I stumbled upon the problem of finding (one of) the biggest (w.r.t. set inclusion) vector spaces contained in $X$.

I tried to look around but I don't seem to be able to find any mention of this problem in literature, not even in its more general formulation involving arbitrary vectors (thus not restricting to binary components and the component-wise modulo 2 sum).

(the considerations below on how I feel about the problem being NP-complete, and about the bounds are inexact and refer to a slightly different problem, which I asked here: Finding a biggest (in size) vector space in a finite set)

While the "dual" problem of finding the smallest vector subspace containing $X$ is well-known, and easy to solve, I feel like this problem of finding the biggest subset which is a vector space constitutes a harder problem, in terms of computational complexity. What can we say about the complexity of this problem? Is there any reduction from a NP-complete problem to the above problem? Is there any efficient way to solve this problem? Any information about this problem is welcome, I find no mentions of it in literature.

Update with some more (useful) informations:

• The existence of a solution is obvious, since the set $\{\vec{0}\}$ is a vector space contained in $X$ by definition, and there are finitely many subsets of $X$ (since $X$ is finite). Note that it might not be unique, if multiple maximal spaces exist in $X$, finding one of them is enough.

• It would also be useful to find some bounds on the size of the solution, for example, if $|X| \geq 2$ then we can infer that any solution has at least dimension 1. Maybe this reasoning extends to a general bound? If I were to guess such a bound would probably end up being very loose.

Answer 1

I provide an upper bound on the computational complexity by giving you a Python function find_maximal_subspace which, given a finite set of vectors, finds a maximal vector subspace included in it.

from typing import Set, List, Tuple, Iterable
from itertools import product, repeat

Vector = int
# I introduce this type synonym just to improve readability.
# I will model vectors as ints using the bitwise xor (^).
# So whenever I view an int as a vector, I add a Vector type hint.

def get_span(lin_indep_list: List[Vector]) -> Iterable[Vector]:
    """If `lin_indep_list` is a linearly independent list of vectors, `get_span`
    iterates over all vectors in its span."""
    for coefficients in product(*repeat((0, 1), len(lin_indep_list))):
        result : Vector = 0
        for coefficient, vector in zip(coefficients, lin_indep_list):
            result ^= coefficient * vector
        yield result

def find_maximal_subspace(X: Set[Vector]) -> Iterable[Vector]:
    """Find a maximal vector subspace of a set of vectors `X`. To do this, we loop over
    the vectors in `X` while keeping a subspace we already found (represented as a basis).
    For each vector in `X`, we check if it can be used to extend the currently found subspace.
    When we find that it can, we extend the currently found basis with it and remove
    from `X` vectors which definitely can't be used to extend the currently found basis.
    When we find that it cannot, we remove it and, possibly, one other useless vector from `X`.
    """
    X.remove(0)
    basis : List[Vector] = []
    def try_to_extend() -> None:
        """If `basis` is a linearly independent list of vectors,
        `X` is nonempty, and none of the vectors of `X` are in the span of `basis`,
        then `try_to_extend` takes a vector from `X` and either
        1. appends it to `basis` (which keeps `basis` linearly independent)
           and removes all vectors in the span of the new `basis` from `X`; or
        2. removes it from `X`, because some vector in the span of the new would-be `basis`
           minus the span of the old `basis` is not in `X`. In this case, it might also
           remove some other vectors `X` which can't be used to extend `basis`.
        """
        potential_basis_vector = X.pop()
        print(f"considering {potential_basis_vector:b} to append")
        for vector_in_span in get_span(basis):
            vector_to_check = vector_in_span ^ potential_basis_vector
            if vector_to_check == potential_basis_vector:
                continue
            elif vector_to_check in X:
                X.remove(vector_to_check)
                print(f"removed {vector_to_check:b}")
            else:
                assert vector_to_check not in X
                print(f"{vector_to_check:b} not in X")
                return
        basis.append(potential_basis_vector)
        print(f"appended {potential_basis_vector:b}")
    while len(X) > 0:
        # Invariant: at each iteration, `basis` is a linearly independent list of vectors,
        # no vectors in `X` are in the span of `basis`,
        # the span of `basis` is a maximal vector subspace of the set of vectors removed from
        # `X` so far
        try_to_extend()
    return get_span(basis)

An example of usage:

X: Set[Vector] = set([ 0b00000,
                       0b00010,
                       0b00110,
                       0b00011,
                       0b11001,
                       0b01000,
                       0b11000,
                       0b01001,
                       0b00100,
                       0b00101,
                       0b00001,
                       0b00111])
maximal_subspace = tuple(find_maximal_subspace(X))
print("A maximal subspace is:")
for x in maximal_subspace:
    print(f"{x:b}")

This prints

considering 1 to append
appended 1
considering 10 to append
removed 11
appended 10
considering 100 to append
removed 110
removed 101
removed 111
appended 100
considering 1000 to append
1100 not in X
considering 1001 to append
1101 not in X
considering 11000 to append
11100 not in X
considering 11001 to append
11101 not in X
A maximal subspace is:
0
100
10
110
1
101
11
111

It's clear that this program is polynomial time in $n |X|$, and I can't be bothered to calculate the computation complexity more accurately than that. Also, it's possible that a more efficient algorithm exists.

I also provide a pseudocode program:

Input: X a finite set of vectors including 0.

Remove 0 from X.
Assign basis := empty set of vectors.
while X is nonempty:
    Assign v := some element from X.
    if v + span(basis) ⊆ X:
        Set X := X \ (v + span(basis)).
        Add v to basis.
    else:
        Set X := X \ (v + span(basis)).
Output span(basis).