Context. I don't expect this question is actually interesting, it just seems like a nice/fun exercise to get better acquainted with $Sp(2n)$ (and to celebrate the new year!). In this question symplectic matrices have coefficients in $\mathbb R$ and are defined by the equation $A^TJA = J$ where $J = \begin{pmatrix}0&I_n\\-I_n&0\end{pmatrix}$. The set of real symplectic $2n\times 2n$ matrices will be denoted $Sp(2n)$.
Question. Can we classify $(0,1)$-matrices of size $2n\times 2n$ which are symplectic? (E.g. Can we understand them well enough to say how many there are?)
Cases found by searching the web.
It is noted already on Wikipedia that in the $2\times 2$ case the symplectic $(0,1)$-matrices are just:
$$I_2, X = \begin{pmatrix}1&1\\0&1\end{pmatrix}, \text{ and } X^T$$
As for the $4\times 4$ case, we can grab some examples from MathWorld, so we at least have
$$I_4,\ \ X = \begin{pmatrix}1&0&0&1\\0&1&1&0\\0&0&1&0\\ 0&0&0&1\end{pmatrix},\ \ Y = \begin{pmatrix}0&1&0&1\\1&0&1&0\\0&0&0&1\\0&0&1&0\end{pmatrix}$$
and their transposes.
Progress. I think I managed to finish the classification just modulo two (just one!) sub-questions I don't know the answer to. Of course, if the answers to either of the sub-questions is "No" it will massively complicate the problem.
My attempts. One question I had was:
Sub-Question 1. Does either the bottom-left or top-right $n\times n$ block of a symplectic $(0,1)$-matrix have to be zero?
Anyway, it can be helpful to think of symplectic matrices in terms of the $n\times n$ blocks. The defining equation
$$\begin{pmatrix}A^T&C^T\\B^T&D^T\end{pmatrix}J\begin{pmatrix}A&B\\C&D\end{pmatrix} = \begin{pmatrix}-C^T&A^T\\-D^T&B^T\end{pmatrix}\begin{pmatrix}A&B\\C&D\end{pmatrix} = J$$
leads to 3 conditions:
-
$A^TC = C^TA\ \ \ $ (or, $A^TC$ is symmetric)
-
$A^TD – C^TB = I\ \ \ $ (and the equivalent $B^TC – D^TA = -I$)
-
$B^TD = D^TB\ \ \ $ (or, $B^TD$ is symmetric)
Continuing here with the assumption one of $B,C$ is zero.
We have some possible solutions coming from assuming either $B = 0$ or $C=0$.
- In the case $B = C = 0$, condition 2 reads $A$ can be any invertible $(0,1)$-matrix such that $D = (A^T)^{-1}$ is also a $(0,1)$-matrix.
Sub-Question 2. Is any invertible $(0,1)$-matrix whose inverse is also a $(0,1)$-matrix orthogonal?
[EDIT: It is true, and very easy:
Assume $AB = I$ for $(0,1)$-matrices $A,B$. Let $A(i) = \{j : a_{ij} = 1\}$ and similarly $B(k) = \{j : b_{jk} = 1\}$. Then the equation $\sum_j a_{ij}b_{jk} = \delta_{ik}$ is equivalent to $|A(i) \cap B(k)| = \delta_{ik}$.
Clearly then $|A(i)\cap A(j)| = |B(i)\cap B(j)| = \delta_{ij}$ as well. So, $A$ is the matrix for the permutation sending $i \mapsto A(i)$ and $B$ its inverse.]
Now, if $B = C = 0$, the condition is $A \in O(n)$ and $D = A$. Even if $B\neq 0$ but $C=0$ this condition is necessary, but then we also need $$B = AB^TA.$$
A couple special cases are in order:
-
$B = A, C = 0$ always works. This was done in the example $Y$ above.
-
If $A = I$ then $B$ can be any symmetric matrix. This was done with $X$ above, and there are two other symmetric $(0,1)$-matrices you could use in the $4\times 4$ case.
Since orthogonal $(0,1)$-matrices are just the permutation matrices, the general condition is actually easy to understand:
Suppose $A$ represents the permutation $s$. Basically, $S_n\times C_2$ is acting on the coefficients of $B = (b_{i,j})$, where the second factor is the transpose, and we are interested in counting the orbits of the subgroup generated by $(s,1)$ which has order $lcm(ord(s),2)$). The action is:
$$b_{i,j} \mapsto b_{s^{-1}(j), s(i)}$$
which either has order 1 or 2.
-
It has order 1 if $s(i) = j$, so there are $n$ orbits of size 1. (Pick any $i$, then set $j=s^{-1}(i)$.)
-
It has order 2 otherwise. So there are $(n^2-n)/2$ orbits of size 2.
Hence the total degrees of freedom is $(n^2+n)/2$.
So if I hadn't made any blunders, we have this conclusion:
Conclusion. There are at least $n!(2^{(n^2 + n)/2+1} – 1)$ symplectic $(0,1)$-matrices of size $2n\times 2n$ over $\mathbb R$. Moreover, if SQ1 and SQ2 hold, this is all of them.
This does produce 3 for $n=1$ as expected, the first few values are:
$$1, 3, 30, 762, 49128, 7864200, 3019898160, 2705829391440, 5541538603950720$$
and you can compare them to the number of special linear $(0,1)$-matrices at this mathoverflow question.
Finally, I will mention that I was also interested in the case of symplectic $(-1,0,1)$-matrices but this seems much harder. The analog of SQ1 fails miserably, as we have the following type of example. Let $n = n_1 + n_2$ for $n_1,n_2 > 0$. Then set
$$A = D = \begin{pmatrix}I_{n_1}&0\\0&0\end{pmatrix}\ \ \text{ and } \ \ B = – C = \begin{pmatrix}0&0\\0&I_{n_2}\end{pmatrix}.$$
Best Answer
No, not all symplectic $(0,1)$-matrices are block-triangular. The following matrix is symplectic: $$\begin{pmatrix}0&1&0&0\\1&0&1&0\\0&1&0&1\\0&0&1&0\end{pmatrix}$$
A computer search found 44 counterexamples in dimension $4\times 4$, so here is another less symmetric one: $$\begin{pmatrix}1&1&0&1\\1&1&1&0\\1&0&1&0\\0&1&0&1\end{pmatrix}$$
WolframAlpha code to check it's symplectic:
[[1,1,0,1],[1,1,1,0],[1,0,1,0],[0,1,0,1]]^T*[[0,0,1,0],[0,0,0,1],[-1,0,0,0],[0,-1,0,0]]*[[1,1,0,1],[1,1,1,0],[1,0,1,0],[0,1,0,1]]