Why are almost all prime sized circulant matrices non-singular? Consider an $n$ by $n$ circulant matrix whose values are either $1$ or $0$. Now let $n$ be a prime. For any such $n$ there are exactly two circulant matrices that are singular (over $\mathbb{R}$). The all zero and the all one matrix. 
Why is this?
 A: Assume $p$ is an odd prime.  Consider the Leibniz formula for the determinant $$\det(A)=\sum_{\sigma \in S_p} \mathrm{sgn}(\sigma) \prod_{i=1}^p A_{i\sigma(i)}$$ modulo $p$.
Consider the contributions to the formula by the permutations highlighted below, formed by cyclically rotation the first permutation diagonally:

Since the matrix is circulant, the entries in the colored cells remain the same.  Further, since $p$ is odd, the sign of the permutation remains the same (we're multiplying it by the even permutation $(12\cdots p)^k$).
Hence the combined contribution of these permutations is divisible by $p$, except in the cases such as:

where cyclic rotation diagonally leaves set of the cells unchanged.  In these cases, we get a contribution of $+1$ if those cells contain $1$s and a contribution of $0$ if those cells contain a $0$.
Hence $$\det(A) \equiv \text{number of broken diagonals containing 1s} \pmod p$$ and since the number of broken diagonals containing 1s is between $0$ and $p$, this congruence can only be zero (and hence $\det(A)$ can only be zero) for the all-0 and all-1 matrices.
A: The eigenvalues of the circulant matrix are the linear combinations of $p$'th roots of unity. If you have such a combination that is zero $a_0+a_1\omega+...+a_{p-1}\omega_{p-1}=0$ ($a_i$ are coefficients of the matrix) then applying the galois group elements $\sigma$ you will $a_0+a_1\omega
'+...+a_{p-1}(\omega')^{p-1}$ for all roots of unity $\omega'$. 
Consider the polynomial $p(x)=a_0+a_1x+...+a_{p-1}x^{p-1}$. From the above we have $1+x+...+x^{p-1}|p(x)$. This means that either all $a_i$ are $0$ or all $1$.
