Conjunto de vectores en $\mathbb{F}_2^n$

Question

Sea $v_1, \dotsc, v_N$ sea un conjunto de vectores de $\mathbb{F}_2^n$ que tiene la siguiente propiedad: para cualquier elección de $1 \leq j_1 < \dotsb < j_n \leq N$ los vectores $v_{j_1}, \dotsc, v_{j_n}$ son linealmente independientes.

¿Cuál es el máximo posible $N$ ? ¿Existe una elección explícita de $v_1, \dotsc, v_N$ ¿en ese caso?

Gracias.

Answer 1

El resultado es un límite superior poco interesante $N\le n+1$ . Esto es relativamente conocido en un marco teórico de codificación . Permítanme darles un argumento sencillo.

Los vectores $v_1,v_2,\ldots,v_n$ obviamente debe constituir una base de $\Bbb{F}_2^n$ . Por lo tanto, podemos empezar a utilizarlas como base para el sistema de coordenadas y, por ejemplo, suponer que $v_1=(1,0,\ldots,0)$ , $v_2=(0,1,0,\ldots,0)$ , $\ldots$ , $v_n=(0,\ldots,0,1)$ . Sea $k>n$ y que $v_k=(b_1,b_2,\ldots,b_n)$ . Si algunos $b_i=0$ entonces el conjunto $v_1,v_2,\ldots,v_{i-1},v_{i+1},v_{i+2},\ldots,v_n,v_k$ depende linealmente. Por lo tanto, podemos concluir que $v_k=(1,1,\ldots,1)$ para todos $k, n<k$ . Sólo hay un vector de este tipo, por lo que debemos tener $k\le n+1$ y por lo tanto también $N\le n+1$ .

Es fácil ver que el conjunto $v_1,v_2,\ldots,v_n,v_{n+1}=\sum_{i=1}^nv_i$ tiene la propiedad prescrita. Por lo tanto $N=n+1$ se consigue.