1
$\begingroup$

I'm trying to bound the spectral radius of a matrix product. The first matrix is $$H = (I-M)^{-1}\Gamma,$$ where $\sum_jM_{ij}<1$, $M_{ij}\geq0$, and $\Gamma$ is a diagonal matrix with non-negative entries (when $\Gamma$ is a zero matrix then the question is trivial, so let’s focus on the case when $\Gamma$ has at least one non-zero entry).

Then the target matrix is $KH$. Matrix $K=P-Q$ is the difference of two right stochastic matrices (a right stochastic matrix has each row sums to 1 and all elements are non-negative), naturally |$K_{ij}| \leq 1$ and $\sum_{j}K_{ij} = 0$. In addition, $Q=\vec{1}\vec{q}'$ is a rank-1 matrix. That implies $|K_{ij}-K_{kj}|\leq1$.

The hypothesis is

$$\rho(KH) = \rho(HK) \leq \rho(H).$$

Alternatively, a bound provided by the norm of H would also be good. The corresponding conjecture is $$\rho(KH)(=\rho(HK))\leq||H||. $$

Does anybody have an idea of how this could be proved or whether this is right? Thanks in advance.

So far I've proved

$$\rho(HK) \leq 2 \|H\|_\infty$$

by the following reasoning: ($\|\cdot\|_\infty$ provides an upper bound of the spectral radius of a matrix, according to Gershgorin Disk Theorem.) \begin{align} \rho(HK) & \leq \|HK\|_\infty\\ &=\max_j\sum_i|HK_{ji}|\\ &=\max_j\sum_i|\Sigma_kH_{jk}K_{ki}| \\ &\leq \max_j\sum_i\Sigma_k|K_{ki}||H_{jk}|\\ &\leq \max_j2\sum_k|H_{jk}|\\ &=2\|H\|_\infty \end{align}

Actually any bound tighter than this would be great to see!

$\endgroup$
1
  • $\begingroup$ Welcome to MSE. Nice first question! $\endgroup$ Jun 27 '20 at 8:12
0
$\begingroup$

Do you think the result depends on the properties of the matrix $M$? I ask because the result is related to $H$ and not to $M$. In fact, the result you have already proven is in terms of $H$, not $M$. Or perhaps you think that it is only when $H$ satisfies these constraints (i.e., that the matrix $M$ associated with $H$ satisfies $\sum_j M_{ij}<1$ and $𝑀_{𝑖𝑗}\geq0$) that you can lower the $2$ to a $1$.

Now, if it is the case that one needs to use the structure of the underlying $M$ matrix, then perhaps using the expansion $(I-M)^{-1} = I + M + M^2 ...$ could help.

$\endgroup$
1
  • $\begingroup$ I'm framing the question based on properties of $H$ since the conditions on H seems easier to be deducted and can be converted into conditions on $M$ once we specify them, for instance via the method you pointed to. We're only interested in H such that the associated $M$ satisfies $M_{ij}\geq0$; $\sum_jM_{ij}<1$ guarantees the existence of H (by guaranteeing $I-M$ is invertible). $\endgroup$ Jun 28 '20 at 7:29
0
$\begingroup$

We have $$\rho(KH)\leq ||(KH)^{n}||_{\infty}^{1/n},\forall n$$ and $$\rho(KH)=\lim_{n\rightarrow \infty} ||(KH)^{n}||_{\infty}^{1/n},\forall n$$ by the spectral radius formula. Examining the norms of the powers of KH, or just starting with KHK, seems like it might be helpful.

$\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.