I am attempting to prove a proposition that I found in Cottle's "The Linear Complementarity Problem" book in which the proof has been omitted.

I will start by introducing some definitions.

${\bf Def.}$ A matrix $A\in\mathbb{R}^{n\times n}$ is said to be irreducible if and only if for any two distinct indices $1\le i,j\le n$, there is a sequence of nonzero elements of $A$ of the form $$ \{a_{ii_1},a_{i_1i_2},\ldots,a_{i_mj}\}. $$

${\bf Def.}$ A matrix $A\in\mathbb{R}^{n\times n}$ is irreducibly diagonally dominant if it is irreducible, weakly diagonally dominant, $|A_{ii}| \ge \sum_{j\neq i}|A_{ij}|$ for all $i$, and there is at least one row or column where strict diagonal dominance holds, that is $\exists$ $i$ such that $|A_{ii}| > \sum_{j\neq i}|A_{ij}|$.

The statement is as follows.

${\bf Prop.}$ Let $A\in\mathbb{R}^{n\times n}$ be symmetric, strictly or irreducibly diagonally dominant, and $A_{ii}>0$ for all $i$, then $A$ is positive definite.

${\bf Pf.}$ (attempt, sketch) My attempt used the Gershgorin Circle Theorem which allowed me to show that the eigenvalues of the matrix were all nonnegative, with one strictly positive. However, I do not know how to use irreducibility or the fact that $A$ has strictly positive diagonal entries to conclude that it is positive definite.


In your mentioned proposition, since $A$ is real symmetric and diagonally dominant and it has a positive diagonal, it is positive semidefinite (Gershgorin discs in play here). The role of irreducibility (coupled with diagonal dominance) is to ensure that $A$ is nonsingular. Every nonsingular positive semidefinite matrix is, of course, positive definite.

To prove that $A$ is nonsingular, suppose $Ax=0$. Since $A$ is irreducible, it has no zero rows. Therefore the diagonal entries of $A$ are nonzero, because $A$ is diagonally dominant. (This fact, of course, also follows from the given assumption that $A$ has a positive diagonal, but here we wish to infer the invertibility of $A$ using only irreducibility and diagonal dominance. So, we deduce the nonzeroness of the diagonal of $A$ from these two assumptions too.)

Now, suppose $x_i$ has the largest modulus among all entries of $x$. By assumption, strict diagonal dominance of $A$ occurs on some row $j$ and there is a path $i_0=i\to i_1\to \ldots\to i_k=j$ such that $a_{i_mi_{m+1}}$ is nonzero for each $m$. Since $|x_{i_0}|$ has a maximum modulus, by (weak) diagonal dominance of row $i_0=i$, for every $\ell$ such that $a_{i_0\ell}\ne0$, we must have $|x_\ell|=|x_{i0}|$. In particular, $|x_{i1}|=|x_{i0}|$. Apply the same argument recursively, we get $|x_j|=|x_{i_k}|=|x_{i_{k-1}}|=\cdots=|x_{i_0}|=|x_i|$. Therefore $x_j$ also has a maximum modulus. But then the strict diagonal dominance of $A$ on row $j$ implies that the $j$-th entry of $Ax$ is nonzero, which is a contradiction. Therefore $A$ must be nonsingular.


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.