For a matrix with eigenvalues the k-roots of unity, will we be sure to have it block-similar to a k size circulant generator matrix $\bf C_4$:
$${\bf C}_4 = \left[\begin{array}{cccc}0&1&0&0\\0&0&1&0\\0&0&0&1\\1&0&0&0\end{array}\right]$$
I have managed to do the opposite, randomizing 4x4 $\bf V$ transform matrix, and then calculated
$$\text{eig}({\bf VC_4V}^{-1})$$
giving me the eigenvalues (from Gnu Octave)
$$\left[\begin{array}{cccc}1+0i&-10^{-15}+1i&10^{-15}-1i&-0.999999999999999+0i\end{array}\right]$$
which seems very close to $[1,i,-1,-i]$ given double precision having been used.
Will this work in general and the other way around?
i.e. if we find matrix $\bf A$ has $$\lambda_k = \exp\left(\frac{-2\pi ik}{n}\right), \forall k \in[1,n]$$
Are we sure we can find a $\bf V$ so that : $\bf {A = VC_nV}^{-1}$
If an $n \times n$ complex matrix has $n$ distinct eigenvalues $\lambda_1, \ldots, \lambda_n$, we know that it is similar to the diagonal matrix $\mathrm{diag}(\lambda_1, \ldots, \lambda_n)$. Hence any two $n \times n$ matrices with the distinct eigenvalues $\lambda_1, \ldots, \lambda_n$ will be similar. So your problem is equivalent to asking whether the $n \times n$ circulant matrix $C_n$ has eigenvalues given by $\mathrm{exp}(2 \pi i k / n)$ for $k \in \{1, \ldots, n\}$. And this should be easy to check, since the eigenvectors have a nice form as powers of $n$th roots of unity.