Diagonal dominance preserved by row elimination I'm trying complete a proof I've seen in a class, which says that diagonally dominant matrices have an LU decomposition. For this, given a diagonally dominant matrix $A \in \mathbb{R}^{n \times n}$  we know that if sequence $A^{(0)}, \ \dots \ , \   A^{(n-1)} $ defined as 
$$
A^{(0)} = A \\ 
a_{ij}^{(k)} = a_{ij}^{(k-1)} -  \frac{a_{ik}^{(k-1)} \cdot a_{kj}^{(k-1)}}{a_{kk}^{(k-1)}} 
$$
which consists of each step of gaussian elimination without pivoting is well defined, (i.e $\ a_{kk}^{(k-1)} \neq 0 $ for each $k$), then there is a LU decomposition. Therefore, it is sufficient to show the stronger statement: 

If $A^{(k)}$ is diagonally dominant, $A^{(k+1)}$ is as well.

Now, here is where I've lost track of my notes. I know this has to be true but I've failed to succeed in proving it. We want to show that
$$
\sum_{j \neq i}|a_{ij}^{(k)}| < |a_{ii}^{(k)}|
$$
which is equivalent to
$$
\sum_{j \neq i}|a_{ij}^{(k-1)} -  \frac{a_{ik}^{(k-1)} \cdot a_{kj}^{(k-1)}}{a_{kk}^{(k-1)}}| < |a_{ii}^{(k-1)} -  \frac{a_{ik}^{(k-1)} \cdot a_{ki}^{(k-1)}}{a_{kk}^{(k-1)}}|
$$
Any thoughts? 
 A: The basic idea of the proof is as follows. Assume you are eliminating the
entry $a_{ik}^{k-1}$ in the $k$th step of Gaussian elimination. Hence,
$a_{ik}^k = 0$ at the end of the computation. To show that the matrix is still
diagonally dominant after the elimination, we show that the total amount that we add
to the $i$th row is less than the eliminated entry.
We start with the diagonal dominance of the $k$th row, i.e.,
$$ \sum_{j \not= k} | a_{kj}^{k-1} | < | a_{kk}^{k-1} | \,. $$
Multiplying by $\frac{| a_{ik}^{k-1} |}{| a_{kk}^{k-1} |}$ gives that
$$  \tag{a} 
    \sum_{j \not= k} 
    \frac{| a_{ik}^{k-1} | \cdot | a_{kj}^{k-1} |}
         {| a_{kk}^{k-1} |} < | a_{ik}^{k-1} | \,. $$
Hence, indeed, what we add to the $i$th row is less than the entry that we
eliminate.
With this knowledge we can start the computation.
We have, because $a_{ik}^{k} = 0$, that
\begin{align}
    \sum_{j \not= i} | a_{ij}^{k} | 
&= 
    \sum_{\substack{j \not= i \\ j \not= k}} | a_{ij}^{k} | 
    \,.
\end{align}
Using the definition of the elimination step and then the triangle
inequality gives that
\begin{align}
    \sum_{j \not= i} | a_{ij}^{k} | 
&= 
    \sum_{\substack{j \not= i \\ j \not=k}} 
      | a_{ij}^{k-1} - 
      \frac{a_{ik}^{k-1} \cdot a_{kj}^{k-1}}{a_{kk}^{k-1}} | \\
&\le
    \sum_{\substack{j \not= i \\ j \not=k}}
      | a_{ij}^{k-1} | +
    \sum_{\substack{j \not= i \\ j \not=k}} 
      | \frac{a_{ik}^{k-1} \cdot a_{kj}^{k-1}}{a_{kk}^{k-1}} |
      \,.
\end{align}
From equation (a) and the fact that we leave out the $i$th term it follows
that
\begin{align}
    \sum_{j \not= i} | a_{ij}^{k} |
&\le 
    \sum_{\substack{j \not= i \\ j \not=k}} | a_{ij}^{k-1} | +
    | a_{ik}^{k-1} | -
    | \frac{a_{ik}^{k-1} \cdot a_{ki}^{k-1}}{a_{kk}^{k-1}} |
\\ &= 
    \sum_{j \not= i} | a_{ij}^{k-1} | -
    | \frac{a_{ik}^{k-1} \cdot a_{ki}^{k-1}}{a_{kk}^{k-1}} |
    \,.
\end{align}
Using that the $i$th row was diagonally dominant before the elimination and
then applying the reversed triangle inequality,
\begin{align}
    \sum_{j \not= i} | a_{ij}^{k} |
& \le
    | a_{ii}^{k-1} | -
    | \frac{a_{ik}^{k-1} \cdot a_{ki}^{k-1}}{a_{kk}^{k-1}} |
\\ &\le
    | a_{ii}^{k-1} | -
    | \frac{a_{ik}^{k-1} \cdot a_{ki}^{k-1}}{a_{kk}^{k-1}} |
\\ &=
    | a_{ii}^{k} |
    \,.
\end{align}
This inequality completes the proof.
