Let $B_n = circ( (d_0, d_1,\cdots,d_{r-1}))$ be a circulant matrix, where $d_0 < d_1 \cdots < d_{r-1}$ are the divisors of $n$. Problem 1: Is it always true that: $\chi_{B_n}(t) = m_{B_n}(t)$ hence the characteristic and minimal polynomial are always the same.
Problem 2: The characteristic polynomial is always separable.
Problem 3: What is the Galois group of $\chi_{B_n}(t)$ over the rationals? (If it is too difficult to give a proof, then a guess is also ok, as long as it is compatible with the empirical data given below.)
Here are some characteristic polynomials for different values of n :
1 t - 1
2 (t - 3) * (t + 1)
3 (t - 4) * (t + 2)
4 (t - 7) * (t^2 + 4*t + 7)
5 (t - 6) * (t + 4)
6 (t - 12) * (t + 4) * (t^2 + 4*t + 20)
7 (t - 8) * (t + 6)
8 (t - 15) * (t + 5) * (t^2 + 6*t + 45)
9 (t - 13) * (t^2 + 10*t + 52)
10 (t - 18) * (t + 6) * (t^2 + 8*t + 80)
11 (t - 12) * (t + 10)
12 (t - 28) * (t + 8) * (t^2 + t + 127) * (t^2 + 13*t + 79)
13 (t - 14) * (t + 12)
14 (t - 24) * (t + 8) * (t^2 + 12*t + 180)
15 (t - 24) * (t + 12) * (t^2 + 8*t + 160)
16 (t - 31) * (t^4 + 26*t^3 + 496*t^2 + 5766*t + 29791)
17 (t - 18) * (t + 16)
18 (t - 39) * (t + 13) * (t^2 + 2*t + 364) * (t^2 + 18*t + 156)
19 (t - 20) * (t + 18)
20 (t - 42) * (t + 12) * (t^2 + 432) * (t^2 + 24*t + 252)
21 (t - 32) * (t + 16) * (t^2 + 12*t + 360)
22 (t - 36) * (t + 12) * (t^2 + 20*t + 500)
23 (t - 24) * (t + 22)
24 (t - 60) * (t + 16) * (t^2 + 16*t + 388) * (t^4 + 20*t^3 + 792*t^2 + 20024*t + 239972)
25 (t - 31) * (t^2 + 28*t + 496)
26 (t - 42) * (t + 14) * (t^2 + 24*t + 720)
27 (t - 40) * (t + 20) * (t^2 + 16*t + 640)
28 (t - 56) * (t + 18) * (t^2 + 972) * (t^2 + 32*t + 448)
Using the theory of circulant matrices I can show, that: $\lambda_j = \sum_{k=0}^{r-1}{d_k \cdot \omega_j^k}$ for $j=0,\cdots,r-1$ are the eigenvalues of $\chi_{B_n}(t)$ where $\omega_j = \exp(\frac{2 \pi I j}{r})$ are $r$-roots of unity. Using this, one can show that $t-\sigma(n)$ is always a divisor of $\chi_{B_n}(t)$.
Edit: On request:
30 $(t - 72) * (t + 22) * (t^2 + 22*t + 650) * (t^4 + 20*t^3 + 1238*t^2 + 38308*t + 542722)$
36 $(t - 91) * (t^2 + 40*t + 763) * (t^6 + 42*t^5 + 3003*t^4 + 139375*t^3 + 4368018*t^2 + 106705623*t + 1248523057)$
48 $(t - 124) * (t + 32) * (t^4 + 3*t^3 + 3794*t^2 + 133632*t + 6044951) * (t^4 + 79*t^3 + 4166*t^2 + 141764*t + 2359631)$