Suppose $A \in \mathbb{C}^{m \times m}$ is strictly column diagonally dominant, which means that for each $k$,

$$\left| a_{kk} \right| > \sum_{j \neq k} \left|a_{jk}\right|$$

Show that if Gaussian elimination with partial pivoting is applied to $A$, no row interchanges take place.

It's easy to show that on the first step no pivoting takes place because $\left|a_{11}\right| > \left|a_{j1}\right|$ for all $j > 1$ and thus the algorithm would choose the first row to be in the first position. If at every step the matrix the algorithm considers permuting is strictly column diagonally dominant then no pivoting will take place. The trick is then to show that the matrix the algorithm works on always remains strictly column diagonally dominant.

This question (and its answer) is almost what I want to do, but unfortunately it refers to row diagonal dominance, not column diagonal dominance. How then would I proceed? Can the argument from the other answer be used here?


It seems to me that the following computation proves the result.

Let ${{a'}}_{j , k}$ be the coefficients after the first step i.e. for $j > 1$

$${{a'}}_{j , k} = {a}_{j , k}-{a}_{j , 1} \frac{{a}_{1 , k}}{{a}_{1 , 1}}$$

Let us compute

$$\renewcommand{\arraystretch}{2} \begin{array}{rcl}\displaystyle \sum\limits _{\substack{j = 2\\j \neq k}}^{n} \left|{{a'}}_{j , k}\right|&=&\displaystyle \sum\limits _{\substack{j = 2\\j \neq k}}^{n} \left|{a}_{j , k}-{a}_{j , 1} \frac{{a}_{1 , k}}{{a}_{1 , 1}}\right|\\ & \leqslant &\displaystyle \sum\limits _{\substack{j = 2\\j \neq k}}^{n} \left|{a}_{j , k}\right|+\sum\limits _{\substack{j = 2\\j \neq k}}^{n} \left|{a}_{j , 1}\right| \frac{\left|{a}_{1 , k}\right|}{\left|{a}_{1 , 1}\right|}\\ & < &\displaystyle \left|{a}_{k , k}\right|-\left|{a}_{1 , k}\right|+\left|{a}_{1 , k}\right| \sum\limits _{\substack{j = 2\\j \neq k}}^{n} \frac{\left|{a}_{j , 1}\right|}{\left|{a}_{1 , 1}\right|}\\ & \leqslant &\displaystyle \left|{a}_{k , k}\right|-\left|{a}_{1 , k}\right|+\left|{a}_{1 , k}\right| \left(1-\frac{\left|{a}_{k , 1}\right|}{\left|{a}_{1 , 1}\right|}\right)\\ & \leqslant &\displaystyle \left|{a}_{k , k}\right|-\left|{a}_{1 , k}\right| \frac{\left|{a}_{k , 1}\right|}{\left|{a}_{1 , 1}\right|}\\ & \leqslant &\displaystyle \left|{a}_{k , k}-{a}_{1 , k} \frac{{a}_{k , 1}}{{a}_{1 , 1}}\right|\\ & \leqslant &\displaystyle \left|{{a'}}_{k , k}\right| \end{array}$$


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.