Implement PSL(2,3)
Since challenge to implement Galois field already have been many, I'm writing a challenge involving a group of Lie type!
Objective
Implement the multiplication and inversion in \$\text{PSL}(2,3)\$.
The ring \$\mathbb{Z}_3\$
The ring \$\mathbb{Z}_3\$ is the set \$\{0,1,2\}\$ with addition, negation, subtraction, and multiplication defined as modular arithmetic:
Addition is the usual addition with the result moduloed by 3;
Negation, subtraction, and multiplication are also analogously defined.
Reciprocal and division is also well-defined, but that's just another detail.
The group \$\text{SL}(2,3)\$
The multiplicative group \$\text{SL}(2,3)\$ is the set of 2-by-2 matrices whose entries are members of \$\mathbb{Z}_3\$ and the determinant is \$1\$. Note that the determinant is calculated using modular arithmetic. Matrix multiplication and matrix inversion is defined as:
Matrix multiplication is the usual matrix multiplication, where addition and multiplication of the entries are modular;
Matrix inversion of \$\begin{pmatrix} a & b \\ c & d \end{pmatrix}\$ is \$\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}\$. This exploits that the determinant is \$1\$.
As a consequence, the elements of \$\text{SL}(2,3)\$ are:
$$\begin{pmatrix} 0 & 1 \\ 2 & 0\end{pmatrix},
\begin{pmatrix} 0 & 1 \\ 2 & 1\end{pmatrix},
\begin{pmatrix} 0 & 1 \\ 2 & 2\end{pmatrix},
\begin{pmatrix} 0 & 2 \\ 1 & 0\end{pmatrix},
\begin{pmatrix} 0 & 2 \\ 1 & 1\end{pmatrix},
\begin{pmatrix} 0 & 2 \\ 1 & 2\end{pmatrix},
\begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix},
\begin{pmatrix} 1 & 0 \\ 1 & 1\end{pmatrix},
\begin{pmatrix} 1 & 0 \\ 2 & 1\end{pmatrix},
\begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix},
\begin{pmatrix} 1 & 1 \\ 1 & 2\end{pmatrix},
\begin{pmatrix} 1 & 1 \\ 2 & 0\end{pmatrix},
\begin{pmatrix} 1 & 2 \\ 0 & 1\end{pmatrix},
\begin{pmatrix} 1 & 2 \\ 1 & 0\end{pmatrix},
\begin{pmatrix} 1 & 2 \\ 2 & 2\end{pmatrix},
\begin{pmatrix} 2 & 0 \\ 0 & 2\end{pmatrix},
\begin{pmatrix} 2 & 0 \\ 1 & 2\end{pmatrix},
\begin{pmatrix} 2 & 0 \\ 2 & 2\end{pmatrix},
\begin{pmatrix} 2 & 1 \\ 0 & 2\end{pmatrix},
\begin{pmatrix} 2 & 1 \\ 1 & 1\end{pmatrix},
\begin{pmatrix} 2 & 1 \\ 2 & 0\end{pmatrix},
\begin{pmatrix} 2 & 2 \\ 0 & 2\end{pmatrix},
\begin{pmatrix} 2 & 2 \\ 1 & 0\end{pmatrix},
\begin{pmatrix} 2 & 2 \\ 2 & 1\end{pmatrix}
$$
The factor group \$\text{PSL}(2,3)\$
\$\text{PSL}(2,3)\$ is defined as cosets of \$\text{SL}(2,3)\$ by \$\{\begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix},
\begin{pmatrix} 2 & 0 \\ 0 & 2\end{pmatrix}\}\$. That is, elementwise multiplications of \$\{\begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix},
\begin{pmatrix} 2 & 0 \\ 0 & 2\end{pmatrix}\}\$.
They are:
$$
\{\begin{pmatrix} 0 & 1 \\ 2 & 0\end{pmatrix},
\begin{pmatrix} 0 & 2 \\ 1 & 0\end{pmatrix}\},
\{\begin{pmatrix} 0 & 1 \\ 2 & 1\end{pmatrix},
\begin{pmatrix} 0 & 2 \\ 1 & 2\end{pmatrix}\},
\{\begin{pmatrix} 0 & 1 \\ 2 & 2\end{pmatrix},
\begin{pmatrix} 0 & 2 \\ 1 & 1\end{pmatrix}\},
\{\begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix},
\begin{pmatrix} 2 & 0 \\ 0 & 2\end{pmatrix}\},
\{\begin{pmatrix} 1 & 0 \\ 1 & 1\end{pmatrix},
\begin{pmatrix} 2 & 0 \\ 2 & 2\end{pmatrix}\},
\{\begin{pmatrix} 1 & 0 \\ 2 & 1\end{pmatrix},
\begin{pmatrix} 2 & 0 \\ 1 & 2\end{pmatrix}\},
\{\begin{pmatrix} 1 & 1 \\ 0 & 1\end{pmatrix},
\begin{pmatrix} 2 & 2 \\ 0 & 2\end{pmatrix}\},
\{\begin{pmatrix} 1 & 1 \\ 1 & 2\end{pmatrix},
\begin{pmatrix} 2 & 2 \\ 2 & 1\end{pmatrix}\},
\{\begin{pmatrix} 1 & 1 \\ 2 & 0\end{pmatrix},
\begin{pmatrix} 2 & 2 \\ 1 & 0\end{pmatrix}\},
\{\begin{pmatrix} 1 & 2 \\ 0 & 1\end{pmatrix},
\begin{pmatrix} 2 & 1 \\ 0 & 2\end{pmatrix}\},
\{\begin{pmatrix} 1 & 2 \\ 1 & 0\end{pmatrix},
\begin{pmatrix} 2 & 1 \\ 2 & 0\end{pmatrix}\},
\{\begin{pmatrix} 1 & 2 \\ 2 & 2\end{pmatrix},
\begin{pmatrix} 2 & 1 \\ 1 & 1\end{pmatrix}\},
$$
You pick an element of each coset as representives, and don't care about the rest.
Multiplication/inversion of such representives is defined as multiplication/inversion in \$\text{SL}(2,3)\$, then taking the representive of the coset the multiplication/inversion is in. For example, \$\begin{pmatrix} 0 & 1 \\ 2 & 0\end{pmatrix}^2 = \begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix}\$, if \$\begin{pmatrix} 0 & 1 \\ 2 & 0\end{pmatrix}\$ and \$\begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix}\$ are representives.
Examples
Picking the left elements as representives of the cosets above:
$$
\begin{pmatrix} 0 & 1 \\ 2 & 0\end{pmatrix}^2 = \begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix},
\begin{pmatrix} 0 & 1 \\ 2 & 1\end{pmatrix}^2 = \begin{pmatrix} 1 & 2 \\ 1 & 0\end{pmatrix},
\begin{pmatrix} 1 & 0 \\ 0 & 1\end{pmatrix}\begin{pmatrix} 1 & 1 \\ 1 & 2\end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 2\end{pmatrix},
\begin{pmatrix} 1 & 2 \\ 2 & 2\end{pmatrix}\begin{pmatrix} 1 & 1 \\ 1 & 2\end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 2 & 0\end{pmatrix},
\begin{pmatrix} 1 & 2 \\ 2 & 2\end{pmatrix}^{-1} = \begin{pmatrix} 1 & 2 \\ 2 & 2\end{pmatrix}
$$
To be more specific about the method of evaluation:
$$
\begin{pmatrix} 0 & 1 \\ 2 & 1\end{pmatrix}\begin{pmatrix} 0 & 1 \\ 2 & 2\end{pmatrix} ≡ \begin{pmatrix} 2 & 2 \\ 2 & 4\end{pmatrix} ≡ \begin{pmatrix} 2 & 2 \\ 2 & 1\end{pmatrix} ≡ \begin{pmatrix} 1 & 1 \\ 1 & 2\end{pmatrix},
\\
\begin{pmatrix} 1 & 1 \\ 1 & 2\end{pmatrix}^{-1} ≡ \begin{pmatrix} 2 & -1 \\ -1 & 1\end{pmatrix} ≡ \begin{pmatrix} 2 & 2 \\ 2 & 1\end{pmatrix} ≡ \begin{pmatrix} 1 & 1 \\ 1 & 2\end{pmatrix}
$$
The steps of this algorithm is:
- Do usual matrix multiplication/inversion;
- Modulo the entries by 3;
- Take the representive of the coset.
Though you can make any possible algorithm.
Rules
- Input type and format doesn't matter, but it must be a container of integers. In C,
int[2][2]
and int[4]
are valid examples. This restriction prevents abusing the fact that \$\text{PSL}(2,3) \cong A_4\$.
- Output type and format doesn't matter either, but it must be the same as the input type and format.
- Invalid inputs fall in don't care situation.
- Multiplication and inversion may be in separate codes. In this case, the score is the sum of their lengths in bytes.
- Since this is a code-golf, the code with least score wins.