The Eigenvalues and Eigenvectors of Tridiagonal Toeplitz Matrix「建议收藏」

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

The Eigenvalues and Eigenvectors of Tridiagonal Toeplitz Matrix

by Changyu Zhou  

Abstract

 Usually, the eigenvalues are calculated first, then are the eigenvectors. But for a special kind of matrix: Tridiagonal Toeplitz Matrix, the eigenvectors will be found at first. Want to know how? Keep reading!

Details

 We investigate a special kind of $n\times n$ real matrix——Tridiagonal Toeplitz Matrix:
$$M={\left(\begin{array}{cccc}a& b& & \\ c& \ddots & \ddots & \\ & \ddots & a& b\\ & & c& a\end{array}\right)}_{n\times n}(b,c\ne 0)$$

 Before dealing with this kind of matrix, let’s look a simpler one, which is symmetric as follow:
$$M_1=\left(\begin{array}{cccc}a& b& & \\ b& \ddots & \ddots & \\ & \ddots & a& b\\ & & b& a\end{array}\right)=aI+b{T}_1(b\ne 0)$$

with
$$T_1=\left(\begin{array}{cccc}0& 1& & \\ 1& \ddots & \ddots & \\ & \ddots & 0& 1\\ & & 1& 0\end{array}\right)$$

 We can know that if $\lambda$ and $v$ satisfy
$$M_{1}v=\lambda v,v\ne 0$$

It can be inferred that
$$M_{1}v=(aI+b{T}_1)v=av+b{T}_{1}v=\lambda v$$

after simplifying,
$$T_{1}v=\frac{\lambda -a}{b}v$$

so ${\lambda }^{\prime }=\frac{\lambda -a}{b}$ is the eigenvalue of $T_1$.

 Similarly, if ${\lambda }^{\prime }$ is the eigenvalue of $T_1$, then ${\lambda }^{\prime }b+a$ is the eigenvalue of $M_1$.

 In other words, $M_1$ and $T_1$ have the same eigenvectors and their respective eigenvalues are related.

 So, to find $M_1$‘s eigenvectors and eigenvalues, it is sufficient to focus on the solution of the simpler matrix $T_1$‘s eigenvectors and eigenvalues.

 Usually, the eigenvalues are calculated first, then are the eigenvectors. But for $T_1$, it is simpler to first find the eigenvectors. Assume that $\lambda$ is $T_1$‘s eigenvalue and $v$ is the corresponding eigenvector. With hindsight, it’s convenient to write $\lambda =2c$, then
$$(T-\lambda I)v=\left(\begin{array}{cccc}-2c& 1& & \\ 1& \ddots & \ddots & \\ & \ddots & -2c& 1\\ & & 1& -2c\end{array}\right)\left(\begin{array}{c}{v}_1\\ v_2\\ ⋮\\ v_{n-1}\\ v_n\end{array}\right)=\left(\begin{array}{c}-2c{v}_1+v_2\\ v_1-2c{v}_2+v_3\\ ⋮\\ v_{n-2}-2c{v}_{n-1}+v_n\\ v_{n-1}-2c{v}_n\end{array}\right)=0$$

 By introducing $v_0=0,v_{n+1}=0$, the forms come into the same:
$$v_{k-1}-2c{v}_k+v_{k+1}=0,k=1,2,\cdots ,n$$

$$v_{k+1}=2c{v}_k-v_{k-1}$$

two sides subtract $r{v}_k$
$$v_{k+1}-r{v}_k=(2c-r)v_k-v_{k-1}$$

Let $a_k=v_{k+1}-r{v}_k$, to form a geometric progression { a k } \small \{a_k\} {
ak​}, the coefficents must satisfy
$$1:2c-r=-r:-1$$

that’s to say,
$$r^2-2cr+1=0$$

 Denote two roots as $r_1,r_2$, there are
$$r_1+r_2=2c,r_1{r}_2=1$$

It can be induced that if $r_1\ne r_2$, or in other words, $c^2-1\ne 0$,
$$v_k=c_1{r}_1^k+c_2{r}_2^k$$

 If $r_1=r_2=r$,
$$v_k=(c_1+c_{2}k)r^k$$

with $c_1$ and $c_2$ are constants.

 In the first case,
$$v_k=c_1{r}_1^k+c_2{r}_2^k$$

$$v_0=c_1+c_2=0$$

then,
$$v_k=c_1(r_1^k-r_2^k)$$

$$v_{n+1}=c_1(r_1^{n+1}-r_2^{n+1})=0$$

Since $v\ne 0$,
$$r_1^{n+1}=r_2^{n+1}=r_1^{-n-1}\Rightarrow r_1^{2(n+1)}=1$$

so $|r_1|=1$, denote $r_1$ as $e^{i\theta }$, we have
$$v_k=c_1(e^{ik\theta }-e^{-ik\theta })=2c_{1}i\sin (k\theta )$$$$e^{i2(n+1)\theta }=1=e^{i2j\pi }$$

Since $v_k\ne 0$, it can be inferred $k\theta \ne 2m\pi ,m\in Z$, therefore $j\ne 0,n+1$,
$${\theta }_j=\frac{j\pi }{n+1},j=1,2,\cdots ,n$$

Let $c_1=1/2i$, then
$$v_k=\sin (k{\theta }_j)$$

$$V_j=\left(\begin{array}{c}\sin ({\theta }_j)\\ \sin (2{\theta }_j)\\ ⋮\\ \sin ((n-1){\theta }_j)\\ \sin (n{\theta }_j)\end{array}\right)$$

corresponding eigenvalue is
$${\lambda }_j=2c=r_1+r_2=e^{i{\theta }_j}+e^{-i{\theta }_j}=2\cos ({\theta }_j)$$

with
$${\theta }_j=\frac{j\pi }{n+1},j=1,2,\cdots ,n$$
 As for the second case: $r_1=r_2=r=c$,
$$\begin{array}{rl}& v_k=(c_1+c_{2}k)r^k\\ & \Rightarrow v_0=c_1=0\\ & \Rightarrow v_k=c_{2}k{r}^k\\ & \Rightarrow v_{n+1}=c_2(n+1)r^{n+1}=0\end{array}$$

then
$$c_2=0\Rightarrow v_k=0\Rightarrow v=0$$

which is not consistent with $v\ne 0$.

 So the eigenvalues of $T_1$ are
$${\lambda }_j=2\cos (\frac{j\pi }{n+1}),j=1,2,\cdots ,n$$

with corresponding eigenvectors
$$V_j=\left(\begin{array}{c}\sin (\frac{1}{n+1}j\pi )\\ \\ \sin (\frac{2}{n+1}j\pi )\\ ⋮\\ \sin (\frac{n-1}{n+1}j\pi )\\ \\ \sin (\frac{n}{n+1}j\pi )\end{array}\right)$$

It can be easily proved that $V_i^T{V}_j=0,i\ne j.$ (Hint: using Euler’s formula)

 Let $V=(V_1,V_2,\cdots ,V_n),D=diag({\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n)$, we have
$$T_{1}V=VDor{V}^{-1}{T}_{1}V=D$$
 Therefore, the eigenvalues of $M_1$ are
$${\lambda }_j=a+2b\cos (\frac{j\pi }{n+1}),j=1,2,\cdots ,n$$

the eigenvectors are the same as those of $T_1$.

At the moment, story just comes into the half.

 Construct $M_2$ as follow:
$$M_2={\left(\begin{array}{cccc}a& b& & \\ -b& \ddots & \ddots & \\ & \ddots & a& b\\ & & -b& a\end{array}\right)}_{n\times n}=aI+b{T}_2(b\ne 0)$$
$$T_2=\left(\begin{array}{cccc}0& 1& & \\ -1& \ddots & \ddots & \\ & \ddots & 0& 1\\ & & -1& 0\end{array}\right)$$

 The eigenvalues of $T_2$ can be found in the same way.
$${\lambda }_j=2i\cos (\frac{j\pi }{n+1}),j=1,2,\cdots ,n$$

so the eigenvalues of $M_2$ are
$${\lambda }_j=a+i2b\cos (\frac{j\pi }{n+1}),j=1,2,\cdots ,n$$

 At last, consider
$$\begin{array}{rl}M& =\left(\begin{array}{cccc}a& b& & \\ c& \ddots & \ddots & \\ & \ddots & a& b\\ & & c& a\end{array}\right)(b,c\ne 0)\\ & =c\left(\begin{array}{cccc}0& & & \\ 1& \ddots & & \\ & \ddots & 0& \\ & & 1& 0\end{array}\right)+b\left(\begin{array}{cccc}0& 1& & \\ & \ddots & \ddots & \\ & & 0& 1\\ & & & 0\end{array}\right)+aI\end{array}$$

 Let
$$S=diag(1,(\frac{|b|}{|c|}{)}^{1/2},\cdots ,(\frac{|b|}{|c|}{)}^{(n-1)/2})={\left(\begin{array}{cccc}1& & & \\ & (\frac{|b|}{|c|}{)}^{1/2}& & \\ & & \ddots & \\ & & & (\frac{|b|}{|c|}{)}^{(n-1)/2}\end{array}\right)}_{n\times n}$$

then
$$S^{-1}=diag(1,(\frac{|c|}{|b|}{)}^{1/2},\cdots ,(\frac{|c|}{|b|}{)}^{(n-1)/2})={\left(\begin{array}{cccc}1& & & \\ & (\frac{|c|}{|b|}{)}^{1/2}& & \\ & & \ddots & \\ & & & (\frac{|c|}{|b|}{)}^{(n-1)/2}\end{array}\right)}_{n\times n}$$

therefore
$$\begin{array}{rl}SM{S}^{-1}& =cS\left(\begin{array}{cccc}0& & & \\ 1& \ddots & & \\ & \ddots & 0& \\ & & 1& 0\end{array}\right)S^{-1}+bS\left(\begin{array}{cccc}0& 1& & \\ & \ddots & \ddots & \\ & & 0& 1\\ & & & 0\end{array}\right)S^{-1}+aSI{S}^{-1}\\ & \\ & =c\left(\begin{array}{cccc}0& & & \\ (\frac{|b|}{|c|}{)}^{1/2}& \ddots & & \\ & \ddots & 0& \\ & & (\frac{|b|}{|c|}{)}^{1/2}& 0\end{array}\right)+b\left(\begin{array}{cccc}0& (\frac{|c|}{|b|}{)}^{1/2}& & \\ & & & \\ & \ddots & \ddots & \\ & & 0& (\frac{|c|}{|b|}{)}^{1/2}\\ & & & \\ & & & 0\end{array}\right)+aI\\ & \\ & =\text{sgn}(c)\sqrt{|bc|}\left(\begin{array}{cccc}0& & & \\ 1& \ddots & & \\ & \ddots & 0& \\ & & 1& 0\end{array}\right)+\text{sgn}(b)\sqrt{|bc|}\left(\begin{array}{cccc}0& 1& & \\ & \ddots & \ddots & \\ & & 0& 1\\ & & & 0\end{array}\right)+aI\end{array}$$

 If $\text{sgn}(b)=\text{sgn}(c)$, then
$$M_3=SM{S}^{-1}=aI+\text{sgn}(b)\sqrt{bc}\left(\begin{array}{cccc}0& 1& & \\ 1& \ddots & \ddots & \\ & \ddots & 0& 1\\ & & 1& 0\end{array}\right)=aI+\text{sgn}(b)\sqrt{bc}{T}_1$$

so $M\sim M_3$, the eigenvalues of $M$ are the same as the those of $M_3$.

 According to the former part, the eigenvalues of $M_3$ are
$${\lambda }_j=a+2\text{sgn}(b)\sqrt{bc}\cos (\frac{j\pi }{n+1}),j=1,2,\cdots ,n$$
 If $\text{sgn}(b)=-\text{sgn}(c)$, then
$$M_4=SM{S}^{-1}=aI+\text{sgn}(b)\sqrt{-bc}\left(\begin{array}{cccc}0& 1& & \\ -1& \ddots & \ddots & \\ & \ddots & 0& 1\\ & & -1& 0\end{array}\right)=aI+\text{sgn}(b)\sqrt{-bc}{T}_2$$

so $M\sim M_4$, the eigenvalues of $M$ are the same as the those of $M_4$.

$${\lambda }_j=a+i2\text{sgn}(b)\sqrt{-bc}\cos (\frac{j\pi }{n+1}),j=1,2,\cdots ,n$$
 The corresponding eigenvectors can be found by solving

$$(M-{\lambda }_{j}I)v=0$$
Acknowledgements

 Thank Mr. Yang for providing me with some useful materials about Tridiagonal Matrix^[1].

References

 [1]. https://www.math.upenn.edu/~kazdan/AMCS602/tridiag-short.pdf
 [2]. https://en.wikipedia.org/wiki/Tridiagonal_matrix
 [3]. https://en.wikipedia.org/wiki/Toeplitz_matrix