Find $\sum\limits_{k=0}^{n-1}\,\omega_n^{k^2\ell}$, where $\omega_n:=\exp\left(\frac{2\pi\text{i}}{n}\right)$.
Solution 1:
I found a very nice paper on the subject, using only elementary linear algebra to prove the statements you mention about the Gauss sum value and the multiplicities of the eigenvalues as you calculated them (although none of the explicit formula you mention are supplied in the document, it is easy to derive these from the information in the paper).
See https://mast.queensu.ca/~murty/quadratic2.pdf.
Note that the '(inverse) discrete Fourier transform matrix A' you mention is equivalent to the matrix used in the article (by changing the order of the base vectors).