**Definition:** Let

*k ≥ 0* and

*n ≥ 2* be integers.
A

*SOMA*, or more specifically a

*SOMA**(k,n)*, is
an

*n × n*
array

*A*, each of whose
entries is a

*k*-subset of a

*kn*-set

*Ω* (the

*symbol-set*),
such that
every symbol of

*Ω* occurs exactly once in each row and exactly
once in
each column of

*A*, and every 2-subset of

*Ω* is contained
in at most one entry of

*A*.

We remark here that the name SOMA is an acronym for simple
orthogonal multi-array.

A SOMA*(k,n)* can be constructed by the superposition of *k* mutually orthogonal Latin squares (MOLS) of order *n* with pairwise disjoint symbol-sets. If a SOMA*(k,n)*
can be constructed
in this way then it is said to be *Trojan*. Note that not every
SOMA*(k,n)* is Trojan.

**Definition:** Let *A* and *B* be two SOMAs. We say
that *B* is *isomorphic* to *A* if *B* can be
obtained from *A* by applying an *isomorphism*, which
consists of one or more of the following:

- a row permutation,
- a column permutation,
- transposing,
- and a bijective relabelling of the symbols.

An *automorphism* of a SOMA*(k,n)* *A* is an
isomorphism from *A* to *A*. The set of all automorphisms
of *A* is a group, denoted by Aut*(A)*, called then *automorphism
group* of *A*. If *H* is a subgroup of Aut*(A)*
then we say that the SOMA *A* is *invariant* under the
group *H*.

Let *A* be a SOMA*(k,n)* with symbol-set *Ω*. Each
symbol *α ∈ Ω* defines a permutation *π*_{α}
of *{1,2,...,n}* by the rule that

*i π*_{α}=j if,
and only if, the symbol *α* is contained in the *(i,j)*-entry
of *A*.
From this rule, we can see that different symbols give different
permutations. If we are only given the set *{ π*_{α}: α
∈ Ω}
then we can use the rule above to reconstruct the SOMA *A* up to
a bijective relabelling of the symbol-set. So we can regard a SOMA*(k,n)*
as
a set of permutations.

**Definition:** Let *B* be a set of permutations of *{1,
2,.., n}*. We call the set *B* a *SOMA**(k,n)*
if:

- for any
*i, j ∈ {1,2,...,n}*, there
exists exactly *k* elements of *B* that map *i* to *j*,
and
- for any distinct
*a, b ∈ B*, there exists at most one *i
∈{1,2,...,n}*
such that *ia=ib*.

Note that the set *B* is has size *kn*.

Again, we let a set of permutations *B* be a SOMA*(k,n)*.
We construct the graph *Φ(B)* with vertex-set the union of *B*,
the Cartesian product *{1,2,..,n} × {1,2,..,n}*, the set *{("row",
i) :1 ≤ i ≤ n}* and the set *{("column", i) : 1 ≤ i ≤ n}*. We
define the undirected edges of *Φ(B)* as follows. An element *b
∈ B* is only adjacent to the
ordered pairs *(i, j)* such that *ib=j*. In addition,
an ordered pair *(i, j)*
is adjacent to the vertices *("row", i)* and *("column",
j)*. Furthermore, *("row", i)* is adjacent to *("row", j)*
for all *i≠j*, and *("column", i)*
is adjacent to *("column", j)* for all *i≠j*.

Let *A*_{1} and *A*_{2} be two SOMA*(k,n)*s
as arrays, and let *B*_{1} and *B*_{2} be
the respective corresponding SOMA*(k,n)*s as sets of permutations.
Then, it can be shown that the SOMAs *A*_{1} and *A*_{2}
are isomorphic (as arrays) if, and only if, the graphs *Φ(B*_{1}) and
*Φ(B*_{2}) are isomorphic.

## The structure of SOMAs

Let a non-empty set of permutations *B*
be a SOMA*(k,n)*.

**Definition:** A subset *C* of *B* is called a *subSOMA*
(or a *subSOMA**(k,n)*) of B if *C* itself is a SOMA*(k',n)*,
for some integer *k'*.

Suppose that *C* is a subSOMA*(k',n)* of the SOMA*(k,n)*
*B*, for some integer *k'*. Then, it follows that *B*
setminus *C* is a subSOMA*(k-k',n)* of *B*.

**Definition:** A *decomposition*
of the SOMA*(k,n)* *B* is a partition *{B*_{1},...,B_{m}}
of *B* into *m* parts say, such that each part *B*_{i}
is a distinct subSOMA*(k*_{i},n)
of *B*, for some integer *k*_{i} ≥ 1. We then call *(k*_{1}
,..,k_{m})
a *type* of *B*.

It is clear that *{B}* is one decomposition of *B*. If
this is the only
decomposition then SOMA *B* is said to be *indecomposable*;
otherwise, we say that the SOMA *B* is said to
be *decomposable*.

**Definition:** An *unrefinable decomposition* of *B*
is a decomposition *{B*_{1},...,B_{m}} of *B*,
such that each SOMA *B*_{i} is indecomposable. Where each
*B*_{i} is a SOMA*(k*_{i},n), we call *(k*_{1}
,..,k_{m})
an *unrefinable decomposition type (ud-type)* of *B*.

Let *A* be a SOMA*(k,n)* as an array, and let *B*
be the corresponding SOMA*(k,n)* as a set of permutations. We say
an unrefinable decomposition (type) of *A* to mean an unrefinable
decomposition (type) of *B*.

It now follows that a SOMA*(k,n)* has a ud-type of (1,1,...,1)
exactly when a SOMA*(k,n)* is Trojan, which in turn is basically *k*
MOLS of order *n*.

Back to top

This page is maintained by John Arhin.

Last updated: September 5th 2007.