# Condition number - proof

I have a problem with which I've been struggling for a while. It's probably not that difficult, but I seem to be stuck so... here we are.

Let A be an invertible lower- or upper-triangular matrix (which means that $a_{ii} \neq 0$). Show that $k_\infty (A) \geq \left\| A \right\|_\infty \frac{1}{\min_i \left|{a_{ii}}\right|}$.

What I am given is the inequality by Kahan, saying that $$\frac{1}{k(A)} = \inf \left\{ \frac{\left\|A - B\right\|}{\left\|A\right\|}, \quad \text{where B is non invertible}\right\}$$

What I've been able to come up with boils down to the following. Let A be lower-triangular, without loss of generality. As we know, the condition number is given by $k(A) = \left\|A\right\| \left\|A^{-1}\right\|$, hence: $$\frac{1}{k(A)} = \frac{1}{\left\|A\right\| \left\|A^{-1}\right\|} \leq \frac{\left\|A - B\right\|}{\left\|A\right\|} \Leftrightarrow \frac{1}{\left\|A^{-1}\right\|} \leq \left\|A - B\right\|$$ where B is non invertible.

Returning to the question, we can easily see that we ask to prove $$k(A) = \left\|A\right\| \left\|A^{-1}\right\| \geq \left\| A \right\| \frac{1}{\min_i \left|{a_{ii}}\right|} \Leftrightarrow \left\|A^{-1}\right\| \geq \frac{1}{\min_i \left|{a_{ii}}\right|} \Leftrightarrow \frac{1}{\left\|A^{-1}\right\|} \leq \min_i \left|{a_{ii}}\right|$$

So, if I am able to prove that $\left\|A - B \right| \leq \min_i \left| a_{ij} \right|$, I will effectively have proven the requested inequality.

As next steps, I've tried analysing the norm: in my case, the max-norm is requested, and it holds that $$\left\| A \right\|_\infty = \max_i \sum_{j=1}^{n} \left|a_{ij}\right| = \max_i \sum_{j=1}^{i} \left|a_{ij}\right| = \max_i \left(\sum_{j=1}^{i-1} \left|a_{ij}\right| + \left| a_{ii} \right| \right)$$

because the matrix is lower-triangular as we supposed.

What I'm thinking about is chosing a specific non-invertible matrix B which would suit my needs, such as, for instance: $$Β = \begin{cases} 0, \quad i \leq j \\ a_{ij}, \quad i > j \end{cases}$$

In this way, the max-norm of $A-B$ would pretty much boil down to the max element $\left|a_{ij}\right|$ but I need the min, not the max.

Any idea or hint will be greatly appreciated, and thank you in advance! :)

It is easy. For any matrix $||B||_{\infty}=\max_i\sum_j|b_{i,j}|\geq \max_i|b_{i,i}|$. Here $B=A^{-1}$ and $b_{i,i}=1/a_{i,i}$; then $||A^{-1}||_{\infty}\geq 1/\min(|a_{i,i}|)$.
• $b_{i,i} = 1/a_{i,i}$? Why? – Rockafellar Dec 28 '18 at 9:19
• @Zhu , because $A$ is triangular. – loup blanc Dec 28 '18 at 9:40