I am trying to find all the eigenvalues of $P$ defined below:

$$P=\begin{bmatrix} 0.5&0.5&0&0&\cdots 0&0 \\ 0.25&0.5&0.25&0&\cdots 0&0\\ 0&0.25&0.5&0.25&\cdots 0&0\\ \vdots \\ 0&0&0&0&\cdots 0.5&0.5 \end{bmatrix}_{n\times n}$$

So $P$ has $0.5$ along the main diagonal. It has $0.25$ on diagonals above and below the main diagonal except for the first and last row. Hence $P$ is not exactly a Toeplitz matrix.

My attempt: A paper I'm looking at, gives eigenvalues of the following Toeplitz matrix

$$ Q=\begin{bmatrix} b&a \\ c&b&a \\ &\ddots&\ddots&\ddots \\ &&c&b&a \\ &&&c&b \end{bmatrix} $$

as $\lambda_j = b+2\sqrt{ca}\cos\left(\frac{j\pi}{n+1} \right)$

So I'm wondering if I will be able to find eigenvalues of $P$ even though its not a Toeplitz matrix precisely?

  • $\begingroup$ I suspect that this wikipedia page could be helpful $\endgroup$ – Ben Grossmann May 11 at 14:25
  • $\begingroup$ You have a typo in the eiegenvalues of the Toeplitz matrix, the coefft of the $\cos$ has to be $2\sqrt{ac}$. $\endgroup$ – ancient mathematician May 11 at 14:26
  • $\begingroup$ There's clearly an eigenvalue $0$ with multiplicity $1$ and another $1$ of multiplicity $1$. $\endgroup$ – ancient mathematician May 11 at 14:28
  • $\begingroup$ @ancientmathematician Thanks, corrected the typo. $\endgroup$ – manifolded May 11 at 14:31
  • $\begingroup$ Did u try to look at $Px = \lambda x$ and expand linear equations? $\endgroup$ – Snowball May 11 at 16:06

$\def\a{\alpha}$ Let $u$ be an eigenvector of the matrix $P$ and assume the elements of the eigenvector have the form: $$ u_k=e^{\alpha k}+ae^{-\alpha k},\tag1 $$ with some parameters $a$ and $\alpha$, which are to be found.

Obviously for all $k=2\dots(n-1)$ $$ (Pu)_k=\frac14\left(e^{\a k}+ae^{-\alpha k}\right)\left(e^\alpha+2+e^{-\alpha}\right) =\frac14\left(e^\alpha+2+e^{-\alpha}\right)u_k.\tag2$$

Thus it remains only to find such $a$ and $\alpha$ that the equation $(2)$ is satisfied for $k=1$ and $k=n$ as well.

For $k=1$: $$\begin{align} &\frac12(e^{\a}+ae^{-\a}+e^{2\a}+ae^{-2\a})=\frac14\left(e^\a+2+e^{-\a}\right)\left(e^\alpha+a e^{-\alpha}\right)\\ &\iff e^{2\a}+ae^{-2\a}=1+a \iff a=e^{2\a}.\tag{3} \end{align}$$

For $k=n$: $$\begin{align} &\frac12(e^{\a(n-1)}+ae^{-\a(n-1)}+e^{\a n}+ae^{-\a n}) =\frac14\left(e^\a+2+e^{-\a}\right)\left(e^{\a n}+a e^{-\a n}\right)\\ &\iff e^{\a (n-1)}+ae^{-\a(n-1)}=e^{\a (n+1)}+ae^{-\a(n+1)}\\ &\iff e^{\a (n-1)}+ae^{-\a (n-1)}=e^{2\a}e^{\a(n-1)}+ae^{-2\a}e^{-\a(n-1)}\\ &\stackrel{(3)}\iff \left(e^{\a (n-1)}-e^{-\a (n-1)}\right)\left(1-e^{2\a}\right)=0\\ &\iff \a_m=\frac{\pi\,i}{n-1}m,\quad m=0\dots n-1 .\tag{4} \end{align}$$

The corresponding eigenvalues are: $$ \lambda_m=\frac14\left(e^{\a_m}+2+e^{-\a_m}\right)=\left(\frac{e^{\frac{\a_m}2}+e^{-\frac{\a_m}2}}2\right)^2=\cos^2\frac{\pi m}{2(n-1)},\quad m=0\dots n-1.\tag5 $$ Since all $n$ eigenvalues are distinct we are done.

  • $\begingroup$ Thanks, I'm looking at $(5)$ now, how do you have $\frac{e^{\alpha_m/2}+e^{-\alpha_m/2}}{2}=\cos\left( \frac{\alpha_m}{2} \right)$? $\endgroup$ – manifolded May 11 at 20:24
  • $\begingroup$ @manifolded I used: $\frac{e^{ix}+e^{-ix}}2=\cos x$ $\endgroup$ – user May 11 at 20:28
  • 1
    $\begingroup$ I see, I missed the $i$ in $\alpha_m$ earlier. Thanks. $\endgroup$ – manifolded May 11 at 20:29
  • $\begingroup$ I see that $(Pu)_k = \frac{1}{4}(e^{(k-1)\alpha}+ae^{-(k-1)\alpha})+\frac{1}{2}(e^{k\alpha}+ae^{-k\alpha})+\frac{1}{4}(e^{(k+1)\alpha}+ae^{-(k+1)\alpha})$, for $k=2,\cdots,n-1$, by definition of matrix multiplication but that is not equal to $(2)$? $\endgroup$ – manifolded May 11 at 20:37
  • 1
    $\begingroup$ @manifolded It is equal, with no doubt. $\endgroup$ – user May 11 at 20:40

(Not a solution)

I numerically found that the answer should be $$ \lambda_j = \sin^{2}\left(\frac{j\pi}{2(n-1)}\right), \quad 0\leq j \leq n-1 $$ but I only have a vague idea to prove this. If we define $B_n = 2P_n - I_n$, then it is enough to show that the eigenvalues of $B_n$ are $$ \cos\left(\frac{j\pi}{n-1}\right),\quad 0\leq j\leq n-1. $$ It seems that the characteristic polynomial of $B_n$ is $$ \phi_n(x) = \frac{1}{2^{n}}(x^2-1)U_{n-2}(x) $$ where $U_n(x)$ is $n$-th Chebyshev polynomial of second kind. However, I'm not sure how to prove this, although it seems that using induction might give recurrence formula for $\phi_n$ which resembles that of $U_n$ a lot.

  • $\begingroup$ For the numerical solution, may I know if you found $\lambda_j^{(n)}$ for different $n$ and then conclude $\lambda_j$ is what you have above? Thanks. $\endgroup$ – manifolded May 11 at 18:12
  • $\begingroup$ @manifolded Yes, I just plotted the eigenvalues and it reminds me $\sin^2$. $\endgroup$ – Seewoo Lee May 11 at 18:14
  • $\begingroup$ May I know why it is enough for $B_n$ to have its eigenvalues as $\cos \left(\frac{j\pi}{n-1} \right)$? I didn't understand how $B_n=2P_n-I_n$ implies that? $\endgroup$ – manifolded May 11 at 18:17
  • $\begingroup$ @manifolded It follows from $\sin^2(x)=(1-\cos(2x))/2$. $\endgroup$ – Seewoo Lee May 11 at 18:30
  • $\begingroup$ I see, I thought if $B_n$ has eigenvalues of $\cos\left(\frac{j\pi}{n-1} \right)$, then $\frac{I_n-B_n}{2}$ will have eigenvalues $\sin^2 \left(\frac{j\pi}{2(n-1)} \right)$ as opposed to $\frac{I_n+B_n}{2}$ which is what you have. I maybe wrong? $\endgroup$ – manifolded May 11 at 18:39

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.