Q:

Eigenvalues and eigenvectors for a quasi-circulant matrix

Related to this question:
 here
There is a well-known closed form expression for eigenvalues and eigenvectors of a circulant matrix. For example, see Wikipedia 
https://en.wikipedia.org/wiki/Circulant_matrix. 
Let us have an $n\times n$ matrix $A$ of a special kind: 
  all of its entries are equal to $r$, $0 < r < 1$, except the diagonal entries: the first $k$ entries are  $1+ \tau^2$, for some given $\tau$, and the last $n-k$ entries are all $1$.
Is there a closed form expression for eigenvalues and eigenvecotrs of $A$? 
For example, can the Fourier transform approach that works for circulant matrices be extended for this example? 
As an example, let 
 $$A = \left[ \begin{array}[ccc] \\
 1.5 & 0.2 & 0.2 \\  0.2  & 1 & 0.2 \\ 0.2 & 0.2 & 1 \end{array} \right]$$

A:

Let's generalize the problem: what are eigenvalues/eigenvectors of the matrix
$$A = ree^T + 
\begin{pmatrix}
a & &   \\
& \ddots&  \\
 & & a \\
& & & b & &   \\
& & & & \ddots&  \\
& & & & & b \\
\end{pmatrix}$$
if $0<r<1$? (in your case, $a = 1+\tau^2-r$ and $b = 1-r$)
If $a=b$ then we know that the eigenvalues are only $n$, associated with the eigenvector $e$,  and the eigenvalues $a$ with multiplicity $n-1$, assiociated with the eigenvectors
$$
\begin{pmatrix}
1\\
-1\\
0\\
\vdots
\end{pmatrix}
\begin{pmatrix}
0 \\
1\\
-1\\
\vdots
\end{pmatrix}
\dots
$$
In the case $a\ne b$, we have $k-1$ eigenvectors for the eigenvalue $a$ and other $n-k-1$ eigenvectors for the eigenvalue $b$ given by
 $$
\begin{pmatrix}
1\\
-1\\
0\\
\vdots\\
\hline
0\\
0\\
0\\
\vdots
\end{pmatrix}\begin{pmatrix}
0\\
1\\
-1\\
\vdots\\
\hline
0\\
0\\
0\\
\vdots
\end{pmatrix}\dots
\qquad
\begin{pmatrix}
0\\
0\\
0\\
\vdots
\\
\hline
1\\
-1\\
0\\
\vdots
\end{pmatrix}\begin{pmatrix}
0\\
0\\
0\\
\vdots
\\
\hline
0\\
1\\
-1\\
\vdots
\end{pmatrix}\dots
$$
Let's call $v$ an other eigenvector associated with the eigenvalue $\lambda$, that is different from $a$ and $b$. It must satisfy
$$
v_1 = v_2 = \dots = v_k = \frac{r\sum v_i}{\lambda -a}
$$
$$
v_{k+1} = v_{k+2} = \dots = v_n = \frac{r\sum v_i}{\lambda -b}
$$
so $\sum v_i$ must be different from 0, and this implies that all the $v_i$ must be non-zero. We thus set $v_1 = 1$ and carry out the calculation, finding that
$$ V := \sum v_i = \frac{nt+b-a\pm\sqrt{(a-b-nr)^2-4rk(b-a)}}{2r}$$
$$ \lambda = rV +a = \frac{nt+b+a\pm\sqrt{(a-b-nr)^2-4rk(b-a)}}{2}$$
so these are the remaining two eigenvalues, and their eigenvectors are
$$
\begin{pmatrix}
\lambda-b\\
\lambda-b\\
\lambda-b\\
\vdots
\\
\hline
\lambda-a\\
\lambda-a\\
\lambda-a\\
\vdots
\end{pmatrix}
$$

