I was asked to prove the following statement:
let $A$ be an $n$ by $n$ matrix with real entries such that $\forall k \in \mathbb N, k\leq n$: $$\sum_{i \neq k} |A_{i,k}| < |A_{kk}|$$
Show that if we were to do gauss elimination (or LU factorization) of $A$, then there will be no need for row changes, no need for partial pivoting.
I don't see why this is true, I'd appreciate a hint in the right direction. Maybe I should take a general $n$ by $n$ matrix that is diagonly dominant, try to $LU$ factor it and see that I don't need row changes? is this the way?
Best Answer
We only need to show that after eliminating $a_{2,1}$, diagonal dominance is preserved, i.e., $$ \left|a_{2,2}-a_{1,2}{a_{2,1}\over a_{1,1}}\right|>\sum_{i=3}^n\left|a_{2,i}-a_{1,i}{a_{2,1}\over a_{1,1}}\right|, $$ which is equivalent to $$ |a_{2,2}a_{1,1}-a_{1,2}a_{2,1}|>\sum_{i=3}^n|a_{2,i}a_{1,1}-a_{1,i}a_{2,1}|. $$ But this is true: \begin{eqnarray*} \sum_{i=3}^n|a_{2,i}a_{1,1}-a_{1,i}a_{2,1}|&\le& |a_{1,1}|\sum_{i=3}^n|a_{2,i}|+|a_{2,1}|\sum_{i=3}^n|a_{1,i}| \\ &<& |a_{1,1}|(|a_{2,2}|-|a_{2,1}|)+|a_{2,1}|(|a_{1,1}|-|a_{1,2}|) \\ &=&|a_{1,1}||a_{2,2}|-|a_{2,1}||a_{1,2}|\\ &\le& |a_{1,1}a_{2,2}-a_{2,1}a_{1,2}| \end{eqnarray*}