4
$\begingroup$

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 $B\equiv\left(I-AV\right)^{-1}$ and finally let $X$ be a vector in the $n$-dimensional simplex, i.e., $x_j \geq 0,\sum_j^n x_j=1$. Consider the matrix $$M \equiv \left(\mathrm{diag}\left\{ B^{T}X\right\} \right)^{-1}B^{T}\left[ V\mathrm{diag}\left\{ X\right\} + (I-V) \mathrm{diag}\left\{ B^{T}X\right\} \right]B\mathrm{diag}(\iota-A \iota),$$ where $\mathrm{diag}\left(u\right)$ is the diagonal matrix formed from vector $u$ and $\iota$ is the vector of all ones. I want to show that the spectral radius of $M$ is (weakly) lower than one, $\rho(M)\leq 1$.

Two simple cases are illustrative. First, if $V = I $ then $M\iota = \iota$ and so $\rho(M)=1$. Second, if $A$ is diagonal then $M$ would be diagonal and so we would just need to show that each diagonal element is lower than one. But each of diagonal element of $M$ would be of the form $$\left(v+\frac{1-v}{1-av}\right)\frac{1-a}{1-av},$$ which is readily shown to be lower than one.

The problem above, namely showing that $\rho(M)\leq 1$, comes from a more general problem, which I ultimately need to solve. Let $D_1$ and $D_2$ be two strictly positive diagonal $n \times n$ matrices and let $$\tilde{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\mathrm{diag}\left(\iota-A\iota\right)D_{2}.$$ I want to show that $\rho(\tilde{M})\leq 1$ provided that $$ \tag{*} D_{1}\left(I-A\right)^{-1}\mathrm{diag}\left(\iota-A\iota\right)D_{2}\iota\leq\iota.$$ This is now posted as a separate question here: Bounding spectral radius of special matrix (extension)

The simpler question stated above obtains from this more general question in the special case in which $D_{k}=d_{k}I,k=1,2$ with $d_1,d_2$ being positive scalars. In that case $$\tilde{M}=\left(\mathcal{\mathrm{diag}}\left\{ B^{T}X\right\} \right)^{-1}B^{T}\left[V\mathcal{\mathrm{diag}}\left\{ X\right\} +\left(I-V\right)\mathcal{\mathrm{diag}}\left\{ B^{T}X\right\} \right]B\mathrm{diag}\left(\iota-A\iota\right)d_{1}d_{2},$$ while condition (*) simply becomes $d_{1}d_{2} \leq 1$, and so we can simply prove that $\rho(M)\leq 1$.

$\endgroup$
2
  • 1
    $\begingroup$ Numerically with random $A$, $V$, I always obtained $\rho(J)\leq1$ for all $X$. Actually $J$ always had two small positive eigenvalues and one close to $1$. Unfortunately, in some cases it occurred that $J\iota\leq\iota$ was false and also the trace of $J$ was not $\leq1$ so that these two approaches failed... $\endgroup$
    – Helmut
    Mar 10 at 14:22
  • $\begingroup$ @Helmut Yes, sorry, I should have mentioned that. This was my first attempt at a proof, namely using the max row sum as a bound on the spectral radius, but simulations reveal examples where $J \iota \leq \iota$ is violated. $\endgroup$
    – Andres
    Mar 10 at 16:07

1 Answer 1

2
+100
$\begingroup$

Here is an answer using ideas of my solution to the linked question.

First recall that $B=\sum_n (AV)^n$ has positive elements and that $B=AVB+I$ implies that $$\tag1 \sum_j a_{rj}v_jb_{jn}=b_{rn}-\delta_{rn}$$ where $\delta_{rn}=1$ if $r=n$ and $=0$ otherwise.

Let us now introduce some notation: $D_B=\newcommand{\diag}{\mbox{ diag}}\diag(B^TX)$, $D_A=\diag(\iota-s)$ with $s=A\iota$ and $D_X=\diag(X)$.

Then $M=D_B^{-1}B^T[VD_X+(I-V)D_B]BD_A$ is only defined if $B^TX$ has nonzero components. This will be assumed in the beginning. It is the case if $X$ has only positive components, but might be wrong for certain $X$, for example if $A$ and hence $B$ are block-triangular.

We want show that its spectral radius $\rho(M)\leq1$. This is equivalent to showing that $\rho(M')\leq1$for the symmetric matrix $$M'=D_B^{-1/2}D_A^{1/2}B^T[VD_X+(I-V)D_B]BD_B^{-1/2}D_A^{1/2}$$ similar to $M$. This in turn is equivalent to showing that $M'-I$ is negative semidefinite. Multiplying with $D_B^{1/2}D_A^{-1/2}$ from the left and the right, this is equivalent to showing that $$M''=B^T[VD_X+(I-V)D_B]B-D_BD_A^{-1}$$ is negative semidefinite. This statement makes sense for all $X$ in the n-dimensional simplex. Since $D_X$ and $D_B$ are linear functions of $X$ and $X$ has nonnegative elements, if suffices to show this for the unit vectors $X=e_j$, $j=1,\ldots,n$. So we have to show that the matrices $$L_j=B^T[VE_j+(I-V)D_j]B-D_jD_A^{-1}$$ are negative semidefinite where $E_j=\diag(e_j)$ and $D_j=\diag(B^Te_j)=\diag(b_{j1},\ldots,b_{jn})$. Fixing an arbitrary vector $w$, we have to show that $z_j:=w^TL_jw\leq0$ for all $j$.

As in the answer to the linked question, it is sufficient for this to show that $$\tag2 \sum_ja_{rj}v_jz_j\geq z_r\mbox{ for all }r,$$ because this implies that the vector $z$ of the $z_r$ can be expressed as $z=-\sum_n (AV)^n d$ with the vector $d$ of the nonnegative differences $d_r=\sum_j a_{rj}v_jz_j - z_r.$

For a proof of (2), we rewrite $z_j$ using the vector $u=Bw$. We have $$z_j=w^TL_jw=u^TVE_ju+u^T(I-V)D_ju-w^TD_jD_A^{-1}w\\ =v_ju_j^2+\sum_m u_m^2(1-v_m)b_{jm}-\sum_m w_m^2b_{jm}/(1-s_m).$$ Using (1), we calculate $$\sum_j a_{rj}v_jz_j=\sum_j a_{rj}v_j^2u_j^2+\sum_m u_m^2(1-v_m)(b_{rm}-\delta_{rm})-\sum_m w_m^2(b_{rm}-\delta_{rm})/(1-s_m)\\ =\sum_j a_{rj}v_j^2u_j^2+z_r-v_ru_r^2-u_r^2(1-v_r)+w_r^2/(1-s_r)\\ =z_r+d_r,\mbox{ where }d_r=\sum_j a_{rj}v_j^2u_j^2-u_r^2+w_r^2/(1-s_r).$$

For a proof of the nonnegativity of all $d_r$, the first idea is to use (1) to calculate $$\sum_j a_{rj}v_ju_j=\sum_{j,n} a_{rj}v_jb_{jn}w_n=\sum_n (b_{rn}-\delta_{rn})w_n=u_r-w_r.$$ Next, we use the Cauchy-Schwarz inequality $\left(\sum_jx_jy_j\right)^2\leq\left(\sum_j x_j^2\right)\left(\sum_j y_j^2\right)$ with $x_j=\sqrt{a_{rj}}$ and $y_j=\sqrt{a_{rj}}v_ju_j$ to show $$\left(\sum_j a_{rj}v_ju_j\right)^2\leq \left(\sum_ja_{rj}\right) \left(\sum_j a_{rj}v_j^2u_j^2\right)=s_r\sum_j a_{rj}v_j^2u_j^2.$$ Hence, except in the exceptional case $s_r=0$, we can estimate $$d_r\geq\frac1{s_r}(u_r-w_r)^2-u_r^2+\frac{w_r^2}{1-s_r} =\frac{(1-s_r)(u_r-w_r)^2-s_r(1-s_r)u_r^2+s_rw_r^2}{s_r(1-s_r)}\\ =\frac{\left((1-s_r)u_r-w_r\right)^2}{s_r(1-s_r)}\geq0.$$ This completes the proof, except in the exceptional case.

If $s_r=0$, then all $a_{rj}=0$, $j=1,\ldots,n$. Then $b_{rj}=\delta_{rj}$,$j=1,\ldots,n$, hence $u_r=w_r$ and $z_r=0$. Therefore (2) is trivially true in the exceptional case.

$\endgroup$
8
  • $\begingroup$ @Andres I modified my answer. I had a hard time finding the estimate of $d_r$ ! I am trying right now to extend the proof to $\bar M$... $\endgroup$
    – Helmut
    Mar 14 at 13:27
  • $\begingroup$ @Andres In numerical simulations, I always had $\rho(\bar M)\leq1$ if the condition on $D_1,D_2$ holds. Unfortunately, they also show that the method of the above proof does not work. $\endgroup$
    – Helmut
    Mar 14 at 20:48
  • $\begingroup$ I see. Thanks. Where does the proof break down in the case with $D_1,D_2 \neq I$. $\endgroup$
    – Andres
    Mar 14 at 21:03
  • $\begingroup$ I am guessing that the problematic one must be $D_2$, because if $D_2 = I$ then condition (*) simply becomes $D_1 \leq I$ (entrywise), and so one can redo the same proof above but with $d_1 = \max_i D_1(ii)$. $\endgroup$
    – Andres
    Mar 14 at 22:24
  • $\begingroup$ @Andres The above proof using $\sum_j a_{rj}v_jd_j-d_r$ only works if $D_1=I$ and in the end needs also $D_2\leq I$. I can only be extended trivially to $D_1\leq d_1 I$, $D_2\leq d_2I$, $d_1d_2\leq1$. A new idea is needed to exploit the condition on $D1,D_2$. $\endgroup$
    – Helmut
    Mar 15 at 10:40

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.