Existe un vector $c\in C$ con $c\cdot b=1$

Question

Sea $n$ sea un número entero positivo, y $A$ sea el conjunto de todos los vectores distintos de cero de la forma $(e_1,e_2,\dots,e_n)$ donde $ e_i\in\{0,1\}$ . Así que $|A|=2^n-1$ . Sea $B$ sea un subconjunto propio de $A$ . ¿Existe siempre un subconjunto $C\subseteq A$ de tamaño máximo $n-1$ tal que para cualquier vector en $b\in B$ existe un vector $c\in C$ con $c\cdot b=1$ ?

Si permitiéramos $B=A$ entonces podemos elegir un conjunto $C$ de tamaño $n$ los vectores unitarios $(1,0,\dots,0),(0,1,\dots,0),\dots,(0,0,\dots,1)$ . Ahora, como tenemos $B$ es un subconjunto propio de $A$ parece que también deberíamos necesitar un $C$ .

Answer 1

Claro. Básicamente usamos un vector perdido para definir las cosas de forma que nos ahorremos 1 miembro de $C$ .

Más formalmente, dejemos que $u$ sea un vector que falta en $B$ , $S$ sea el soporte de $u$ y que $v_i$ sea el vector que tiene un único $1$ en el $i$ -Enésima posición. A continuación, defina $C$ como sigue:

• incluir en $C$ todos los vectores $v_i$ para $i\notin S$ ;
• arreglar algunos $s\in S$ e incluir en $C$ todos los vectores de la forma $v_s + v_j$ donde $j\in S-\{s\}$ .

Esto da un total de $|C|=n-1$ elementos. Ahora dejemos que $v\in B$ sea un vector cualquiera. Si $v_i=1$ para algunos $i\notin S$ podemos utilizar $v_i\in C$ . De lo contrario, el apoyo de $v$ es un subconjunto de $S$ . Si $v_s\neq 1$ habrá algunos $j$ tal que $v_j=1$ y podemos utilizar $v_s+v_j\in C$ .

Por lo demás, $v_s=1$ ; este es el paso clave: esto significa que habrá $j\in S$ tal que $v_j=0$ ya que de lo contrario $v=u$ . Así, podemos utilizar $v_s+v_j\in C$ .

Esto cubre todos los casos y completa el análisis.