# Name for a matrices having a specific property

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?

• If the permutation matrix $P$ is an exchange matrix, then a square matrix $A$ such that $AP=(AP)^T$ is called persymmetric (see arxiv.org/abs/1007.3239) Jul 6 '20 at 13:46

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 , 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.

• Nice. I understand that $AA^T=UDQQ^TDU^T$ where $U$ is a real unitary matrix, $D$ is a real diagonal matrix with distinct diagonal entries and $Q$ is an arbitrary real unitary matrix. So the square roots of $AA^T$ are represented as $B = UDQ$. 1. I think your conclusion $2^r$ comes from the sign of the diagonal entries of $D$. But does $Q$ not play the role of supplying distinct square roots as well? 2. How do you find $P$ for which $AP=UDQ$ for some $Q$ and $D$ with the right signs of the diagonal entries?
– Hans
Jul 6 '20 at 16:52
• Given $A$, it seems you are presuming there exists a known permutation $P$ such that $(AP)^T=AP$. I thought the question was to determine 1) whether there is such a $P$; 2) if it does exist, how to find it. It seems your answer does not answer either question. What am I missing?
– Hans
Jul 6 '20 at 22:37
• @Hans: I have written a more detailed explanation in the answer I posted. This should address your questions. Jul 7 '20 at 11:58
• +1. Nice. This argument holds for any orthonormal $P$ not just a permutation matrix, right?
– Hans
Jul 8 '20 at 20:02
• @Hans : Yes, that's right, but note that $A^{-1}Q^{\prime}$ is always an orthogonal matrix, so you'd need to be looking for a particular type of orthogonal matrix. Jul 8 '20 at 20:21