$W$ ser un $d$-dimensional subespacio de $\mathbb R^n$. Entonces ¿cómo mostrar que $|\{(x_1,...,x_n) \in W : x_i \in \{0,1\}\}| \le 2^d$?

Question

Que $W$ ser un $d$-dimensional subespacio de $\mathbb R^n$. Entonces ¿cómo mostrar que $|{(x_1,...,x_n) \in W : x_i \in {0,1}}| \le 2^d$?

Veo que estamos hecho si podemos encontrar una función inyectiva de ${(x_1,...,x_n) \in W : x_i \in {0,1}}$ $\mathbb F_2^d$, pero no veo absolutamente ningún tal inyección natural.

Answer 1

Si $S$ es cualquier conjunto deje $\Bbb R^S$ denota el espacio vectorial de todas las funciones de$S$$\Bbb R$. Respecto a$\Bbb R^n$$\Bbb R^{\{1,2,\dots,n\}}$.

Ahora si $S\subset\{1,2\dots,n\}$ hay una natural lineal mapa $$T_S:\Bbb R^n\to \Bbb R^S$$ defined by $$T_Sx=x|_S.$$

(Tal vez de aclarar, de manera menos formal: Si $d=3$ $S=\{1,3\}$ se podría considerar $T_S$ como se define por $T_S(x_1,x_2,x_3)=(x_1,x_3)$.)

Observe esto:

Nota: Si $W$ es un subespacio de dimensión $d$ existe $S\subset\{1,2,\dots,n\}$ tal que $|S|=d$ y la restricción de $T_S$ $W$es inyectiva.

Poco elegante "prueba": Decir $A$ es una matriz que tiene los elementos de una base para la $W$ como filas. A continuación, $A$ rango $d$; deje $S$ consta de los índices donde de una forma escalonada por $A$ tiene pivotes...

Uno podría agregar un par de detalles, pero que sin duda parece justo. Si es así, entonces no es tu inyectiva mapa de tu conjunto a $\{0,1\}^d$.

Edit: Ok, un poco más detallada de la prueba de la Nota anterior: Vamos a $A$ $d\times n$ matriz de modo que las filas de a $A$ forma una base para $W$. Desde la fila rango es igual a la columna de rango, $A$ $d$ independiente de las columnas. Decir $C_j(A)$ $j$ésima columna de a $A$. Decir $|S|=d$ $\{C_j(A):j\in S\}$ es independiente. Deje $D$ ser la matriz cuadrada con columnas, precisamente,$C_j(A)$$j\in S$. A continuación, $D$ $d\times d$ matriz de rango $d$, lo $D$ es invertible, y por lo tanto, las filas de $D$ son independientes.

Así: a Partir de una base $b_1,\dots,b_d$ $W$ hemos encontrado $S$ $|S|=d$ tal que $T_Sb_1,\dots,T_Sb_d$ son independientes. Por lo tanto la restricción de $T_S$ $W$es inyectiva.

Answer 2

Este es esencialmente el mismo argumento como David C. Ullrich, pero se explica sin las matrices:

Nos gustaría mostrar que los elementos de la $W$ son determinados por $d$ bien elegido, fijo, proyecciones de $p_i$ $n$ natural proyecciones de $\mathbb R^n \to \mathbb R$. I. e. queremos que la intersección de la $\ker p_i$ intersecta $W$ trivialmente. Dicho de otra manera, queremos un $n-d$-dimensiones subespacio generado por $n-d$ estándar de la base de los elementos, que es complementaria a la de $W$.

Podemos generalizar el resultado que necesitamos de la siguiente manera:

La proposición. Deje $V$ ser finito-dimensional espacio vectorial, $\dim V = n$, e $W \subseteq V$ un subespacio, $\dim W = d$. Deje $U \subseteq V$ ser un conjunto que abarca $V$ junto con $W$. Entonces no existe $n-d$ elementos en $U$ que abarcan un subespacio complementario a $W$.

Prueba 1. Por inducción en $n-d$: $d=n$ no hay nada que demostrar. Supongamos $d < n$, debido a $W \neq V$ existe $u \in U - W$. Aplicar la hipótesis de inducción a$W' = W + \langle u \rangle$$U' = U - \{u\}$, y la nota que $\dim W' = d + 1$. $\square$

Prueba 2. Quotienting todo por $W$, esto simplemente dice que si $U$ (en realidad: su imagen en el cociente) abarca a $V/W$, entonces es contiene una base de $V/W$. $\square$

Basta con aplicar esta para $V = \mathbb R^n$, $W=W$ y $U$ el estándar de base.