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?
$\begingroup$
$\endgroup$
1
asked Jul 6, 2020 at 13:30
-
2$\begingroup$ 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) $\endgroup$– Carlo BeenakkerCommented Jul 6, 2020 at 13:46
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
answered Jul 6, 2020 at 14:05
-
$\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$– HansCommented Jul 6, 2020 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$– HansCommented Jul 6, 2020 at 22:37
-
$\begingroup$ @Hans: I have written a more detailed explanation in the answer I posted. This should address your questions. $\endgroup$ Commented Jul 7, 2020 at 11:58
-
$\begingroup$ +1. Nice. This argument holds for any orthonormal $P$ not just a permutation matrix, right? $\endgroup$– HansCommented Jul 8, 2020 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$ Commented Jul 8, 2020 at 20:21