inverse of a circulant matrix If c(x) is a circulant matrix of a vector x, is it always true that 
$c(x)^{-1}=\mathcal{F}^{-1}(\mathcal{F}(1/x))$? How can we prove it?
In this case $c(x)^{-1}$ is the inverse of the circulant matrix of vector x, $\mathcal{F}(x)$ represent the fourier transform while $\mathcal{F}^{-1}$ is the fourier inverse. The division in $1/x$ is performed element wise (in matlab it is written as "1./x").
 A: Let $\mathcal{C}(\mathbf{x}) \in \mathbb{C}^{N\times N}$ denote the circulant matrix generated by $\mathbf{x} \in \mathbb{C}^N$ (with $\mathbf{x}$ as its first column). Finding eigenvalues/eigenvectors for $\mathcal{C}(\mathbf{x})$ shows that the latter can be written as
\begin{equation}
\mathcal{C}(\mathbf{x}) = \mathbf{F}_N^H\mathcal{D}(\sqrt{N}\mathbf{F}_N\mathbf{x})\mathbf{F}_N,
\end{equation}
where $\mathbf{F}_N \in \mathbb{C}^{N\times N}$ is the unitary DFT matrix, i.e., $[\mathbf{F}_N]_{n,k}=\frac{1}{\sqrt{N}}e^{-i 2\pi k n /N}$, $(\cdot)^H$ denotes hermitian traspose, and $\mathcal{D}(\mathbf{z})$ is the diagonal matrix with main diagonal elements given by $\mathbf{z}$. 
Note that $\sqrt{N}\mathbf{F}_N\mathbf{x}$ is equal to matlab's "fft($\mathbf{x}$)" and $(1/\sqrt{N})\mathbf{F}_N^H\mathbf{x}$ is equal to matlab's "ifft($\mathbf{x}$)" and the above decomposition essentially states that compuation of $\mathcal{C}(\mathbf{x})\mathbf{y}$ is equivalent to "ifft(fft(x).*fft(y))", i.e., (circular) convolution in time domain corresponds to multiplication in (discrete) frequency domain.
Now, if  $\sqrt{N}\mathbf{F}_N\mathbf{x}$ does not have a zero element, then $\mathcal{D}(\sqrt{N}\mathbf{F}_N\mathbf{x})$ is invertible, therefore, 
\begin{align}
\mathcal{C}^{-1}(\mathbf{x}) &= \left(\mathbf{F}_N^H \mathcal{D}(\sqrt{N}\mathbf{F}_N\mathbf{x})\mathbf{F}_N\right)^{-1} \\
 &= \mathbf{F}_N^{-1} \mathcal{D}^{-1}(\sqrt{N}\mathbf{F}_N\mathbf{x})(\mathbf{F}_N^{H})^{-1} \\
 &= \mathbf{F}_N^{H} \mathcal{D}^{-1}(\sqrt{N}\mathbf{F}_N\mathbf{x})\mathbf{F}_N\\
\end{align}
which implies that $\mathcal{C}^{-1}(\mathbf{x})\mathbf{y}$ can be computed as 
"ifft(fff(y)./fft(x))".
