Basic definitions regarding SOMAs

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.

Graphs corresponding to a SOMAs

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₁ and A₂ be two SOMA(k,n)s as arrays, and let B₁ and B₂ be the respective corresponding SOMA(k,n)s as sets of permutations. Then, it can be shown that the SOMAs A₁ and A₂ are isomorphic (as arrays) if, and only if, the graphs Φ(B₁) and Φ(B₂) 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₁,...,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₁ ,..,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₁,...,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₁ ,..,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.

This page is maintained by John Arhin.

Last updated: September 5th 2007.