# Eigenvalues of a matrix close to a tridiagonal Toeplitz matrix

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?

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

• 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)$? – manifolded May 11 at 20:24
• @manifolded I used: $\frac{e^{ix}+e^{-ix}}2=\cos x$ – user May 11 at 20:28
• I see, I missed the $i$ in $\alpha_m$ earlier. Thanks. – manifolded May 11 at 20:29
• 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)$? – manifolded May 11 at 20:37
• @manifolded It is equal, with no doubt. – 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.

• 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. – manifolded May 11 at 18:12
• @manifolded Yes, I just plotted the eigenvalues and it reminds me $\sin^2$. – Seewoo Lee May 11 at 18:14
• 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? – manifolded May 11 at 18:17
• @manifolded It follows from $\sin^2(x)=(1-\cos(2x))/2$. – Seewoo Lee May 11 at 18:30
• 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? – manifolded May 11 at 18:39