# How can it be proved that if number of samples are less than $d+1$, then the sample set is linearly separable?

Pattern classification by Duda, Hart, Stork (Section- 9.6.8) states that a 2-class training set of $d+1$ or less samples in a d−dimensional space is always linearly separable i.e. if the samples span the $d$ dimensions and not in any sub-space of $d$.

In short, for $n \le d + 1$, where $n$ is the number of samples, there exists a separating hyperplane.

How can it be proved?

Upon increasing the dimension by 1, it's easy to construct a separating hyperplane explicitly.

Index the vectors $$v_i \in \mathbb{R}^d$$ so that the first $$k$$ of them ($$0 \le k \le d+1$$) belong to one class and the remaining $$d+1-k$$ belong to the other. Embed them all (linearly) into $$\mathbb{R}^{d+1}$$ by sending $$v_i$$ to $$u_i$$ where the first $$d$$ coordinates of $$u_i$$ are those of $$v_i$$ and the $$d+1^{st}$$ coordinate is $$1$$. Let's call this map $$\sigma$$. The assumptions imply the $$u_i$$ are a basis for $$\mathbb{R}^{d+1}$$. Let $$\omega_i, i=1,2,\ldots,d+1$$ be the dual basis: that is, $$\omega_j(u_i) = \delta_{ji}$$. Define the linear form $$\phi: \mathbb{R}^{d+1} \to \mathbb{R}$$ via

$$\phi = \sum_{i=1}^k \omega_i - \sum_{i=k+1}^{d+1} \omega_i.$$

That is, $$\phi(u_i) = 1$$ when $$i$$ is in the first class and $$\phi(u_i) = -1$$ when $$i$$ is in the second class. A separating hyperplane is

$$H: \{x \in \mathbb{R}^{d} \ | \ \phi(\sigma(x)) = 0\}.$$

### Example

Let $$v_1 = (0,1)'$$, $$v_2 = (1,0)'$$, and $$v_3 = (1,1)'$$ in $$\mathbb{R}^2$$ and suppose $$k=1$$ (i.e., $$v_1$$ is in one class--"blue"--and $$v_2$$ and $$v_3$$ are in the other class, "red").

Then

$$u_1 = (0,1,1)', \quad u_2 = (1,0,1)', \quad \text{and } u_3 = (1,1,1)'.$$

The forms dual to the $$u_i$$ are

$$\omega_1 = (-1,0,1), \quad \omega_2 = (0,-1,1), \quad \omega_3 = (1,1,-1),$$

as is readily checked by matrix multiplication (e.g., $$\omega_2(u_1)$$ = $$(0,-1,1)(0,1,1)'$$ = $$0 + -1 + 1 = 0$$, as required). Whence

$$\phi = \omega_1 - \omega_2 - \omega_3 = (-2,0,1).$$

For $$x = (x_1, x_2)' \in \mathbb{R}^2$$, $$\phi(\sigma(x)) = (-2,0,1)(x_1,x_2,1)' = -2x_1 + 1$$. A separating hyperplane is

$$H: -2x_1 + 1 = 0.$$

As a check, apply this formula for $$H$$ to the $$v_i$$, obtaining $$1$$, $$-1$$, and $$-1$$, as intended.