Measuring real square matrix's deviation from being circulant? What metrics or measurements exist for determining how much a (real square) matrix deviates from being circulant?
 A: One that pops into mind is to compute the distance of a given matrix to the linear subspace of circulant matrices.
Let $\mathcal{C}$ be the set of circulant matrices. Let $P_\mathcal{C}$ be the projection onto that set, that is:
$$
P_\mathcal{C}(\mathbf{A}) = \underset{\mathbf{C}\in\mathcal{C}}{\textrm{min}} 
\,\,||\mathbf{C}-\mathbf{A}||
$$
Where $\mathbf{C}$ is a circulant matrix (borrowing Wikipedia's LaTeX):
$$\mathbf{C}=\begin{bmatrix}
c_0      & c_{n-1} & \cdots  & c_2     & c_1     \\
c_1      & c_0     & c_{n-1} &         & c_2     \\
\vdots   & c_1     & c_0     & \ddots  & \vdots  \\
c_{n-2}  &         & \ddots  & \ddots  & c_{n-1} \\
c_{n-1}  & c_{n-2} & \cdots  & c_1     & c_0     \\
\end{bmatrix}$$
For the F norm, the minimizing $\mathbf{C}$, denoted $\hat{\mathbf{C}}$, will have as entries the mean of all of $\mathbf{A}$'s entries corresponding to a given $c_i$. For example, $\hat{c}_0 = \frac{1}{N}\sum_{i=1}^N A_{i,i}$, $\hat{c}_1 = \frac{1}{N-1}\sum_{i=1}^{N-1} A_{i+1,i} + \frac{1}{N}A_{1,N}$, and so on.
Then we can denote the deviation from the set of circulant matrices as $\Vert\mathbf{A}-P_\mathbf{C}(\mathbf{A})\Vert_F$.
