Complemento de todo un vector en espacio del vector binario

Question

Deje $V$ ser un k-dimensional subespacio de $(\mathbb{F}_2)^n$, de tal manera que el vector $\vec{j}=(1,1,...,1) \in V$.

Estándar de álgebra lineal muestra que es posible encontrar una $(k-1)$espacio tridimensional $W$ tal que $\langle \vec{j},W\rangle=V$. Sin embargo, esta opción no es único.

Hay alguna "canónica" opción para $W$, es decir, uno que no depende de ciertas posiciones especiales, como es el complemento ortogonal en el $\mathbb{R}$-caso?

En caso de que importa, mis parámetros son $n=2058$, $k=52$ y todos los vectores en $V$ tienen peso (de manera ortogonal complemento es inútil).

Edit: aclaración de lo que quiero decir con "sin hacer ciertas posiciones especiales". Considere la posibilidad de la acción de la $S_n$ como una permutación de grupo en las posiciones de los vectores en el espacio, y deje $G\le S_n$ ser el estabilizador de $V$ en esa acción. A continuación, $G$ también debe estabilizar $W$, como en el complemento ortogonal caso. (Tenga en cuenta que $G$ automáticamente se estabiliza $\vec{j}$.) No estoy seguro de si tales existen espacios en general, por lo que un posible algoritmo para encontrar uno es apreciado también.

Answer 1

He encontrado la respuesta para mi código en particular. Voy a contarles acerca de mi historia en el caso de que otras personas a publicar aquí por si otras personas que lea esto, pero voy a dejar la recompensa abierto para que si otros interesantes respuestas pueden venir.

Exhaustivamente la generación de todos los $2^{52}$ palabras de código (en realidad, $2^{51}$ $\vec{j}\in V$ optimization), encontré que el más pequeño distinto de cero número de $1$s que aparecen es $562$, y el conjunto de $S$ de todos los $562$-palabras ha $\langle S\rangle = V$, y, por supuesto, el estabilizador de la $V$ también debe estabilizar $S$ (como permuting posiciones no cambia el número total de unidades).

Ahora, vamos a $S'=\{v+v'|v,v'\in S\}$. A continuación, $W:=\langle S'\rangle$ es $k$-dimensional o $(k-1)$-dimensional. En mi caso es $(k-1)$-dimensional, por lo que el resultado es el deseado de construcción.

Answer 2

Denotamos $j = \begin{bmatrix} 1 & 1 & \dots & 1 \end{bmatrix}^T \in V$ donde $V$ $k$- dimensiones subespacio de $\{0,1\}^n$.

Observemos el caso de $2n = k$ (desde $j \in V$, sabemos que $n$ es incluso) y $V = \mathop{\rm span}\{v_1,\dots,v_k\}$ donde $v_i = e_{2i-1} + e_{2i}$. Aquí, los vectores $e_i$ denotan los vectores de la norma canónica base en $\mathbb{R}^n$, es decir, las columnas de la matriz identidad.

Definimos $W_i := \mathop{\rm span}\left(\{v_1,\dots,v_k\} \setminus \{v_i\}\right)$ y consigue $k$ candidatos para el espacio de $W$ (estos son, obviamente, no son los únicos; sólo los más simples a definir). Honestamente, no veo ninguna razón por qué elegir cualquiera de ellos (o cualquiera de esos que no se entre $W_i$) sobre las demás, así que yo diría que la respuesta a su pregunta es "no".

Un ejemplo similar podría ser acuñado para su $n$$k$, $v_i$ sumas de $38$ o $40$ canónica de vectores $e_l$.

La ortogonalidad es una poderosa propiedad, que hace de estos subespacios una muy interesante opción. Teniendo esa ventaja, su especial recogida puede depender solo de alguna otra propiedad deseable, por lo que usted puede ser que desee comprobar si usted tiene cualquiera.