is there an established name for the property that a square matrix can be made symmetric by permutation of its columns?


Is it possible to recognize those kind of matrices efficiently?



Name for a matrices having a specific property
Here is a suggestion (not an answer) for the second question, at least for real matrices $A$: Suppose that there is a permutation matrix $P$ such that $(AP)^{T} = AP.$
Then $(AP)^{2} = (AP)(AP)^{T} = AA^{T}$, so that $AP$ is a symmetric square root of the positive semidefinite (symmetric) matrix $AA^{T}$. If the non-zero eigenvalues of $AA^{T}$ are all of algebraic multiplicity one, then there are $2^{r}$ real symmetric square roots of $AA^{T}$, where $r$ is the rank of $A$. This is basically a matter of finding an orthonormal basis of (real) eigenvectors for $AA^{T}$.


In view of comments, let me explain further: For exposition's sake, consider the case where $A$ has full rank $n$ and $AA^{T}$ has no non-zero eigenvalue of multiplicity greater than one. After finding an orthonormal basis of (real) eigenvectors for $AA^{T}$, we have an orthogonal real matrix $U$ such that $UAA^{T}U^{T}$ is diagonal. Then $UAA^{T}U^{T}$ has $2^{n}$ symmmetric square roots, all of which are diagonal. If $Q$ is one of these, then $Q^{\prime} = U^{T}QU$ is a symmetric square root of $AA^{T}$, and each symmetric square root of $AA^{T}$ arises in this way. Hence there is such a permutation matrix $P$ with $AP$ symmetric if and only if one (or more) of the $Q^{\prime}$ as above is such that $A^{-1}Q^{\prime}$ is a permutation matrix.


If $A$ has rank $r <n$, but $AA^{T}$ does not have any non-zero eigenvalue of algebraic multiplicity greater than one, then $AA^{T}$ has $2^{r}$ real symmetric square roots $Q^{\prime}$ , and we need to inspect whether any of these $2^{r}$ choices of $Q^{\prime}$ has the same columns as $A$, simply permuted around.


If $AA^{T}$ has a non-zero eigenvalue of algebraic multiplicity greater than one, then this strategy will not work as it stands.


