2

This is an extension of Bounding spectral radius of special matrix (extension), which has been already solved.

Let $A$ be an $n \times n$ matrix with all nonnegative entries and row sums strictly less than one, let $V$ be an $n \times n$ nonnegative diagonal matrix satisfying $V \leq I$ (entrywise), let $D_0$ be an $n \times n$ nonnegative diagonal matrix such that $I \leq D_0 < I + \mathrm{diag} \left\{ \iota - A \iota \right\} \left( \mathrm{diag} \left\{ A \iota \right\} \right)^{-1}$, let $X$ be a vector in the $n$-dimensional simplex (i.e., $x_j \geq 0,\sum_j^n x_j=1$), let $D_1$ and $D_2$ be two strictly positive diagonal $n \times n$ matrices. Define $B \equiv \left(I - AV\right)^{-1}$, $B_{1} \equiv \left(I - D_0 AV\right)^{-1}$ and $B^{*}_{1} \equiv\left(I - D_0 A\right)^{-1}$. Finally, let $$M \equiv \left(\mathrm{diag}\left\{ B^{T}X\right\} \right)^{-1}B^{T}\left[V\mathrm{diag}\left\{ X\right\} +\left(I-V\right)\mathrm{diag}\left\{ B^{T}X\right\} \right]D_{1} B_{1} D_{2}.$$ I want to show that the spectral radius of $M$ is less than or equal to one, $\rho(M)\leq 1$, provided that the following condition holds $$\tag{1} D_{1} B^{*}_{1} D_{2} \iota\leq\iota.$$

Observe that if $D_0 = I$, then we get the same problem as in Bounding spectral radius of special matrix (extension).

Also, I used subscript $1$ for matrix $B_{1}^{*}$ to distinguish it from matrix $B^{*} \equiv \left(I - A\right)^{-1}$ that might be useful for a proof.

Update on May 25, 2022: Changed notation and, importantly, dropped dependence of matrix $D_{2}$ on $D_{0}$. We don't need this dependence: numerically $\rho \left(M \right) < 1$ with independent $D_{2}$ and $D_{0}$.

Update on Sep 22, 2022: I thought that there might be monotonicity of the spectral radius with respect to $D_{0}$. In particular, I thought that once the dependence of $D_{2}$ on $D_{0}$ is dropped, then $\rho \left(M \right)$ is falling as we increase diagonal elements of $D_{0}$. But this is not true.

  • @Andres There is a crucial difference between this extension and the previous one: the matrix is not easily similar to a symmetric one. The proof of the previous extension cannot be carried over unchanged. Are you sure, you want to have $B_1$ on the left of the $[$ and $B_2$ right of $D_1$? – Helmut Apr 19 '22 at 16:07
  • $D_0 = \mathrm{diag} \left{ \iota - A \iota \right} \left( \mathrm{diag} \left{ A \iota \right} \right)^{-1}$ is not possible: This gives a singular matrix $I-(I+D_0)A$. – Helmut Apr 19 '22 at 23:29
  • @Helmut About $B_{1}$ on the left: numerically it works. This is what we want. Indeed, the previous extension cannot be carried over easily. About $D_{0}$ -- you are right, sorry. It has to be $D_{0} < \mathrm{diag} \left{\iota - A \iota \right} \left( \mathrm{diag} \left{ A \iota \right} \right)$. I edited the question. – Konstantin Apr 19 '22 at 23:45
  • @Andres Yes, numerically it works. Moreover, the spectral radius seems to be decreasing, when the components of $D_0$ increase provided $D_1B^*D_3\iota=\iota$. Unfortunately, not all entries of $\bar M$ decrease at the same time. – Helmut Apr 22 '22 at 10:14
  • @Helmut. Interesting point that the SR falls as $D_0$ increases provided the condition holds with equality. I am not sure why it matters that not all entries of $\tilde{M}$ decrease at the same rate, but one option would be to consider (perhaps as a first step) the case in which $D_0 = d_0 I$. – Andres Apr 22 '22 at 11:47
  • @Helmut I checked the monotonicity with respect to the elements of $D_{0}$: it doesn't look it works. Given a random $D_{0}$, I was changing one of its diagonal elements between $0$ and $0.99 \cdot \mathrm{diag} \left{ \iota - A \iota \right} \left( \mathrm{diag} \left{ A \iota \right} \right)^{-1}$. The spectral radius of $\tilde{M}$ generally has a non-monotone dependence on the elements of $D_{0}$. I often see the pattern where, as we increase one diagonal element of $D_{0}$, the spectral radius of $\tilde{M}$ first increases and then decreases (and never achieves $1$). – Konstantin May 17 '22 at 12:35
  • @Andres I did my simulations the following way: I decreased one element of $D_0$ a little bit AND calculated $D_1$ such that $D_1 B^* D_3 \iota = \iota$ where $B^*, D_3$ are considered as functions of $D_0$. Then always (in $100.000$ simulations) the spectral radius of $\bar M$ was slightly larger (and still $<1$). Please confirm! – Helmut May 22 '22 at 11:28
  • @Helmut Do you change $B_{2}$ when you change $D_{0}$? In any case, I think I can find a counterexample to the monotonicity. Here it is: https://www.dropbox.com/s/lex2netcyvs0xs2/counterexample_1.txt?dl=0 – Konstantin May 22 '22 at 12:51
  • Of course, I also change $B_2$. $B_2,B^$ and $D_3$ are functions of $D_0$ and then so is $D_1$ such that $D_1 B^ D_3 \iota = \iota$. I wiill check your example if I can. – Helmut May 22 '22 at 13:30
  • I confirm your counterexample! Apparently, I was not looking at the right $D_0$. Now I do not know what to do, but I never give up. – Helmut May 22 '22 at 14:21
  • Thank you, Helmut! Our experience with these matrices shows that monotonicity rarely works... – Konstantin May 23 '22 at 00:04
  • You did not only change notation! The relation connecting $D_3$ and $D_0$ disappeared. So in the present form, the problem is more general than before I think. – Helmut May 26 '22 at 19:03
  • @Helmut: Sorry, I didn't notice your last comment here up until now. The connection between $D_{3}$ and $D_{0}$ disappeared from the new notation because $D_{3}$ had another random diagonal matrix inside of it that was making $D_{3}$ basically independent from $D_{0}$. – Konstantin Jun 13 '22 at 10:54

1 Answers1

1

This is not an answer, but some thoughts.

Consider the case when $D_{2}$ has only one positive diagonal entry, and all other diagonal entries equal to $0$ -- similar to what we did here.

First, as in here, it is enough to consider the unit vectors $X = e_{j}$ for $j = 1,\dots,n$. We have $\mathrm{diag} \left\{ B^{T} e_{j} \right\} = \mathrm{diag} \left\{ b_{j1}, \dots, b_{jn} \right\}$.

Consider any $e_{j}$. Assume that $d_{2,i} > 0$ for some $i$ and $d_{2,k} = 0$ for $k \neq i$. Then $\rho(M)$ is given by \begin{align*} \rho(M) = \dfrac{b_{ji}v_{j}d_{1,j}b_{1,ji}d_{2,i}+\sum_{k}b_{ki}\left(1-v_{k}\right)b_{jk}d_{1,k}b_{1,ki}d_{2,i}}{b_{ji}}, \end{align*} and condition (1) is given by $d_{1,k} b^{*}_{1, ki} d_{2,i} \leq 1$ for $k = 1,\dots, n$. This gives $d_{1,k} \leq \left( b^{*}_{1, ki} d_{2,i} \right)^{-1}$ and \begin{align*} \rho(M) \leq \dfrac{b_{ji}v_{j} \left[ b^{*}_{1,ji} \right]^{-1} b_{1,ji} + \sum_{k}b_{ki}\left(1-v_{k}\right)b_{jk} \left[ b^{*}_{1,ki} \right]^{-1} b_{1,ki} }{b_{ji}}. \end{align*} If we can show that the right-hand side of the above is not larger than $1$, then we would be done. So, we want to show that \begin{align*} v_{j} b_{ji} \dfrac{ b_{1,ji} }{ b^{*}_{1,ji} } + \sum_{k} \left(1-v_{k}\right) b_{ki} b_{jk} \dfrac{ b_{1,ki} }{ b^{*}_{1,ki} } \leq b_{ji} . \qquad (2) \end{align*}

I thought that the following is true: $b_{1,ki} \big/ b^{*}_{1,ki} \leq b_{ki} \big/ b^{*}_{ki}$ for all $k$ and $i$. However, it does not generally hold.

  • (2) seems to me like a new "Inequality involving matrix inverse elements". It is a very first step towards a solution of your problem. I will try soon... – Helmut May 26 '22 at 19:16
  • @Helmut Thank you! I was trying to crack it, but no luck so far. I see that numerically it holds: I had billions of simulations of this inequality. – Konstantin May 27 '22 at 23:01
  • 1
    One idea is to apply the trick of my solutions. Let $z_j$ the differences of left hand minus right hand side of (2). In order to prove that all $z_j$ are negative, it suffices to prove that all $g_r=\sum_j a_{rj}v_j z_j - z_r$ are positive. Numerically this seems to be the case, but I did not try many examples yet. A formal proof that all $g_r$ are positive succeeds in the case $D_0=I$ of course, but how to do it for other $D_0$ ?? – Helmut May 28 '22 at 21:19
  • @Helmut The conjecture that $g_{ri} = \sum_j a_{rj} v_{j} z_{ji} - z_{ri}$ does not seem to be true numerically for matrices of size larger than $3$. Strange, but in my simulations, for matrices of size 4 and larger there is always one and exactly one pair of $(r, i)$ such that $g_{ri} < 0$. – Konstantin May 30 '22 at 09:42
  • I will check this. I tried to show that $g_{ri}>0$ using convexity (for the product $(x,y)\mapsto xy$ instead of the square), but this did not work. (2) is true, it seems, for $j=i$, because $B_{1ki}/B^{1ki}\leq B{1ii}/B^_{1ii}$ as shown in the remark my oldest answer. – Helmut May 30 '22 at 18:50
  • I forgot: I also tried differentiating with respect to the elements of $D_0$, but as for the previous questions, this becomes very complicated and does not seem to work. Have you tried (2) and the inequality of your question for matrices of size larger than 3? I admit, I only did it for size 3. – Helmut May 30 '22 at 19:03
  • I checked the positivity of $g_{ri}$ for a number of random matrices of size 4 and it was always ok (which would be good news). Please recheck your calculations. – Helmut May 31 '22 at 07:41
  • @Helmut: For your last comment about matrices of size 4, can you check this example: https://www.dropbox.com/s/anq8ing36ufy0qe/counterexample_02.txt?dl=0 – Konstantin May 31 '22 at 08:56
  • I ran simulations of (2) for matrices of size 4 and 5 and it worked. – Konstantin May 31 '22 at 08:58
  • Unfortunately, I must confirm your counterexample. I probably did not enough tests. So we have to find a different idea of proof for (2). – Helmut May 31 '22 at 13:00
  • As you say, it is not true that $b_{1,ki} \big/ b^{}{1,ki} \leq b{ki} \big/ b^{}_{ki}$ for all $k$ and $i$. Today I found one counterexample among millions of random $A$, $V$, $D_0$. Maybe, we should study those counterexamples? – Helmut Jun 01 '22 at 19:46
  • Yes, we need to understand these counterexamples. I was trying to understand why your conjecture about $g_{ri}$ works for all pairs of $r$ and $i$ except for one. That is, in my simulations, all $g_{ri}$ are always positive except for one. This is very strange. – Konstantin Jun 02 '22 at 03:15
  • In the above counterexamples (I found about 60 by now trying nearly a billion random matrices), if the quotient is maximal then exactly one of the entries of $D_0$ does not equal 1. I will investigate further. – Helmut Jun 04 '22 at 22:37
  • I checked the counterexamples for $b_{1,ki} \big/ b^{}{1,ki} \leq b{ki} \big/ b^{}{ki}$ whether some $g{ri}$ is negative as well. This did never happen. Conversely, in your counterexample with negative $g_{ri}$, the inequality for the quotients is true. If in all cases, either the inequality for all quotients or the positivity of all $g_{ri}$ is true then (2) is also true... – Helmut Jun 11 '22 at 13:22
  • @Helmut: This is a good idea! I will launch extensive simulations for this as well. But we might need to think about what can be the worst case scenario for this pattern: it can just be that the space of counterexamples is "thin". Anyways, if the quotients inequality is true, then (2) follows immediately. Now we need to understand if we can prove the second part: given that the quotients inequality breaks, then $g_{ri} \geq 0$. – Konstantin Jun 13 '22 at 09:01
  • @Helmut Unfortunately, this does not seem to work. I found a counterexample: https://www.dropbox.com/s/bbqwea3eo5chn5k/counterexample_03.txt?dl=0 In this counterexample, $g_{ri} < 0$ for $r = 4$ and $i = 1$, and $b_{1,ki} \big/ b^{}{1,ki} > b{ki} \big/ b^{}_{ki}$ for $k = 4$ and $i = 1$. – Konstantin Jun 13 '22 at 12:33