1
$\begingroup$

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! :)

$\endgroup$
1
$\begingroup$

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}|)$.

$\endgroup$
  • $\begingroup$ Thank you very much! It really is simple, I don't know why it bothered me so much... $\endgroup$ – Iordan Iordanov Oct 5 '14 at 16:32
  • $\begingroup$ $b_{i,i} = 1/a_{i,i}$? Why? $\endgroup$ – Rockafellar Dec 28 '18 at 9:19
  • 1
    $\begingroup$ @Zhu , because $A$ is triangular. $\endgroup$ – loup blanc Dec 28 '18 at 9:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.