Let $A$ be non singular, prove that $\frac{1}{\|A^{-1}\|} = \min_{\|x\| = 1} \|Ax\|$

Question

Let $A$ be non singular, prove that $\frac{1}{\|A^{-1}\|} = \min_{\|x\| = 1} \|Ax\|$

I know that $\|A\| = \sup_{\|x\| = 1} \|Ax\|$

but I have no idea how to proceed from here.

Answer 1

Maybe this will help to grasp the idea: $$ \begin{split} \|A^{-1}\| &= \max_{x\neq 0}\frac{\|A^{-1}x\|}{\|x\|} = \max_{y\neq 0}\frac{\|y\|}{\|Ay\|} = \left(\min_{y\neq 0}\frac{\|Ay\|}{\|y\|}\right)^{-1}. \end{split} $$

Answer 2

$\|A\|$ equals to the largest singular value of $A$. Since $A$ is nonsingular, all singular values are nonzero. Hence, the singular values of $A^{-1}$ are the inverses of the singular values of $A$. Therefore, $\|A^{-1}\|$ is the inverse of the smallest singular value of $A$.

Sine $\min_{\|x\|=1}\|Ax\|$ is the smallest singular value of $A$, the equality holds!

More precisely, assume that $\newcommand{\reals}{{\mathbf R}} A\in \reals^{n\times n}$. Suppose that $A=U\Sigma V^T$ is the singular value decomposition of $A$ with $U^TU = V^TV = I_n$, $\newcommand{\diag}{{\bf diag}}\diag(\sigma_1,\ldots,\sigma_n)$ and $\sigma_1\geq \sigma_2 \geq \cdots \geq \sigma_n$. Since $\sigma_i$ are singular values, $\sigma_i\geq0$. Since $\newcommand{\det}{{\bf det}}|\det A| = |\det(U)||\det(\Sigma)||\det(V)| = |\sigma_1 \cdots \sigma_n|$, nonsingularity of $A$ implies that $\sigma_i > 0$ for all $1\leq i\leq n$.

Now \begin{eqnarray} \|A\| &=& \sup_{\|x\|=1}\|Ax\| = \sup_{\|x\|=1}\sqrt{\|Ax\|^2} = \sup_{\|x\|=1}\sqrt{x^TA^TAx} = \sup_{\|x\|=1}\sqrt{x^TA^TAx} \\ &=& \sup_{\|x\|=1}\sqrt{x^TV\Sigma U^T U\Sigma V^Tx} \\ &=& \sup_{\|x\|=1}\sqrt{x^TV\Sigma^2V^Tx} \\ &=& \sup_{\|x\|=1} \|\Sigma V^Tx\| \\ &=& \sup_{y=V^Tx,\ \|x\|=1} \|\Sigma y\| \\ &=& \sup_{\|y\|=1} \|\Sigma y\| \\ &=& \sup_{\|y\|=1} \sqrt{\sigma_1^2 y_1^2 + \cdots + \sigma_n^2 y_n^2} \end{eqnarray} since $\|y\|^2 = y^T y = x^T V V^T x = x^T x = \|x\|^2$. Now \begin{equation} \sigma_1^2 y_1^2 + \cdots + \sigma_n^2 y_n^2 \leq \sigma_1^2 y_1^2 + \cdots + \sigma_1^2 y_n^2 = \sigma_1^2 \|y\|^2 = \sigma_1^2 \end{equation} with the equality achieved when $y_1=1$ and $y_2=\cdots=y_n = 0$. Therefore \begin{equation} \|A\| = \sigma_1, \end{equation} i.e., $\|A\|$ equals to the largest singular value of $A$. Therefore \begin{equation} \frac{1}{\|A^{-1}\|} = \frac{1}{1/\sigma_n} = \sigma_n, \end{equation} i.e., the smallest singular value.

Now the same derivation as before gives \begin{equation} \inf_{\|x\|=1} \|Ax\| = \inf_{\|y\|=1} \|\Sigma y\|. \end{equation} Since \begin{equation} \sigma_1^2 y_1^2 + \cdots + \sigma_n^2 y_n^2 \geq \sigma_1^2 y_n^2 + \cdots + \sigma_n^2 y_n^2 = \sigma_n^2 \|y\|^2 = \sigma_n^2 \end{equation} with the equality achieved with $y_1=\cdots=y_{n-1}=0$ and $y_n=1$, \begin{equation} \inf_{\|x\|=1} \|Ax\| = \sigma_n, \end{equation} hence the proof!

Answer 3

Let $v\in \mathbb{R}^n$ such that $\|v\|=1$. Then $$1=\|v\|=\|A^{-1}Av\|\leq \|A^{-1}\|\|Av\|$$ This means $\frac{1}{\|A^{-1}\|}$ is a lower bound of $\{\|Av\|:\|v\|=1\}$. Thus $\frac{1}{\|A^{-1}\|}\leq\inf_{\|x\|=1}\|Ax\|$. On the other hand, $$\begin{eqnarray} 1 &=& \|v\| \\ &=& \|Av\| \cdot \Bigg\|A^{-1}\Bigg(\frac{Av}{\|Av\|}\Bigg)\Bigg\| \\& \geq & \inf_{\|x\|=1}\|Ax\|\cdot \Bigg\|A^{-1}\Bigg(\frac{Av}{\|Av\|}\Bigg)\Bigg\|\end{eqnarray}$$ Since $u\mapsto \frac{Au}{\|Au\|}$ is a surjection on $S^{n-1}$ we see $\frac{1}{\inf_{\|x\|=1}\|Ax\|}$ is an upper bound of $\{\|A^{-1}v\|:\|v\|=1\}$. Thus $$\|A^{-1}\|\leq \frac{1}{\inf_{\|x\|=1}\|Ax\|} \iff \inf_{\|x\|=1}\|Ax\|\leq \frac{1}{\|A^{-1}\|}$$ The result follows.