# LU decomposition of a diagonally dominant matrix

Let $A \in M_{n\times n}(\mathbb{R})$ a matrix such that $a_{ij}< 0$ for $i \ne j$ and $A$ is diagonally (row) dominant, that is $a_{ii}>\sum_{j\ne i} |a_{ij}|$. I know that all the leading minors of $A$ are $>0$, and so $A$ has an LU decomposition $$A= L \cdot D \cdot U$$ where $L$ is lower triangular with $1$ on the diagonal, $D$ is a diagonal matrix with positive diagonal elements, $U$ is upper triangular with $1$ on the diagonal. I would like to get a confirmation whether the off-diagonal elements of $L$ and $U$ are negative.

After the first step of the elimination (introduce the ${\bf D}$ if you want), we have $${\bf A}:= \begin{bmatrix} a_{11} & {\bf a}_{12}^T \\ {\bf a}_{21} & {\bf A}_{22} \end{bmatrix} = \begin{bmatrix} 1 & 0^T \\ {\bf l}_{21} & {\bf I} \end{bmatrix} \underbrace{\begin{bmatrix} u_{11} & {\bf u}_{12}^T \\ 0 & \tilde{\bf A}_{22} \end{bmatrix}}_{\tilde{\bf A}}$$ where $$u_{11} = a_{11}>0, \quad {\bf u}_{12}={\bf a}_{12}<0, \quad {\bf l}_{21}=\frac{1}{a_{11}}{\bf a}_{21}<0, \quad \tilde{\bf A}_{22}={\bf A}_{22}-\frac{1}{a_{11}}{\bf a}_{21}{\bf a}_{12}^T.$$ The LU factorization continues by applying this step to the submatrix $\tilde{\bf A}_{22}$, which is again diagonally dominant with negative off-diagonal entries.
Using the row diagonal dominance of ${\bf A}$ and the inequality $|\alpha|\geq|\alpha-\beta|-|\beta|$ we show that $$\begin{split} \tilde{a}_{ii} &= a_{ii}-\frac{a_{i1}a_{1i}}{a_{11}} \\&> \sum_{j\neq i}|a_{ij}|-\frac{a_{i1}a_{1i}}{a_{11}} \\&= |a_{i1}|+\sum_{j\geq 2\\j\neq i}|a_{ij}|-\frac{a_{i1}a_{1i}}{a_{11}} \\&= |a_{i1}|+\sum_{j\geq 2\\j\neq i}\left|a_{ij}-\frac{a_{i1}a_{1j}}{a_{11}}\right|-\frac{|a_{i1}|}{a_{11}}\sum_{j\neq i}|a_{1j}| \\&= \sum_{j\geq 2\\j\neq i}|\tilde{a}_{ij}| +|a_{i1}|\left(1-\frac{1}{a_{11}}\sum_{j\neq i}|a_{1j}|\right) \\&> \sum_{j\geq 2\\j\neq i}|\tilde{a}_{ij}|, \quad i\geq 2, \end{split}$$ so $\tilde{\bf A}_{22}$ is also row diagonally dominant. It is easy to see that $\tilde{\bf A}_{22}$ has negative off-diagonal elements because $\frac{1}{a_{11}}{\bf a}_{21}{\bf a}_{12}^T>0$.
• thanks a lot, nice answer, so is the $U$ component also diagonally dominant. – Orest Bucicovschi Jun 15 '18 at 12:50
• @orangeskid Indeed. Since the rows of $U$ are constructed from rows of the intermediate row diagonally dominant matrices, the $U$ itself is row diagonally dominant (even in the case of a unit triangular matrix $U$ in the LDU factorization). – Algebraic Pavel Jun 15 '18 at 18:55