I'm reading Ankur Moitra's excellent lectures notes at http://people.csail.mit.edu/moitra/docs/bookex.pdf .
In Chapter4, the notes claim that a certain circulant matrix of fourier coefficients is invertible [left as exercise to reader, and I can't find the footnote]. I can not prove it. I'm also not convinced it's true. The pages are attached. Any pointers as to what I should read up on would be helpful.
EDIT: Images are high resolution. Click "open image in new tab".