linear functional separates finite number of points

Question

Let $0 < m < \infty$ be a finite integer. Given $m$ distinct points $\{z_k\}_{k=1}^m$ in $\mathbb{R}^n$, why does there exist a linear functional $\Lambda: \mathbb{R}^n \to \mathbb{R}$ that separates them?

Answer 1

The idea is straightforward, but tedious to write.

If $n>1$, let $z_k = (a_k,b_k)$, where $a_k$ are the first $n-1$ components. Using induction, find a functional $f:\mathbb{R}^{n-1} \to \mathbb{R}$ that separates the distinct elements of $\{a_k\}_k$ (it is possible that $a_k = a_{k'}$ for $k \neq k'$).

Now consider the functional $\phi_\alpha(x) = f((x_1,...,x_{n-1}))+ \alpha x_n$. If $\phi_0$ separates the $z_k$ we are done, so assume that at least two points have the same $\phi_0$ value.

Since the points are distinct, if $\phi_0(z_k) = \phi_0(z_{k'})$ for distinct $k,k'$ then $b_k \neq b_{k'}$. We need to chose $\alpha$ so that it separates.

Partition the $z_k$ into sets $E_1,...,E_p$ according to the value that $\phi_0$ assigns them, and let $v_1,...,v_p$ be the corresponding distinct values. Note that by our last assumption, $p>1$.

Let $\delta = \min_{i \neq j} |v_i-v_j|$ and let $M= \max_k |b_k|$ (so that the $b_k$ lie in $[-M,M]$) and let $\alpha = {\delta \over 3} {1 \over 2M}$.

Then $\phi_\alpha$ separates the points. The idea behind the choice of $\alpha$ is that the $b_k$ components separates the elements of the clusters $E_i$ but not by enough that would cause two points to have the same $\phi_\alpha$ value.

To check, suppose $k \ne k'$. If $z_k, z_k'$ belong to the same $E_i$, then $\phi_\alpha(z_k-z_{k'}) = \alpha (b_k-b_{k'}) \neq 0$. If they belong to different $E_i$, then (by swapping if necessary) $f(a_k) - f(a_{k'}) \ge \delta$, and since $\alpha | b_k-b_{k'} | \le {\delta \over 3} $, we see that $\phi_\alpha(z_k-z_{k'}) = f(a_k - a_{k'})+ \alpha (b_k-b_{k'}) \ge {2 \over 3}\delta >0$.

Another approach:

Here is another proof, quicker but relies on measure theory. Suppose $h \neq 0$ and let $N_h = \{ \phi \mid \phi \text{ is a linear functional}, \phi(h) = 0\}$. It is straightforward to show that $N_h$ has measure zero. Then the set of functionals that do not separate the $z_k$ is given by $\cup_{i<j} N_{z_i-z_j}$ and since this is a finite collection of measure zero sets, we see that it has measure zero. In particular, almost any (in a measure theoretic sense) linear functional will separate the collection $z_k$.

As an aside, the same approach shows that almost any linear functional will separate a countable collection of points.

Answer 2

If $\{z_k\}_{k=1}^m$ is a finite set of points in $\mathbb R^n$, then using the standard inner product or "dot product", that is, $\langle x,y \rangle =\sum_{i=1}^n x_iy_i$ for $x= (x_1,\ldots,x_n)^{\intercal}$, $y =(y_1,\ldots,y_n)^{\intercal}$, any linear functional on $\mathbb R^n$ is equal to $\theta_v\colon \mathbb R^n \to \mathbb R$ for some $v \in \mathbb R^n$, where $\theta_v(x)= \langle v,x \rangle$.

Thus to show we can separate the $\{z_k\}_{k=1}^m$ we must find a $v \in \mathbb R^n$ such that, for any $i,j$ with $1\leq i,j\leq m$ we have $\theta_v(z_i)=\theta_v(z_j)$ if and only if $i=j$.

But now if we let $D=\{z_i-z_j: 1\leq i<j\leq m\}$, this condition becomes $\theta(w)\neq 0$ for all $w\in D$. But since $D$ is a finite set (indeed $|D|\leq \binom{m}{2}$) and $\theta_v(w) = \langle v,w\rangle = \langle w,v \rangle = \theta_w(v)$, if we let $$ \mathcal H= \bigcup_{w \in D} H_w, \quad \text{ where } \quad H_w = \{x \in \mathbb R^n: \theta_w(x)=\langle w,x\rangle = 0\} $$ then the condition on $v$ becomes $v \notin \mathcal H$. Thus we can complete the proof using the following:

Lemma If $V$ is a finite-dimensional vector space over an infinite field $\mathsf k$ then if $H_1,\ldots,H_m$ is a finite collection of proper subspaces of $V$, then $\bigcup_{i=1}^m H_i$ is a proper subset of $V$.

Proof: We use induction on $m$. If $m=1$ then $H_1$ is a proper subspace of $V$ by assumption, so the result is trivial. Now suppose we know the result for any collection of $k<m$ proper subspaces and we are given subspaces $H_1,\ldots, H_m$ proper subspaces of $V$. If $H_m\subseteq H_j$ for some $j<m$ then $\bigcup_{i=1}^m H_i = \bigcup_{i=1}^{m-1} H_i$ and we are done by induction. Otherwise, for each $j<m$, $H_m\cap H_j$ is a proper subspace of $H_m$ and so by induction there is some $u \in H_m\backslash \bigcup_{j=1}^{m-1} H_j\cap H_m$. Since $H_m$ is a proper subspace of $V$ we may also choose $v \in V\backslash H_m$.

But now consider the vectors $w_t = v+tu$ ($t\in \mathsf k$). Since $v \notin H_m$ and $u\in H_m$ we have $w_t \notin H_m$ for all $t \in \mathsf k$. But if $s,t\in \mathsf k$ are distinct, then as $w_s = w_t+ (s-t)u$, if both lie in $H_j$ it follows $u\in H_j$, contradicting our choice of $u$. It follows that if $F\subseteq \mathsf k$ is any subset with at least $m$ elements (since $\mathsf k$ is infinite, such subsets exist!) then $\{w_t: t \in F\}$ must contain a vector not in any $H_j$ $(1\leq j\leq m)$.