$W$ be a $d$-dimensional subspace of $\mathbb R^n$. Then how to show that $|\{(x_1,...,x_n) \in W : x_i \in \{0,1\}\}| \le 2^d$?

Question

Let $W$ be a $d$-dimensional subspace of $\mathbb R^n$. Then how to show that $|\{(x_1,...,x_n) \in W : x_i \in \{0,1\}\}| \le 2^d$ ?

I can see that we are done if we can find an injective function from $\{(x_1,...,x_n) \in W : x_i \in \{0,1\}\}$ to $\mathbb F_2^d $ , but I can't quite see any such natural injection.

Answer 1

If $S$ is any set let $\Bbb R^S$ denote the vector space of all functions from $S$ to $\Bbb R$. Regard $\Bbb R^n$ as $\Bbb R^{\{1,2,\dots,n\}}$.

Now if $S\subset\{1,2\dots,n\}$ there is a natural linear map $$T_S:\Bbb R^n\to \Bbb R^S$$defined by $$T_Sx=x|_S.$$

(To perhaps clarify, less formally: If $d=3$ and $S=\{1,3\}$ one might regard $T_S$ as defined by $T_S(x_1,x_2,x_3)=(x_1,x_3)$.)

Note this:

Note: If $W$ is a subspace of dimension $d$ then there exists $S\subset\{1,2,\dots,n\}$ such that $|S|=d$ and the restriction of $T_S$ to $W$ is injective.

Inelegant "proof": Say $A$ is a matrix that has the elements of a basis for $W$ as rows. Then $A$ has rank $d$; let $S$ consist of the indices where an echelon form for $A$ has pivots...

One might add a few details, but that certainly seems right. If so then there's your injective map from your set to $\{0,1\}^d$.

Edit: Ok, a somewhat more detailed proof of the Note above: Let $A$ be a $d\times n$ matrix such that the rows of $A$ form a basis for $W$. Since the row rank equals the column rank, $A$ has $d$ independent columns. Say $C_j(A)$ is the $j$th column of $A$. Say $|S|=d$ and $\{C_j(A):j\in S\}$ is independent. Let $D$ be the square matrix with columns precisely $C_j(A)$ for $j\in S$. Then $D$ is a $d\times d$ matrix of rank $d$, so $D$ is invertible, and hence the rows of $D$ are independent.

So: Starting with a basis $b_1,\dots,b_d$ for $W$ we have found $S$ with $|S|=d$ such that $T_Sb_1,\dots,T_Sb_d$ are independent. Hence the restriction of $T_S$ to $W$ is injective.

Answer 2

This is essentially the same argument as David C. Ullrich's, but explained without matrices:

We would like to show that elements of $W$ are determined by $d$ well-chosen, fixed, projections $p_i$ out of the $n$ natural projections $\mathbb R^n \to \mathbb R$. I.e. we want that the intersection of the $\ker p_i$ intersects $W$ trivially. Put differently, we want an $n-d$-dimensional subspace spanned by $n-d$ standard basis elements, which is complementary to $W$.

We can generalize the result we need as follows:

Proposition. Let $V$ be a finite-dimensional vector space, $\dim V = n$, and $W \subseteq V$ a subspace, $\dim W = d$. Let $U \subseteq V$ be a set that spans $V$ together with $W$. Then there exist $n-d$ elements in $U$ that span a subspace complementary to $W$.

Proof 1. By induction on $n-d$: For $d=n$ there is nothing to prove. Suppose $d < n$, then because $W \neq V$ there exists $u \in U - W$. Apply the induction hypothesis to $W' = W + \langle u \rangle$ and $U' = U - \{u\}$, and note that $\dim W' = d + 1$. $\square$

Proof 2. Quotienting everything by $W$, this simply says that if $U$ (actually: its image in the quotient) spans $V/W$, then it contains a basis of $V/W$. $\square$

It suffices to apply this for $V = \mathbb R^n$, $W=W$ and $U$ the standard basis.