Inequality involving matrix inverse elements

Question

Let $A$ be an $N \times N$ matrix with all nonnegative entries and row sums strictly less than one, let $v$ be an $N$ dimensional vector with all nonnegative entries and weakly lower than one, let $B\equiv\left(I-A\mathrm{diag}\left(v\right)\right)^{-1}$ and let $B^*\equiv\left(I-A\right)^{-1}$, where $\mathrm{diag}\left(v\right)$ is the diagonal matrix formed from vector $v$. I want to show that for any $i,j=1,...,N$ the following inequality holds: $$ v_{j}b_{ji}^2+\sum_{k}\left(1-v_{k}\right) b_{jk}b_{ki}^{2}\leq b_{ji} b_{ii}^{*}. $$

Simulations suggest that this is true.

The case in which $v$ is the vector of all ones follows from the fact that $b_{ji} \leq b_{ii}^{*}$, which is shown here. The case with $A$ diagonal is trivial for $i \neq j$, whereas for $i=j$ it boils down to showing $$v_{i}b_{ii}+(1-v_{i})b_{ii}^{2}\leq b_{ii}^{*},$$ which can be shown by plugging in for $$b_{ii}=\frac{1}{1-v_{i}a_{ii}},\quad b_{ii}^{*}=\frac{1}{1-a_{ii}},$$ and basic algebra.

Apart from these simple cases, I have been able to show the result for the case in which $j=i$, but it is an arduous induction proof that does not extend to the case in which $i \neq j$. We would appreciate hints for approaches that could be useful to prove the claim.

The problem above comes from a more general problem in matrix algebra, which is to show that $ii$ of the following matrix is less than $b_{ii}^*$, $$J \equiv \left(\mathrm{diag}\left\{ B^{T}x\right\} \right)^{-1}B^{T}\left[ \mathrm{diag}\left\{ v\right\}\mathrm{diag}\left\{ x\right\} +\mathrm{diag}\left\{ 1-v\right\} \mathrm{diag}\left\{ B^{T}x\right\} \right]B,$$ with $x$ being an $N$ dimensional vector in the simplex, i.e., $x_j \geq 0,\sum_j x_j=1$. It can be shown that the diagonal elements will be maximized with respect to $x$ when $x$ is at a corner of the simplex, and that if $x_j = 1$ then $$ J_{ii} = v_{j}b_{ji}+\sum_{k}\left(1-v_{k}\right) \frac{b_{jk}b_{ki}^{2}}{b_{ji}}\leq b_{ii}^{*}. $$ Multiplying by $b_{ji}$ on both sides leads to the inequality postulated above. A closely related problem is to show that the spectral radius of $J\mathrm{diag}(\iota-A \iota)$ is lower than one (where $\iota$ is the vector of all ones), see here. (Note that if $v=\iota$ then $J\mathrm{diag}(\iota-A \iota)\iota = J(I-A)\iota = \iota$ and so the spectral radius of $J\mathrm{diag}(\iota-A \iota)$ is one.)

Answer 1

I first give a proof if $i=j$. I will treat the general case in the EDIT. I will show later that $b_{ji}\leq b_{ii}$ and $b^*_{ji}\leq b^*_{ii}$ for $i\neq j$. This is actually well known. Since $B^*=\sum_n A^n$ and $B=\sum_n (AV)^n$, $V=\mbox{diag}\{v\}$, it follows that $0\leq b_{ij}\leq b^*_{ij}$ for all $i,j$.

Hence we have $$ v_{i}b_{ii}^2+\sum_{k}\left(1-v_{k}\right) b_{ik}b_{ki}^{2}\leq \left(v_{i}b_{ii}+\sum_{k}\left(1-v_{k}\right) b_{ik}b_{ki}\right)b_{ii}. $$ Therefore it remains to show that $$v_{i}b_{ii}+\sum_{k}\left(1-v_{k}\right) b_{ik}b_{ki}\leq b^*_{ii}.$$ Since $b_{ik}\leq b^*_{ik}$, the left hand side is at most equal to the $ii$-th element of $VB+B^*(I-V)B$. Now we calculate $$VB+B^*(I-V)B=B^*(I-A)VB+B^*(I-V)B=B^*(I-AV)B=B^*.$$ This completes the proof.

In the case $j\neq i$, an analogous proof shows that$$ v_{j}b_{ji}^2+\sum_{k}\left(1-v_{k}\right) b_{jk}b_{ki}^{2}\leq b^*_{ji} b_{ii}. $$ Unfortunately, experiments show that this does not imply the wanted inequality because $b^*_{ji} b_{ii}\geq b_{ji} b^*_{ii}$ for $j\neq i$.

Proof of the inequalities $b_{ji}\leq b_{ii}$ and $b^*_{ji}\leq b^*_{ii}$ for $i\neq j$.: We have $(I-A)B^*=I$ and hence $B^*=AB^*+I$. Suppose now that $b^*_{ji}>b^*_{ii}$ for some $j\neq i$. We fix such an $i$ and choose $j$ such that, additionally, $b^*_{ji}$ is maximal among the elements $b^*_{ki},k=1,\dots,N$. Then $B^*=AB^*+I$ implies that $$b^*_{ji}=\sum_k a_{jk}b^*_{ki}\leq\left( \sum_k a_{jk}\right) b^*_{ji}$$ which contradicts $\sum_k a_{jk}<1$.

For the proof of $b_{ji}\leq b_{ii}$ replace $A$ by $AV$.

EDIT: I finally found a proof. In a first step, we use the convexity of $f(x)=x^2$ (or the Cauchy-Schwarz inequality) to show that $$(\alpha_1\beta_1+\cdots+\alpha_n\beta_n)^2\leq \alpha_1\beta_1^2+\cdots+\alpha_n\beta_n^2$$ if $\alpha_i,\beta_i$ are non-negative and $\alpha_1+\cdots+\alpha_n\leq1$.

Recalling that $AVB=B-I$ implies that $\sum_k a_{rk}v_k b_{ki}=b_{ri}$ if $r\neq i$, this can be used to show that $$\tag{1}\sum_k a_{rk}v_k^2b_{ki}^2-b_{ri}^2\geq \left(\sum_k a_{kr}v_kb_{ki}\right)^2-b_{ri}^2=0\mbox{ if }r\neq i,$$ because by assumption $\sum_k a_{rk}<1$.

Now put $$d_{ji}=v_{j}b_{ji}^2+\sum_{k}\left(1-v_{k}\right) b_{jk}b_{ki}^{2}- b_{ji} b^*_{ii}.$$ We have shown above that $d_{ii}\leq0$ for all $i$ and want to show that also $d_{ji}\leq0$ if $j\neq i$. The idea is to consider the quantities $\sum_{j\neq i} a_{rj}v_j d_{ji}-d_{ri}$ for $r\neq i$. We prove later
Claim We have $\sum_{j\neq i} a_{rj}v_j d_{ji}-d_{ri}=:g_{ri}\geq0$ for $r\neq i$.
This implies the wanted inequalities $d_{ri}\leq0$ for $r\neq i$ in the following way. Using the vectors $d$ of the $d_{ri}, r\neq i$, $g$ of the $g_{ri}, r\neq i$ and the matrix $A'$ of the $a_{rj}v_j,r,j\neq i$ the Claim means that $A'd-d=g\geq0$ componentwise. Hence $d=A'd-g$. Finally the fact that the row sums of $A'$ are strictly less than one implies that its norm $||A'||_\infty<1$ and hence we obtain that $$d=-\sum_{n=0}^\infty (A')^ng\leq0.$$ For a proof of the Claim, we have to calculate using $\sum_j a_{rj}v_jb_{jk}=b_{rk}-\delta_{rk}$, where $\delta_{rk}=0$ if $r\neq k$ and $=1$ if $r=k$: $$\sum_{j} a_{rj}v_j d_{ji}=\sum_j a_{rj}v_j^2b_{ji}^2+\sum_k(1-v_k)\sum_j a_{rj}v_jb_{jk}b_{ki}^2-\sum_j a_{rj}v_jb_{ji}b^*_{ii}\\= \sum_j a_{rj}v_j^2b_{ji}^2+\sum_k (1-v_k)(b_{rk}-\delta_{rk})b_{ki}^2-b_{ri}b^*_{ii}\\ =\sum_j a_{rj}v_j^2b_{ji}^2+d_{ri}-v_rb_{ri}^2-(1-v_r)b_{ri}^2\\ =d_{ri}+\sum_j a_{rj}v_j^2b_{ji}^2-b_{ri}^2\geq d_{ri}$$ because of (1). This finally implies that $$\sum_{j\neq i} a_{rj}v_j d_{ji}-d_{ri}\geq -a_{ri}v_id_{ii}\geq0$$ because we already have that $d_{ii}\leq0$. This completes the proof.

Remark: The same idea can be used to prove that $b_{ji}^*b_{ii}\geq b_{ji}b^*_{ii}$ which shows that the inequality of the question is sharper than the one I found in the beginning of the proof. Indeed if $D_{ji}=b_{ji}^*b_{ii}-b_{ji}b^*_{ii}$ then (using $v_j\leq1$) $$\sum_{j\neq i} a_{rj}v_jD_{ji}\leq D_{ri}$$ for $r\neq i$. Hence $D\geq A'D$ and therefore $D\geq0$ for the vector $D$ of the $D_{ji},j\neq i$.

The inequality $J_{ii}\leq b_{ii}^*$ near the end of the question can be written $$\sum_k x_k v_k b_{ki}^2+\sum_k(1-v_k)s_kb_{ki}^2\leq s_i b_{ii}^*,\mbox{ where }s_i=\sum_j x_jb_{ji}.$$ As the difference of both sides can be written $\sum_j x_j d_{ji}$ with the $d_{ji}$ of the above proof, it follows from the main inequalities of the question.