Base minimale pour un ensemble de vecteurs binaires utilisant XOR

Je serais surpris si ce n'était pas un problème bien étudié, mais je ne sais pas quoi chercher d'autre à ce stade: on vous donne un ensemble de -vecteurs binaires . Le problème est de trouver un autre ensemble de vecteurs binaires , avec une taille minimale, de sorte que chaque vecteur de peut être exprimé par les résultats XOR d'un sous-ensemble de (donc est essentiellement une base pour utilisant XOR au lieu de l'addition et n'autorisant que des coefficients binaires dans la combinaison linéaire).$n$$S \subset \{0,1\}^n$$n$$B \subset \{0,1\}^n$$|B|$$S$$B$$B$$S$

D'une certaine manière, c'est une forme de PCA pour les vecteurs binaires. En cherchant de la littérature sur ce problème, je suis tombé sur le problème de base discrète également discuté dans cette thèse de doctorat , qui semble étroitement lié. Au lieu de XOR, il utilise OR, et iciest une entrée supplémentaire (et la tâche consiste à minimiser l'erreur de représentation de avec des vecteurs de ). Ce problème est NP-difficile. La même chose s'applique-t-elle au problème que j'ai présenté ci-dessus ou existe-t-il une solution efficace? Tout pointeur sur la littérature existante serait très apprécié.$|B|$$S$$B$

Si vous traitez vos vecteurs comme sur le champ plutôt que sur l'ensemble , alors ce que vous demandez est de trouver une base pour l'étendue d'un ensemble de vecteurs. C'est un problème bien étudié en algèbre linéaire, pour lequel vous connaissez probablement la solution. (Une option est l'élimination gaussienne.)$GF(2)$$\{0,1\}$