Conditioning of Triangular Matrices:

Let $U \in \mathbb{R}^{N\times N}$ be upper triangular. $U$ is well conditioned if the magnitude of the diagonal elements is sufficiently large compared to that of the corresponding off-diagonal elements.

I'm trying to show that if $|u_{ii}| -2\,\displaystyle\sum_{j\neq i}{|u_{ij}|}>0$, for all $1\leq i\leq N,$ then $\kappa_{\infty}(U)\leq 2\>\dfrac{\|U\|_{\infty}}{\min_{1\leq j\leq N}{|u_{jj}|}}.$

I am struggling to show $\|U^{-1}\|_{\infty} \le \dfrac{2}{\min_{1\leq j\leq N}{|u_{jj}|}}$.

Does anyone have any ideas?

• Can you remind us, what is this $\kappa_{\infty}$? Mar 15, 2015 at 22:11
• $\kappa_{\infty}(U)$ is the condition number of $U$ with respect to inversion. So $\kappa_{\infty}(U) = \|U^{-1}\|_{\infty}\|U\|_{\infty}$
– Drew
Mar 15, 2015 at 22:13

1 Answer

The proof is essentially same as here. The matrix does not need to be triangular; only a row-wise diagonal dominance is needed.

Assume $U$ is a square invertible matrix such that $$\tag{1} |u_{ii}|-\alpha\sum_{j\neq i}|u_{ij}|\geq 0, \quad i=1,\ldots,N,$$ for some $\alpha>1$. Let $x$ be an $N$-vector and $i$ be the index such that $\|x\|_\infty=|x_i|$. Then \begin{align} \|Ux\|_\infty\geq|(Ux)_i|&\geq|u_{ii}||x_i|-\sum_{j\neq i}|u_{ij}||x_j| &&\text{(triangle inequality)} \\ &\geq|u_{ii}||x_i|-\sum_{j\neq i}|u_{ij}||x_i| && \text{(since |x_j|\leq|x_i|=\|x\|_\infty)}\\ &\geq\left(1-\frac{1}{\alpha}\right)|u_{ii}||x_i|&&\text{(using (1))} \\&\geq\left(1-\frac{1}{\alpha}\right)\min_i|u_{ii}|\|x\|_\infty&&\text{(making bound independent of i).} \end{align} Hence $$\frac{\|Ux\|_\infty}{\|x\|_\infty}\geq \frac{\alpha-1}{\alpha}\min_i|u_{ii}|.$$ We have then $$\tag{2} \|U^{-1}\|_\infty=\max_{x\neq 0}\frac{\|U^{-1}x\|_\infty}{\|x\|_\infty}=\max_{x\neq 0}\frac{\|x\|_\infty}{\|Ux\|_\infty}\leq\frac{\alpha}{\alpha-1}\frac{1}{\min\limits_i|u_{ii}|}.$$ This already gives the bound you seek with $\alpha=2$.

Note that (1) also implies a bound on $\|U\|_\infty$ in terms of the diagonal entries $u_{ii}$ and hence a more neat bound on $\kappa_{\infty}$ :-). We have $$|u_{ii}|+\sum_{j\neq i}|u_{ij}|\leq\left(1+\frac{1}{\alpha}\right)|u_{ii}|, \quad i=1,\ldots,N \quad\Rightarrow\quad \|U\|_{\infty}\leq\frac{\alpha+1}{\alpha}\max_i|u_{ii}|,$$ so with (2), we get $$\kappa_\infty(U)\leq\frac{\alpha+1}{\alpha-1}\frac{\max\limits_i|u_{ii}|}{\min\limits_i|u_{ii}|}.$$