My question flows out of the top answer to this question, from which I learned that a "linear function" is any function $f$ with properties of additivity and homogeneity of degree 1:
$$ f(x + y) = f(x) + f(y) \\ f(ax) = af(x) $$
Just reflecting on the formula for the median it seems to me that the function does not have additivity, but does have homogeneity of degree 1. Am I right about this? How can I prove what the right answer is?
Let $a$ be a real scalar and $\mathbf{x}$ be a vector in $\mathcal{R}^n$. Let us number the elements of $\mathbf{x}$ in order so that $x_1 \leq x_2 \leq \ldots \leq x_n $. Let $x_m = f(\mathbf{x})$ be the median of $\mathbf{x}$.
Observe that for $a \geq 0$, the elements of the vector $a\mathbf{x}$ have the same order: $$ a x_1 \leq \ldots \leq a x_m \leq \ldots \leq a x_n $$ And for $a < 0$ the order is reversed: $$ a x_n \leq \ldots \leq a x_m \leq \ldots \leq a x_1 $$ In either case $ax_m$ is in the middle, it's the median.
Counterexample to additivity: $$\mathbf{x} = \left[\begin{array}{c}2 \\ 4 \\ 6 \end{array} \right] \quad \quad \mathbf{y} = \left[\begin{array}{c} 0 \\ -4 \\ 4 \end{array}\right] \quad \quad \mathbf{x} + \mathbf{y} = \left[\begin{array}{c} 2 \\ 0 \\ 10 \end{array}\right] $$
$$ f(\mathbf{x}) = 4\quad \quad f(\mathbf{y}) = 0 \quad \quad f(\mathbf{x} + \mathbf{y}) = 2$$
Pedantic subpoint: if all the elements of both $\mathbf{x}$ and $\mathbf{y}$ are in ascending (or descending) order, then the median does satisfy additivity.
The OP is correct -- median is not linear since additivity does not hold, but homogeneity of degree $1$ holds.
We show by counterexample that the additivity does not hold: let $x=(0,1,2)$ and $y=(2,0,0)$ and let $f$ be the mapping from a vector to the median of its elements. Now, $f(x)=1,~f(y)=0$, so, \begin{equation} f(x+y) = f((2,1,2)) = 2 \neq 1 = f(x) + f(y). \end{equation}
The homogeneity of degree $1$ indeed holds as postulated in the answer:multiplying by a scalar does not change the order (except by reversing it if the scalar is negative, but this does not change who is in the middle), so if the median of $x$ is $x_i$, then also the median of $a\,x$ is $a\,x_i$. For even number of elements, the reasoning works if the median is defined to be the average of the two middle elements.
First, median minimizes the absolute error (Hurley, 2009) and $\mathrm{abs}$ is not a linear function.
As about $\alpha f(x) = f(\alpha x)$, there can be two interpretations depending on if you ask about case where $\alpha$ is a scalar, or a vector. Let's consider both cases, but first recall that we calculate median by sorting the values and taking the middle one.
If $\alpha$ is a scalar (as implied by the definition), then $\alpha f(x) = f(\alpha x)$ holds since multiplying $x$ by a scalar does not change the ordering.
If $\alpha$ is a vector, then taken at face value it doesn't have much sense since median is a function that maps $\mathbb{R}^n \to \mathbb{R}$, as noticed by @JuhoKokkala. In such case we only can re-phrase your question to comparing multiplying vectors and then sorting, versus sorting and then multiplying. In such case, the ordering of elements in $x\alpha$ may be different then ordering of $x$. So in both cases you may take different $x_i$ multiplied by $\alpha_i$ as your median.
You can easily produce numerical examples to convince yourself about that:
set.seed(123)
N <- 51
x <- rnorm(N)
a <- runif(N)
(x*a)[order(x*a)][(N+1)/2] # multiply and then sort
(x[order(x)]*a[order(x)])[(N+1)/2] # sort and then multiply
It is similar for $f(xy) = f(x) + f(y)$, where $x$ and $y$ are vectors, since sum of the elements may change the ordering (again, this is very simple to check numerically).
Hurley, W. J. (2009) An Inductive Approach to Calculate the MLE for the Double Exponential Distribution. Journal of Modern Applied Statistical Methods: 8(2), Article 25.
