1
$\begingroup$

I have the companion matrix

$$\mathbf{M}:=\left(\begin{array}{ccccc} 1-p+pa_{1}&pa_{2}&pa_{3}&\cdots&pa_{m}\\ 1&&&&\\ &1&&&\\ &&1&&\\ &&&1&\end{array}\right)$$

where $p\in(0,1)$ and $\sum_{i}a_{i}=1$, and the null entries are $0$. So, obviously, $\lambda_{1}:=1$ is an eigenvalue and the corresponding right-eigenvector is $\mathbf{v}_{1}:=(1,1,\cdots,1)^{\mathsf{T}}$. How can I show that the modulus of the other eigenvalues are strictly smaller than $1$?

I believe this is something well-known.

Thank you.

$\endgroup$
2
  • $\begingroup$ Consider the companion polynomial, its roots are the eigenvalues of your matrix. The conditions on $p$ and on $a_i$ should preclude the existence of roots bigger than $1$ in modulus. $\endgroup$ – Giuseppe Negro Mar 13 '18 at 12:16
  • $\begingroup$ Related question: here also the problem is determining the dominant eigenvalue in a situation where $(1,1,\ldots, 1)$ is an eigenvector. There are many beautiful answers. $\endgroup$ – Giuseppe Negro Mar 14 '18 at 12:38
1
$\begingroup$

Define the characteristic polynomial by $P(\lambda):=\det(\mathbf{M}-\lambda\mathbf{I})$, then \begin{equation} P(\lambda):=(\pm1)\bigl[\underbrace{\lambda^{m}-(1-p+pa_{1})\lambda^{m-1}-pa_{2}\lambda^{m-2}-\cdots-pa_{m}}_{Q(\lambda)}\bigr]=0.\nonumber \end{equation} If $P(\lambda)=0$ and $|\lambda|>1$, then \begin{align} 1\leq{}&(1-p+pa_{1})\frac{1}{|\lambda|}+pa_{2}\frac{1}{|\lambda|^{2}}+\cdots+pa_{m}\frac{1}{|\lambda|^{m}}\nonumber\\ <{}&(1-p+pa_{1})+pa_{2}+\cdots+pa_{m}=1,\nonumber \end{align} which is a contradiction. Thus, if $P(\lambda)=0$, then $|\lambda|\leq1$. Clearly, $P(1)=0$ and \begin{align} Q^{\prime}(1)={}&1+(m-1)p-(m-1)pa_{1}-(m-2)pa_{2}-\cdots-pa_{m-1}\nonumber\\ \geq{}&1+(m-1)p-(m-1)pa_{1}-(m-1)pa_{2}-\cdots-(m-1)pa_{m-1}\nonumber\\ ={}&1+(m-1)p[1-(a_{1}+a_{2}+\cdots+a_{m-1})]\geq1,\nonumber \end{align} which shows that $P^{\prime}(1)=\pm{}Q^{\prime}(1)\neq0$, i.e., $1$ is simple. Next, assume that $P(\lambda)=0$ and $|\lambda|=1$ such that $\lambda\neq1$, i.e, $\lambda=\mathrm{e}^{\mathrm{i}\theta}$, where $\theta\in(0,2\pi)$. Since $\theta\in(0,2\pi)$, we have \begin{align} 1={}&\bigl|(1-p+pa_{1})\mathrm{e}^{-\mathrm{i}\theta}+pa_{2}\mathrm{e}^{-2\mathrm{i}\theta}+\cdots+pa_{m}\mathrm{e}^{-m\mathrm{i}\theta}\bigr|\nonumber\\ <{}&(1-p+pa_{1})+pa_{2}+\cdots+pa_{m}=1,\nonumber \end{align} which is again a contradiction. Thus, $|\lambda|<1$ if $P(\lambda)=0$ and $\lambda\neq1$.

$\endgroup$
1
$\begingroup$

Use Gershgorin theorem. The eigenvalues must be confined in the disks $\{λ\in\mathbb C\ :\ |\lambda|\le 1\}$ and $$\left\{\lambda\in\mathbb{C}:\ |\lambda- (1-p+p a_{1})|\le \sum_{j=2}^{m} a_{j}\right\}.$$ The second disk is included in the first.

IMPORTANT. This shows that any eigenvalue $\lambda$ must satisfy $|\lambda|\le 1$, but it is not strong enough to prove the strict bound $|\lambda|<1$ except for $\lambda=1$. To obtain this stronger result I think there is no way around the computations with the characteristic polynomial of the other answer.

$\endgroup$
4
  • $\begingroup$ I drew the discs, and saw that $D_{1}\cap{}D_{2}=D_{2}\ni1$. I am not sure if GCT avoids $\lambda_{1}=1$ to be repeated. $\endgroup$ – bkarpuz Mar 15 '18 at 11:33
  • $\begingroup$ By "smaller" in the main text, do you mean "strictly smaller"? In that case, GCT is insufficient. $\endgroup$ – Giuseppe Negro Mar 15 '18 at 11:58
  • $\begingroup$ Yes, I mean the rest to be strictly smaller. $\endgroup$ – bkarpuz Mar 15 '18 at 13:54
  • 1
    $\begingroup$ Then this argument is not enough, as you found. I have added a remark. $\endgroup$ – Giuseppe Negro Mar 15 '18 at 16:21

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.