1
$\begingroup$

I have a hard time solving the following two matrix equations for unknown permutation matrix $X \in \mathbb{R}^{n \times n}$: $$X^T A X = B_1$$ $$X A X^T = B_2$$ where, $A$, $B_1$ and $B_2$ are all $n \times n$ symmetric permutation matrices such that $B_1 \neq B_2$ in general. The solution $X$ may not be symmetric.

If this can be solved, can we say anything about the uniqueness of the solution?

Improve this question
$\endgroup$
4
  • 4
    $\begingroup$ If $B_1=I\neq B_2$, then there is no such $X$ because $B_1$ and $B_2$ are not similar. Note that $X^T=X^{-1}$. So, if the above equations hold, then $B_1$ and $B_2$ must be similar. $\endgroup$
    – Sungjin Kim
    Commented Oct 18, 2023 at 14:17
  • 3
    $\begingroup$ Moreover, $A,B_1,B_2$ must all have the same cycle structure (as permutations). $\endgroup$
    – Christian Remling
    Commented Oct 18, 2023 at 20:57
  • 1
    $\begingroup$ I think this is better phrased as a question about (conjugacy of) permutations. $\endgroup$
    – Christian Remling
    Commented Oct 18, 2023 at 21:01
  • $\begingroup$ $A$, $B_1$, and $B_2$ are permutation matrices for product of disjoint transpositions (or possibly empty product, which gives $I$). Of course, similar, so the number of transpositions must be the same. $\endgroup$
    – Sungjin Kim
    Commented Oct 19, 2023 at 5:38

1 Answer 1

Reset to default
1
$\begingroup$

Two permutations are conjugated in $S_n$ iff they have same spectrum (as matrices). Since $A,B_1,B_2$ are symmetric, they are a product of $k$ (the same $k$ for all) disjoint transpositions.

Let $A,B_1,B_2$ be such matrices. Then there exist $X,Y\in S_n$ s.t. $X^TAX=B_1,Y^TAY=B_2$.

EDIT. Although the OP does not seem very passionate about what I write, I give below a method to solve part of the problem for matrices of order up to $30$.

Does there exist $Z\in S_n$ s.t. $Z^TAZ=B_1,ZAZ^T=B_2$ ?

and what is the number of solutions if there are any ?

We suppose -for example- that $k$ is maximum. Note that -up to a permutation- we may assume that $A=[[1,2][3,4]]\in S_4$ (if $n$ is even) and $A=[[1,2][3,4]]\in S_5$ (if $n$ is odd).

We consider the algebraic system formed by the equations relating the entries of $Z$ and we solve it -if possible- using a computer and the Groebner theory.

We obtain that follows. "time" indicates the time to obtain the solutions -if there are any- or to prove that there are no solutions.

$\bullet$ $n=10$. $0$ solution time<1"; $16$ solutions time=21".

$\bullet$ $n=14$. $0$ solution time<2"; $80$ solutions time=9'43".

$\bullet$ $n=18$. $0$ solution time=8".

$\bullet$ $n=20$. $0$ solution time=14"5.

The Groebner method concludes much more quickly when there are no solutions. Thus when $n$ is great, if the processor runs too long (time to be specified), then there are solutions.

$\textbf{Remark.}$ Of course, if $X,Y$ are randomly chosen, then $Z$ does not exist with a probability close to 1 - especially if $n$ is large-.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .