Existence of latin squares with an involutory symmetry Let $M \in \mathbb{N}$ and let $\pi \in S_{M}$ be an involution with at least one fixed point. I'm interested in finding a latin square $A$ of order $M$ such that $A_{i,j} = \pi(A_{j,i})$ for each $i,j \in \{1,\ldots, N^2\}$.
A $B_1$-type latin square is a latin square $A$ indexed by $\mathbb{Z}_{n,1} = \mathbb{Z}_n \cup \{\infty\}$ such that $A_{i+1, j+1} = A_{i,j} + 1$ for every $i,j \in \mathbb{Z}_{n,1}$. Theorem 11 in this survey shows that the latin squares I'm looking for exist when $M \geq 2$ is odd, $\pi$ has a unique fixed point and there exists a symmetric $B_1$-type latin square ($B_1$-type latin squares of order $M$ exist for every $M \geq 2$ by Theorem 6 in the same document).
I'm particularly interested in the case when $M = N^2$ for some $N \in \mathbb{N}$ and $\pi \in S_{N^2}$ has exactly $N$ fixed points. By permuting rows and columns we can assume that $\pi$ fixes the last $N$ elements in $\{1,\ldots, N^2\}$ and $\pi(i) = (N^2 - N)/2 + i$ for $i \in \{1,\ldots, (N^2 - N)/2\}$.
My original motivation comes from constructing symmetric finite-state codes.
 A: To achieve your goal, we can use the "tensor product construction" for Latin squares.  It is carried out as follows: Let $X_a$ be a latin square indexed by $a$, i.e. $X_a$ is a function $a \times a \rightarrow a$ and $X_b$ similarly. Then $X_a  \otimes  X_b : (a \times b) \times(a \times b) \rightarrow (a \times b) $ is defined as $((a_1,b_1),(a_2,b_2)) \rightarrow (X_a(a_1,a_2),X_b(b_1,b_2))$.
The point is that, if there exists permutations $\pi$ and $\rho$ such that $X_a(i,j) = \pi(X_a(j,i))$ and $X_b(i,j) = \rho(X_b(j,i))$ for all $i$, $j$, then $X_a  \otimes  X_b$ satisfies $X_a  \otimes  X_b (k,l)=(\pi \otimes \rho) (X_a  \otimes  X_b (l,k))$, where $\pi \otimes \rho$ is a permutation on $a \times b$ defined by $(\pi \otimes \rho)(a,b)=(\pi(a),\rho(b))$. The number of fixed points of $(\pi \otimes \rho)$ is the product of that of $\pi$ and that of $\rho$.
For $p$ an odd prime, it's possible to construct latin squares $A_p(p)$ and $A_1(p)$ such that the $A_p(p)$ has all classes invariant under involution, and $A_1(p)$ has exactly one class invariant under involution.
Index $A_p(p)$ and $A_1(p)$ by $\mathbb{Z}_p$. Then $A_p(p)$ and $A_1(p)$ can be defined as $A_p(x,y)=x+y$ and $A_1(x,y)=x-y$.
Thus $A_p(p) \otimes A_1(p)$ has order $p^2$ and $p$ classes invariant under involution. Call it $B_p$.
We also need a special latin square $B_2$ that has two classes invariant under involution:
 1 2 3 4
 4 3 2 1
 3 4 1 2
 2 1 4 3

By the factorization of $N$ into primes $N=2^{n_0}p_1^{n_1}...p_k^{n_k}$ (the primes $p_1,...,p_k$ are odd) we can construct a latin square $(\otimes^{n_0} B_2) \otimes (\otimes^{n_1} B_{p_1}) \otimes ... \otimes (\otimes^{n_k} B_{p_k})$ that has order $N^2$ and $N$ classes in involution.
A: Let $g=(1,2)(3,4)\dots(17,18)(19,20)$. I was able to quickly produce a $25\times 25$-Latin square $A$ such that $A_{i,j}=g(A_{j,i})$ for each $i,j\in\{1,\dots,25\}$ using unoptimized and quickly written code.
The algorithm that I have used is similar to an evolutionary algorithm in the sense that the rows of $A$ are originally random permutations but where we mutate $A$ randomly and use natural selection to keep the mutation if it does not increase the loss function (the loss function tells you how close $A$ is to being a Latin square with $A_{i,j}=g(A_{j,i})$ for each $i,j\in\{1,\dots,25\}$). For simplicity, I just kept the population to size 1 for my algorithm.
We define the loss function that we want to minimize $L:S_{n}^{n+1}\rightarrow\mathbb{Z}$ by letting
$$L(g;f_{1},\dots,f_{n})=|\{(i,j)\mid g(f_{i}(j))\neq f_{j}(i)\}|+\sum_{k=1}^{n}(n-|\{f_{i}(k)\mid 1\leq i\leq n\}|).$$
The motivation behind this loss function is that if $A_{i,j}=f_{i}(j)$ for each $i,j$, then $A=(A_{i,j})_{i,j}$ is a Latin square where $A_{i,j}=g(A_{j,i})$ for each $i,j$ if and only if $L(g;f_{1},\dots,f_{n})=0$.
The mutation operator takes an input $(g;f_{1},\dots,f_{n})$ and randomly returns a tuple $(g;f_{1}',\dots,f_{n}')$ such that there exists some $i,a,b$ where $f_{i}'=f_{i}\circ (a,b)$ but where $f_{j}'=f_{j}$ whenever $j\neq i$.
Here is the code that I have written in the language GAP to produce such a Latin square $A$. This code is quite inefficient, but it may be more readable than the more optimized code.
latinsquare:=function(x) 
local n,i,j,q,c; 
c:=0; n:=Length(x); 
for i in [1..n] do q:=[]; 
for j in [1..n] do Add(q,x[j][i]); od; 
Sort(q); 
for j in [1..n-1] do if q[j]=q[j+1] then c:=c+1; fi; od; 
od; 
return c;
# c=0 precisely when x is a latin square and each row in x is a permutation.
end;

# ils is the loss function.

ils:=function(g,x) 
local n,c,i,j; 
n:=Length(x); 
c:=latinsquare(x); 
for i in [1..n] do for j in [1..i] do if not x[i][j]=x[j][i]^g then c:=c+1; fi; od; od; 
return c; 
end;

g:=(); for i in [1..10] do g:=g*(2*i-1,2*i); od;

x:=List([1..25],v->[1..25]);

p:=ils(g,x); 
while p>0 do 
a:=Random([1..25]); b:=Random([1..25]); c:=Random([1..25]);
if b=c then continue; fi; xx:=StructuralCopy(x); r:=xx[a][b]; xx[a][b]:=xx[a][c]; xx[a][c]:=r; q:=ils(g,xx); 
# xx is the mutation of x
if q<=p then 
# this statement is the selection that keeps the mutant xx if it is at least as fit # as x
p:=q; x:=xx; Display(p); fi; 
od;

This sort of evolutionary algorithm is good for producing combinatorial objects similar to Latin squares.
More efficient computation: added 1/2/2022
Let us make some observations and modifications to our original algorithm to improve its efficiency. To improve efficiency, we first need to use a simpler loss function $L^{\sharp}$ defined by letting
$L^{\sharp}(g;f_{1},\dots,f_{n})=\{(i,j)\mid g(f_{i}(j))\neq f_{j}(i)\}$
whenever $g,f_{1},\dots,f_{n}\in S_{n},g=g^{-1}$.
Now observe that the difference
$L^{\sharp}(g;f_{1},\dots,f_{n})-L^{\sharp}(g;f_{1}',\dots,f_{n}')$ is easy to compute whenever $f_{i}$ and $f_{i}'$ are closely related for all $i$. Therefore, since this difference is easy to compute, one can easily compute
$L^{\sharp}(g;f_{1}',\dots,f_{n}')$ from $L^{\sharp}(g;f_{1},\dots,f_{n})$ whenever $f_{i}$ and $f_{i}'$ are closely related for all $i$. This code is quite efficient since I was able to produce a $250\times 250$ involutory symmetric Latin square by running 1 core on my laptop for 3 minutes.
mls:=function(g,x) 
local n,c,i,j; 
n:=Length(x); 
c:=0; 
for i in [1..n] do for j in [1..i] do if not x[i][j]=x[j][i]^g then c:=c+1; fi; od; od; 
return c; 
end;


g:=(); for i in [1..10] do g:=g*(2*i-1,2*i); od;

x:=List([1..25],v->[1..25]);


difference:=function(g,x,a,b,c)
local p;
p:=0;
if a=b then
if x[a][a]=x[a][a]^g then p:=p-1; fi;
if x[a][c]^g=x[c][a] then p:=p-1; fi;
if x[a][c]=x[a][c]^g then p:=p+1; fi;
if x[c][a]=x[a][a]^g then p:=p+1; fi;

elif a=c then
if x[a][a]=x[a][a]^g then p:=p-1; fi;
if x[a][b]^g=x[b][a] then p:=p-1; fi;
if x[a][b]=x[a][b]^g then p:=p+1; fi;
if x[b][a]=x[a][a]^g then p:=p+1; fi;
else

if x[a][b]^g=x[b][a] then p:=p-1; fi;
if x[a][c]^g=x[c][a] then p:=p-1; fi;
if x[a][b]^g=x[c][a] then p:=p+1; fi;
if x[a][c]^g=x[b][a] then p:=p+1; fi;
fi;
return p;
end;

n:=250;

g:=(); for i in [1..100] do g:=g*(2*i-1,2*i); od;

x:=List([1..n],v->[1..n]);

p:=mls(g,x); 

har:=0;
perm:=[1..n];
while p>0 do 
am:=Random([1..n]);
bm:=Random([1..n]);
rm:=perm[am];
sm:=perm[bm];
perm[am]:=sm;
perm[bm]:=rm;
har:=har+1;
a:=Random([1..n]); b:=Random([1..n]); 
if x[a][b]=x[b][a]^g then 
c:=Random([1..n]);
if b=c then continue; fi;
if difference(g,x,a,b,c)>=0 then
p:=p-difference(g,x,a,b,c);
r:=x[a][b]; x[a][b]:=x[a][c]; x[a][c]:=r;
if Random([1..100])=1 then
Display(p); 
fi;
fi;
continue; 
fi;

for c in perm do
har:=har+1;
if b=c then continue; fi; 
if difference(g,x,a,b,c)>=0 then
p:=p-difference(g,x,a,b,c);
r:=x[a][b]; x[a][b]:=x[a][c]; x[a][c]:=r;
if Random([1..100])=1 then
Display(p); 
fi;
if x[a][b]=x[b][a]^g then
break;
fi;
fi;
od;
od;

A: Let's develop some of the basic theory of involutory symmetric quasigroups since this theory will help us know where to look for examples.
An involutory symmetric quasigroup is an algebra $(X,*,/\backslash,g)$ where
$(X,*,/,\backslash)$ is a quasigroup and $g$ is a unary operation that satisfies the identities $g(g(x))=x$ and $g(x*y)=y*x$.
Proposition: Suppose that $(X,*,/,g)$ is an algebraic structure that satisfies the identities $(x*y)/y=x=(x/y)*y$ and $g(x*y)=y*x$ for all $x,y\in X$. Then

*

*$g$ is an involution.


*$g$ is definable from $X$ by the identity $g(x)=y*(x/y)$.


*There exists a unique operation $\backslash$ on $X$ such that $(X,*,/,\backslash)$ is a quasigroup (and in this case $(X,*,/,\backslash,g)$ is an involutory symmetric quasigroup). Furthermore $\backslash$ is definable from $(X,*,/)$ by letting $x\backslash y=g(y)/x$.
Proof:
1-2. Observe that $g(g(x))=g(g((x/y)*y))=g(y*(x/y))=(x/y)*y=x$, so $g$ is an involution, and $g(x)=y*(x/y)$.


*It suffices to show that for all $a,b\in X$, there is a unique solution $x$ to the equation $a*x=b$, namely where $x=g(b)/a$.

Uniqueness: Suppose that $a*x=b$. Then $x*a=g(a*x)=g(b)$. Therefore, $x=g(b)/a$.
Existence: Suppose that $x=g(b)/a$. Then $a*x=a*(g(b)/a)=g(g(a*(g(b)/a)))
=g((g(b)/a)*a)=g(g(b))=b$.
Q.E.D.
Proposition: Suppose that $(X,*,\backslash,g)$ is an algebraic structure that satisfies the identities $x=y*(y\backslash x)=y\backslash(y*x)$ and $g(x*y)=y*x$ for each $x,y\in X$. Then

*

*$g$ is an involution.


*$g$ is definable from $X$ by letting $g(y)=(x\setminus y)*x$.


*there is a unique operation $/$ on $X$ such that $(X,*,/,\backslash)$ is a quasigroup. In this case, $y/x=x\backslash g(y)$ whenever $x,y\in X$.
Proposition: Suppose that $(X,*,/,\backslash,g)$ is an algebra where $g$ is unary, $(X,*/,\backslash)$ is a quasigroup. Then $(X,*,/,\backslash,g)$ is an involutory symmetric quasigroup if and only if $x\backslash y=g(y)/x$ for all $x,y$.
A squag (Steiner quasigroup) is an algebraic structure $(X,*)$ that satisfies the identities
$x*y=y*x,x*x=x,(x*y)*x=y$.
A Steiner triple system is a pair $(X,\mathcal{C})$ such that $X$ is a set, and $\mathcal{C}$ is a collection of $3$ element subsets of $X$ where whenever $x,y\in X,x\neq y$, there exists a unique $z\in X$ such that $\{x,y,z\}\in\mathcal{C}$. The Steiner triple systems are in a canonical one-to-one correspondence with the squags. If $(X,\mathcal{C})$ is a Steiner triple system, the define an operation $*$ on $X$ by letting $x*x=x$ and $\{x,y,x*y\}\in\mathcal{C}$ whenever $x\neq y$. Furthermore, if $(X,*)$ is a squag, then $\{\{x,y,x*y\}\mid x,y\in X,x\neq y\}$ is a Steiner triple system.
Every squag $(X,*)$ is an involutory symmetric quasigroup $(X,*,/,\backslash,g)$ where $x*y=x/y=x\setminus y$ and where $g(x)=x$ for all $x,y\in X$. Furthermore, every idempotent involutory symmetric quasigroup is a squag.
The following result shows you where to look for squags.
Theorem: If $(X,\mathcal{C})$ is a finite Steiner triple system, then
$|X|=1\mod 6$ or $|X|=3\mod 6$. Furthermore, if $n=1\mod 6$ or $n=3\mod 6$, then there exists a Steiner triple system $(X,\mathcal{C})$ such that $|X|=n$.
