Orthosymmetrical matrices

The code for this implementation can be found in its git repository at git://git.lemen.xyz/orthosymmetrical.git or as a tarball. A PDF transcript is also available here. The outputs of the program take a while to compute. For this reason they are available in the data directory.

Let $k$ be a field and let ${\mathrm{OS}}_n\left(k\right)=\{A=A^T\text{ and }A{A}^T=I_n\}$ denote the set of orthogonal symmetric matrices over $k$. Does this set have an interesting structure with regards to the regular matrix operations?

The following simple lemma will be used throughout the following discussion.

Notation

• $I_n$ denotes the identity matrix of size $n$
• $C_m$ denotes the cyclic group of order $m$ i.e. $C_m=\mathbb{Z}/m\mathbb{Z}$

Regarding addition

The zero matrix is not an element of ${\mathrm{OS}}_n\left(k\right)$ since all elements of it are invertible (all elements have order $2$). Let $A$ be in ${\mathrm{OS}}_n\left(k\right)$. Then $-A={\left(-A\right)}^T$ by definition and $-A{\left(-A\right)}^T=\left(-A\right)\left(-A\right)=I_n$ implies that $-A\in {\mathrm{OS}}_n\left(k\right)$. So ${\mathrm{OS}}_n\left(k\right)$ is not closed under regular matrix addition.

Regarding multiplication

The identity matrix is fortunately included in ${\mathrm{OS}}_n\left(k\right)$.

The case $n\ge 3$

Consider the matrix product:
$$\left[\begin{array}{ccc}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\right]\left[\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right]=\left[\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 0& 0\end{array}\right]\notin {\mathrm{OS}}_n\left(k\right)$$ The resulting matrix is not symmetric and by that ${\mathrm{OS}}_n\left(k\right)$ is not closed under multiplication for $n\ge 3$.

The case $n=1$

All elements trivially fulfill $A=A^T$ This reduces the set to ${\mathrm{OS}}_1\left(k\right)=\{A^2=1\}$ or in other words all square roots of unity. Using the above lemma you can conclude $A=\pm 1$. This implies ${\mathrm{OS}}_1\left(k\right)=\{\begin{array}{}{C}_2\text{ if }\mathrm{char}k\ne 2\\ C_1\text{ if }\mathrm{char}k=2\end{array}$

The case $n=2$

First case $\mathrm{char}k\ne 2$

Since $\mathrm{char}k$ the elements $1$ and $-1$ are not equal and the matrix product $$\left[\begin{array}{cc}1& 0\\ 0& -1\end{array}\right]\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]=\left[\begin{array}{cc}0& 1\\ -1& 0\end{array}\right]\notin {\mathrm{OS}}_n\left(k\right)$$ is not contained in ${\mathrm{OS}}_2\left(k\right)$ Further can ${\mathrm{OS}}_2\left(k\right)$ be embedded into larger ${\mathrm{OS}}_n\left(k\right)$ via: $$\left[\begin{array}{cc}{\mathrm{OS}}_2\left(k\right)& 0\\ 0& I_{n-2}\end{array}\right]\subset {\mathrm{OS}}_n\left(k\right)$$ This mapping preserves multiplication and restates the case fo $n\ge 3$.

The interesting case $\mathrm{char}k=2$

All elements have order $2$ so you get: $$\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right]={\left[\begin{array}{cc}a& b\\ b& c\end{array}\right]}^2=\left[\begin{array}{cc}{a}^2+b^2& ab+bc\\ ba+cb& b^2+c^2\end{array}\right]=\left[\begin{array}{cc}{a}^2+b^2& b(a+c)\\ b(a+c)& b^2+c^2\end{array}\right]$$ If $b=0$ then $a^2=1=c^2$ which implies $a=1=c$. Otherwise $a=c$ as $0=b(a+c)$ implies $a+c=0$ since $k$ has no zero divisors. Focusing on the first entry you get $$1=a^2+b^2={(a+b)}^2$$ which using the lemma implies $a+b=1$ or in other words $b=a+1$. Putting these all together you get: $${\mathrm{OS}}_2\left(k\right)=\left\{\left[\begin{array}{cc}\lambda & \lambda +1\\ \lambda +1& \lambda \end{array}\right]\right| \text{for} \lambda \in k\}$$ Furthermore the map $$k\to {\mathrm{OS}}_2\left(k\right):\lambda \mapsto \left[\begin{array}{cc}\lambda & \lambda +1\\ \lambda +1& \lambda \end{array}\right]$$ is a bijection between $k$ and ${\mathrm{OS}}_2\left(k\right)$. Whats left to show is that ${\mathrm{OS}}_2\left(k\right)$ is closed under multiplication: $$\left[\begin{array}{cc}\lambda & \lambda +1\\ \lambda +1& \lambda \end{array}\right]\left[\begin{array}{cc}\rho +1& \rho \\ \rho & \rho +1\end{array}\right]=\left[\begin{array}{cc}\lambda +\rho & \lambda +\rho +1\\ \lambda +\rho +1& \lambda +\rho \end{array}\right]$$ So ${\mathrm{OS}}_2\left(k\right)$ has a group structure with regards to the regular matrix multiplication. This calculation also shows that the group is abelian as the addition is commutative in $k$.

This gives a simple classification for the finite fields:

Numerical exploration

The above shows that ${\mathrm{OS}}_n\left(k\right)$ carries no relevant structure for $n\ge 3$. Noting that the field $k=F_2=\mathbb{Z}/2\mathbb{Z}$ has exactly $2$ elements, which can be easily mapped to binary bits, the following mapping into the integers is immediate: $$M_{n\times n}\to \mathbb{Z}:\left[\begin{array}{cccc}{b}_1& b_2& ...& b_n\\ b_{n+1}& ...& ...& ...\\ ...& ...& ...& ...\\ ...& ...& ...& b_{n\times n}\end{array}\right]\mapsto \sum _{\mathrm{i}=1}^{n\times n}{b}_i 2^{i-1}$$ This mapping sends a matrix to the integer represented by a binary string (in least significant bit order and gives also rise to an ordering on $M_{n\times n}$ by retracting the ordering on $\mathbb{Z}$ back onto the matrices. In other words: You interpret the matrix as a single binary represented integer. The ordering is used in the following discussion when talking about the smallest and largest matrices. With this mapping you can easily enumerate all matrices in $M_{n\times n}$ by using its partial inverse map.

Computing the sizes of the ${\mathrm{OS}}_n\left(F_2\right)$ for some small $n$ by brute force checking results in this table:

This sequence is currently not found in the OEIS which indicates that the above is not of greater significance.

Implementation details

Some speedups can be achieved when considering the inherent structure of ${\mathrm{OS}}_n\left(k\right)$. As we are only considering symmetric matrices it is enough to set half the matrix and reflect it along its diagonal. This reduces the search space from $n^2$ to $\frac{n(n+1)}{2}$ and cuts it approximately in half. It is also useful to note that this reduction preserves the ordering. In the case for $n=4$: $$b_1\cdots b_{10}\mapsto \left[\begin{array}{cccc}{b}_1& b_2& b_3& b_4\\ b_2& b_5& b_6& b_7\\ b_3& b_6& b_8& b_9\\ b_4& b_7& b_9& b_{10}\end{array}\right]$$

Some marginal time improvements can be gained by optimizing the start and end indices. The smallest index is a matrix with $1$ on its anti-diagonal: $$\left[\begin{array}{cccccc}0& 0& 0& 0& 0& 1\\ 0& 0& 0& 0& 1& 0\\ 0& 0& 0& 1& 0& 0\\ 0& 0& 1& 0& 0& 0\\ 0& 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 0& 0\end{array}\right]$$ Proof. You can calculate that the proposed starting index is indeed in ${\mathrm{OS}}_n\left(k\right)$.
As each element in ${\mathrm{OS}}_n\left(k\right)$ is invertible, the minimal element can not have a zero row or column. This implies that each row must have at least one $1$. Indeed it is the case that there is no smaller invertible matrix with that property:
None of the entries right of the anti-diagonal can be $1$ as they would be larger than the proposed starting index. This leaves a matrix in triangle form. As the matrix is invertible it needs to have full rank. If any of the entries on the anti-diagonal would be $0$ the rank would not be full. Then if any of the entries left of the anti-diagonal would be $1$ it would again be bigger than the proposed matrix.

The end index depends on the dimensions parity: First is even dimension, second is odd dimension.

Proof. You can check that both type of matrices are contained in their respective ${\mathrm{OS}}_n\left(k\right)$.
Consider the even case first. Every row and column needs to have an odd number $0$s or the square will not be equal to $I_n$. It follows that every row needs to have at least one $0$. This implies that the last row is equal to the proposed row as shifting the $0$ to any other place would decrease the associated index. The same reasoning can be applied to the next row with the caveat that the $0$ can't be further left as this would duplicate a row beneath it.
The argument for the odd case is similar with the difference that every row needs to have an even number of $0$s. No row can have only $1$s as this would make the square not equal $I_n$ again.