I have a $N\times N$ symmetric matrix ${\bf A}$ containing only entries in $\{0, 1\}$.
Is there a method to find two matrices ${\bf A}^*$ and ${\bf B}$ with entries in $\{0, 1\}$ such that:
- ${\bf B}$ is circulant;
- $\forall i,j : {\bf A}^*_{ij} \leq {\bf B}_{ij}$;
- $\| {\bf B} - {\bf A}^*\|_1$ is minimal;
where ${\bf A}^*$ is a permutation of rows/columns of ${\bf A}$?
Let us consider an example. The following matrix is given:
${\bf A} = \begin{pmatrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0\end{pmatrix}$
There exists a permutation ${\bf A}^*$ of the rows/columns of ${\bf A}$ as follows:
${\bf A}^* = \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0\end{pmatrix}$
Such that the following matrix ${\bf B}$ is circulant:
${\bf B} = \begin{pmatrix} 0 & 1 & 0 & 0 & \color{red}{1} \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ \color{red}{1} & 0 & 0 & 1 & 0\end{pmatrix}$
In that case, we have $\| {\bf B} - {\bf A}^*\|_1 = 2$, which is the minimum for all possible permutation ${\bf A}^*$.