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.

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

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

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

$\bullet$ I know a random example -when $n=5$- without solutions in $Z$.

$\bullet$ Conversely, if at least one such a $Z$ exists, I know $2$ random examples -when $n=8$- with $12$ or $16$ solutions in $Z$.

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.