# Connection between irreducibly diagonally dominant matrices and positive definiteness?

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.