Since $H$ is a circulant matrix, the decomposition using Fourier transform matrix $F$
$$H = F^{-1} \Lambda F$$
where $\Lambda$ is the diagonal matrix with the eigenvalues of $H$. If I plug in the decomposition of $H$ into $H^T H$, I get
$$H^T H = F^{T} \Lambda(F^{-1})^{T}F^{-1}\Lambda F$$
I have seen somewhere that this simply equals to $F^{-1}\Lambda^{2}F$. Is this true? Why?
If the matrix $H$ is real, then the tranpose of $H$, $H^T$, is the same as the conjugate transpose of $H$, $H^*$. (The notation $H^H$ is also used, but we already have one $H$ running around.) The Fourier matrix $F$ is unitary, so $F^* = F^{-1}$. Thus
$$H^TH = H^*H = F^*\Lambda^* (F^{-1})^*F^{-1}\Lambda F = F^*\Lambda^* (F^*)^*F^{-1}\Lambda F = F^*\Lambda^* FF^{-1}\Lambda F = F^{-1}\Lambda^* I\Lambda F = F^{-1}\Lambda^*\Lambda F.$$
If the entries of $\Lambda$ are real, then $\Lambda^* = \Lambda$ and you recover the formula you proposed $H^TH = F^{-1}\Lambda^2F$. In general, if $\Lambda$ has complex entries, this formula may fail to hold.