Circulant matrices are very useful in digital image processing. I found the general formula for determinant of circulant matrix. But I think it is not suitable for block-circulant matrices.
For example, consider the formula for $\det(K)$,
where $$K = \left(\begin{array}{cccc} A & B & C & D \\ D & A & B & C \\ C & D & A & B \\ B & C & D & A \end{array}\right) $$
and $A$ , $B$ , $C$ and $D$ are size $n \times n$.
The formula for the specific case is $$\det K=\det(A+B+C+D)\det(A-B+C-D)\det(A+iB-C-iD)\det(A-iB-C+iD).$$ More generally, for a block-circulant matrix with $n$ square blocks $A_0,\ldots,A_{n-1}$, the formula is $$\det K=\prod_{\omega^n=1}\det(A_0+\omega A_1+\cdots+\omega^{n-1}A_{n-1}).$$ To see this, observe that $K$ is block-diagonalisable, $$K=U^*{\rm diag}(A_0+\alpha A_1+\cdots+\alpha^{n-1}A_{n-1},A_0+\alpha^2 A_1+\cdots+\alpha^{2(n-1)}A_{n-1},\ldots)U$$ where $\alpha=\exp\frac{2i\pi}n$ and $$U=\frac1{\sqrt n}((\alpha^{(i-1)(j-1)}I_d))_{1\le i,j\le n}.$$ Hereabove, the blocks $A_j$ are $d\times d$. This shows the formula, up to the factor $|\det U|^2$, which is easily seen to be equal to $1$.
