# Linear separability

In geometry, two sets of points in a two-dimensional space are linearly separable if they can be completely separated by a single line. In general, two point sets are linearly separable in n-dimensional space if they can be separated by a hyperplane.

In more mathematical terms: Let $X_{0}$ and $X_{1}$ be two sets of points in an n-dimensional space. Then $X_{0}$ and $X_{1}$ are linearly separable if there exists n+1 real numbers $w_{1}, w_{2},..,w_{n}, k$, such that every point $x \in X_{0}$ satisfies $\sum^{n}_{i=1} w_{i}x_{i}\ge k$ and every point $x \in X_{1}$ satisfies $\sum^{n}_{i=1} w_{i}x_{i} < k$, where $x_{i}$ is the $i$-th component of $x$.

Equivalently, two sets are linearly separable precisely when their respective convex hulls are disjoint (colloquially, do not overlap).

## Example

Three points in two classes ('+' and '-') are always linearly separable in two dimensions. This is illustrated by the three examples in the following figure:

However, not all sets of four points are linearly separable in two dimensions. The following example would need two straight lines and thus is not linearly separable:

## Linear separability of hypercubes in n dimensions

Number of linearly separable Boolean hypercubes in each dimension[1] (sequence A000609 in OEIS)
Dimension Linearly separable Boolean hypercubes
2 14
3 104
4 1882
5 94572
6 15028134
7 8378070864
8 17561539552946
9 144130531453121108

## Usage

Linear separability allows simple Classification in machine learning.