# Common basis for permutation matrices

How can I check whether there exists a common basis with respect to which two matrices 𝐴 and 𝐵 are permutation matrices?

More explicitly, let $$A$$ and $$B$$ be two unitary matrices whose eigenvalues form complete sets of roots of unity (meaning there is a unitary transformation to a permutation matrix for each). How can I check whether their exists a single unitary $$U$$ such that $$P_A = U A U^\dagger, \quad P_B = U B U^\dagger,$$ such that $$P_A$$ and $$P_B$$ are permutation matrices?

• Another restatement: is there a subset of $\mathbf{C}^n$ that forms an orthonormal basis, and which is invariant by both $A$ and $B$? (the existence of such a subset for each of $A$ and $B$ being the assumption)
– YCor
Mar 9, 2020 at 14:19
• When you say "how can I check", are you imagining that you have been given $A$ and $B$ explicitly, and you want to do a computation... Or are you asking for theoretical conditions that are equivalent? One obvious necessary condition is that $\langle A, B\rangle$ is isomorphic to a subgroup of $S_n$... I'm not sure how close it is to being sufficient. Mar 9, 2020 at 14:53
• Yes, what I am imagining is being given two matrices and trying to determine whether there exists such a U. This could either be using the properties of A and B, or it could be determined through some algorithm designed to find U. Could you also clarify what you mean by the angled bracket notation please? Mar 9, 2020 at 17:48
• @MarkSapir and all the subgroup they generate. This is why I added the group tag. For instance one can wonder, if the product of, say all $2^n$ $n$-fold products ($n$ being the size) of $A,B$ are conjugate to permutation matrices, whether it's enough to ensure that they can be simultaneously conjugate into the subgroup of permutation matrices. (Already one can wonder about an algorithm to check if two matrices generate a finite group.)
– YCor
Mar 10, 2020 at 7:20
• The angled backed notation means "the group generated by $A$ and $B$" -- i.e. all matrices obtained by taking finite length products of $A$, $B$ and their inverses. Mar 13, 2020 at 16:57

Here's a possible method:

We might as well assume that $$A$$ is already a permutation matrix -- just conjugate $$A$$ and $$B$$ by the same unitary matrix $$C$$ and relabel.

Now if we are looking to conjugate $$B$$ to a permutation matrix AND retain $$A$$ as a permutation matrix, then we'll need to conjugate by something that centralizes $$A$$ -- so our conjugating matrix, call it $$X$$, must lie in $$C_G(A)$$, where $$G=U(n)$$.

(Note: you might wonder about the possibility that $$A$$ could be conjugated to a different permutation matrix instead, therefore allowing a larger choice for $$X$$; however this question assures us that if we were to do this, we could then conjugate by a permutation matrix to return $$A$$ to its original form, without affecting whether or not $$B$$ is a permutation matrix.)

$$C_G(A)$$ is easy enough to calculate -- especially if $$A$$ is made up of cycles of different lengths. Now let $$\mathcal{B}$$ be the natural basis. We use the reformulation of @YCor to consider what happens when we apply $$X$$ to $$\mathcal{B}$$. So, for instance, if $$A=\begin{pmatrix} & 1 & \\ & & 1 \\ 1 & & \end{pmatrix}$$ then the elements of $$C_G(A)$$ are unitary matrices of the form $$X=\begin{pmatrix} a & b & c \\ c & a & b \\ b & c & a \end{pmatrix}.$$ If we apply the matrix $$X$$ to the natural basis, then we obtain a basis of the form $$\left\{\begin{pmatrix}a \\ c \\ b \end{pmatrix}, \begin{pmatrix} b \\ a \\ c\end{pmatrix}, \begin{pmatrix} c \\ b \\ a \end{pmatrix}\right\}$$ where $$a,b,c$$ are restricted to ensure the basis is orthonormal.

These are all of the orthonormal bases for which $$A$$ is the permutation matrix written above. Now $$B$$ will be a permutation matrix with respect to one of these bases, say $$\mathcal{B}_1$$, if and only if, for all $$v\in \mathcal{B}_1$$, $$Bv\in\mathcal{B}_1$$. One simply has to test whether any of the listed bases have this property.

Remarks:

1. I'd like to find a nice, neat way to do that last bit -- check whether the matrix $$B$$ fixes any of the bases thrown up by considering the centralizer of $$A$$... But it's not obvious to me that one can do this in any efficient sort of a way...
2. The centralizer of $$A$$ will be a lot larger if there are cycles of the same length -- and this will yield a lot more possible bases to test at the end. One should clearly label $$A$$ and $$B$$ so that $$A$$ has as few cycles as possible.

So, algorithmically, it might be most efficient to use the observations in the comments about products of $$A$$ and $$B$$: take a few products of $$A$$ and $$B$$ of some bounded length -- if any of these can't be conjugated to permutation matrices, then, obviously, you stop. If they ALL can be conjugated to a permutation matrix, then choose whichever product resulted in a permutation matrix with fewest repeated cycles.

Added later: In fact, we can make that final step (where we study the action of the matrix $$B$$ on a bunch of bases) much more efficient if we check the isomorphism type of the group $$\langle A, B\rangle$$; this must be isomorphic to a subgroup of $$S_n$$, in which $$A$$ must correspond to the given permutation matrix (so, for instance, if $$A$$ was the matrix in the example above, then its image in $$S_n$$ would be the 3-cycle $$(1,2,3)$$). This allows us to explicitly list the possible permutations corresponding to $$B$$. For each of these possibilities, one has an explicit action on the basis $$\mathcal{B}_1$$.

So, for instance, in the example above, if $$B$$ were to correspond to the element $$(1,2)$$, then its action on the basis $$\mathcal{B}_1$$ would need to swap the first two basis elements. Checking this specific property is much more straightforward than checking if $$B$$ preserves any of the possible bases obtained using the centralizer of $$A$$.

• One can conjugate a permutation matrix to a permutation matrix without centralising it. EDIT: Oops, I see you address this in a later paragraph. Mar 13, 2020 at 17:09
• I have not added it to my question (yet) but can we do any better if we know that $A$ and $B$ are representations of the generators of the modular group? Mar 14, 2020 at 8:30
• Can you give an example where A, B and AB are all separately unitarily equivalent to permutations but that A and B can't be transformed to permutations simultaneously? Mar 26, 2020 at 16:37

One partial answer, for which you don't need the knowledge that the spectra are complete sets of roots of unity.

First step : verify that the group $$G$$ generated by $$A$$ and $$B$$ is finite (it should be contained a permutation group of $$n$$ elements). For this, explore the free group in two letters $$a$$ and $$b$$ (together with $$a^{-1}$$ and $$b^{-1}$$). Consider the disk $$D_k$$ of words $$w$$ of length $$\le k$$, and let $$N_k$$ be the number of distinct elements $$w(A,B)$$ for $$w\in D_k$$. If $$N_k$$ comes to exceed $$n!$$, the basis does not exist. If not, you have reached a $$k$$ so that $$N_{k+1}=N_k$$ ; the group is finite and you still have a chance, provided this $$N=N_k$$ is $$\le n!$$.

Next step : In the latter case, you must verify that the trace of $$w(A,B)$$ is a non-negative integer, for every $$w\in D_k$$.

I suspect that the converse is true, and that it is a result about linear representations of finite groups. Does anyone have a clue ?

• Not only does $w(A,B)$ have integer trace, but also non-negative integer trace. This is actually enough to show that if $G$ is finite, then its order does indeed divide $n!$, by a result of Blichfeldt, which has appeared on MO in relation to several questions. Mar 15, 2020 at 14:45
• Specifically, if $n_{1},n_{2}, \ldots, n_{t}$ are all the distinct values taken by ${\rm trace}(w(A,B))$ as $w(A,B)$ runs over all non-identity elements of $G$, then , assuming $G$ is finite, its order divides $(n-n_{1})(n-n_{2}) \ldots (n-n_{t})$. Mar 15, 2020 at 15:05
• @GeoffRobinson, do you have a reference for that result? Mar 15, 2020 at 15:37
• @LSpice : See this question |: mathoverflow.net/questions/240317/… Mar 15, 2020 at 15:51