Is there a sound proof of or a counter example to the following conjecture:



> 
> if $\boldsymbol{A}^T=\boldsymbol{A}$ is the cost-matrix of a bipartite assignment problem with unique optimal assignment,  
> 
> then the symmetry carries over to the solution, i.e., $$i\mapsto j\iff j\mapsto i$$ in the optimal assignment.
> 
> 
> 



Symmetry of optimal solutions to symmetric assignment problems
$\newcommand\si\sigma$Yes, this is true. Indeed, write $A=(a\_{i,j}\colon i\in[n],j\in[n])$, where $[n]:=\{1,\dots,n\}$, so that $a\_{i,j}=a\_{j,i}$ for all $i,j$ in $[n]$. The cost of an assignment $\si\in S\_n$ (where $S\_n$ is the symmetric group acting on $[n]$) is
$$c(\si):=\sum\_{i\in[n]}a\_{i,\si(i)}.$$
Since $A$ is symmetric, for each $\si\in S\_n$ we have
$$c(\si^{-1})=\sum\_{i\in[n]}a\_{i,\si^{-1}(i)}
=\sum\_{j\in[n]}a\_{\si(j),j}=\sum\_{j\in[n]}a\_{j,\si(j)}=c(\si).$$


So, if a permutation $\pi$ is an optimal assignment, then $\pi^{-1}$ is also optimal. Since the optimal assignment is assumed to be unique, we have $\pi^{-1}=\pi$, so that $\pi$ is an involution, as claimed: $j=\pi(i)\iff i=\pi(j)$ for all $i,j$ in $[n]$.


