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:
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:
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 A1 and A2 be two SOMA(k,n)s as arrays, and let B1 and B2 be the respective corresponding SOMA(k,n)s as sets of permutations. Then, it can be shown that the SOMAs A1 and A2 are isomorphic (as arrays) if, and only if, the graphs Φ(B1) and Φ(B2) are isomorphic.
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 {B1,...,Bm} of B into m parts say, such that each part Bi is a distinct subSOMA(ki,n) of B, for some integer ki ≥ 1. We then call (k1 ,..,km) 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 {B1,...,Bm} of B, such that each SOMA Bi is indecomposable. Where each Bi is a SOMA(ki,n), we call (k1 ,..,km) 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.
This page is maintained by John Arhin.
Last updated: September 5th 2007.