# Finding a symmetric adjacency matrix closest to a given (non-symmetric) adjacency matrix

I am trying to solve a problem on graphs, which I have reduced to the following optimization problem in matrix $$X \in \{0,1\}^{n \times n}$$

$$\begin{array}{ll} \text{minimize} & \| X - A \|_F^2\\ \text{subject to} & X 1_n = m 1_n\\ & X=X^\top\end{array}$$

where matrix $$A \in \{0,1\}^{n \times n}$$ is given. Matrix $$X$$ is the adjacency matrix of a non-directed $$m$$-regular graph, while matrix $$A$$ is the adjacency matrix of a directed graph.

I am quite clueless on how to go on solving this problem and would be happy to get a direction.

• Are all those conditions saying that $X$ is adjacency matrix or am I missing some subtlety there? – Radost Jun 4 at 9:59
• X is an adjacency matrix for a non directed graph, where each vertex is of rank m. While the input A is an adjacency matrix of a directed graph. – Jonathan Jun 4 at 10:08
• Thanks, that's much clearer! – Radost Jun 4 at 10:08
• I'm guessing $||.||_F$ is Frobenius norm. And the min has to be taken along the undirected graph otherwise the obvious solution would be $X=A$. – Radost Jun 4 at 10:11
• The norm is Frobenius. As for the second observation, $X=A$ would also not hold the constraint of the row sums, as we have no information about them in A. – Jonathan Jun 4 at 10:15

We have the following optimization problem in matrix $$\mathrm X \in \{0,1\}^{n \times n}$$

$$\begin{array}{ll} \text{minimize} & \| \mathrm X - \mathrm A \|_{\text{F}}^2\\ \text{subject to} & \mathrm X 1_n = m 1_n\\ & \mathrm X = \mathrm X^\top\\ & \mathrm X \in \{0,1\}^{n \times n}\end{array}$$

where matrix $$\mathrm A \in \{0,1\}^{n \times n}$$ is given. Note that

$$\| \mathrm X - \mathrm A \|_{\text{F}}^2 = \| \mathrm X \|_{\text{F}}^2 - 2 \langle \mathrm A, \mathrm X \rangle + \| \mathrm A \|_{\text{F}}^2$$

and that $$\| \mathrm X \|_{\text{F}}^2 = m n$$, due to the constraints. Hence, we have the following integer program (IP)

$$\begin{array}{ll} \text{maximize} & \langle \mathrm A, \mathrm X \rangle\\ \text{subject to} & \mathrm X 1_n = m 1_n\\ & \mathrm X = \mathrm X^\top\\ & \mathrm X \in \{0,1\}^{n \times n}\end{array}$$

which appears to be a generalization of the assignment problem. Perhaps there is a generalization of the Hungarian algorithm, too.