By the circulant matrix $C$ in $M\_n(\mathbb{R})$, we mean that
$$C=[e\_n|e\_1|\cdots|e\_{n-1}]$$ where $e\_1,\cdots,e\_n$ are the standard basis vectors in $\mathbb{R}^n$. It is well-known that  

$$C=\mathbf{F}\operatorname{Diag}(1,w,\cdots,w^{n-1})\mathbf{F}^{-1}$$
where $\mathbf{F}$ is just the discrete Fourier matrix and $w=\exp(\frac{2\pi i}{n})$


Let $U=(u\_{ij})$ be a upper triangular matrix. We say it is supper upper triangular if $u\_{i, i+1}=0$.


Let $U$ be a supper upper triangular whose entries are either 0 or 1.
Is $C+U$ diagonalizable?



Is the sum of the circulant matrix with a super upper triangular matrix diagonalizable?
Here's a counterexample: For $U$ take
$\left(\begin{smallmatrix}
0& 0 &0& 0& 1& 1& 1& 1\\
0& 0 &0 &1& 0& 1& 1& 1\\
0& 0 &0& 0& 1& 0& 0& 1\\
0& 0 &0& 0& 0& 0& 0& 1\\
0& 0 &0& 0& 0& 0& 1& 0\\
0& 0 &0& 0& 0& 0& 0& 0\\
0& 0 &0& 0& 0& 0& 0& 0\\
0& 0 &0& 0& 0& 0& 0& 0
\end{smallmatrix}\right)$.


Then the rational canonical form of $C+U$ is
$\left(\begin{smallmatrix}
-1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
 0 &-1& 0 & 0 & 0 & 0 & 0 & 0\\
 0 &0 & 0 & 1 & 0 & 0 & 0 & 0\\
 0 &0 & 0 & 0 & 1 & 0 & 0 & 0\\
 0 &0 & 0 & 0 & 0 & 1 & 0 & 0\\
 0 &0 & 0 & 0 & 0 & 0 & 1 & 0\\
 0 &0 & 0 & 0 & 0 & 0 & 0 & 1\\
 0 &0 & 1 & 1 & -1 & 4& -2 & 2
\end{smallmatrix}\right)$


