Finding eigenvalues in almost tridiagonal matrix

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?

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).