Given a $2n \times 2n$ binary symplectic matrix$^1$ $M$, I need to decompose that into a product of matrices from the following set S. It is guaranteed that multiple such decompositions exist.
$S = \{ A \} \cup \{ B\}$
Where set $A$ contains matrices of the form:
$A = I_{2n \times 2n} + (1)_{n+i,j} + (1)_{n+j,i} + (1)_{n+i,i} + (1)_{n+j,j} $
And set $B$ contains matrices of the form:
$B = I_{2n \times 2n} + (1)_{i,n+j} + (1)_{j,n+i} + (1)_{i,n+i} + (1)_{j,n+j}$
$i,j \in [1,n]$
Here $I$ is identity and $(1)_{n+i,j}$ means (n+i,j) element is 1. (If there is better notation to denote this, please let me know.)
If it helps, $M$ also satisfies the following condition:
$^1$ : $M$ is matrix which satisfies $M \cdot J \cdot M^T = J$ where
$J = \begin{bmatrix} 0_{n \times n} & I_{n \times n}\\ I_{n \times n} & 0_{n \times n} \end{bmatrix}$
Any idea on how can I approach this problem? Are there any matrix decomposition, factorization algorithms? If yes, how efficient in terms of computation are they?
Any input would be greatly appricaited!