4

Prove that if $|x_1-t|+|x_2-t|+\cdots+|x_n-t| = |y_1-t|+|y_2-t|+\cdots+|y_n-t|$ for all values of $t$ then $\{x_1,\ldots,x_n\} = \{y_1,\ldots,y_n\} $

(All the variables are real numbers).

I tried to prove that minimums are equal then continue by induction, but I couldn't progress much in that line.

Community
  • 1
hhsaffar
  • 2,937

3 Answers3

2

It is easy to see that $(*)$ the local minima of the function $f\colon t \mapsto |x_1-t|+|x_2-t|+\cdots+|x_n-t|$ are exactly the $x_i$. This answers your question.

To check $(*)$, noting $u_1<u_2<\cdots <u_s$ the distinct values among the $x_i$, we see that $f(t)=\displaystyle\sum_{k=1}^{s} n_k |x-u_k|$ where the $n_k$ are positive integers. The function $f$ is piecewise affine: for $x$ between $u_j$ and $u_{j+1}$ we have $$ f(x)=\sum_{k\leq j} n_k(x-u_k)+\sum_{k > j} n_k(u_k-x) $$ from which $(*)$ can be easily deduced.

dfeuer
  • 9,069
Ewan Delanoy
  • 61,600
  • Thank you very much but can clarify your hint further, So it goes like this In the minimum $f_x(x_i) = f_y(y_j)$, and then? Can I deduce $x_i=y_j$? How? – hhsaffar Nov 12 '13 at 17:06
  • I don't get it, the minimum of $t \mapsto \Vert x - t.\mathbf 1 \Vert_1$ is the median of $x$, which may take several values, but it is not the $x_i$... – roger Nov 12 '13 at 17:24
  • You are right Roger, I my self was thinking about it right now. I deleted my previous comments. – hhsaffar Nov 12 '13 at 17:26
  • This is incorrect. The function $f$ is convex and hence the local minimizers are either a single point or an interval. In fact, a point $t$ is a minimizer of $f$ iff $t$ is a median of the data $x_1,...,x_n$. So, while it is true that you can determine the (ordered values of) $x$ from $f$, it is not true that you can determine the values from the minimizers. – copper.hat Nov 12 '13 at 17:52
2

Note: this answer is only valid for real values. However, the same idea can be used for complex values (assuming that $t \in \mathbb{C}$ as well), by taking $t$ to lie on a line parallel to the real axis through each $x_k$.

Suppose $x \in \mathbb{R}^n$ and $x_1 \le \cdots \le x_n$. Let $\phi_x(t) = \sum_k |x_k-t|$. We note that $\phi_x$ is differentiable on $D=\mathbb{R} \setminus \{x_1,\ldots,x_n\}$, and $\phi_x'(t) = | \{i: x_i < t\}| - | \{i: x_i > t\}| $ for $t \in D$ (here I am using $|\cdot|$ for the cardinality). Note that $\phi_x'(t) \in \{-n,\ldots,n\}$ and at the points of discontinuity, $\phi_x'$ changes by 2.

Then $\phi_x$ completely specifies $x$. To see this, first note that $\lim_{t \to \infty} \phi_x'(t) = n$, hence we know the number of points $n$.

We note that $\phi_x'$ is non-decreasing. Let $A = \{ \tau : \lim_{t \uparrow \tau} \phi_x'(t) < \lim_{t \downarrow \tau} \phi_x'(t) \}$, and note that $A$ is finite. For $a \in A$, let $n(a) = \frac{1}{2}(\lim_{t \downarrow a} \phi_x'(t) - \lim_{t \uparrow a} \phi_x'(t))$. Then if we let $A = \{ a_1,\ldots,a_k\}$ where $a_i < a_{i+1}$, and define the matrix $P:\mathbb{R}^k \to \mathbb{R}^n$ by $$[P]_{ij} = \begin{cases} 1, & 1 \le i \le n(a_1) \\ 1, & 1<j, \ n(a_1)+\cdots +n(a_{j-1})< i \le n(a_1)+\cdots +n(a_{j}) \\ 0, & \text{otherwise,}\end{cases}$$ then $x=Pa$.

It follows from this that if $\phi_x = \phi_y$, where the $x,y$ are “ordered” then $x=y$.

Addendum: The complex case is similar, except that (taking $\phi_x$ as a map $\mathbb{R}^2 \to \mathbb{R}$) $\phi_x'(t) = \sum_k \frac{t-x_k}{|t-x_k|}$, for $ t \notin D = \mathbb{R}^2 \setminus \{x_1,\ldots,x_n\}$. Then $\phi_x'$ is continuous for $x \notin D$. Furthermore, if we let $n(a) = \frac{1}{2}(\lim_{\delta \downarrow 0} \phi_x'(a+\delta) - \lim_{\delta \downarrow 0} \phi_x'(a-\delta))$ (note that $\delta$ only takes real values), then $n(a)=0$ for $a\in D$, and if $ a \in \{x_1,\ldots,x_n\}$, then $n(a) = | \{ x_i | x_i = a \} | $.

In this case, $\phi_x$ determines the $x_i$ and their multiplicities, but not the order. However, this is sufficient to show that if $\phi_x = \phi_y$, then $\{x_1,\ldots,x_n\} = \{y_1,\ldots,y_n\}$ (and multiplicities as well, although this was not part of the question).

Note: It would have been simpler to show that $n(a) = \frac{1}{2}(\lim_{\delta \downarrow 0} \phi_x'(a+\delta) - \lim_{\delta \downarrow 0} \phi_x'(a-\delta))$ is defined everywhere and $n(a) = | \{ x_i | x_i = a \} | $. Then if $\phi_x=\phi_y$, the corresponding '$n$s' must be equal, and the result follows immediately from the fact that $n(a) = | \{ x_i | x_i = a \} | $.

copper.hat
  • 172,524
  • I replaced "completely specified by $\phi_x'$" with "completely specified by $\phi_x$", which I imagine is what you intended. I also switched vertical bars to colons because $|{a|b}|$ is just confusing. – dfeuer Nov 12 '13 at 19:17
  • @dfeuer: Thanks! And thanks for the other editing. Despite being my first language, grammar was never a strong point. – copper.hat Nov 12 '13 at 19:19
  • Me likes grammar alot. Me are much well of them! Actually, the vast majority of my edits this time were $\LaTeX$ tweaks. – dfeuer Nov 12 '13 at 19:21
  • The idea of using derivative was very nice, I didn't understand the last part of your proof but I think I came by a solution based your idea. Thank you very much. – hhsaffar Nov 12 '13 at 19:21
  • 1
    @hhsaffar: The last part is just formalizing the fact that the points of discontinuity of $\phi_x'$ are the $x_i$, and the limits ($n(a)$ above) give the 'multiplicity' if each $x_i$. The $P$ is just an awkward way of expressing that $x=(a_1,...,a_1, a_2,...,a_2,...)$ where each $a_i$ occurs $n(a_i)$ times. – copper.hat Nov 12 '13 at 19:26
  • @copper.hat, thank you, I also added my answer. – hhsaffar Nov 12 '13 at 19:42
  • @hhsaffar: I added a note about the complex case. The key point is that the function $n(a)$ which is defined everywhere, completely determines the $x_i$ and their multiplicities. – copper.hat Nov 12 '13 at 19:42
0

The idea of this answer is based on copper.hat's Idea.

Suppose $x_1\leq x_2...\leq x_n$ and $y_1\leq y_2...\leq y_n$ and $\phi_x(t) = \sum_k |x_k-t|$ and $\phi_y(t) = \sum_k |y_k-t|$.

The least $t$ that $\phi_x(t)$ is not differentiable at is $x_1$ and the least $t$ that $\phi_y(t)$ is not differentiable at is $y_1$. But $\phi_x(t)=\phi_y(t)$ so $x_1=y_1$.

Now we can use induction.

hhsaffar
  • 2,937