I am trying to proof that the inverse of a circulant matrix is also circulant and had figured the best way to do it would be using the diagonalisation:
$$ \begin{align*} C^{-1} &= (\frac{1}{n} F_{n}^{-1} diag(F_{n}c) F_{n})^{-1}\\ C^{-1} &= n F_{n}^{-1} diag(F_{n}c)^{-1} F_{n} \end{align*} $$ However I don't see how I can make proof or confirm that $n F_{n}^{-1} diag(F_{n}c)^{-1} F_{n}$ is circulant?
I beg to differ. The easiest proof in my opinion is as follows. Let $P$ be the cyclic shift matrix. If $C$ is circulant, it is a polynomial in $P$. However, by Cayley-Hamilton theorem, $C^{-1}$ is a polynomial in $C$. Consequently, $C^{-1}$ is a polynomial in $P$. Hence $C^{-1}$ is circulant.
The characterisation of circulant matrices as polynomials in $P$ is actually a very basic and essential fact. It explains not only why the inverse of a circulant matrix is circulant, but also why all complex circulant matrices are diagonalisable and share the same orthonormal eigenbasis: since $P$ is a permutation matrix, it is normal and unitarily diagonalisable as $UDU^\ast$; if we write a circulant matrix $C$ as $f(P)$ for some polynomial $f$, then $Uf(D)U^\ast$ is a unitary diagoalisation of $C$.