The absolute value is a particular instance of a norm. Or perhaps, you can think of norms as functions $\mathbf{V}\to\mathbb{R}$ where $\mathbf{V}$ is a vector space over a field $\mathbf{F}$, and "absolute values" are "norms on the base field".
The absolute value is a function $|\>|\colon\mathbb{R}\to[0,\infty)$; given any real number $r$, you get a nonnegative real number that we write $|r|$, and which satisfies the following properties:
- $|x|\geq 0$ for all $x\in\mathbb{R}$; $|x|=0$ if and only if $x=0$.
- $|rx| = |r||x|$ for all $r,x$.
- $|x+y| \leq |x|+|y|$.
It's a real valued function of real variable, because it takes a real number as an input, and gives a (nonnegative) real number as an output. It's just that instead of calling the function, say, $f$, and writing the output as $f(x)$, we call the function "$|\>|$" and write the output as $|x|$.
Similarly, we have the modulus function for complex numbers, $|\>|\colon\mathbb{C}\to[0,\infty)$, defined by $|z| = \sqrt{z\overline{z}}$, and which also satisfies the three conditions above.
If $\mathbf{V}$ is a vector space over $\mathbb{R}$, then a norm on $\mathbf{V}$ is a function $||\>||\colon \mathbf{V}\to[0,\infty)$ that generalizes the absolute value; it must satisfy:
- $||\mathbf{x}|| \geq 0$ for all $\mathbf{x}\in\mathbf{V}$; $||\mathbf{x}||=0$ if and only if $\mathbf{x}=\mathbf{0}$.
- $||r\mathbf{x}|| = |r|\,||\mathbf{x}||$ for all $r\in\mathbb{R}$, all $\mathbf{x}\in\mathbf{V}$.
- $||\mathbf{x}+\mathbf{y}|| \leq ||\mathbf{x}|| + ||\mathbf{y}||$ for all $\mathbf{x},\mathbf{y}\in\mathbf{V}$.
Again, this is a function: given any vector $\mathbf{x}$ in the domain, $||\mathbf{x}||$ is the output of the function (a nonnegative real number).
In particular, if you view $\mathbb{R}$ as a vector space over itself, then the absolute value gives a norm on $\mathbb{R}$.
For vector spaces over $\mathbb{C}$, you replace the absolute value of $r$ in the second property with the modulus of $r$.
The norm you describe in your post, $||\epsilon||=\max|\epsilon_i|$ is a particular norm that can be placed on $\mathbb{R}^n$; there are many norms that can be defined on $\mathbb{R}^n$.
The notion of norm on a vector space can be done with any field that is contained in $\mathbb{C}$, by restricting the modulus to that field.
Added. One can also extend the notion of norm by starting with any field $\mathbf{F}$, such as the rationals, simply asking for an "absolute value" function $|\>|\colon \mathbf{F}\to [0,\infty)$ that satisfies properties 1, 2, and 3 above. Then you extend the notion of norm for any vector space over that field. It is common to refer to such "absolute values" as "norms" so as not to confuse them with the usual absolute value. One classical example, mentioned by Asaf, are the $p$-adic norms on the rationals. First, fix a prime $p$; given an integer $p$, we define the $p$-order of $a$ to be the largest power of $p$ that divides $a$: that is, $\mathrm{ord}_p(a) = n$ if and only if $p^n$ divides $a$ and $p^{n+1}$ does not divide $a$. We formally set $\mathrm{ord}_p(0)=\infty$. We then extend this to the rationals: given a rational $\frac{a}{b}$, we let $\mathrm{o}_p(\frac{a}{b}) = \mathrm{ord}_p(a) - \mathrm{ord}_p(b)$. Finally, we define the $p$-adic norm on the rationals, $||\>||_p\colon\mathbb{Q}\to[0,\infty)$ by $||\frac{a}{b}||_p = p^{-o_p(a/b)}$. (You can use bases other than $p$; they amount to what are called "equivalent norms").
Here you really want to think of $||\>||_p$ as a kind of "non-standard absolute value" on the rationals; it leads to a lot of interesting mathematics, beginning with the $p$-adic numbers, if you use $||\>||_p$ to define "Cauchy-sequences" instead of $|\>|$ and do the same construction that leads to the reals in the latter case.
For any $k$-plane $U$ in $\mathbb{C}^n$, let $i_U$ be the inclusion of $U$ into $\mathbb{C}^n$ and let $p_U$ be the orthogonal projection of $\mathbb{C}^n$ onto $U$.
Lemma: Let the singular values of $A$ be $\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_n$. Then $\max_{U, V} \ \mathrm{Tr} \left( p_V \circ A \circ i_U \right)= \sigma_1+ \cdots +\sigma_k$, where the max is over all pairs of $k$-planes in $\mathbb{C}^n$.
Proof is left for the reader, using his or her favorite definition of singular values.
Then $\max_{U, V} \ \mathrm{Tr} \left(p_V \circ (A+B) \circ i_U\right) \leq \max_{U, V} \ \mathrm{Tr} \left( p_V \circ A \circ i_U \right) + \max_{U, V} \ \mathrm{Tr} \left( p_V \circ B \circ i_U \right)$.
Best Answer
If we adapt the proof of IV.2.1 from Bhatia's Matrix Analysis, it suffices to prove the following facts:
For vectors $x, y \in \Bbb R^n_+$: if $$ \sum_{j=1}^k x_k^\downarrow \leq \sum_{j=1}^k y_k^\downarrow, \quad k = 1,\dots,n $$ then $\|x\|_p \leq \|y\|_p$
For vectors $x, y \in \Bbb R^n_+$: if $x \leq y$ (entrywise), then $\|x\|_p \leq \|y\|_p$
The result regarding the Ky-Fan norms can be proven as follows: