# Strictly column diagonally dominant matrices and Gaussian elimination with partial pivoting

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?

## 1 Answer

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