Monotone matrix norms

Solution 1:

For part 2:

To simplify notation, define a function $g:\mathbb R^n\to\mathbb R$ by $g(x_1,\ldots,x_n)=\|\text{diag}(x_j)\|$. Since $\|\cdot\|$ is a unitarily invariant matrix norm, we have that

• $g$ is a norm on $\mathbb R^n$

• $g(x_1,\ldots,x_n)=g(|x_1|,\ldots,|x_n|)$ (this comes from the unitary invariance)

• $g(x_1,\ldots,x_n)=g(x_{\sigma(1)},\ldots,x_{\sigma(n)})$ for any permutation $\sigma$.

Such a $g$ is called a gauge function.

Now, if $t\in[0,1]$, then (writing $x=(x_1,\ldots,x_n)$) \begin{align} g(tx_1,x_2,\ldots,x_n)&=g\left(\frac{1+t}2\,x+\frac{1-t}2(-x_1,x_2,\ldots,x_n\right)\\ \ \\ &\leq\frac{1+t}2\,g(x)+\frac{1-t}2g(-x_1,x_2,\ldots,x_n)\\ \ \\ &=\frac{1+t}2g(x)+\frac{1-t}2g(x)=g(x). \end{align} Applying the above inductively, we get $$ g(t_1x_1,\ldots,t_nx_n)\leq g(x) $$ whenever $t_1,\ldots,t_n\in [0,1]$.

Since $0\leq\lambda_j(A)\leq\lambda_j(B)$ for all $j$, we have $\lambda_j(A)=t_j\lambda_j(B)$ for appropriate $t_1,\ldots,t_n\in[0,1]$. Then \begin{align} \|A\|&=\|\text{diag}(\lambda_j(A))\|=\|\text{diag}(t_j\,\lambda_j(B))\|\\ \ \\ &\leq \|\text{diag}(\lambda_j(B))\|=\|B\| \end{align}

For part 3, I know of the original proof by Marshall and Olkin (1973). Assume $\text{cond}(A)\leq\text{cond}(B)$. Let $A'=A/\|A\|$, $B'=B/\|B\|$, and $t=\frac{\|A\|}{\|A\|+\|B\|}$.

We have, in the new notation, that $$\tag{0}\|(A')^{-1}\|\leq\|(B')^{-1}\|.$$ And $$\tag{1} \|tA'+(1-t)B'\|\leq t\|A'\|+(1-t)\|B'\|=1. $$ Also, as the inverse is convex on the set of positive-definite matrices, $$\tag{2} (tA'+(1-t)B')^{-1}\leq t(A')^{-1}+(1-t)(B')^{-1}. $$ Thus, using $(2)$ and $(0)$, \begin{align}\tag{3} \|(tA'+(1-t)B')^{-1}\|&\leq\|t(A')^{-1}+(1-t)(B')^{-1}\|\\ &\leq t\|(A')^{-1}\|+(1-t)\|(B')^{-1}\|\\ &\leq\|(B')^{-1}\| \end{align} Now, combining $(1)$, and $(3)$, \begin{align}\tag{4} \|tA'+(1-t)B'\|\,\|(tA'+(1-t)B')^{-1}\|&\leq \|(tA'+(1-t)B')^{-1}\|\leq\|(B')^{-1}\|. \end{align} If we now use the definitions of $A'$ and $B'$, we get $$ tA'+(1-t)B'=\frac1{\|A\|+\|B\|}\,\left(A+B\right),\ \ \ \ (B')^{-1}=\|B\|\,B^{-1}. $$ We may thus rewrite $(4)$ as $$ \|A+B\|\,\|(A+B)^{-1}\|\leq \|B\|\,\|B^{-1}\|, $$ as desired.