10
$\begingroup$

Let $P\in \mathbb{R}^{n\times n}$ be the inverse of a positive definite M-matrix and $V\in \mathbb{R}^{n\times n}$ be any diagonal matrix. Prove (or disprove) that $PVPVP$ is elementwise nonnegative.

I know of the following:

$P$ is positive definite and elementwise nonnegative. Moreover, $p_{jk}p_{ii} \ge p_{ji}p_{ik}$ for any $i,j,k$.

I can verify that the statement is true for $n=2$, but I don't know how to work with $n$ large. Playing around with randomly generated matrices in Matlab seems to suggest that the statement is true. Any hint or suggestion would be greatly appreciated.

I've googled out that a very similar statement was put as a conjecture in this paper: Optimization of an on-chip active cooling system based on thin-film thermoelectric coolers (http://dl.acm.org/citation.cfm?id=1870955)

Edit: Perhaps someone can solve this easier question: Is there a positive semi-definite and elementwise nonnegative $P$ and diagonal $V$ such that $PVPVP$ is not elementwise nonnegative?

$\endgroup$
12
  • 1
    $\begingroup$ The same question was asked about a week ago at MSE: math.stackexchange.com/q/985073/166535 $\endgroup$ Oct 28, 2014 at 20:26
  • 1
    $\begingroup$ Hint: There exists $S \in \mathbb R^{n \times n}$ such that $P = S^2 = S^T S$. Now, use the definition of nonnegative definiteness. $\endgroup$
    – cardinal
    Oct 29, 2014 at 0:01
  • 1
    $\begingroup$ @cardinal: please excuse my slowness, but is it then immediate that one gets elementwise nonnegativity? $\endgroup$
    – Suvrit
    Oct 29, 2014 at 5:02
  • 1
    $\begingroup$ @mathnotgoodatmath, if you repost, it's polite to mention it and give a link. Therefore I added the comment. About the question itself: It could be a good idea to include the definition of nonnegativity in the question. I first thought the question was simple, but then I realised that nonnegativity must mean something other than positive semidefiniteness and had to find the definitions. $\endgroup$ Oct 29, 2014 at 6:11
  • 1
    $\begingroup$ @JoonasIlmavirta: Thanks for your comments. Just edited the question. I'll be more careful next time. $\endgroup$
    – vansy
    Oct 29, 2014 at 14:57

2 Answers 2

11
$\begingroup$

First, we repeat the arguments from this stackexchange answer. $P^{-1}$ is an $M$-matrix, and can thus be written as $s(I-A)$ for some positive $s$ and some $A$ with non-negative entries. As $P^{-1}$ is positive definite, the spectrum of $A$ lies to the left of $\{ z: \hbox{Re}(z) = 1 \}$, and hence by Perron-Frobenius the spectral radius of $A$ is less than $1$. Thus we have the absolutely convergent Neumann series $$ P = s^{-1} (I + A + A^2 + \dots )$$ and hence $$ PVPVP = s^{-3} \sum_{i=0}^\infty \sum_{j=0}^\infty \sum_{k=0}^\infty A^i V A^j V A^k.$$ It thus suffices to show that $$ \sum_{i+j+k=m} A^i V A^j V A^k \quad (1)$$ has non-negative coefficients for each $m \geq 0$ (where $i,j,k$ are understood to be non-negative integers). By change of variables, this is $$ \sum_{0 \leq q \leq r \leq m} A^q V A^{r-q} V A^{m-r}.$$ Writing $A = (a_{st})_{1 \leq s,t \leq n}$ and $V = \hbox{diag}(v_1,\dots,v_n)$, the $st$ coefficient of (1) can be expanded as $$ \sum_{s=s_0,s_1,\dots,s_m=t} a_{s_0 s_1} \dots a_{s_{m-1} s_m}\sum_{0 \leq q \leq r \leq m} v_{s_q} v_{s_r}.$$ But the quadratic form $$ \sum_{0 \leq q \leq r \leq m} x_q x_r = \frac{1}{2}(x_0+\dots+x_m)^2 + \frac{1}{2} x_0^2 + \dots + \frac{1}{2} x_m^2$$ is positive definite, and the $a_{st}$ are non-negative, and the claim follows.

[For the record, I found this argument while performing a perturbative analysis in the case where $P$ was close to $I$, or more precisely $P = (I-A)^{-1}$ for some $A$ with small non-negative entries.]

$\endgroup$
1
  • $\begingroup$ Wow, thanks so much for your proof. I came across this argument when looking at $(L+\mathrm{diag}(x))^{-1}$ where $L$ is a Laplacian matrix and $x$ is a nonnegative (and nonzero) vector. $\endgroup$
    – vansy
    Apr 7, 2016 at 22:47
2
$\begingroup$

Although you said you already proved the result for $n=2$, perhaps it's worth recording a proof here.

The statement is clear if both diagonal entries of $V$ have the same sign, so assume that $V = \left(\matrix{v_1&0\\ 0&-v_2}\right)$ with $v_1\ge0$ and $v_2\ge0$. If $P = \left(\matrix{a&b\\ c&d}\right)$ then by direct computation, $$PVPVP = \left(\matrix{a^3v_1^2 - bc(2av_1v_2 - dv_2^2)&b(a^2v_1^2-(ad+bc)v_1v_2 + d^2v_2^2)\\ c(a^2v_1^2-(ad+bc)v_1v_2 + d^2v_2^2)& d^3v_2^2 - bc(2dv_1 v_2 - av_1^2 )}\right).$$ Since the determinant of $P$ is positive, $-bc \ge -ad$, so $$a^2v_1^2-(ad+bc)v_1v_2 + d^2v_2^2 \ge a^2v_1^2-2adv_1v_2 + d^2v_2^2 = (av_1 - dv_2)^2 \ge 0.$$ Therefore the off-diagonal entries of $PVPVP$ are nonnegative. If $2av_1v_2 - dv_2^2<0$ then the $(1,1)$ entry of $PVPVP$ is clearly nonnegative; otherwise, $$a^3v_1^2 - bc(2av_1v_2 - dv_2^2)\ge a^3v_1^2 - ad(2av_1v_2 - dv_2^2) =a(av_1 -dv_2)^2 \ge 0. $$ Similarly, if $2dv_1 v_2 - av_1^2 < 0$ then the $(2,2)$ entry is clearly nonnegative; otherwise $$d^3v_2^2 - bc(2dv_1 v_2 - av_1^2 )\ge d^3v_2^2 - ad(2dv_1 v_2 - av_1^2 ) = d(dv_2 - av_1)^2 \ge 0. $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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