Infimum of the sum of absolute differences from $x$ occurs when $x$ is the median You have a set of real numbers $\{x_i\}_{i=1}^n$. You want to find what $x_{min}$ that minimizes $$\sum_{i=1}^n |x_i - x_{min}|$$
I can argue that this is minimized when $x_{min}$ is the median since, if it's not, then you either moving up or down by a distance $y$ will cause a smaller value since you make $n$ terms smaller by $y$ and $m$ terms larger by $y$, with $n > m$.
However, is there a more clean, algebraic / less hand-wavy way to prove it?
 A: Looking at each $x_i$ individually, we know that the derivative of $x\mapsto |x_i-x|$ is
$x \mapsto
\left\{
\begin{array}{ll}
      -1 & (x< x_i) \\
      1 & (x> x_i) \\
\end{array} 
\right.$
Therefore, we know that the solution isn't at $]-\infty,x_i[$ or at $]x_i,+\infty[$, as $|x_i-x|$ will grow indefinitely in those regions.
Let's suppose for simplicity that the $x_i$ are different one from the other when compared each two, and let's rewrite $\{x_i\}$ as $\{x_{\phi(i)}\}$ where $\phi$ is a bijection of $\{1,...,n\}$ where the $x_i$ are reordered in increasing order.
Now, let's consider the function $f:x\mapsto \sum_{i=1}^n |x_i-x|=\sum_{i=1}^n |x_{\phi(i)}-x|$.
For $x<x_{\phi(1)}$, $f'(x)=-|\{x_i\}|=-n$. For $x_{\phi(1)}<x<x_{\phi(2)}$, $f'(x)=2-n$. Generalizing, for $x_{\phi(j)}<x<x_{\phi(j+1)}$ we have $f'(x)=2j-n$.
If $n$ is even, $f'(x)=0$ for $x_{\phi(\frac{n}{2})}<x<x_{\phi(\frac{n+1}{2})}$, and so $x_{min}$ is in this interval.
If it isn't, $f'$ changes its signal in $x_{\phi(\frac{n+1}{2})}$, and so $x_{min}=x_{\phi(\frac{n+1}{2})}$.
