# Finding roots of a recursively given polynomial sequence / eigenvalues of an almost Toeplitz matix

I would like to find the roots of the polynomial sequence given by a recurrence relation as follows:

$V_0(x) = 1-a^2$

$V_1(x) = 1-a^2 - x$

$V_{k \geq 2}(x) = (1+a^2 - x)V_{k-1}(x) - a^2V_{k-2}(x)$

I know that $a \in (0,1)$.

Another formulation of the problem could be to find the eigenvalues of the tridiagonal symmetric matrix $C_n$

$C_n = \left[ \begin{matrix} 1-a^2 & -a\sqrt{1-a^2} & & \\ -a\sqrt{1-a^2} & 1+a^2 & -a & \\ & -a & 1+a^2 & \ddots \\ & & \ddots & \ddots \end{matrix} \right]$

Since the matrix is symmetric, the roots are going to be real. I also know that the matrices $C_n$ are positive definite.

This is almost like a Chebyshev recursion, but a little bit perturbed.

A bonus question: I have some vague memories about the proof of the roots of Chebyshev polynomials that involved an argument that the roots of the consecutive polynomials in the sequence separate each other, and from this, with some additional tools the roots were derived. If someone can point to a location where I can find that proof, it would be really helpful.

Edit after the solutions: Based on the trigonometric equations derived by Pietro Mejer, I suspect that there is no closed formula that describes the roots.

• Orthogonal polynomials and refs therein. Actually, your polynomials do look orthogonal. – Alex Degtyarev Mar 1 '14 at 10:12
• They do look orthogonal, you have a three-term recurrence. – Per Alexandersson Mar 1 '14 at 10:26
• I guess it's not difficult to compute explicitly the roots, solving the linear recursion for $V_k$. That is, write $V_k=\alpha_1 {v_1}^k + \alpha_2 {v_2}^k$, where $v_1$ and $v_2$ are the roots of the quadratic polynomial $v^2 - (1+a^2-x)v+ a^2$. So the roots of $V_k$ are roots of $(v_1/v_2)^k= -(\alpha_2/\alpha_1)$. Did you try this computation? – Pietro Majer Mar 1 '14 at 10:29
• Yes, because of the three term recursion, they are orthogonal. – kolixx Mar 1 '14 at 10:58
• I did not try what Pietro Majer suggested. I will do it, and I get back to you on this one. Thanks. – kolixx Mar 1 '14 at 10:59

For $k\in\mathbb{N}$ and $0<a<1$ your polynomial $V_k$ has indeed $k$ distinct real roots in the interval $\big( (1-a)^2, (1+a)^2 \big)$ ; these can be written $$x_j:=1+a^2-2a\cos(t_j)$$ where $t_1<\dots < t_k$ are the $k=\lceil k/2\rceil+\lfloor k/2\rfloor$ solutions in the interval $(0,\pi)$ to either $$\cos\Big(\frac{k+1}{2}t\Big)=a\cos\Big(\frac{k-1}{2}t\Big)$$ or
$$\sin\Big(\frac{k+1}{2}t\Big)=a\sin\Big(\frac{k-1}{2}t\Big)\, .$$

To see it, write $x:=1+a^2-2az$ and introduce the polynomials $P_k(z):=a^{-k}V_k(x)$. This way $P_k$ satisfy the Chebyshev polynomials linear recurrence, $$P_{k+2}=2zP_{k+1} - P_k\, ,$$ with initial conditions $$P_0=1-a^2$$ $$P_1=2z-2a\, .$$ Solving the linear recurrence one finds a representation $$P_k(z):=\big(u^{k+1}-au^k-au+1 \big)\big(u^{k+1}-au^k+au-1\big)\frac{u^{-k}}{u^2-1}=$$

$$\frac{\Big(u^{\frac{k+1}{2}}+u^{-\frac{k+1}{2}}-a(u^{\frac{k-1}{2}}+u^{-\frac{k-1}{2}}) \Big)\Big(u^{\frac{k+1}{2}}-u^{-\frac{k+1}{2}}-a(u^{\frac{k-1}{2}}-u^{-\frac{k-1}{2}}) \Big)}{u-u^{-1}}\, ,$$

where $u:=z+i\sqrt{1-z^2}$.

If we write $u:=\exp(it)$ and $z=\cos(t)$ we get

$$P_k\big(\cos(t)\big)=\frac{2\bigg(\cos\Big(\frac{k+1}{2}t\Big)-a\cos\Big(\frac{k-1}{2}t\Big)\bigg)\bigg(\sin\Big(\frac{k+1}{2}t\Big)-a\sin\Big(\frac{k-1}{2}t\Big)\bigg)}{\sin(t)}\, .$$

It is easy to see that the first factor has $\lceil k/2\rceil$ zeros in $(0,\pi)$, while the other has $\lfloor k/2\rfloor$ zeros, and of course they have no common zeros, as $|a|\neq 1$. Since $\cos$ is bijective on $(0,\pi)$, these $k$ values $t_1\dots t_k$ correspond to distinct roots $z_j:=\cos(t_j)$ of $P_k(z)$, thus all of them. $$*$$ Note that for $a=0$ the roots of $P_k$ are $\cos(t_j)$ with $\cos\Big(\frac{k+1}{2}t_j\Big)\sin\Big(\frac{k+1}{2}t_j\Big)=0$, that is $\sin\Big((k+1)t_j\Big)=0$, which is what we expect since $P_k(z)=U_k(z)$ for $a=0$, whose roots are $z_j(0)=\cos\big(\pi j/(k+1)\big)$ for $1\le j\le k$.

For $a=1$ one finds $P_k(z)=2(z-1)U_{k-1}(z)$, with roots $z_j(1)=\cos\big(\pi (j-1)/k\big)$ for $1\le j\le k$.

Also, if I'm not wrong, it's easy to see that the $z_j=z_j(a)$ are increasing wrto the parameter $a\in[0,1]$, so that $z_j(0)\le z_j(a)\le z_j(1)$ for all $j$ and $a$.

• The above computation should be completed by means of an analytic representation of the solutions to the equations $$\cos(\theta)=a\cos(b\theta)$$ and $$\sin(\theta)=a\sin(b\theta).$$ For the moment, I'll not approach this interesting problem, a well studied one I suppose. – Pietro Majer Mar 2 '14 at 19:41
• Thanks a lot. I will get back to you as I digested things above. – kolixx Mar 3 '14 at 8:36
• I have to prepare a talk in the next few days, but I will resume to this problem afterwards. I hope this is not transcendental equation :) – kolixx Mar 3 '14 at 9:08
• I can confirm the statement about $z_j(a)$ being a monotonic function of a from a different perspective. The inverse of the eigenvalues of this matrix has a stochastic interpretation of some kind of correlation and that quantity is also monotonic in $a$. – kolixx Mar 5 '14 at 8:09
• After correcting the sign issue the numerical test also checks out. – kolixx Mar 12 '14 at 8:55

We write about these type of matrices here, Schur polynomials, banded Toeplitz matrices and Widom's formula, Electr. Jour. Comb. 19, No.4 (2012)

In that article, there is a simple method on how to compute exactly where the roots of your polynomials accumulate. They will lie on a semi-algebraic curve in general, (when real-rooted, it will of course be an interval).

The $x \in \mathbb{C}$ such that the roots of $t^2 - (1 + a^2 - x) t + a^2$ (in $t$) have the same magnitude will be the interval where the eigenvalues accumulate. In your case, it seems to be the interval $\left[(-1+a)^2,(1+a)^2\right]$.

See for example here regarding the three-term recurrence.

Orthogonal polynomials in general, see for example the references in here.

• Unfortunately the presence of the first row and column is essential for me and I need exact expressions for the eigenvalues of $C_n$ for finite values of $n$. (With the initial rows my original problem involves a stochastic process started from its stationary distribution. Without the initial row the process would be started from zero initial condition, which is not realistic. I might resort to this approximation if the mathematics does not work out for the non-Toeplitz case). – kolixx Mar 2 '14 at 12:10
• Ah, yes the measure should be independent of the initial conditions... so I don't think it may give much info in the finite case. You might be able to get nice expressions for the $V_k$:s; you essentially have a linear recurrence, but with polynomial coefficients, so one can use the same theory that works for linear recurrences with constant coefficients, i.e., express the terms as linear combinations of the zeros of the characteristic polynomial, (in fact, that is the polynomial that I have in the answer above here). It will most likely be quite ugly... – Per Alexandersson Mar 2 '14 at 15:30