# How can I prove that the median is a nonlinear function?

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?

• To prove something is not true, finding a counterexample tends to be the easiest method. – Matthew Gunn Aug 30 '16 at 8:37

### Median is homogenous of degree 1

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.

• Another pedantic comment: the same if either $x$ or $y$ are constant, or $x_i \ll y_i$, or $y_i \ll x_i$ for all $i$. – Tim Aug 30 '16 at 8:46
• (+1) Re the pedantic subpoint: the set of vectors in ascending or descending order does not however form a vector space, so the concept of linear mapping is perhaps not so appropriate. – Juho Kokkala Aug 30 '16 at 8:52
• @JuhoKokkala Yeah, if $\mathcal{A}$ is the set of vectors in ascending order and $\mathbf{x} \in \mathcal{A}$, the additive inverse $-\mathbf{x}$ doesn't belong to $\mathcal{A}$. That requirement of a vector space is violated. – Matthew Gunn Aug 30 '16 at 9:00

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, $$f(x+y) = f((2,1,2)) = 2 \neq 1 = f(x) + f(y).$$

### Homogeneity of degree 1 holds

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.

1. 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.

2. 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.

• I don't understand how this is related to linearity of median, or how the componentwise product $x\,\alpha$ would at all occur in considerations about linearity. Instead, the argument would work if one replaced the product by summation. – Juho Kokkala Aug 30 '16 at 7:10
• I do not understand what the construction $x\alpha$ has to do with the question. Is the question about something else than whether the median (as a mapping from a list of observations to the value of the median) is a linear function $\mathbb{R}^n \rightarrow \mathbb{R}$? – Juho Kokkala Aug 30 '16 at 7:17
• Um, no, that $a$ is a scalar. – Juho Kokkala Aug 30 '16 at 7:22
• The question links to this definition: en.wikipedia.org/wiki/… also OP didn't mention, nor comment that $\alpha$ is a scalar... EDIT: added notice about it in my answer. – Tim Aug 30 '16 at 7:24
• But the definition you linked to says that $\alpha$ is a scalar - -and without mentioning anything one would assume that "linear function" refers to the commonly used definition of linear function. Furthermore since $f$ maps to scalars, if $a$ was a vector, the LHS would be a scalar and the RHS a vector, so the equality would not even make sense. – Juho Kokkala Aug 30 '16 at 7:28