4
$\begingroup$

I have the following matrix arising when I tried to discretize the Green function, now to show the convergence of my algorithm I need to find the eigenvalues of the matrix $G$ and show it has absolute value less than 1 for certain choices of $N$.

Note that the explicit formula for entry $(i,j)$ is $-i(N+1-j)$ when $i\le j$ and it is symmetric, so we can get the formulas for $i>j$ by interchanging $i$ and $j$ in the $i\le j$ case.

Any one has any ideas about how to find the analytical representation of eigenvalues of the matrix $G$, i,e, the eigenvalues represented by $N$? Thank you so much for any help!

$\begin{pmatrix} - N & - N + 1 & -N+2 & -N+3 &\ldots & 1(-2) & 1(-1) \\ - N + 1 & 2( - N + 1) & 2(-N+2) & 2(-N+3) &\ddots & 2(-2) & 2(-1) \\ - N + 2 & 2( - N + 2) & 3(-N+2) & 3(-N+3) &\ddots & 3(-2) & 3(-1) \\ - N + 3 & 2( - N + 3) & 3(-N+3) & 4(-N+3) &\ddots & 4(-2) & 4(-1) \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ - 2 & 2(-2) & 3(-2) & 4(-2) &\ddots & ( - 1 + N)( - 2) & ( - 1 + N)( - 1) \\ - 1 & 2(-1) & 3(-1) & 4(-1) &\ldots & ( - 1 + N)( - 1) & N( - 1) \\ \end{pmatrix}$

$\endgroup$
  • $\begingroup$ Do you just need to prove that the spectral radius is smaller than 1? This may be a much easier problem than finding an analytical expression for the eigenvalues. For instance, since the matrix has all negative entries, you can hope to use Perron-Frobenius theory to bound the maximum eigenvalue. $\endgroup$ – Federico Poloni Aug 22 '18 at 19:44
4
$\begingroup$

It's straightforward to show that this is the inverse of $1/(N+1)$ times the tridiagonal matrix $T_N$ with $-2$ on its main diagonal and $1$ on its super- and sub-diagonals.

Let $t_N$ be the characteristic polynomial of $T_N$. We have $t_0(x)=1$, $t_1(x)=x+2$, and by cofactor expansion $t_N(x)=(x+2)t_{N-1}(x)-t_{N-2}(x)$. That is, $t_N$ is related to the Chebyshev polynomials of the second kind by $t_N(x)=U_N(x/2+1)$. The roots of the Chebyshev polynomials are $\cos(\frac{k\pi}{N+1})$ for $k=1,\dots,N$, so the eigenvalues of the inverse of your $G$ are $\frac{2}{N+1}(\cos(\frac{k\pi}{N+1})-1)$. These have absolute value less than $1$ for $N\ge 3$.

$\endgroup$
  • $\begingroup$ This is such a brilliant idea! Thank you so much! $\endgroup$ – Sherry Aug 22 '18 at 21:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.