6
$\begingroup$

Let $A$ be a non-negative zero-diagonal invertible matrix. Which $A$ make the following assertions true, which are all equivalent:

  1. The all-one vector $j$ is contained in the conic hull of $col(A)$.
  2. The row sums of $A^{-1}$ are non-negative.
  3. $ADj > 0$, where $D$ is any diagonal matrix with trace $1$.
  4. The affine hull of $col(-A)$ does not intersect the non-negative orthant.

The equivalency of $(1)$ and $(2)$ follows from the equation $$Ax = j.$$ Assertion $(3)$ is deduced from Farkas' Lemma, as the existence of a positive solution to the above equation implies that there cannot exist a vector $y$ with $y'j = -1$ such that $Ay \geq 0$ (I normalized $y$ without loss of generality). The set of $y$ with sum-of-entries $-1$ is given by $\{y\;|\;y=-Dj: tr(D)=1 \;\text{and}\; D \; \text{diagonal}\}$, the affine combinations of the negative standard basis vectors. This leads to $-ADj <0$.

Finally, the matrix of images of the negative standard basis under $A$ is simply $-A$. Hence, requiring the affine hull of these images not to contain any non-negative vector should be equivalent to $(3)$.

Two sufficient conditions are that $A$ be positive monomial with zero diagonal (as at least one of the entries of $y$ must be negative), or the adjacency matrix of a regular graph. What can be said in general?

$\endgroup$
  • 2
    $\begingroup$ What is a conic hull, please? $\endgroup$ – Gerry Myerson Sep 6 '18 at 11:49
  • $\begingroup$ The (strict) conic hull of a set of real vectors $V=\{v_1, \dots, v_n\}$ is defined as $\left\{\sum_{i = 1}^n \alpha_i v_i \;|\; \alpha_i > 0 \right\}$. $\endgroup$ – bodhisat Sep 6 '18 at 11:57
  • 2
    $\begingroup$ No. Consider the matrix \begin{pmatrix} 0&1&0 \\ 2&0&2 \\ 1&0&0 \end{pmatrix} Vector $j$ lies in the span of the columns with weights $1,1,-1/2$. But it does not lie in their conic hull. $\endgroup$ – bodhisat Sep 6 '18 at 17:19
  • 1
    $\begingroup$ The set of matrices $M$ with $j$ in their conic hull is a (closed?) convex cone. The set of non-negative matrices is a pointed, closed, convex cone, and the set of matrices with zero diagonals is a linear subspace. The set of matrices we are interested in is the intersection of all these, therefore it is also a (closed?) pointed convex cone. My intuition is that this whose set should be closed but I will have to double check this. Then we can apply theorem 2.55 from ams.jhu.edu/~abasu9/AMS_550-465/notes-without-frills.pdf to get a reduced version of the problem. $\endgroup$ – Pushpendre Sep 9 '18 at 19:22
  • 2
    $\begingroup$ The cone is not convex. Consider the following counter-example: $$ \begin{pmatrix} 0&9&1 \\ 3 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix} = \begin{pmatrix} 0&9&0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix} + \begin{pmatrix} 0&0&1 \\ 3 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}$$ The matrix is a positive linear combination of two monomial matrices which are part of the cone. Yet their sum yields a matrix whose inverse has the row-sums $.75, .25, -1.25$. $\endgroup$ – bodhisat Sep 10 '18 at 17:30
1
$\begingroup$

Some further thoughts approaching the solution.

I found a connection of the question to potential theory. Let $A$ be an invertible non-negative matrix, and $j$ the all-one vector. The (right) signed potential $\nu$ of $A$ is the solution to \begin{equation} A\nu = j.\end{equation} Additionally requiring $\nu > 0$ leads to a strict equilibrium potential. Hence, my question can be rephrased as follows:

Which are the necessary and sufficient conditions on $A$ for the existence of a strict equilibrium potential?

Of relevance is the definition of a strict potential matrix. $A$ is a potential iff its inverse is a strictly row-diagonally dominant $M$-matrix. This subsumes, for example, the strictly ultrametric matrices whose inverses are strictly row-diagonally dominant Stieltjes, and generalized strictly ultrametric matrices for $A$ asymmetric.

Yet none of these classes allows for zero diagonals, and all of this is just sufficent. For instance, positive monomial matrices obviously have strict equilibrium potentials as well. Strikingly, if $A$ has the potential $\nu > 0$, then $SA$, where $S$ is pseudo-stochastic (i.e. row-sums equal one) must have the exact same potential. This can be seen by noting that $SA\nu = Sj = j$.

Let $A = DS_A$, where $D_{ii} = \sum_j A_{ij}$. Interpreting $A$ as a graph, $S_A$ is the Markov chain on $A$. We now have $$DS_A\nu = j = S_A^{-1}DS_A\nu.$$

Hence, $A$ has the same potential as its degree matrix, expressed in the basis given by the columns of its Markov chain. Is this useful to think about the existence of equilibrium potentials in general?

Nabben, Reinhard, and Richard S. Varga. "Generalized ultrametric matrices—a class of inverse M-matrices." Linear Algebra and its Applications 220 (1995): 365-390.

$\endgroup$
  • $\begingroup$ The zero-diagonal requirement can be dispensed with, by the way. I found a way to get rid of it for my purposes. $\endgroup$ – bodhisat Sep 18 '18 at 13:44

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.