I asked this question previously on math.stackexchange.com, where it had little traction. 


Consider the symmetric random walk on $\{0,1,…,n\}$ with transition probabilities $P(j→j±1)=1/2$ for $0 < j < n$ and $P(0→0)=P(0→1)=P(n→n)=P(n→n−1)=1/2$. I am interested in the spectrum of the transition matrix (which is symmetric, hence the spectrum is real).


Mathematica suggests that the characteristic polynomial of the transition matrix is of the form $p\_n(x)=(1−x)q\_n(x)$, where $q\_n$ is a polynomial that is odd / even iff $n−1$ is odd / even and that has only simple zeroes. Therefore, the spectrum appears to be a symmetric set of n points from the open unit interval, plus the point $λ=1$.


It occurs to me that this ought to be well known. In particular, the factors $q\_n(x)$ in the characteristic polynomials ought to be special. 


Does anybody know more?



Spectrum of transition matrix for symmetric random walk
The previous answer of Pablo Lessa seems to be related to a different problem:
with periodic
boundary conditions. Your conditions are not periodic.


Your matrix is a special Jacobi matrix, and the characteristic polynomial
can be found explicitly.


Let $A$ be your matrix, $x=(x\_0,\ldots,x\_n)$ an eigenvector with eigenvalue 
$\lambda$. Then $(A-\lambda)x=0$ gives you $n+1$ linear equations
which I enumerate $0$ to $n$. Let us fix arbitrary $\lambda$ and try
to solve for $x$. WLOG set $x\_0=1$. Then equation $0$ gives
$$x\_1=2\lambda-1,$$
And the next $n-1$ equations are 
$$x\_{k+2}-2\lambda x\_{k+1}+x\_k=0,\quad k=0,...,n-2.$$
This is a linear recurrency, and it is solved in the usual way.
Let us denote $\lambda=\cos\theta$. The characteristic equation is
then $\rho^2-2\cos\theta+1=0$ thus $\rho=\exp(\pm i\theta).$
The general solution is $x\_k=c\_1\cos k\theta+c\_2\sin k\theta$. Substituting
$k=0$ and $k=1$ we obtain $c\_1=1,c\_2=(\cos\theta-1)/\sin\theta$. So
$$x\_k=\cos k\theta+\frac{\sin k\theta}{\sin\theta}(\cos\theta-1)$$
Or, returning to $\lambda$,
$$x\_k=T\_k(\lambda)+(\lambda-1)U\_{k-1}(\lambda),$$
where $T\_k$ and $U\_k$ are Chebyshev polynomials of the first and second
kind, respectively.


Now the equations number $n-1$ and $n$ give two expressions for $x\_n$.
Equating these two expressions we obtain the characteristic equation:
$$(1-2\lambda)(T\_n+(\lambda-1)U\_{n-1}(\lambda))+T\_{n-1}+(\lambda-1)U\_{n-2}(\lambda)=0.$$
Probably this can be simplified using the
relations between Chebyshev polynomials.


A general reference for Jacobi matrices is the book by Gantmakher and Krein, Oscillation matrices, etc., recently translated by AMS.


