Strictly Diagonally Dominant Matrices Suppose $A ∈ C^{n×n}$ is strictly diagonally dominant. Prove that Gaussian elimination (without pivoting) proceeds to completion to produce a non-singular upper triangular matrix U, without ever encountering any zero pivot entries.
Ran across this in a friends notes studying for one of three my master's exams. It's been star'd but not completed so I was wondering if anyone had any clue as to how to go about it...
 A: There are two important facts which we need to note:


*

*If a matrix $A \in M_n(\mathbb{C})$ is strictly diagonally dominant, then we could use Gaussian elimination to clear the first column of $A$, i.e.
\begin{align}
\begin{pmatrix}
a_{11} & a_{12} & \ldots & a_{1n}\\
a_{21} & a_{22} & \ldots & \vdots\\
\vdots & \ldots & \ddots & \vdots\\
a_{n1} & \ldots & \ldots & a_{nn}
\end{pmatrix}
\xrightarrow[\text{Gaussian Elimination}]{}
\begin{pmatrix}
a_{11} & a_{12} & \ldots & a_{1n}\\
0 & & & \\
\vdots & & \tilde A & \\
0 & & &
\end{pmatrix}
\end{align}
where $\tilde A \in M_{n-1}(\mathbb{C})$. 

*Moreover, $\tilde A$ is also strictly diagonally dominant. 


Fact 1 is trivial because $A$ being strictly diagonally dominant means $a_{11} \neq 0$. Hence let us focus on proving Fact 2. 
Observe the $ij$-entries of $\tilde A$ is given by the formula
\begin{align}
(\tilde A)_{ij} = a_{(i+1)(j+1)}- \frac{a_{(i+1)1} a_{1(j+1)}}{a_{11}}.
\end{align}
In particular, we have
\begin{align}
|(\tilde A)_{ii}| =&\ \left|a_{(i+1)(i+1)} - \frac{a_{(i+1)1}a_{1(i+1)}}{a_{11}} \right|= \frac{1}{|a_{11}|}\left|a_{(i+1)(i+1)}a_{11} - a_{(i+1)1}a_{1(i+1)} \right|\\
\geq&\ \frac{1}{|a_{11}|}(|a_{11}||a_{(i+1)(i+1)}| - |a_{(i+1)1}||a_{1(i+1)}|)\\
=&\ \frac{1}{|a_{11}|}\left\{|a_{11}|(|a_{(i+1)(i+1)}|-|a_{(i+1)1}|)+|a_{(i+1)1}|(|a_{11}|-|a_{1(i+1)}|) \right\}\\
>&\ \frac{1}{|a_{11}|}\left\{|a_{11}|\sum_{\substack{j=1 \\  j \neq i }}^{n-1}|a_{(i+1)(j+1)}|+|a_{(i+1)1}|\sum_{\substack{j=1 \\ j \neq i }}^{n-1}|a_{1(j+1)}| \right\}\\
\geq&\ \frac{1}{|a_{11}|}\left\{\sum_{\substack{j=1 \\ j \neq i }}^{n-1}|a_{11}a_{(i+1)(j+1)}-a_{(i+1)1}a_{1(j+1)}| \right\} = \sum_{\substack{j=1\\ j\neq i}}|(\tilde A)_{ij}|
\end{align}
which means $\tilde A$ is still strictly diagonally dominant. 
Recursively, we could show $A$ can be reduced to an upper triangular matrix without pivoting. 
