matrices - Eigenvalue Decomposition of a Triadiagonal Matrix

I need to compute explicitly an eigenvalue decomposition of the following $N\times N$ tridiagonal matrix,

$T = \left[ {\begin{array}{*{20}{c}} { - 2\left( {\frac{1}{{{h^2}}} + \frac{1}{{{k^2}}}} \right)}&{\frac{1}{{{h^2}}}}&{}&{}&{}\\ {\frac{1}{{{h^2}}}}&{ - 2\left( {\frac{1}{{{h^2}}} + \frac{1}{{{k^2}}}} \right)}&{\frac{1}{{{h^2}}}}&{}&{}\\ {}& \ddots & \ddots & \ddots &{}\\ {}&{}&{\frac{1}{{{h^2}}}}&{ - 2\left( {\frac{1}{{{h^2}}} + \frac{1}{{{k^2}}}} \right)}&{\frac{1}{{{h^2}}}}\\ {}&{}&{}&{\frac{1}{{{h^2}}}}&{ - 2\left( {\frac{1}{{{h^2}}} + \frac{1}{{{k^2}}}} \right)} \end{array}} \right]$

which appears in solving Poisson problem numerically on rectangular uniform mesh in two dimensional space.

I know $T$ is a Toeplitz matrix. Hence eigenvalues of $T$ are

${\lambda _i}\left( T \right) = - 2\left( {\frac{1}{{{h^2}}} + \frac{1}{{{k^2}}}} \right) + \frac{2}{{{h^2}}}\cos \frac{{i\pi }}{{N + 1}},i = 1,2, \ldots ,N$

and the corresponding eigenvectors of $T$ are

$\begin{array}{l} {x_i} = {\left[ {{x_{i,1}},{x_{i,2}}, \ldots ,{x_{i,N}}} \right]^T},i = 1,2, \ldots ,N\\ {x_{i,j}} = \sin \frac{{ij\pi }}{{N + 1}},i = 1:N,j = 1:N \end{array}$

1. I now need to compute the inverse of $X = \left\{ {\sin \frac{{ij\pi }}{{N + 1}}} \right\}_{i,j = 1}^N$ to obtain an eigenvalue decomposition of $T$. How can I compute this $X^{-1}$?

2. I also notice that $T$ is normal. Hence, it has an singular value decomposition as the form $T = Udia{g_{{N}}}\left\{ {{\lambda _i}\left( {{T_N}} \right)} \right\}{U^*}$, where $U$ is unitary. How can I find this $U$?

Thank in advanced.

Answer

We have $X^{-1}=\frac{2}{N+1}X$.

If $u\neq v$, $\left< x_u,x_v\right>=\sum_{i=1}^N \sin(\frac{ui\pi}{N+1})\sin(\frac{vi\pi}{N+1})$.

$\sin(a)\sin(b)=\frac{1}{2}(\cos(a-b)-\cos(a+b))$.

So $\left< x_u,x_v\right>=\frac{1}{2}\sum_{i=1}^N \left(\cos(\frac{(u-v)i\pi}{N+1})-\cos(\frac{(u+v)i\pi}{N+1})\right)$.

$\cos(0)+\sum_{i=1}^N\cos(\frac{(u-v)i\pi}{N+1})=\sum_{i=0}^N\cos(\frac{(u-v)i\pi}{N+1})=0$ because $-2(N+1)

$\cos(0)+\sum_{i=1}^N\cos(\frac{(u+v)i\pi}{N+1})=\sum_{i=0}^N\cos(\frac{(u+v)i\pi}{N+1})=0$ because $0

So $\left< x_u,x_v\right>=0$.

$\left< x_u,x_u\right>=\frac{1}{2}\sum_{i=1}^N \left(\cos(0)-\cos(\frac{2ui\pi}{N+1})\right)=\frac{1}{2}(N+1)$ because $0<2u<2(N+1)$.

So $X^*X=\frac{1}{2}(N+1)I_N$.

But $X^*=X$. So $X^{-1}=\frac{2}{N+1}X$.