4
$\begingroup$

I need to find the eigenvalues of an $n\times n$ symmetric tridiagonal matrix $A$, except it has $1$s on $A_{1n}$ and $A_{n1}$. The diagonal entries are all $4$, while superdiagonal and subdiagonal entries are all $1$.

$$A=\pmatrix{ 4&1&&&&&&1\\ 1&4&1&&&&&\\ &1&4&1&&&&\\ &&1&4&\ddots&&&\\ &&&1&\ddots&1&&\\ &&&&\ddots&4&1&\\ &&&&&1&4&1\\ 1&&&&&&1&4\\ }$$

If there were zeroes in the corners $A_{1n}$ and $A_{n1}$, I would use the formula:

$$ a - 2 \sqrt{bc} \, \cos(k \pi / {(n+1)}),$$

for $k=1,...,n$. But how can I find eigenvalues in this case?

$\endgroup$
  • 3
    $\begingroup$ en.wikipedia.org/wiki/Circulant_matrix $\endgroup$ – Semiclassical Oct 17 '17 at 21:03
  • $\begingroup$ I have reorganized the presentation of the solution in order to proceed in a straightforward way to the result and "reject" the example and the DFT construction as (important) Annexes. $\endgroup$ – Jean Marie Oct 18 '17 at 6:44
6
$\begingroup$

For further reference, taking $a=4,b=c=1$ in your formula (given in (https://en.wikipedia.org/wiki/Tridiagonal_matrix)), the eigenvalues of tridiagonal matrix $A'$ being obtained from $A$ by setting $A'_{n1}=A'_{1n}=0$, are:

$$\tag{*}\mu_k=4 + 2 \cos(\tfrac{2\pi k}{n+1})\ \ \ \ \text{for} \ \ \ \ k=1,\cdots n.$$

$A$, being a circulant matrix [with circulant "message" $410...01$ associated with polynomial $f(x):=4+1x+1x^{n-1}$], has the following eigenvalues:

$$\tag{1}\lambda_k=f(\omega_k) \ \ \text{where} \ \ \omega_k=\exp(\tfrac{2 i\pi k}{n}) \ \ \text{(k - th root of unity)}$$

(see (https://en.wikipedia.org/wiki/Circulant_matrix)).

$$\lambda_k=4 + 1 \omega_k+ 1 (\omega_k)^{n-1}=4+\exp(\tfrac{2 i\pi k}{n})+\exp(\tfrac{2 i\pi k (n-1)}{n})=4+\exp(\tfrac{2 i\pi k}{n})+\exp(\tfrac{-2 i\pi k}{n}).$$

Thus

$$\tag{2}\lambda_k=4 + 2 \cos(\tfrac{2\pi k}{n})\ \ \ \ \text{for} \ \ \ \ k=0,1,\cdots n-1.$$

A striking fact is that formula (2) is almost identical to formula (*), except that denominators $n+1$ have been replaced by denominators $n$.

Thus, for large values of $n$, the induced perturbation is small...

Nice, isn't it ?

Let us now give an example and show that all this can be considered in connection with the Discrete Fourier Transform (DFT).


An example: If $n=4$, matrix

$$A=\begin{pmatrix}4 & 1 & 0 & 1 \\ 1 & 4 & 1 & 0 \\ 0 & 1 & 4 & 1\\ 1 & 0 & 1 & 4 \end{pmatrix}$$

has eigenvalues

$$\lambda_0=6,\lambda_1=4,\lambda_2=2,\lambda_3=4$$

that comply with formulas (2).

A connection with the Discrete Fourier Transform (DFT).

Let us proceed with the same example. The DFT of "message" $V=(1,4,1,0)$ is given by a matrix-vector multiplication, with the Fourier matrix whose coefficients are:

$$\tag{3}F_{KL}=e^{f KL} \ \ \text{with} \ \ f :=- i \tfrac{2\pi}{n}, \ \text{here with} \ n=4.$$

(please note the minus sign), i.e.,

$ \underbrace{\begin{pmatrix} e^{f0\times0} & e^{f0\times1} & e^{f0\times2} & e^{f0\times3} \\ e^{f1\times0} & e^{f1\times1} & e^{f1\times2} & e^{f1\times3} \\ e^{f2\times0} & e^{f2\times1} & e^{f2\times2} & e^{f2\times3} \\ e^{f3\times0} & e^{f3\times1} & e^{f3\times2} & e^{f3\times3} \end{pmatrix}}_{F}$ $\begin{pmatrix}1 \\ 4\\ 1\\ 0 \end{pmatrix}= \left(\begin{array}{rrrr}1 & 1 & 1 & 1 \\ 1 & -i & -1 & i \\ 1 & -1 & 1 & -1 \\ 1 & i & -1 & -i \\ \end{array}\right) \begin{pmatrix}4 \\ 1\\ 0\\ 1 \end{pmatrix}=\begin{pmatrix}6 \\ 4\\ 2\\ 4 \end{pmatrix}$

finding back in this way the eigenvalues given above.

This example can be extended to an $n \times n$ matrix $A$, where the matrix-vector multiplication shown above is equivalent to the linear combination

$$\tag{4}4F_0+1F_1+1F_{n-1}$$

(where $F_k$ is the $k$th column of $F$). And we find back expression (2).

For a little more about the connection with Fourier Transform, see the answer to this question (Circulant matrix : eigenvector).

$\endgroup$

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.