We call a norm $\|\cdot\|$ on $\mathbb{R}^n$ absolutely monotonic if $$ |a_i| \leq |b_i|, i=1,\cdots,n \implies \|a\| \leq \|b\|. $$
What's an example of norm on $\mathbb{R}^2$ that's not absolutely monotonic?
This is an exercise left to the reader -- so presumably not too difficult. But it's giving me some trouble.
The usual suspects that come to mind, i.e. the $\ell^p$ norms, $p \in [1,\infty]$, are all absolutely monotonic.
On
I would like to give an answer similar to Smiley-Craft but from a different point of view:
The standard norm on $\mathbb{R}^2$ is given by $\|(a,b)\|= \sqrt {a^2+b^2}$. We can define a similar norm using a different basis.
Given $u,v$ a basis of $\mathbb{R}^2$. We can define the norm of $w$ by $$\|w\| = \sqrt{a^2+b^2}$$ where $w=au+bv$.
It is an easy exercise to show that this is indeed a norm (same proof as in the standard norm case).
Since we can change coordinates it will be really easy to define a non-monotonic norm:
For instance choose $u=(\frac{1}{2},0)$ and $v=(1,1)$ then $\|(1,0)\| = 2$ while $\|(1,1)\| = 1$.
Side note: It is an interesting question whether every norm is absolutely monotonic with respect to some basis. I would guess the answer is yes but I don't know how to approach this question yet.
On
Here's a way to come up with an answer using as little geometric intuition as possible.
The standard norm on $\mathbb{R}^2$ can be written as:
$$ \left\Vert \begin{pmatrix} a \\ b \end{pmatrix} \right\Vert^{\;2} \mapsto \begin{pmatrix}a \\ b\end{pmatrix}^T \begin{bmatrix} 1 & 0 \\ 0 & 1\end{bmatrix} \begin{pmatrix} a\\ b \end{pmatrix} \tag{1} $$
or
$$ \left\Vert \begin{pmatrix} a \\ b \end{pmatrix} \right\Vert^{\;2} \mapsto a^2 + b^2 \tag{2} $$
Which makes it immediately clear that, for arbitrarily chosen $(a_1, b_1)$ and $(a_2, b_2)$ .
$$ \frac{a_1^2 \le a_2^2 \;\;\;\;\text{and}\;\;\;\; b_1^2 \le b_2^2}{a_1^2 + b_1^2 \le a_2^2 + b_2^2} \tag{3} $$
If we stare at (1) and (2), it suggests that by adding a cross term we can "penalize" negative components, so let's pick a simple one, let's call the new norm $\nu$.
$$ \left\Vert \begin{pmatrix} a \\ b \end{pmatrix} \right\Vert^{\;2}_{\,\nu} \mapsto \begin{pmatrix}a \\ b\end{pmatrix}^T \begin{bmatrix} 1 & 1 \\ 0 & 1\end{bmatrix} \begin{pmatrix} a\\ b \end{pmatrix} \tag{4} $$
$$ \left\Vert \begin{pmatrix} a \\ b \end{pmatrix} \right\Vert^{\;2}_{\,\nu} \mapsto a^2 + ab + b^2 \tag{5} $$
Let's pick $(a_1, b_1) = (2, 2)$ and $(a_2, b_2) = (-3, 3)$ .
$$ \left\Vert \begin{pmatrix} 2 \\ 2 \end{pmatrix} \right\Vert^{\;2}_{\,\nu} = 4 + 4 + 4 = 12 \tag{6} $$
$$ \left\Vert \begin{pmatrix} -3 \\ 3 \end{pmatrix} \right\Vert^{\;2}_{\,\nu} = 9 - 9 + 9 = 9 \tag{7} $$
So, $(2, 2)$ and $(-3, 3)$ indeed demonstrates that $\nu$ is not absolutely monotonic.
All that's left is to verify that it's an actual norm.
The norm axioms are:
$$ \nu\,(\alpha v) = |\alpha| \,\nu\,(v) \tag{8} $$ $$ \nu\,(u+v) \le \nu\,(u) + \nu\,(v) \tag{9} $$ $$ \nu\,(v) = 0 \implies v = \vec{0} \tag{10} $$
(8) falls out of the fact that matrix multiplication is linear. (10) falls out of the invertibility of $\left[\begin{smallmatrix}1& 1\\0& 1\end{smallmatrix}\right]$
I think the most straightforward way to prove (9) is to note that the matrix $\left[\begin{smallmatrix}1& 1\\0& 1\end{smallmatrix}\right]$ is upper triangular and hence its eigenvalues with multiplicity are the multiset $\{1, 1\}$ . Since all of its eigenvalues are positive, the matrix is positive definite and therefore the quadratic form $\nu\,(u) = u^T \left[\begin{smallmatrix}1 & 1 \\0 & 1\end{smallmatrix}\right] u$ is a norm.
Consider a sheer $A(x,y):=(x,y-x)$ and then the norm $\|(x,y)\|:=\|A(x,y)\|_1$. Then $\|(1,0)\|=2$ but $\|(1,1)\|=1$.
EDIT: This post used to have a proof that every norm on $\mathbb{R}^2$ is absolutely monotonic after some basis transformation, but this is actually false. The proof only guarantees local absolute monotonicity, meaning any vector has a neighborhood where absolute monotonicity holds with respect to that vector, but due to an oversight, global absolute monotonicity fails.
The main oversight is that the coordinates can change sign. In fact, if $|a_i|=|b_i|$ for $i=1,\ldots,n$ then we need $\|a\|=\|b\|$. This implies quite a lot of symmetry, which I did not realize.
Let us refer to a basis $\{b_1,\ldots,b_n\}$ as extremal if they all have norm $1$ and the unit sphere is contained in $[-1,1]b_1+\ldots+[-1,1]b_n$. The old proof relied on this being equivalent to the linear basis transform $e_i\mapsto b_i$ resulting in an absolutely monotonic norm, however this is not the case.
If the unit sphere of a norm is sufficiently asymmetrical then no basis transformation can make the norm absolutely monotonic. Consider a norm with the following asymmetrical hexagonal unit sphere.
Only the bases $\{\pm A,\pm B\}$ and $\{\pm A',\pm B'\}$ are extremal, however neither result in absolute monotonicity.
What is true is that extremality is necessary for local absolute monotonicity. It is sufficient for local absolute monotonicity in at most two dimensions and it is sufficient for global absolute monotonicity in at most one dimension. The old proof thus still suffices for local absolute monotonicity.
To end off this note, here is a much simpler and less heuristic argument that every norm admits an extremal basis which generalizes to any finite number of real dimensions.
The space of all sets of $n$ vectors with norm $1$ is compact. The determinant thus admits its maximum for some set $\{b_1,\ldots,b_n\}$. The claim is that is an extremal basis. Note that the determinant can be positive due to non-degeneracy, so this is indeed a basis.
Assume without loss of generality some vector $x=\lambda_1b_1+\ldots+\lambda_nb_n$ has $\lambda_i>1$ for some $i$. Then replacing $b_i$ with $x$ results in a higher determinant, so such $x$ cannot exist.
OLD (WRONG) PROOF:
Interestingly though, for every norm $\|\cdot\|:\mathbb{R}^2\to[0,\infty)$ there exists a linear map $A:\mathbb{R}^2\to\mathbb{R}^2$ such that $\|\cdot\|\circ A$ is an absolutely monotonic norm.
To prove this, note that a norm is absolutely monotonic if (and only if, may I add) the smallest axis-aligned rectangle containing the unit disk touches the unit circle at the intersections with the $x$- and $y$-axis. This is a consequence of the triangle inequality. So if we find vectors $v$ and $u$ on the unit sphere such that the unit disk is contained in the parallellogram $[-1,1]v\times[-1,1]u$, then the unique linear map that sends $v$ to $(1,0)$ and $u$ to $(0,1)$ suffices.
In order to find such $v$ and $u$, we will use the intermediate value theorem. For any angle $\theta$ let $v(\theta)$ be the unique vector on the unit sphere with angle $\theta$ with respect to the origin. The uniqueness follows from the scaling property and the non-degeneracy of norms, and the continuity follows from the triangle inequality. Then let $u(\theta)$ be the vector on the unit sphere furthest to the left of the line generated by $v(\theta)$. A little bit of a problem here is that $u(\theta)$ is not always uniquely defined, and $\theta\mapsto u(\theta)$ is only continuous at points where it is uniquely defined. However, for now just pretend that it is a well-defined continuous function, and I will come back to this later.
We now find that $\mathbb{R}v\times[-1,1]u$ contains the unit disk. Most importantly the intersection of the unit disk with $(1,\infty)v\times[-1,1]u$ is fully contained in either $(1,\infty)v\times[-1,0]u$ or $(1,\infty)v\times[0,1]u$, due to the triangle inequality. If for some $\theta$ this intersection lies in one of the two, then if we move $\theta$ such that the new $v(\theta)$ is where the old $u(\theta)$ was, the intersection will lie in the other one. For some $\theta$ in between, we must therefore have that the intersection lies in neither. Therefore the unit disk will be contained in $[-1,1]v\times[-1,1]u$.
Finally, to come back to the little problem. For such problematic $\theta$ you can imagine fixing $v(\theta)$ while moving $u(\theta)$ continuously along the set of all possible values.
This is a little bit heuristic, but I hope it is convincing anyways.