Why does the unit cube have $2^n$ basic feasible solutions?

Question

A unit cube is defined by $2n$ constraints of the form:

$\{ x \in \mathbb{R}^n | 0 \leq x_i \leq 1, i = 1... n \}$

Why does this give $2^n$ basic feasible solutions?

I calculated the number of basic feasible solutions like so:

$(2n) C (n)$:

$\frac{(2n)!}{n! (2n-n)!}$

$\frac{(2n)!}{n!^2}$

This expression is not equal to $2^n$.

Answer 1

$\binom{2n}{n}$ is not the right quantity since we can't have $x_i=0$ and $x_i=1$ at the same time. Also, note the condition of independence of constraint in the definition of BFS.

For each variable, there are $2$ options, it is either $0$ or $1$, hence we have $2^n$ BFS for a unit cube.

Answer 2

In conventional linear programming notation, you would add $n$ slack variables $s_{i}$ and write this as a system of $n$ linear equality constraints

$x_{i} + s_{i}=1$, $i=1, 2, \ldots, n$

with

$x,s \geq 0$.

It’s easy to see that exactly one of $x_{i}$ or $s_{i}$ will be basic for $i=1, 2, \ldots, n$ in any basic feasible solution. At least one of $x_{i}$ or $s_{i}$ must be greater than 0 (and thus basic) to satisfy the $i$th constraint. There are only $n$ basic variables, so if a pair of $x_{i}$ and $s_{i}$ were both basic, then you'd be left with $n-2$ basic variables to satisfy the remaining $n-1$ constraints.

There’s a correspondence between bases and $n$ digit binary numbers with the $i$th digit equal to 0 if $x_{i}$ is basic and 1 if $s_{i}$ is basic. It is well known that there are $2^{n}$ binary numbers with $n$ bits.

It is true that there are $2n$ choose $n$ potential bases, but many of these are infeasible.

In general, with $m$ equality constraints and $n$ non-negative variables there are $m+n$ choose $m$ possible bases, but some bases may be infeasible, and multiple bases may represent the same (degenerate) basic feasible solution. There is not a one-to-one correspondence between possible bases and basic feasible solutions.

You could also treat this as an LP with no linear equality constraints, lower bounds of 0 on each variable, and upper bounds of 1 on each variable. In that case, each variable would be nonbasic at either its lower or upper bound and there are $2^{n}$ combinations of the lower and upper bounds.