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! 🙂
Best Answer
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}|)$.