# Natural matrix norm of an inverse matrix

Let $\left\|\cdot\right\| : \text{GL}(n,\mathbb{R})\to\mathbb{R}_{\ge 0}$ denote the natural matrix norm, i.e. $$\left\|A\right\|:=\max_{x\ne 0}\frac{\left\|Ax\right\|}{\left\|x\right\|}=\max_{\left\|x\right\|=1}\left\|Ax\right\|$$ is induced by a vector norm $\left\|\cdot\right\| : \mathbb{R}^n\to\mathbb{R}_{\ge 0}$. I want to show, that it holds $$\left\|A^{-1}\right\|=\left(\min_{\left\|x\right\|=1}\left\|Ax\right\|\right)^{-1}$$ Proof: $$\begin{split} \left\|A^{-1}\right\|&=\max_{\left\|x\right\|=1}\left\|A^{-1}x\right\|\\ &=\max_{\left\|Ay\right\|=1}\left\|y\right\|\\ &=\left(\min_{\left\|Ay\right\|=1}\left\|y\right\|^{-1}\right)^{-1}\\ &=\left(\min_{\left\|x\right\|=1}\left\|Ax\right\|\right)^{-1} \end{split}$$ How does the last step work?

• I'd use the full-space form of the operator norm for these computations, $\|A^{-1}\|=\sup_{x\ne 0}\frac{\|A^{-1}x\|}{\|x\|}=\sup_{y\ne 0}\frac{\|y\|}{\|Ay\|}$ etc. The steps remain the same, but in your form it is not quite obvious from first glance when why which factors appear and disappear, especially in the later steps. But in principle it looks correct. – Lutz Lehmann Feb 28 '14 at 21:07
• @LutzL - Hm, I still don't understand how the last step works. If I use the full-space form I get $$\begin{split} \left\|A^{-1}\right\|&=\max_{x\ne 0}\frac{\left\|A^{-1}x\right\|}{\left\|x\right\|}\\ &=\max_{Ay\ne 0}\frac{\left\|y\right\|}{\left\|Ay\right\|}\\ &=\left(\min_{Ay\ne 0}\frac{\left\|Ay\right\|}{\left\|y\right\|}\right)^{-1}\\ \end{split}$$ But again: How do I proceed from here? – 0xbadf00d Mar 1 '14 at 14:23
• $A$ is invertible, per setup of the problem, so you can reduce the condition to $y\ne 0$. Then restrict to $\|y\|=1$, since the fraction is independent of the scale of $y$. – Lutz Lehmann Mar 1 '14 at 14:28
• @LutzL - So, this leads us to $$\begin{split} &=\max_{\left\|y\right\|=1}\frac{1}{\left\|Ay\right\|}\\ &=\max_{\left\|A^{-1}x\right\|=1}\frac{1}{\left\|x\right\|} \end{split}$$ – 0xbadf00d Mar 1 '14 at 14:36
• I was thinking about \begin{align} =\left(\min_{Ay\ne 0}\frac{\|Ay\|}{\|y\|}\right)^{-1} =\left(\min_{y\ne 0}\frac{\|Ay\|}{\|y\|}\right)^{-1} =\left(\min_{\|y\|=1}\|Ay\|\right)^{-1} \end{align} – Lutz Lehmann Mar 1 '14 at 14:50

The last step in your proof can be finished as follows. The mapping $$y=\frac{x}{\|Ax\|}$$ from $$X=\{x:\|x\|=1\}$$ to $$Y=\{y:\|Ay\|=1\}$$ is bijective. Its inverse is $$x=\frac{y}{\|y\|}$$. Therefore \begin{aligned} \left(\min_{\|Ay\|=1}\|y\|^{-1}\right)^{-1} =\left(\min_{y\in Y}\frac{\|Ay\|}{\|y\|}\right)^{-1} =\left(\min_{x\in X}\frac{\left\|A\frac{x}{\|Ax\|}\right\|}{\left\|\frac{x}{\|Ax\|}\right\|}\right)^{-1} =\left(\min_{\left\|x\right\|=1}\left\|Ax\right\|\right)^{-1}. \end{aligned} However, as pointed out by another user in a comment under your question, it is much easier to prove the original identity in another way: \begin{aligned} \|A^{-1}\|&=\max_{y\ne0}\frac{\|A^{-1}y\|}{\|y\|} =\max_{x\ne0}\frac{\|x\|}{\|Ax\|} =\left(\min_{x\ne0}\frac{\|Ax\|}{\|x\|}\right)^{-1} =\left(\min_{\|x\|=1}\|Ax\|\right)^{-1}. \end{aligned}