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.
[Math] LU decomposition of a diagonally dominant matrix
linear algebramatrices
Best Answer
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|\tag{*}$$ we show that, for all $i \geq 2, $ $$ \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}} \\&\overset{(*)}{\geq} |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}|, \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$.