0
$\begingroup$

I'm working with matrices defined by $$T_{ki} = \sum_{j} M_{kj}N_{ji} + \delta_{ki}\biggl(1 - \sum_{j}N_{ji}\biggr)$$ where $M$ is a stochastic (or probability) matrix, where $\sum_{k} M_{kj} = 1$, $N$ satisfies $0 \leq \sum_j N_{ji} \leq 1$, and hence $T$ is also stochastic, $\sum_{k} T_{ki} = 1$. I notice that the eigenvalues of $T$, in the cases I've checked numerically, are always very close to $1$, typically $0.99999999 \leq \lambda \leq 1$. For all I know, the eigenvalues are all equal to $1$ and the only reason my numerical results don't reflect this is roundoff or truncation error in the algorithm.

I know that the largest eigenvalue of $T$ must be $1$, because it's stochastic, but is it true in general that all the eigenvalues of $T$ (given the definition above) are equal to $1$, or very close to $1$? If not, is there some reason the eigenvalues would be particularly likely to all be close to $1$?

In case anyone's curious the context is a calculation of particle absorption and emission. $N$ represents the probability of an incoming particle in state $i$ being absorbed and putting the absorbing system into a transient state $j$, and $M$ represents the probability of a system in state $j$ emitting a particle in outgoing state $k$.

$\endgroup$
4
  • $\begingroup$ Why is $T$ stochastic? It's not even necessarily entrywise nonnegative. Are there any additional conditions that you haven't revealed? $\endgroup$
    – user1551
    Sep 14, 2015 at 6:00
  • $\begingroup$ @user1551 $M$ and $N$ are entrywise nonnegative, although I can show that $T$ satisfies $\sum_k T_{ki} = 1$ without using that fact. $\endgroup$
    – David Z
    Sep 14, 2015 at 6:42
  • $\begingroup$ Are we on the same page? A matrix is called (column) stochastic if it is nonnegative and its column sums are all equal to 1. That $N$ is entrywise nonnegative is not enough to ensure that $T$ is entrywise nonnegative. So I'm not sure why you call it stochastic. $\endgroup$
    – user1551
    Sep 14, 2015 at 7:01
  • $\begingroup$ @user1551 oh, I see what you mean. Yeah, I forgot to mention that $\sum_j N_{ji} \leq 1$. Of course, again, that's not necessary to establish that $\sum_k T_{ki} = 1$, but I believe it does ensure nonnegativity. And as my answer shows, the fact that the matrix is entrywise nonnegative turns out to be irrelevant to the eigenvalue question. $\endgroup$
    – David Z
    Sep 14, 2015 at 7:28

2 Answers 2

Reset to default
1
$\begingroup$

This is not true in general, even if $N$ is also stochastic. For a counterexample, suppose $N$ is the $n\times n$ matrix with all entries equal to $\frac1n$ and $M\in\{I,N\}$ (so that both $M,N$ are doubly stochastic). Then $T=N$ and zero is an eigenvalue of $T$ of multiplicity $n-1$.

$\endgroup$
0
$\begingroup$

Not all eigenvalues of $T$ are $1$. The numerical example your alluded to must have some property that is abstracted away from the condition you have stated.

Consider the following counterexample. $M=\frac{1}{n}\mathbf 1 \mathbf 1^T$, where $\mathbf 1$ is the $n\times 1$ entries column matrix of all $1$ entries. $N = aI$ where $I$ is the $n\times n$ identity matrix for a real $0\le a\le 1$. Obviously, $T$ has a single simple eigenvalue $1$ with left and right eigenvectors both equal to $\mathbf 1$, and eigenvalue $1-a$ of geometric multiplicity $n-1$ with its eigenspace perpendicular to $\mathbf 1$.

$\endgroup$
6
  • $\begingroup$ I'm not claiming that all eigenvalues of $T$ are 1. It's an empirical observation that they tend to be close to 1, so unless you're saying there is a programming error in the linear algebra library I use, it does no good to suggest a computational error. This is good information to have, sure, but it doesn't answer my question. $\endgroup$
    – David Z
    Nov 11, 2015 at 1:56
  • $\begingroup$ Actually, to be fair, it answers the first part of my question. (Though user1551's answer does the same.) What I'm really interested in is the second part. $\endgroup$
    – David Z
    Nov 11, 2015 at 4:05
  • $\begingroup$ @DavidZ: Your question asked whether rather than claimed "all eigenvalues of $T$ are 1". However, the answer you have provided and since deleted after I have posted my answer did clearly CLAIM to prove that "all eigenvalues of $T$ are 1" and moreover said it was "trivial" to see that. My answer was directed at both your question and your answer AT THE TIME. I am not trying to pick on your statement but simply want to be precise. It is hard to chase a moving target, do you agree? user1551's answer does answer the first question as well, though I saw it after I have made the (to be continued) $\endgroup$
    – Hans
    Nov 11, 2015 at 19:19
  • $\begingroup$ @DavidZ: comment on your (accepted) answer explaining why the "proof" did not prove your own claim, and posted mine. Regarding your second question, my answer, more than what user1551 has shown, has answered it by giving an example where the eigenvalue $1-a$ can be anywhere between $0$ and $1$ as $a$ varies. So there is NO "reason the eigenvalues would be particularly likely to all be close to $1$". Your numerical example must possess some property your present statement of the condition has abstracted away. You can try random matrices that only satisfy the condition listed (to be continued) $\endgroup$
    – Hans
    Nov 11, 2015 at 19:37
  • $\begingroup$ in your question to see numerically the eigenvalue does not have to be close to $1$. Then look carefully at your original example to see what other extra property is not covered by your present abstraction. Maybe you can show here a concrete numerical example (without which it is hard to see what is missing) of somewhat small size, as a followup to your original question. It is better done without changing the original question but as a followup to preserve the continuity of the questions and answers. On another note, I have now edited the tone of my first paragraph of my answer. $\endgroup$
    – Hans
    Nov 11, 2015 at 19:54

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .