Condition number and $LU$ decomposition

Question

Consider $A: n \times n$ non-singular and the factors $L$ and $U$ of $A$ obtained with partial pivoting strategy, such as: $PA = LU$. Proof that $$\kappa_{\infty}(A) \geq \dfrac{||A||_{\infty}}{\min_{j}|u_{jj}|}.$$

The condition number $\kappa_{\infty}(A)$ is defined by $\kappa_{\infty}(A)=||A||_{\infty}||A^{-1}||_{\infty}$.

All I could show was that $\kappa_{\infty}(A) \geq \dfrac{||A||_{\infty}}{n ||U||_{\infty}}$.

But I can't get the "$n$" from the denominator.

This question seems to me to have some trick that I can´t get it. I discussed with some colleagues and we were thinking that this question is wrong. But still, we don´t know how to prove it.

Answer 1

Hint:

Let’s drop the permutation matrix (assume $A=LU$) and note that the partial pivoting implies that the absolute values of the elements under the unit diagonal of $L$ are bounded from above by $1$.

Now try using this: $$ |u_{ii}^{-1}|=|e_i^TU^{-1}e_i| =|e_i^TA^{-1}Le_i| \leq\|A^{-T}e_i\|_1\|Le_i\|_\infty \leq\|A^{-T}\|_1 =\|A^{-1}\|_\infty. $$

We used the facts that $|x^Ty|\leq\|x\|_1\|y\|_\infty$ for vectors and $\|X^T\|_1=\|X\|_\infty$ for matrices.

Answer 2

Partial answer:

What we're supposed to show is: $$ ||A^{-1}||_{\infty} \geq \frac 1 {\min_{j}|u_{jj}|} $$ We have further: $$ ||A^{-1}|| = ||(PA)^{-1}||= ||(LU)^{-1}|| = ||U^{-1}L^{-1}|| $$

Now, the diagonal of an inverted triangular matrix is simply the diagonal of the original triangular matrix with every element inverted.

Let further $i$ be chosen so that $\min_j U_{j,j} = U_{i,i} $, and let $(A)_{k,l}$ depict the entry of $A$ in the $k$-th row and $l$-th column.

Then we have: $$ ||U^{-1}L^{-1}||\ge |(U^{-1}L^{-1})_{i,i}| = \left|\sum_{k=1}^n (R^{-1})_{i,k}(L^{-1})_{k,i}\right| \\\\ =\left|(R^{-1})_{i,i}(L^{-1})_{i,i}+\sum_{k=1\\ k\neq i}^n (R^{-1})_{i,k}(L^{-1})_{k,i}\right| \\\\ =\left|\frac 1{\min_j U_{j,j}} + \sum_{k=1\\ k\neq i}^n (R^{-1})_{i,k}(L^{-1})_{k,i}\right| $$

So, to show the inequality, we now need to show $$ \sum_{k=1\\ k\neq i}^n (R^{-1})_{i,k}(L^{-1})_{k,i}\ge 0 $$