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

  • $\begingroup$ thanks a lot, nice answer, so is the $U$ component also diagonally dominant. $\endgroup$ – Orest Bucicovschi Jun 15 '18 at 12:50
  • $\begingroup$ @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). $\endgroup$ – Algebraic Pavel Jun 15 '18 at 18:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.