9
$\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$
  • 1
    $\begingroup$ The same question was asked about a week ago at MSE: math.stackexchange.com/q/985073/166535 $\endgroup$ – Joonas Ilmavirta Oct 28 '14 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 '14 at 0:01
  • 1
    $\begingroup$ @cardinal: please excuse my slowness, but is it then immediate that one gets elementwise nonnegativity? $\endgroup$ – Suvrit Oct 29 '14 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$ – Joonas Ilmavirta Oct 29 '14 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 '14 at 14:57
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$
  • $\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 '16 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, privacy policy and cookie policy

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