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?


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.

| cite | improve this answer | |
  • $\begingroup$ 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? $\endgroup$ – Hans Jul 6 at 16:52
  • $\begingroup$ 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? $\endgroup$ – Hans Jul 6 at 22:37
  • $\begingroup$ @Hans: I have written a more detailed explanation in the answer I posted. This should address your questions. $\endgroup$ – Geoff Robinson Jul 7 at 11:58
  • $\begingroup$ +1. Nice. This argument holds for any orthonormal $P$ not just a permutation matrix, right? $\endgroup$ – Hans Jul 8 at 20:02
  • $\begingroup$ @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. $\endgroup$ – Geoff Robinson Jul 8 at 20:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.