On the Construction of
Orthogonal Arrays and Covering Arrays
Using Permutation Groups

George Sherwood

# Abstract

An alternate formulation is given for index one orthogonal arrays based on computer searches. Orthogonal arrays in diagonal form, and their elements' products, powers, and orders, are derived from first column vectors which result from the searches. Mapping operators relating the first column vectors for each number of levels (m) are described. A scheme for factoring the mapping operators is suggested also. Results are given for values of m which are primes, prime powers, and prime power products. An association between first column vectors and irreducible monic polynomials is made for selected prime power values of m.

Permutation vectors which extend the formulation to groups with orders of powers of m are defined for values of m which are primes and prime powers. Properties of the permutation vectors are described. A formulation is given for strength two covering arrays based on the permutation vectors. These arrays have wm2-(w-1)m rows and (mw+1-1)/(m-1) columns for values of w which are positive integers. A sliding levels technique is suggested to include values of m which are prime power products.

Zero sum arrays are constructed using the permutation vectors. A recursive construction for strength three covering arrays is given for m equal to two. Alternatively, the cats program is used to find strength three and four covering arrays by removing redundant rows from covering arrays of permutation vectors.

For values of m which are primes and prime powers, another formulation describes sets of permutation vectors which do not cover. The formulation is used to find covering arrays of strength greater than two, by forming arrays of permutation vectors in which each combination of columns contains a combination of permutation vectors which is not noncovering. Resulting covering arrays of strengths l=3 and l=4 have zml-(z-1)m rows for values of z which are positive integers. The numbers of columns found are consistent with the conjecture that arrays of this form can have m+1 columns for z=1 and mz columns for z>1.

For values of m which are primes and prime powers, and for strengths greater than two, a narrower, recursive search is described for index one orthogonal arrays of permutation vectors. The search results suggest a formula for orthogonal arrays with m+1 columns, and strengths up to m+1. Selected results are given for strengths up to four.

# Preface

Four years ago I started a mathematical journey. These are my travel notes. They document my search for ways to construct covering arrays using various computer search techniques. The computer search has been a heuristic tool for me, with results leading to improved searches, as well as to the mathematical patterns described here.

I suppose the reader who is interested in orthogonal arrays and covering arrays may desire a rigorous mathematical deduction of results. That is not the purpose of these notes. I have included some informal logical illustrations, but the emphasis here is on pattern recognition and description, rather than formal proof. The reader will not find a clear boundary drawn between derivation and conjecture. Instead, I invite the reader who travels these paths to join in the logical development of the ideas, to add the rigor where it fits.

AT&T Labs provided computer facilities supporting this work. (A Sun Microsystems Ultra 5 workstation executed the searches described here.) Also, I would like to acknowledge the interest and support of several people in my earlier work on the Constrained Array Test System (which was one of the motivators of the present work). These colleagues include:

 Otto Sgro David Gelperin Jim Prowse Bob Stahl Alex Gillon Willa Ehrlich Merle Poller Colin Mallows Bob Brownlie Neil Sloane Madhav Phadke

In particular, Colin and Neil showed me there was new ground to explore here. Finally I want to thank my family – Ann, Jeffrey, Andrew, and Daniel – for their patience and understanding during my travels.

Have a good trip!
George Sherwood
March 2002

-Current browser versions, Netscape 6 or IE 5.50, or later are recommended. Earlier versions (Netscape 4.7, IE 5.00) don't always get the formatting just right.
May 17, 2002-The total number of noncovering sets wel,m is expressed as a product of a power of m and a Gaussian binomial coefficient.
November 10, 2002- The covering array search algorithm for strength l>2 and rows of vectors z>1 is improved for better efficiency. A new section describes the search algorithm.
November 10, 2002- The improved search algorithm yields the following results for strength l=3. The covering arrays have zm3-(z-1)m rows for positive integers z. For z=2 rows of vectors, n=9 columns are found for number of levels m=3; 16 columns are found for m=4; 24 columns for m=5; 31 columns for m=7; 40 columns for m=8. For z=3 rows of vectors, n=20 columns are found for number of levels m=3; 28 columns are found for m=4. The numbers of columns found are consistent with the conjecture that arrays of this form can have mz columns.
November 10, 2002-Additional arrays of permutation vectors, for m=7, m=8, and m=9, are included in an appendix.
November 10, 2002-The pound sign # in a section heading indicates the material is not required to understand later sections, and may be skipped on a first reading. The pound sign provides a link to the next section not so marked.
January 4, 2003- Additional strength l=3 results are included. For z=2 rows of vectors, n=39 columns are found for number of levels m=9.
March 22, 2003- Additional strength l=3 results are included. For z=1 row of vectors, n=10 columns are found for number of levels m=8; 10 columns are found for m=9; 12 columns are found for m=11; 14 columns are found for m=13. For z=2 rows of vectors, n=44 columns are found for number of levels m=11; 39 columns are found for m=13.
March 22, 2003- Numbers of covering arrays found for l=3 and for selected values of m and z are tabulated and described in a revised section. (For z=1 these results are for orthogonal arrays of index one.)
June 8, 2003- The improved search algorithm described earlier is used to find strength l=4 arrays with w=3. For z=2 rows of vectors, n=8 columns are found for number of levels m=2; 9 columns are found for m=3.
August 15, 2003- Additional strength l=4 results are included. For z=1 row of vectors, n=6 columns are found for number of levels m=5. For z=2 rows of vectors, n=10 columns are found for number of levels m=3; 9 columns are found for m=4; 11 columns are found for m=5. For z=3 rows of vectors, n=8 columns are found for number of levels m=2; 16 columns are found for m=3. For z=4 rows of vectors, n=11 columns are found for number of levels m=2. A new section gives numbers of wFwP arrays found for l=4.
August 15, 2003- Two new sections summarize results for m=2 levels with strengths l=3 and l=4. Another new section gives numbers of w,zFwP(') arrays found for m=2.
August 15, 2003- The section mark notation § is introduced to represent the operation of removing redundant rows via the cats program. This use (typically for m=2) is to distinguish clearly from the removal of the (z-1)m duplicate rows indicated by the apostrophe in w,zFwP'. For example, for m=2 and l=4, the operation of the cats program on the lowest covering array 3,3F3P§ yields the same array as the lowest 3,2F3P' array (which illustrates the high redundancy in the 3,3F3P' array).
June 8, 2004-Highlights of this site have been collected in a paper submitted to the Journal of Combinatorial Designs.
June 8, 2004-Some of the construction methods described here are used in a covering test case generator service available from Testcover.com.
June 8, 2004-Question for Site Visitors: The coveringarray.org domain has been reserved as a possible site for a public domain covering array database. The idea is to collect "interesting" arrays, e.g. which represent various construction methods, or which may be of particularly small size, etc. To gauge whether there is sufficient interest to justify the project, would you please respond by email as to whether and how such a data base would be of use to you? And if you are a researcher, would you be willing to contribute arrays to the database?

 Abstract Preface Table of Contents Table of Symbols Table of Covering Arrays Definitions Preparation First Column Vectors and their Mapping Operators Mapping Operators First Column Vectors and Mapping Operators for m=prime First Column Vectors and Mapping Operators for m=prime power First Column Vectors and Mapping Operators for m=prime power product and c=2 First Column Vectors and Mapping Operators for m=prime power product and c>2 Covering Arrays for Strength l=2 Permutation Vectors Covering Arrays for m=prime or m=prime power and n=mw Covering Arrays for m=prime or m=prime power and n=(mw+1-1)/(m-1) Covering Arrays for m=prime power product Covering Arrays for Strength l>2 Zero Sum Arrays Covering Arrays for l>2 and m=2 Noncovering Combinations of Permutation Vectors Covering Arrays for l>2 and m>2 Covering Array Searches for z>1 Orthogonal Arrays of Index One Orthogonal Array Recursive Search Orthogonal Arrays for l=3 and m>2 Orthogonal Arrays for l>3 and m>3 Orthogonal Array Formula for l

# Table of Symbols

SymbolMeaning
A, B, Cvector or array
A * Bcomposite vector operation or vector product of A and B
Dv, ^Dvfirst column vector mapping operators for different multiplication table
wEzero sum array
wFan array of one row of levels for which wFwP is a covering array
w,zFan array of z rows of levels for which w,zFwP is a covering array
w,zFwP'a covering array w,zFwP for z>1 from which (z-1)m redundant rows have been removed
w,zFwP§a covering array w,zFwP processed by the cats program to remove redundant rows, typically for m=2 levels
wGcovering array for n=mw
wHcovering array for n=(mw+1-1)/(m-1)
wHm/m'covering array using sliding levels technique
wIcovering array using recursive construction for l=3 and m=2
J, Krow vector of level representation array R
wLindex one orthogonal array of permutation vectors given by formula for n=m+1
Muvfirst column vector level mapping operator Su * Dv
^Muvfirst column vector position mapping operator ^Su * ^Dv
wNindex one orthogonal array of permutation vectors using recursive search for n=m+1
wPhorder mw+1 permutation vector of h
wPh–order mw reduced permutation vector of h
wPmw+1-by-mw array whose columns are the permutation vectors,
permutation vector operator
w,lQarray of noncovering permutation vector levels in base m notation
w,lQ~noncovering permutation vector formula array
Rlevel representation array or function
Su, ^Sufirst column vector mapping operators for same multiplication table
Ttemplate array for diagonal form construction
apower or exponent
bnumber of primaries in a prime power product
cmaximum number of plus vector columns in an index one orthogonal array for l=2 and r=m2
dqdifference vector
wel,mnumber of noncovering sets of permutation vectors
f(x)irreducible monic polynomial
fuvfirst column vector of an index one orthogonal array in diagonal form
guvfirst row vector of an index one orthogonal array in standard form
hlevel or value of an array element from 0 to m-1,
level to label a permutation vector from 0 to mw-1
hw order vector whose components give the level h in base m notation, from 0 to mw-1
h., dot vectors of h, dot operators acting on h
h[w]zero sum vector of h, zero sum operator acting on h
hwPpermutation vector operator acting on h
irow position or subscript for array of vectors
jrow position or subscript for vector, table or array
kcolumn position or subscript for vector, table, or array
k+, k+plus vectors of k, plus operators acting on k
k+{m}plus vector of k, plus operator acting on k for m values, from 0 to m-1
kx, kxcross vectors of k, cross operators acting on k
kx{c/}cross vector of k, cross operator acting on k truncated to c of m values, from 0 to c-1
lstrength of an array
mnumber of levels taken by the factors in an array
nnumber of columns or factors in an array
pprime number
qtotitive of m-1
rnumber of rows or runs in an array
srow position of a subarray in a covering array
tvector component or position for h, a place in base m notation,
column position of a subarray in a covering array
u, vvectors to label first column vectors in terms of their mapping operators
wbase m logarithm of the order of the group of permutation vectors wPh with the composite vector operation *
order of vector of subarrays wG
iteration label for recursive construction of wI
..., :ellipses
=/=not equal to

# Table of Covering Arrays

StrengthNumber
of Levels
Number
of Rows
Number
of Columns
ArrayReference Tables
lmrn

any
up to n
11any{n}
1anymany0+·{n}
22431E formulavectorslevels
22431H formulavectorslevels
22672H formulavectorslevels
228153H formulavectorslevels
2210314H formulavectorslevels
2212635H formulavectors
23931E formulavectorslevels
23941H formulavectorslevels
2315132H formulavectorslevels
2321403H formulavectorslevels
241631E formulavectorslevels
241651H formulavectorslevels
242461H4/5 formulavectorslevels
2428212H formulavectorslevels
2440853H formulavectors
252561H formulavectorslevels
2545312H formulavectorslevels
25651563H formula
263631H formulavectorslevels
264881H6/7 formulavectorslevels
266291H6/8 formulavectorslevels
2678101H6/9 formulavectorslevels
2690572H6/7 formulavectors
26118732H6/8 formula
274981H formulavectorslevels
276391H7/8 formulavectorslevels
2779101H7/9 formulavectorslevels
2791572H formulavectors
286491H formulavectorslevels
2880101H8/9 formulavectorslevels
28118121H8/11 formulavectorslevels
28120732H formula
2981101H formulavectorslevels
29119121H9/11 formulavectorslevels
29153912H formula
21010031H formulavectorslevels
210120121H10/11 formulavectorslevels
210166141H10/13 formulavectorslevels
2102301332H10/11 formula
211121121H formulavectorslevels
211167141H11/13 formulavectorslevels
2112311332H formula
21214451H formulavectorslevels
212168141H12/13 formulavectorslevels
212252171H12/16 formulavectorslevels
212284181H12/17 formulavectorslevels
2123241832H12/13 formula
213169141H formulavectorslevels
213253171H13/16 formulavectorslevels
213285181H13/17 formulavectorslevels
2133251832H formula
21419631H formulavectorslevels
21422451H14/15 formulavectorslevels
214254171H14/16 formulavectorslevels
214286181H14/17 formulavectorslevels
214356201H14/19 formulavectorslevels
2144942732H14/16 formula
21522551H formulavectorslevels
215255171H15/16 formulavectorslevels
215287181H15/17 formulavectorslevels
215357201H15/19 formulavectorslevels
2154952732H15/16 formula
216256171H formulavectorslevels
216288181H16/17 formulavectorslevels
216358201H16/19 formulavectorslevels
2164962732H formula
217289181H formulavectorslevels
217359201H17/19 formulavectorslevels
217523241H17/23 formulavectorslevels
2175613072H formula
21832431H formulavectorslevels
218360201H18/19 formulavectorslevels
218524241H18/23 formulavectorslevels
219361201H formulavectorslevels
219525241H19/23 formulavectorslevels
22040051H formulavectorslevels
220526241H20/23 formulavectorslevels
22144151H formulavectorslevels
221527241H21/23 formulavectorslevels
22248431H formulavectorslevels
222528241H22/23 formulavectorslevels
223529241H formulavectorslevels
32832L formulavectorslevels
32842E formulavectorslevels
32840I or 2P or 2,1F2P or 2,2F2P§ formulavectorslevels
321442,2F2P' formulavectorslevels
321481I or 3P§ formulavectorslevels
321482,3F2P§ formulavectorslevels
322082,3F2P' formulavectorslevels
3220164P§ formulavectorslevels
3222162I formulavectorslevels
3226162,4F2P' formulavectorslevels
3228325P§ formulavectorslevels
3232323I formulavectorslevels
3234646P§ formulavectors
3244644I formulavectors
332742E formulavectorslevels
332742,1F2P formulavectorslevels
332742L or 2N formulavectorslevels
335192,2F2P' formulavectorslevels
3375192,3F2P' formulavectorslevels
3375202,3F2P' formulavectors
346442E formulavectorslevels
346452L or 2N formulavectorslevels
346462,1F2P formulavectorslevels
34124162,2F2P' formulavectorslevels
34184282,3F2P' formulavectors
3512562,1F2P formulavectorslevels
3512562L or 2N formulavectorslevels
35245232,2F2P' formulavectorslevels
35245242,2F2P' formulavectors
3621642E formulavectorslevels
3634282F2P 6/7 formulavectorslevels
36678312,2F2P 6/7' formulavectors
3734382F2P formulavectorslevels
3734382L or 2N formulavectorslevels
37679312,2F2P' formulavectors
3851292F2P formulavectorslevels
3851292L or 2N formulavectors
38512102F2P formulavectors
381016402,2F2P' formulavectors
39729102F2P formulavectors
39729102L or 2N formulavectors
391449392,2F2P' formulavectors
3101330122F2P 10/11 formula
3101330122L10/11 or 2N10/11 formula
3102650442,2F2P 10/11' formula
3111331122F2P formulavectors
3111331122L or 2N formulavectors
3112651442,2F2P' formulavectors
3122196142F2P 12/13 formula
3124380392,2F2P 12/13' formula
3132197142F2P formulavectors
3134381392,2F2P' formulavectors
421643,1F3P formulavectorslevels
421653E formulavectorslevels
423064F4P§ formulavectorslevels
423275F5P§ formulavectorslevels
423083,2F3P' or 3,3F3P§ formulavectorslevels
42408_ formulavectorslevels
424483,3F3P' formulavectorslevels
4258113,4F3P' formulavectorslevels
438143L formulavectorslevels
438153E formulavectorslevels
438153F3P formulavectorslevels
4315993,2F3P' formulavectorslevels
43159103,2F3P' formulavectorslevels
43237163,3F3P' formulavectors
4425653E formulavectorslevels
4425653F3P formulavectorslevels
4425653L formulavectorslevels
4450893,2F3P' formulavectors
4562563F3P formulavectors
4562563L formulavectors
451245113,2F3P' formula
46129653E formula
46240083L6/7 formula
47240183L formula

# Definitions

## Dot Vectors

This section defines Dot Vectors and Dot Operators.

For each of the m levels h=0, 1, ..., m-1, define the vector h. given by repeating the value of h m times. For example, for m=3, the dot vectors are:

 h. : 0. 1. 2. 0 0 0 1 1 1 2 2 2

The unary dot operator acts on an array to replace each element with its corresponding dot vector. The result is an array with m times the number of rows compared to the original array. Thus,

 (0 1 2). = 0 0 0 1 1 1 2 2 2

Similarly, the raised dot operator replaces each element of an array with its corresponding dot vector transposed. The result is an array with m times the number of columns compared to the original array:

 (0 1 2)· = 0 0 0 1 1 1 2 2 2

The number of levels m for a dot vector or operator usually is taken from its context. If the number of levels is not clear, the value is indicated in braces after the dot (e.g. h.{3}). When the number of columns c<m, the dot vectors may be truncated to c elements. This case is indicated by {c/m} or just {c/} after the dot (e.g. {2/6} when m=6).

## Plus Vectors

This section defines Plus Vectors and Plus Operators for three cases:

• m=prime (p)
• m=prime power (pa)
• m=prime power product (p0a0 p1a1 ... pb-1ab-1)

In all cases the zero plus vector 0+{m} is defined to contain all m levels in ascending order:

 0 1 : m-1

Note that the definitions given in this section are not the only choice leading to the formulations given here. Later sections will illustrate two cases in which alternate plus vector definitions can affect results. However, a systematic study of all choices of plus vectors is beyond the current scope.

### Plus Vectors for m=prime

Construct the modulo m=p addition table (p=prime) for the m order cyclic group. Each table element in row j=0, 1, ..., m-1 and column k=0, 1, ..., m-1 has the value j+k (mod m).

For example, for m=3, the table is

 k: j: 0 1 2 0 1 2 0 1 2 1 2 0 2 0 1

Now define the m vectors k+ given by the table columns. In this example, they are

 k+: 0+ 1+ 2+ 0 1 2 1 2 0 2 0 1

The unary plus operator acts on an array to replace each element with its corresponding plus vector. The result is an array with m times the number of rows compared to the original array. Thus,

 (0 1 2)+ = 0 1 2 1 2 0 2 0 1

Similarly, the raised plus operator replaces each element of an array with its corresponding plus vector transposed. The result is an array with m times the number of columns compared to the original array:

 (0 1 2)+ = 0 1 2 1 2 0 2 0 1

The number of levels m for a plus vector or operator usually is taken from its context. If the number of levels is not clear, the value is indicated in braces after the plus (e.g. h+{3}). When c<m, the plus vectors may be truncated to c elements. This case is indicated by {c/m} or just {c/} after the plus (e.g. h+{2/6} when m=6).

### Plus Vectors for m=prime power

For m=pa, in which p=prime and a>1, the plus vectors are defined in terms of the pa-1 plus vectors. Thus, plus vectors for m=pa can be found recursively from those of p. An R function associates each of the m levels with a row in an m-by-a level representation array. The R function is given by

R(0+{m})=(0.{mp-1} R(0+{mp-1}))+{p}

Here R(0+{p}) is defined to be 0+{p}. So for m=9, p=3, and a=2,

R(0+{9})=(0.{3} R(0+{3}))+{3}

and

 R( ) = 0 1 2 3 4 5 6 7 8 0 1 2 0 1 2 0 1 2 0 1 2 1 2 0 2 0 1

The addition table for m=pa is constructed by modulo p addition of elements from the level representation array. For each table element in the jth row, there is a corresponding row J in the level representation array, with values J0, ..., Ja-1. For each table element in the kth column, there is a corresponding row K in the level representation array, with values K0, ..., Ka-1. The j,k table element is found by vector addition of the two level representation rows (mod p), and then finding the position of the row with the resulting sum J0+K0, ... , Ja-1+Ka-1. The j,k table element is

R-1(R(j)+R(k)mod p) = R-1(J+Kmod p)

Here R(j) gives the jth row of the level representation array, and R-1 is defined as the function which gives the position of each row of the level representation array.

For example, for m=9, j=4, and k=5, the rows to add are 1 2 and 2 0. The resulting row is 0 2 which is represented by the level 6. So the 4+5 element in the addition table is 6. The complete addition table for this example is

 k: j: 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 1 2 0 4 5 3 7 8 6 2 0 1 5 3 4 8 6 7 3 4 5 6 7 8 0 1 2 4 5 3 7 8 6 1 2 0 5 3 4 8 6 7 2 0 1 6 7 8 0 1 2 3 4 5 7 8 6 1 2 0 4 5 3 8 6 7 2 0 1 5 3 4

Now define the m vectors k+ given by the table columns.

k+ = R-1(R(0+)+R(k.)mod p) = R-1(R(0+)+K.mod p)

In this example, they are

 k+: 0+ 1+ 2+ 3+ 4+ 5+ 6+ 7+ 8+ 0 1 2 3 4 5 6 7 8 1 2 0 4 5 3 7 8 6 2 0 1 5 3 4 8 6 7 3 4 5 6 7 8 0 1 2 4 5 3 7 8 6 1 2 0 5 3 4 8 6 7 2 0 1 6 7 8 0 1 2 3 4 5 7 8 6 1 2 0 4 5 3 8 6 7 2 0 1 5 3 4

Similarly, for m=27, p=3, and a=3, R(0+{27})=(0.{9} R(0+{9}))+{3} and

 R( 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ) = 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 1 2 0 2 0 1 0 1 2 1 2 0 2 0 1 0 1 2 1 2 0 2 0 1 0 1 2 1 2 0 2 0 1 1 2 0 2 0 1 0 1 2 2 0 1 0 1 2 1 2 0

The k+ vectors for m=27 are

 k+: 0+ 1+ 2+ 3+ 4+ 5+ 6+ 7+ 8+ 9+ 10+ 11+ 12+ 13+ 14+ 15+ 16+ 17+ 18+ 19+ 20+ 21+ 22+ 23+ 24+ 25+ 26+ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 1 2 0 4 5 3 7 8 6 10 11 9 13 14 12 16 17 15 19 20 18 22 23 21 25 26 24 2 0 1 5 3 4 8 6 7 11 9 10 14 12 13 17 15 16 20 18 19 23 21 22 26 24 25 3 4 5 6 7 8 0 1 2 12 13 14 15 16 17 9 10 11 21 22 23 24 25 26 18 19 20 4 5 3 7 8 6 1 2 0 13 14 12 16 17 15 10 11 9 22 23 21 25 26 24 19 20 18 5 3 4 8 6 7 2 0 1 14 12 13 17 15 16 11 9 10 23 21 22 26 24 25 20 18 19 6 7 8 0 1 2 3 4 5 15 16 17 9 10 11 12 13 14 24 25 26 18 19 20 21 22 23 7 8 6 1 2 0 4 5 3 16 17 15 10 11 9 13 14 12 25 26 24 19 20 18 22 23 21 8 6 7 2 0 1 5 3 4 17 15 16 11 9 10 14 12 13 26 24 25 20 18 19 23 21 22 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 0 1 2 3 4 5 6 7 8 10 11 9 13 14 12 16 17 15 19 20 18 22 23 21 25 26 24 1 2 0 4 5 3 7 8 6 11 9 10 14 12 13 17 15 16 20 18 19 23 21 22 26 24 25 2 0 1 5 3 4 8 6 7 12 13 14 15 16 17 9 10 11 21 22 23 24 25 26 18 19 20 3 4 5 6 7 8 0 1 2 13 14 12 16 17 15 10 11 9 22 23 21 25 26 24 19 20 18 4 5 3 7 8 6 1 2 0 14 12 13 17 15 16 11 9 10 23 21 22 26 24 25 20 18 19 5 3 4 8 6 7 2 0 1 15 16 17 9 10 11 12 13 14 24 25 26 18 19 20 21 22 23 6 7 8 0 1 2 3 4 5 16 17 15 10 11 9 13 14 12 25 26 24 19 20 18 22 23 21 7 8 6 1 2 0 4 5 3 17 15 16 11 9 10 14 12 13 26 24 25 20 18 19 23 21 22 8 6 7 2 0 1 5 3 4 18 19 20 21 22 23 24 25 26 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 19 20 18 22 23 21 25 26 24 1 2 0 4 5 3 7 8 6 10 11 9 13 14 12 16 17 15 20 18 19 23 21 22 26 24 25 2 0 1 5 3 4 8 6 7 11 9 10 14 12 13 17 15 16 21 22 23 24 25 26 18 19 20 3 4 5 6 7 8 0 1 2 12 13 14 15 16 17 9 10 11 22 23 21 25 26 24 19 20 18 4 5 3 7 8 6 1 2 0 13 14 12 16 17 15 10 11 9 23 21 22 26 24 25 20 18 19 5 3 4 8 6 7 2 0 1 14 12 13 17 15 16 11 9 10 24 25 26 18 19 20 21 22 23 6 7 8 0 1 2 3 4 5 15 16 17 9 10 11 12 13 14 25 26 24 19 20 18 22 23 21 7 8 6 1 2 0 4 5 3 16 17 15 10 11 9 13 14 12 26 24 25 20 18 19 23 21 22 8 6 7 2 0 1 5 3 4 17 15 16 11 9 10 14 12 13

As before the unary plus operator acts on an array to replace each element with its corresponding plus vector.

### Plus Vectors for m=prime power product

When m>1, and is divisible by b>1 distinct primes, m can be expressed as a product of b primaries, which contain the prime factors of m raised to the appropriate powers: m=p0a0 p1a1 ... pb-1ab-1. In this case, the plus vectors are defined in terms of the plus vectors of the b primaries. An R function associates each of the m levels with a row in an m-by-b level representation array. The R function is given by

R(0+{m})=0.{mp0-a0}+{p0a0} 0.{mp1-a1}+{p1a1} ... 0.{mpb-1-ab-1}+{pb-1ab-1}

Each column of the level representation array consists of repetitions of the zero plus vectors of one of the primaries. The number of repetitions is chosen to form a total of m rows. So for m=12, b=2, p0=2, a0=2, p1=3, and a1=1.

 R( 0 1 2 3 4 5 6 7 8 9 10 11 ) = R(0+{12}) = 0.{3}+{4} 0.{4}+{3} = 0+{4} 0+{4} 0+{4} 0+{3} 0+{3} 0+{3} 0+{3} = 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 0 1 2 0 1 2 0 1 2

The addition table for m is constructed by addition of elements from the level representation array using the addition tables as defined above for the corresponding primaries. For each table element in the jth row, there is a corresponding row J in the level representation array, with values J0, ..., Jb-1. For each table element in the kth column, there is a corresponding row K in the level representation array, with values K0, ..., Kb-1. The j,k table element is found by addition of the corresponding level representation row elements, using the addition table for the primary of each column, and then finding the position of the row with the resulting sum J0+K0, ... , Jb-1+Kb-1. The j,k table element is R-1(J+Kaddition tables).

For example, for m=12, j=4, and k=5, the rows to add are 0 1 and 1 2, using the addition tables for p0a0 = 22 = 4

 k0: j0: 0 1 2 3 0 1 2 3 0 1 2 3 1 0 3 2 2 3 0 1 3 2 1 0

and p1a1 = 31 = 3

 k1: j1: 0 1 2 0 1 2 0 1 2 1 2 0 2 0 1

respectively. The resulting row is 1 0 which is represented by the level 9. So the 4+5 element in the addition table is 9. The complete addition table for this example is

 k: j: 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 1 8 3 10 5 0 7 2 9 4 11 6 2 3 4 5 6 7 8 9 10 11 0 1 3 10 5 0 7 2 9 4 11 6 1 8 4 5 6 7 8 9 10 11 0 1 2 3 5 0 7 2 9 4 11 6 1 8 3 10 6 7 8 9 10 11 0 1 2 3 4 5 7 2 9 4 11 6 1 8 3 10 5 0 8 9 10 11 0 1 2 3 4 5 6 7 9 4 11 6 1 8 3 10 5 0 7 2 10 11 0 1 2 3 4 5 6 7 8 9 11 6 1 8 3 10 5 0 7 2 9 4

Now define the m vectors k+ given by the table columns.

In this example, they are

 k+: 0+ 1+ 2+ 3+ 4+ 5+ 6+ 7+ 8+ 9+ 10+ 11+ 0 1 2 3 4 5 6 7 8 9 10 11 1 8 3 10 5 0 7 2 9 4 11 6 2 3 4 5 6 7 8 9 10 11 0 1 3 10 5 0 7 2 9 4 11 6 1 8 4 5 6 7 8 9 10 11 0 1 2 3 5 0 7 2 9 4 11 6 1 8 3 10 6 7 8 9 10 11 0 1 2 3 4 5 7 2 9 4 11 6 1 8 3 10 5 0 8 9 10 11 0 1 2 3 4 5 6 7 9 4 11 6 1 8 3 10 5 0 7 2 10 11 0 1 2 3 4 5 6 7 8 9 11 6 1 8 3 10 5 0 7 2 9 4

As before the unary plus operator acts on an array to replace each element with its corresponding plus vector.

## Composite Vector Operators

Each of the addition tables of the previous section defines the addition operation for a group of order m. The sum of j+k is given by the table element in the jth row and the kth column. 0 is the identity element, and inverses are identified by row-column pairs whose sum is 0.

The plus vectors associated with each table, and their composite vector operation, also form a group of order m. Each of these vector groups is isomorphic to the corresponding integer addition group of order m.

In the following definition vectors are described as functions of their positions or subscripts. That is, for a vector A of order m, the element in the jth row is given by

A(j) = Aj

Similarly, all the elements of A can be expressed as

 A = A(0+) = A( 0 1 : m-1 ) = A(0) A(1) : A(m-1) = A0 A1 : Am-1

The composite vector operation is the binary operation of one vector on another. It is defined1 by

(A * B)(0+) = B(A(0+))

The elements of the A * B vector are those of the B vector arranged according to the values of the A vector elements. The jth element of A * B is found by using the jth element of A as the position of B. The resulting value is the jth element of A * B. For example, if A = 4+{12} and B = 5+{12}, then A * B = 9+{12}, as follows.

 A * B = (4+ * 5+)(0+) = 5+(4+( 0 1 2 3 4 5 6 7 8 9 10 11 )) = 5+( 4 5 6 7 8 9 10 11 0 1 2 3 ) = 9 4 11 6 1 8 3 10 5 0 7 2 = 9+

The plus vectors form abelian groups in that

j+ * k+ = k+ * j+

However generally vectors will not commute in the composite vector operation:

A * B =/= B * A

A more general definition of the composite vector operation will be needed below. Consider two arrays of vectors A and B with r rows and c columns. That is, the element of A in the ith row and the kth column Aik is a vector. Similarly the element of B in the ith row and the kth column Bik is a vector. For such arrays the composite vector operation A * B is defined to be the r-by-c array of vectors C whose elements are given by

Cik = Aik * Bik

for all rows i and columns k. The composite vector operation is also called the vector product here.

1. This definition differs from the usual composite function definition because the order of the functions A and B is reversed. The order of functions in this definition is chosen to be consistent with the left-to-right order of operations implied by the dot, plus and cross operations.

# Preparation

## Orthogonal Array Search Criterion

Consider an m-by-c array of vectors A which forms an orthogonal array of strength1 l=2 and index one2. That is, each pair of distinct columns k and k' contains each pair of levels h and h' once. (Here, h and h' may be equal; k and k' cannot be.) Suppose each vector Aik is of order m and contains each of the m levels once. Thus, each vector can be expressed as a bijective function of its position

Aijk = Aik(j)

and there is an inverse function which gives the position for each of the levels

j = Aik-1(h)

Consider a pair of distinct columns k and k'. Each is composed of m vectors of order m. The vector elements with position j in the ith row of vectors are Aik(j) = h and Aik'(j) = h'. The pair of levels h and h' can appear only once, in this ith row of vectors. Consider also a pair of vectors in the same columns k and k', but in a different row of vectors i'. The vectors are Ai'k and Ai'k' as illustrated below.

 : : ... Aik(j) ... Aik'(j) ... : : ... Ai'k(j') ... Ai'k'(j') ... : :

Select the position j' such that

Ai'k'(j') = h' = Aik'(j)

Since the pair of levels h and h' occur in k and k' in the ith row of vectors and that pair of levels cannot occur more than once, the corresponding elements in column k must be different:

Aik(j) = h =/= Ai'k(j')

And since

j' = Ai'k'-1(h') = Ai'k'-1(Aik'(j))

substitution yields

Aik(j) =/= Ai'k(Ai'k'-1(Aik'(j)))

Application of Ai'k-1 gives

Ai'k-1(Aik(j)) =/= Ai'k'-1(Aik'(j))

and the definition of the composite vector operation yields

Aik * Ai'k-1 =/= Aik' * Ai'k'-1

This is the criterion to be used to find orthogonal arrays of vectors, for all distinct i and i', and all distinct k and k'.

For a given set of vectors, say h+, h=0, ... , m-1, a table of m2 products h+ * h'+-1 can be computed for reference. Then the search can be done over an m-by-c array of vectors, which is faster than a more general search over an m2-by-c array of levels.

1. An orthogonal array with index one has strength l (greater than or equal to 0, and less than or equal to c) if every r-by-l subarray contains each l-tuple of levels exactly once as a row.
2. Generally the term position (rather than index) is used here to mean the subscript of a vector or array, or its independent variable when considered as a function. The index of an orthogonal array refers to the number of times each l-tuple occurs.

## Standard Form

To narrow its scope and thus improve its speed, the orthogonal array search will require found arrays to be in standard form. A strength l=2 array of plus vectors is in standard form when

1. its 0th column consists of m 0+ vectors;
2. its 1st column consists of the m i+ vectors in ascending order, i=0, 1, ... , m-1;
3. its 0th row consists of c 0+ vectors; and
4. its 1st row consists of c plus vectors in ascending order.

Requiring these conditions poses no loss of generality due to well known properties of orthogonal arrays1. To illustrate this point consider an orthogonal array of plus vectors Aik in some other, arbitrary form. The following four transformations can be applied to the array to produce an orthogonal array in standard form. Conversely, an orthogonal array in standard form can lead to many other forms by similar transformations in reverse.

1. To make the 0th column consist of 0+ vectors, apply to each row of vectors, the inverse of the vector in the 0th column. Each row i of vectors is transformed as follows.
 Ai0-1 ·{c/m} * (Ai0 Ai1 ... Ai c-1) = Ai0-1*Ai0 Ai0-1*Ai1 ... Ai0-1*Ai c-1

(Here the ·{c/m} notation means the Ai0-1 vector is to be repeated over c columns, because c may be less than m.) By definition, the effect of applying Ai0-1 to form the vector product is the rearrangement of the rows of levels within the ith row of vectors. This transformation is a permutation of rows, which results in an orthogonal array with the same parameters -- l, m, c, and r.

2. Consider the orthogonal array search criterion with k=0 and k'=1. For all distinct i and i',
Ai0 * Ai'0-1 =/= Ai1 * Ai'1-1

For an array with 0.+ as its 0th column,

0+ = 0+ * 0+-1 =/= Ai1 * Ai'1-1

so

Ai'1 =/= Ai1

Thus the m vectors in the 1st column are all different and must include all plus vectors from the set under consideration. Now it is possible to rearrange of the rows of vectors so that the 1st column contains the i+ vectors in ascending order. This transformation is a permutation of rows, which results in an orthogonal array with the same parameters.

3. To make the 0th row of vectors consist of 0+ vectors, apply to each column of vectors the inverse of the vector in the 0th row of vectors repeated m times. Each column k of vectors is transformed as follows.
A0k * A0k-1
A1k * A0k-1
:
Am-1 k * A0k-1

By definition, the effect of taking the vector product of each plus vector in the column with A0k-1 is a remapping of levels within the kth column. Specifically, the level h of each column vector element is mapped to the level of the element of A0k-1 with position h. Consequently, this transformation is a permutation of levels of a column, which results in an orthogonal array with the same parameters.

4. Consider the orthogonal array search criterion with i'=0 and i=1. For all distinct k and k',
A1k * A0k-1 =/= A1k' * A0k'-1

For an array with + as its 0th row of vectors,

A1k * 0+-1 =/= A1k' * 0+-1

so

A1k =/= A1k'

Thus the c vectors in the 1st row are all different. Now it is possible to rearrange the columns so that the 1st row of vectors contains the plus vectors in ascending order. This transformation is a permutation of columns, which results in an orthogonal array with the same parameters.

When c=m, the orthogonal array of plus vectors can be expressed as an m-by-m array to which the plus operator is applied. If the orthogonal array is in standard form, the m-by-m array can be interpreted as a multiplication table. Its 0th row and 0th column consist of the element 0, indicating all multiplication products of 0 equal 0. Its 1st row and 1st column consist of the m elements in ascending order, indicating 1 is the multiplicative identity element. For example, when l=2 and c=m=5, the orthogonal array of plus vectors is

 A = ( 0 0 0 0 0 0 1 2 3 4 0 2 4 1 3 0 3 1 4 2 0 4 3 2 1 )+

The corresponding multiplication table is contained in the parentheses. In this example, the table represents multiplication modulo 5.

When m=p is a prime, or m=pa is a prime power, then c=m. In these cases corresponding addition and multiplication tables may define rings or fields for the elements h=0, 1, ..., m-1. Similarly the tables may define isomorphic rings or fields for the plus vectors h+=0+, 1+, ..., (m-1)+ . Here the addition operation is the composite vector operation, and the multiplication operation is given by the multiplication table.

1. For example, see Chapter 1 of Orthogonal Arrays Theory and Applications by A. S. Hedayat, N. J. A. Sloane, and John Stufken, 1999 Springer-Verlag.

## Diagonal Form

To narrow its scope and improve its speed further, the orthogonal array search will look for arrays in diagonal form. A strength l=2 orthogonal array of plus vectors B is in diagonal form when it can be written as a vector product of a template array T and a first column vector fuv as follows.

B = (T * fuv·{c/m})+

in which T is an m-by-c array, and fuv is a vector with m rows. (The u and v vectors are used to label the first column vectors as described in a later section.) For m>1, the template array elements are defined as follows.

 Tik = 0 if i=0 or k=0, andif m>1. T11 = 1 if i=1 and k=1, andif m=2. (Tik-1)mod m = (i-1 + k-1)mod m-1 if i>0 and k>0, andif m>2.

The fuv vector contains a permutation of the m levels with 0 and 1 in the 0th and 1st positions respectively. For example, for m=5 and c=5, the template array is

 T = 0 0 0 0 0 0 1 2 3 4 0 2 3 4 1 0 3 4 1 2 0 4 1 2 3

and a first column vector is

 f00 = 0 1 2 4 3

Their product is

 T * f00· = 0 0 0 0 0 0 1 2 4 3 0 2 4 3 1 0 4 3 1 2 0 3 1 2 4

(Note the first column of this array is f00, which leads to the name first column vector for an orthogonal array in diagonal form.) Finally, the application of the plus operator gives the full array:

 B = 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 4 0 1 2 3 3 4 0 1 2 0 1 2 3 4 2 3 4 0 1 4 0 1 2 3 3 4 0 1 2 1 2 3 4 0 0 1 2 3 4 4 0 1 2 3 3 4 0 1 2 1 2 3 4 0 2 3 4 0 1 0 1 2 3 4 3 4 0 1 2 1 2 3 4 0 2 3 4 0 1 4 0 1 2 3

Because an orthogonal array in diagonal form has 0+ vectors in its 0th row of vectors and in its 0th column, it already satisfies conditions 1 and 3 for standard form (above). Thus, only transformations of type 2 and 4 are needed to change the orthogonal array from diagonal form to standard form. It is convenient to express the array in standard form in terms of the first column vector, as follows.

 Aik = 0+ if i=0 or k=0, andif m>1. A11 = 1+ if i=1 and k=1, andif m=2. Aik = fuv({fuv-1(i) - 1 + fuv-1(k) - 1}mod m-1 + 1mod m)+ if i>0 and k>0, andif m>2.

In this example

 A24 = f00({f00-1(2) - 1 + f00-1(4) - 1}mod 4 + 1mod 5)+ = f00({2-1 + 3-1}mod 4 + 1mod 5)+ = f00(3+1mod 5)+ = f00(4)+ = 3+

The entire orthogonal array in standard form is

 A = ( 0 0 0 0 0 0 1 2 3 4 0 2 4 1 3 0 3 1 4 2 0 4 3 2 1 )+ = 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3 0 1 2 3 4 2 3 4 0 1 4 0 1 2 3 1 2 3 4 0 3 4 0 1 2 0 1 2 3 4 3 4 0 1 2 1 2 3 4 0 4 0 1 2 3 2 3 4 0 1 0 1 2 3 4 4 0 1 2 3 3 4 0 1 2 2 3 4 0 1 1 2 3 4 0

In general the mapping from orthogonal arrays of plus vectors in diagonal form to those in standard form is not injective. This is because there can be multiple diagonal form arrays mapped to the same standard form array. In particular, for m=5 and c=5, the first column vector

 f10 = 0 1 3 4 2

maps to the same standard form array as f00 does.

Generally the mapping from an orthogonal array of plus vectors in diagonal form to one in standard form is not surjective either, because there are orthogonal arrays of vectors in standard form1 which do not have corresponding diagonal forms. (They are not found in a search for arrays in diagonal form.)

Requiring the orthogonal array search to find arrays of plus vectors in diagonal form is neither necessary nor sufficient. It is not a necessary condition because there are other orthogonal arrays which are not found by the search for arrays in diagonal form. Search results include orthogonal arrays based on Galois fields however. Finding an array in diagonal form is not sufficient because there are diagonal arrays of plus vectors which do not satisfy the orthogonal array search criterion. For example, for m=5 and c=5, the identity vector

 0+ = 0 1 2 3 4

yields a nonorthogonal array, though its product with the template array is diagonal. Thus 0+ is not a first column vector in this example.

The advantage of searching for orthogonal arrays in diagonal form is the reduction in the scope of the search, leading to shorter execution times for large m. The search is reduced to finding first column vectors, for which there may be (m-2)! permutations of levels. In practice, the number of cases to test is less than (m-2)! because the first column vector can be built incrementally. After level 0 is assigned to the 0th row and column, and after 1 is assigned to the first diagonal position, each candidate level can be checked in a partial array to see if it meets the orthogonal array search criterion. If it does, a candidate level is chosen for the next diagonal. If it does not, the search considers the next candidate level for the current diagonal, without consideration of additional diagonals containing this nonorthogonal, partial permutation.

1. For m=9 and c=9, a search for orthogonal arrays of plus vectors in standard form yields 17 arrays. Three of these are obtained from a corresponding search for orthogonal arrays of plus vectors in diagonal form, followed by the mapping to standard form (as described below). Two of the 17 are based on noncommutative rings with identity, because the multiplication tables are not symmetric. However each can be described in terms of the following template array (with four diagonal subarrays) and one of two first column vectors.
 0 0 0 0 0 0 0 0 0 0 0 T = 0 0 0 0 1 2 3 4 2 3 4 1 3 4 1 2 4 1 2 3 5 8 7 6 6 5 8 7 7 6 5 8 8 7 6 5 with f = 1 3 2 6 or 1 3 2 6 0 0 0 0 5 8 7 6 6 5 8 7 7 6 5 8 8 7 6 5 3 4 1 2 4 1 2 3 1 2 3 4 2 3 4 1 4 7 8 5 8 7 4 5

The remaining 12 orthogonal arrays from the search yield multiplication tables which are not associative.

## Products, Powers, and Primitive Elements

### Products of Elements

The interpretation of the standard form orthogonal array of plus vectors as a multiplication table, and its expression in terms of the first column vector, lead to formulas for products of the levels. The multiplication products expressed in terms of the first column vectors are as follows:

 h x h' = 0 if h=0 or h'=0, andif m>1. h x h' = 1 if h=1 and h'=1, andif m=2. h x h' = fuv({fuv-1(h) - 1 + fuv-1(h') - 1}mod m-1 + 1mod m) if h>0 and h'>0, andif m>2.

### Powers of Elements

In particular, for m>1 the powers of h are given by

 ha = 0 if h=0. ha = 1 if h=1. ha = fuv(a{fuv-1(h) - 1}mod m-1 + 1mod m) if h>1.

In the m=5 example,

 43 = f00(3{f00-1(4) - 1}mod 4 + 1mod 5) = f00(3{3 - 1}mod 4 + 1mod 5) = f00(2 + 1mod 5) = f00(3) = 4

### # Primitive Elements

The powers of h formula for h>1 implies which positions in a first column vector can contain primitive elements. (The powers of a primitive element generate all m-1 nonzero levels.) If q is a totitive of m-1, then fuv(q+1) is a primitive element. (q is a totitive of m-1 if it is a relative prime of m-1 and less than m-1.)

When h=fuv(q+1),

ha = fuv(aqmod m-1 + 1mod m)

If q equals a totitive of m-1,

aqmod m-1 takes on all values = 0, 1, ..., m-2, for a=1, 2, ..., m-1

To see this, divide aq by m-1 as follows,

aq = (m-1)y + z

in which y and z are integers. aqmod m-1 = z, the remainder. A similar expression for a different power is:

a'q = (m-1)y' + z'

Now consider when z'=z.

a'q - (m-1)y' = z' = z = aq - (m-1)y

so

(a'-a)q = (m-1)(y'-y)

Since the right side of the equation is a multiple of m-1, and since q and m-1 are relative primes, a'-a must be a multiple of m-1. Since the values of a=1, 2, ..., m-1 differ by less than m-1, aqmod m-1 = z takes on all m-1 values 0, 1, ..., m-2 without repeating. Now in

ha = fuv(aqmod m-1 + 1mod m)

the argument of fuv must take on all values 1, 2, ..., m-1, so ha generates all nonzero levels.

In the m=5 example, q=1 or 3 (relative primes of 4), so the first column vectors can have primitive elements only with positions 2 or 4. The primitive elements are 2 and 3.

Note that for any m>2, q may be 1 or m-2. Therefore the first column vector positions 2 and m-1 must contain primitive elements.

### # Orders of Elements

Generally the powers of h formula implies which positions in a first column vector contain elements of a particular order. For an element h>1 with order a,

1 = ha = fuv(a{fuv-1(h) - 1}mod m-1 + 1mod m)

Application of fuv-1 and subtraction yield

0 = fuv-1(1) - 1mod m = a{fuv-1(h) - 1}mod m-1

so

y(m-1)=a{fuv-1(h) - 1}

for some integer y. Solving for h yields

h = fuv(y(m-1)/a + 1)

in which 0<y<a, so the position of fuv is greater than 1 and less than m. Also, a must divide y(m-1) so that the position of fuv is an integer. Now y must be a totitive of a (i.e. y/a must be irreducible). To see this, suppose there is a reduced fraction

y'/a' = y/a

in which y'<y and a'<a. Replacement of y/a with y'/a' gives

h = fuv(y'(m-1)/a' + 1)

Then the powers of h formula indicates a' is the order of h:

ha' = fuv(a'{y'(m-1)/a'}mod m-1 + 1mod m) = 1

which contradicts the statement that a is the order of h. Thus, since y is a totitive of a, a cannot divide y, and a must divide m-1.

The order of the first column vector element in each position greater than 1 is determined as follows.

1. Find the allowed orders from the set of integers a>1 which divide m-1.
2. For each order a, find the totitives, which are the allowed values of y.
3. Compute the position y(m-1)/a + 1 for each pair of a,y.

For example, for m=16, the orders and corresponding positions are as follows.

ordertotitiveposition
ayy(m-1)/a + 1
316
211
514
27
310
413
1512
23
45
78
89
1112
1314
1415

The elements of order a=m-1=15 are the primitive elements in this example.

The association of an element's order with its position in the first column vector implies which positions are allowed for the element when there are more than one first column vectors with the same multiplication table. Consider a multiplication table when m=16. The orders of all the nonzero elements are determined by the table, so the orders cannot vary among the first column vectors associated with the table. Thus, the element occurring in position 6 has order 3, and can occur only in position 6 or position 11 of any first column vector associated with this table. Similarly, elements in positions 4, 7, 10, and 13 have order 5 and can occur only in those positions, etc.

A further consequence of the association of an element's order with its position is that there is only one position for order a=2 elements, (m-1)/2+1. When m is odd, m-1 is even, so a can be 2. y must be 1 in this case, so the position for the only order 2 element is (m-1)/2+1. In the cases with m=p a prime, m>2 is odd, and the multiplication table gives modulo m multiplication. In these cases, the element in the (m-1)/2+1 position is m-1, and (m-1)x(m-1)=1.

## Cross Vectors

### Definitions

The m cross vectors kx are defined to be the columns of the multiplication table derived from a first column vector. The vectors are defined for all columns k=0, 1, ..., m-1, disregarding the possibility that only c<m columns may form an orthogonal array. Thus,

kx i = Aik

for i=0, 1, ..., m-1, in which

 Aik = 0 if i=0 or k=0, andif m>1. A11 = 1 if i=1 and k=1, andif m=2. Aik = fuv({fuv-1(i) - 1 + fuv-1(k) - 1}mod m-1 + 1mod m) if i>0 and k>0, andif m>2.

In the example c=m=3, the cross vectors are

 kx: 0x 1x 2x 0 0 0 0 1 2 0 2 1

The unary cross operator acts on an array to replace each element with its corresponding cross vector. The result is an array with m times the number of rows compared to the original array. Thus,

 (0 1 2)x = 0 0 0 0 1 2 0 2 1

Similarly, the raised cross operator replaces each element of an array with its corresponding cross vector transposed. The result is an array with m times the number of columns compared to the original array:

 (0 1 2)x = 0 0 0 0 1 2 0 2 1

The number of levels m for a cross vector or operator usually is taken from its context. If the number of levels is not clear, the value is indicated in braces after the cross (e.g. hx{3} when m=3). When c<m, the cross vectors may be truncated to c elements. This case is indicated by {c/m} or just {c/} after the cross (e.g. hx{2/6} when m=6).

### #Isomorphic Groups and Fields

Note that the addition and multiplication tables given here specify abelian groups for the indicated elements. The addition group is of order m (elements h=0, 1, ..., m-1); the multiplication group is of order m-1 (elements h=1, ..., m-1). When m is a prime or a prime power, the tables define finite (Galois) fields of order m. Other values of m do not yield fields because their multiplication operations are not distributive over addition.

Also note that the plus vectors form isomorphic groups for addition and multiplication. Thus

 h+ + h'+ = (h + h')+ = h+ * h'+ and h+ x h'+ = (h x h')+

If m is a prime or a prime power, the plus vectors form an isomorphic field of order m.

The cross vectors also form isomorphic groups for addition and multiplication. Thus

 hx + h'x = (h + h')x and hx x h'x = (h x h')x = hx * h'x

If m is a prime or a prime power, the cross vectors form an isomorphic field of order m. Moreover, if m is a prime or a prime power, the cross vector addition operation is vector addition according to the addition table. That is, the cross vector components are added as follows

hxj + h'xj = (h + h')xj

for j=0, 1, ..., m-1.

The isomorphisms of the plus and cross vectors to the multiplication groups imply the vectors have the multiplication properties of the multiplication tables. Thus the multiplication properties described in the Products, Powers, and Primitive Elements section apply to the plus vectors and cross vectors as well as to the elements that comprise them. (And these properties do not depend on m being a prime or on m being a prime power.)

### Expressions for Orthogonal Arrays of Strength l=2 and Index One

The orthogonal array of plus vectors of strength l=2 and index one now can be expressed as

0+x{c/}+ or 0+{c/}x+

in terms of the plus and cross operators, when c=2 or c=m. Inclusion of the solutions at infinity1 yields an additional column

0+. 0+x{c/}+

expressed in terms of the plus and dot operators.

For c=m=3, the expression is evaluated as follows.

 0+. 0+x{c/}+ = ( 0 1 2 ). ( 0 1 2 )x+ = ( 0 1 2 ). ( 0 0 0 0 1 2 0 2 1 )+ = 0 0 0 1 1 1 2 2 2 0 1 2 0 1 2 0 1 2 0 1 2 1 2 0 2 0 1 0 1 2 2 0 1 1 2 0

When c=2 or c=m, the standard form orthogonal array expressions above can be used, because each vector in the first row is k+, k=0, 1, ..., c-1, with no gaps in the sequence. When 2<c<m, some values of k<c may not follow from the first column vector. For example, when m=12 and c=4, there is a first column vector

 fuv = 0 1 2 4 10 9 8 11 3 6 7 5 labeled by the vectors u = 0 and v = 0 1

fuv yields the orthogonal array

 ( 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 4 10 9 8 11 3 6 7 5 0 2 4 10 9 8 11 3 6 7 5 1 0 4 10 9 8 11 3 6 7 5 1 2 )+ in diagonal form, and ( 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 0 2 4 6 10 1 7 5 11 8 9 3 0 4 10 7 9 2 5 1 3 11 8 6 )+ in standard form.

In this case the vectors in the first row are k+, k=0, 1, 2, 4.

Generally each orthogonal array of plus vectors of strength l=2 and index one can be expressed as

0+. guv x+

in terms of a first row vector

guv = sort(fuvT {c/})

which is a first column vector transposed, truncated to c columns, and sorted in ascending order. In this example guv = 0 1 2 4 .

Examples of first column vectors and first row vectors for the values of m between 2 and 23 are given below.

1. 3.2 Bush's Construction, Orthogonal Arrays Theory and Applications by A. S. Hedayat, N. J. A. Sloane, and John Stufken, 1999 Springer-Verlag.

### #Alternate Plus Vector Definitions

It is also possible to remove the gaps in the k+ sequence k=0, 1, ..., c-1 with alternate definitions of the plus vectors. An appropriate selection of level representations yields a first row vector

guv = 0+{c/}

so the earlier l=2 orthogonal array expressions

0+. 0+x{c/}+ or 0+. 0+{c/}x+

can be used.

In the m=12 example from the previous section, consider the alternate level representation array R' which has the levels 3 and 4 interchanged compared to the original definition of R.

 R'(0+) = R( 0 1 2 4 3 5 6 7 8 9 10 11 ) = 0 1 2 0 3 1 2 3 0 1 2 3 0 1 2 1 0 2 0 1 2 0 1 2

The alternate level representation array R' leads to an alternate addition table and alternate plus vectors and plus operators, as follows.

 + 0+ 1+ 2+ 3+ 4+ 5+ 6+ 7+ 8+ 9+ 10+ 11+ 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 1 8 4 5 10 0 7 2 9 3 11 6 2 4 3 6 5 7 8 9 10 11 0 1 3 5 6 8 7 9 10 11 0 1 2 4 4 10 5 7 0 2 9 3 11 6 1 8 5 0 7 9 2 3 11 6 1 8 4 10 6 7 8 10 9 11 0 1 2 4 3 5 7 2 9 11 3 6 1 8 4 10 5 0 8 9 10 0 11 1 2 4 3 5 6 7 9 3 11 1 6 8 4 10 5 0 7 2 10 11 0 2 1 4 3 5 6 7 8 9 11 6 1 4 8 10 5 0 7 2 9 3

The corresponding first column vector f'uv becomes

 f'uv = 0 1 2 3 10 9 8 11 4 6 7 5 and f'uv yields the orthogonal array

 ( 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 10 9 8 11 4 6 7 5 0 2 3 10 9 8 11 4 6 7 5 1 0 3 10 9 8 11 4 6 7 5 1 2 )+ in diagonal form, and ( 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 0 2 3 10 6 1 7 5 11 8 9 4 0 3 10 9 7 2 5 1 4 11 8 6 )+ in standard form.

Thus the vectors in the first row are k+, k=0, 1, 2, 3, and the gap is eliminated.

# First Column Vectors and their Mapping Operators

## Mapping Operators

### Level Mapping Operators

The numbers of first column vectors and standard form arrays for values of m up to 23 are tabulated below.

mc Number of
First Column
Vectors
Number of
Standard Form
Arrays
2211
3311
4421
5521
62241
7721
88488
99123
1028!1
111141
1242424
131341
14212!1
1546464
16162688336
171781
18216!1
191961
20437443744
2141237212372
22220!1
2323101

It is apparent from the table that the number of first column vectors can increase rapidly with m. It is convenient to express the first column vectors for m in terms of one particular first column vector because typically there are mapping operators which can be factored and tabulated concisely. The mapping operators also highlight the relationships among the first column vectors.

For a given value of m, the first column vectors are ordered by assigning decreasing significance to elements with increasing positions. Thus, the element with position 0 has the most significance, and the element with position m-1 has the least. For example, 0. = 0x is the lowest possible vector, and the identity vector 0+ = 1x is the lowest candidate for a first column vector. (Lowest first column vectors and lowest first row vectors for the values of m between 2 and 23 are given below.) Each first column vector for m is expressed in terms of the lowest first column vector, which is f00. Specifically,

fuv = f00 * Muv

in which the first column vector mapping operator

Muv = f00-1 * fuv

The effect of Muv (operating on the right) is to map the levels of f00 to those of fuv .

For example, for m=9 the two lowest first column vectors are

 f00 = 0 1 3 4 7 2 6 8 5 and fuv = 0 1 3 7 8 2 6 5 4 in which the vectors u = 11 and v = 1

label the second lowest first column vector. The mapping operator is

 Muv = 0 1 2 3 7 4 6 8 5 and fuv = f00 * Muv = 0 1 3 4 7 2 6 8 5 * 0 1 2 3 7 4 6 8 5

Here each position h of Muv(h) equals a level of f00 and is mapped to a corresponding level of fuv:

fuv = f00 * Muv = Muv(f00)

The mapping can be tabulated as follows.

 Level of f00h Level of fuvMuv(h) 0 => 0 1 => 1 2 => 2 3 => 3 4 => 7 5 => 4 6 => 6 7 => 8 8 => 5

Thus Muv is called a level mapping operator because it maps the levels of the vector on its left to a new set of levels.

In the cases considered here, Muv can be factored into two level mapping operators Su and Dv, so that

Muv = Su * Dv

in which Su maps f00 to first column vectors yielding the same multiplication table, and Dv maps f00 to first column vectors yielding different multiplication tables. In the m=9 example

 Su * Dv = 0 1 2 5 8 3 7 6 4 * 0 1 2 4 5 3 8 6 7 = 0 1 2 3 7 4 6 8 5 = Muv

Here,

fu0 = f00 * Su

yields the same multiplication table as that of f00, and

f0v = f00 * Dv

yields a different multiplication table (since v is not 0, the zero vector).

Generally the first column vectors for m=9 can be expressed in terms of level mapping operators associated with the components of the u and v vectors:

Su = Su0 * Su1

and

Dv = Dv0

so

Muv = Su * Dv = Su0 * Su1 * Dv0

with the level mapping operators tabulated as follows.

u0: 0 1 u1: 0 1 v0: 0 1 2 3 4 5 6 7 8 0 1 2 7 8 6 5 3 4 0 1 2 3 4 5 6 7 8 0 1 2 6 4 7 3 5 8 0 1 2 3 4 5 6 7 8 0 1 2 4 5 3 8 6 7 0 1 2 5 3 4 7 8 6

The twelve first column vectors are given by evaluating f00 * Muv for all combinations of values for u0, u1 and v0. The first column vectors for m=9 are tabulated in a later section.

### Position Mapping Operators

The cap operator ^ acts on a vector of order m to yield its vector product with f00 on the left and f00-1 on the right.

^Muv = f00 * Muv * f00-1

The cap operator transforms a level mapping operator (acting on the right) to a position mapping operator which acts on the left:

^Muv * f00 = f00 * Muv * f00-1 * f00 = fuv

In the m=9 example with the two lowest first column vectors,

 f00 = 0 1 3 4 7 2 6 8 5 and fuv = 0 1 3 7 8 2 6 5 4 in which the vectors u = 11 and v = 1

label the second lowest first column vector. The position mapping operator is

 ^Muv = 0 1 2 4 7 5 6 8 3 and fuv = ^Muv * f00 = 0 1 2 4 7 5 6 8 3 * 0 1 3 4 7 2 6 8 5

Here the value of ^Muv(i) equals a position of f00 and is mapped to the corresponding position i of fuv(i):

fuv = ^Muv * f00 = f00(^Muv)

The mapping can be tabulated as follows.

 Position of fuvi Position of f00^Muv(i) 0 <= 0 1 <= 1 2 <= 2 3 <= 4 4 <= 7 5 <= 5 6 <= 6 7 <= 8 8 <= 3

Thus ^Muv is called a position mapping operator because it maps the positions of the vector on its right to a new set of positions.

Now when Muv is factored into Su and Dv, ^Muv can be factored also:

^Muv = ^Su * ^Dv

In the m=9 example

 ^Su * ^Dv = 0 1 8 7 6 5 4 3 2 * 0 1 3 8 6 5 7 4 2 = 0 1 2 4 7 5 6 8 3 = ^Muv

Generally the first column vectors for m=9 can be expressed in terms of position mapping operators associated with the components of the u and v vectors:

^Muv = ^Su * ^Dv = ^Su0 * ^Su1 * ^Dv0

with the position mapping operators tabulated as follows.

u0: 0 1 u1: 0 1 v0: 0 1 2 3 4 5 6 7 8 0 1 4 7 2 5 8 3 6 0 1 2 3 4 5 6 7 8 0 1 6 3 8 5 2 7 4 0 1 2 3 4 5 6 7 8 0 1 3 8 6 5 7 4 2 0 1 8 2 7 5 4 6 3

The twelve first column vectors are given by evaluating ^Muv * f00 for all combinations of values for u0, u1 and v0.

### #Isomorphic Groups

In the cases considered here, when m is a prime or a prime power, each of the position mapping operators ^Su, which maps to the same multiplication table, is equal to a difference vector dq:

^Su = dq

in which

 dq(i) = 0 if i=0, andif m>1. dq(i) = 1 if i=1, andif m=2. dq(i) = (i-1)qmod m-1 + 1mod m if i>0, andif m>2.

Here q is a totitive of m-1.

In the m=9 example, q=1, 3, 5, or 7.

Regardless of whether m is a prime or a prime power, the difference vectors form a group with the vector product operator. This group is isomorphic to the group of totitives of m-1 with multiplication modulo m-1.

For m>2 and i>0,

 (dq * dq')(i) = dq'(dq(i)) = dq'((i-1)qmod m-1 + 1mod m) = (i-1)qq'mod m-1 + 1mod m = dqq'(i)

And for i=0,

(dq * dq')(0) = 0 = dqq'(0)

so

dq * dq' = dqq'

Thus, for example, when m=6, the difference vectors are

d1d2d3d4
0
1
2
3
4
5
0
1
3
5
2
4
0
1
4
2
5
3
0
1
5
4
3
2

and the table of their vector products is

while for m=9, the difference vectors are

d1d3d5d7
0
1
2
3
4
5
6
7
8
0
1
4
7
2
5
8
3
6
0
1
6
3
8
5
2
7
4
0
1
8
7
6
5
4
3
2

and the table of their vector products is

In both cases examination of the q subscripts in the table indicates the structure of modulo m-1 multiplication.

When m is a prime or a prime power, ^Su=dq, so the ^Su position mapping vectors also form an isomorphic group with the vector product. And since

^Su * ^Su' = f00 * Su * f00-1 * f00 * Su' * f00-1
= f00 * Su * Su' * f00-1
= ^(Su * Su')

the Su level mapping vectors form an isomorphic group with the vector product as well.

Note that the number of Su or ^Su mapping vectors is the number of totitives of m-1 (the totient of m-1).

## First Column Vectors and Mapping Operators for m=prime

### # First Column Vectors for m=prime

Listed below are the first column vectors fuv for prime values of m up to 23. When multiple first column vectors are possible, they are listed in ascending order. The u and v vectors label the first column vectors according to the mapping operators given in the following sections. The lowest first column vector f00 is listed first. Each column in a table below lists

• the u vector,
• the v vector, and
• the corresponding fuv vector.

Note that the primitive elements are contained in positions 2 and m-1 (and sometimes other positions). Also note that for m>2, position (m-1)/2+1 always contains the level m-1.

The first column vector tables for m=prime are as follows.

m: m: m: m: m: m: u: u: u: u: u: u: v: v: 2 3 5 7 11 13 0 0 0 1 0 1 00 01 11 10 00 10 11 01 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 2 0 1 2 4 3 0 1 3 4 2 0 1 3 2 6 4 5 0 1 5 4 6 2 3 0 1 2 4 8 5 10 9 7 3 6 0 1 6 3 7 9 10 5 8 4 2 0 1 7 5 2 3 10 4 6 9 8 0 1 8 9 6 4 10 3 2 5 7 0 1 2 4 8 3 6 12 11 9 5 10 7 0 1 6 10 8 9 2 12 7 3 5 4 11 0 1 7 10 5 9 11 12 6 3 8 4 2 0 1 11 4 5 3 7 12 2 9 8 10 6

 m: m: m: u: u: u: v: v: v: fuv: fuv: fuv: 17 19 23 000 101 011 110 100 001 111 010 00 02 11 10 01 12 00 14 02 04 12 13 10 03 01 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 3 9 10 13 5 15 11 16 14 8 7 4 12 2 6 0 1 5 8 6 13 14 2 10 16 12 9 11 4 3 15 7 0 1 6 2 12 4 7 8 14 16 11 15 5 13 10 9 3 0 1 7 15 3 4 11 9 12 16 10 2 14 13 6 8 5 0 1 10 15 14 4 6 9 5 16 7 2 3 13 11 8 12 0 1 11 2 5 4 10 8 3 16 6 15 12 13 7 9 14 0 1 12 8 11 13 3 2 7 16 5 9 6 4 14 15 10 0 1 14 9 7 13 12 15 6 16 3 8 10 4 5 2 11 0 1 2 4 8 16 13 7 14 9 18 17 15 11 3 6 12 5 10 0 1 3 9 8 5 15 7 2 6 18 16 10 11 14 4 12 17 13 0 1 10 5 12 6 3 11 15 17 18 9 14 7 13 16 8 4 2 0 1 13 17 12 4 14 11 10 16 18 6 2 7 15 5 8 9 3 0 1 14 6 8 17 10 7 3 4 18 5 13 11 2 9 12 16 15 0 1 15 16 12 9 2 11 13 5 18 4 3 7 10 17 8 6 14 0 1 5 2 10 4 20 8 17 16 11 9 22 18 21 13 19 3 15 6 7 12 14 0 1 7 3 21 9 17 4 5 12 15 13 22 16 20 2 14 6 19 18 11 8 10 0 1 10 8 11 18 19 6 14 2 20 16 22 13 15 12 5 4 17 9 21 3 7 0 1 11 6 20 13 5 9 7 8 19 2 22 12 17 3 10 18 14 16 15 4 21 0 1 14 12 7 6 15 3 19 13 21 18 22 9 11 16 17 8 20 4 10 2 5 0 1 15 18 17 2 7 13 11 4 14 3 22 8 5 6 21 16 10 12 19 9 20 0 1 17 13 14 8 21 12 20 18 7 4 22 6 10 9 15 2 11 3 5 16 19 0 1 19 16 5 3 11 2 15 9 10 6 22 4 7 18 20 12 21 8 14 13 17 0 1 20 9 19 12 10 16 21 6 5 8 22 3 14 4 11 13 7 2 17 18 15 0 1 21 4 15 16 14 18 10 3 17 12 22 2 19 8 7 9 5 13 20 6 11

### # Level Mapping Operators for m=prime

Listed below are the level mapping operators Su and Dv associated with the first column vectors fuv for prime values of m up to 23. These operators give the mapping

fuv = f00 * Muv = f00 * Su * Dv

in which f00 is the lowest first column vector. Each column in a table below lists the u vector and corresponding Su operator, or the v vector and corresponding Dv operator. When multiple level mapping operators Su are possible, they are listed in the same order as the position mapping operators ^Su in a following section.

Note that for prime values of m, v=0 and Dv=0+ the identity operator. This means that there is only one multiplication table for each prime m, and all the first column vectors yield that table. (This is the modulo m multiplication table.)

Also note that Su(h) gives the allowed levels fu0(i) mapped from f00(i) according to the fu0=Su(f00) level mapping. Consider, for example, when m=11 and i=3. Then f00(3)=4=h. The allowed levels for fu0(3) are given in the h=4 "position" of Su(h). In this case the allowed levels are 4, 9, 5, and 3. In particular, for

 u = 11 , fu0(3) = Su(f00(3)) = Su(4) = 5

Finally, note that for m=prime, level m-1 maps to itself. Thus for m=11,

fu0(6) = Su(f00(6)) = Su(10) = 10, for all u.

The level mapping operator tables for m=prime are as follows.

m: m: m: m: m: u: v: u: v: u: v: u: v: u: v: Su: 2 3 5 7 11 0 0 0 0 0 1 0 0 1 0 00 10 11 01 0 0 1 0 1 0 1 2 0 1 2 0 1 2 3 4 0 1 3 2 4 0 1 2 3 4 0 1 2 3 4 5 6 0 1 4 5 2 3 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 8 9 10 0 1 8 5 9 4 7 2 6 3 10 0 1 7 9 5 3 8 6 2 4 10 0 1 6 4 3 9 2 8 7 5 10 0 1 2 3 4 5 6 7 8 9 10

 m: m: u: v: u: v: Su: Dv: Su: Dv: 13 17 00 10 01 11 0 000 100 101 001 010 110 111 011 0 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 6 9 10 5 2 11 8 3 4 7 12 0 1 11 3 4 8 7 6 5 9 10 2 12 0 1 7 9 10 8 11 2 5 3 4 6 12 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 1 8 10 13 6 12 3 2 15 14 5 11 4 7 9 16 0 1 15 5 4 14 7 11 9 8 6 10 3 13 12 2 16 0 1 9 11 13 10 14 12 15 2 5 3 7 4 6 8 16 0 1 2 14 4 12 11 10 8 9 7 6 5 13 3 15 16 0 1 8 7 13 11 5 14 2 15 3 12 6 4 10 9 16 0 1 15 12 4 3 10 6 9 8 11 7 14 13 5 2 16 0 1 9 6 13 7 3 5 15 2 12 14 10 4 11 8 16 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

 m: m: u: v: u: v: Su: Dv: Su: Dv: 19 23 00 10 01 12 02 11 0 00 02 01 10 04 11 03 13 14 12 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 0 1 13 15 17 9 5 11 12 16 3 7 8 14 10 2 4 6 18 0 1 14 2 6 16 9 7 8 4 15 11 12 10 3 13 17 5 18 0 1 15 10 16 6 17 11 12 5 14 7 8 2 13 3 9 4 18 0 1 3 14 9 17 4 7 8 6 13 11 12 15 2 10 5 16 18 0 1 10 13 5 4 16 11 12 17 2 7 8 3 15 14 6 9 18 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 8 4 18 10 9 21 6 16 11 20 3 12 7 17 2 14 13 5 19 15 22 0 1 9 13 12 20 2 17 16 8 19 5 18 4 15 7 6 21 3 11 10 14 22 0 1 13 2 8 17 3 5 12 4 14 7 16 9 19 11 18 20 6 15 21 10 22 0 1 6 18 13 11 16 15 9 2 20 19 4 3 21 14 8 7 12 10 5 17 22 0 1 4 9 16 21 13 20 18 12 15 17 6 8 11 5 3 10 2 7 14 19 22 0 1 16 12 3 19 8 14 2 6 5 10 13 18 17 21 9 15 4 20 11 7 22 0 1 18 16 2 15 12 19 13 3 17 14 9 6 20 10 4 11 8 21 7 5 22 0 1 3 6 9 7 18 11 4 13 21 15 8 2 10 19 12 5 16 14 17 20 22 0 1 12 8 6 14 4 10 3 18 7 21 2 16 5 20 13 19 9 17 15 11 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

### # Level Mapping Operator Factors for m=prime

Listed below are the level mapping operator factors for prime values of m up to 23. These operators give the mapping

fuv = f00 * Muv = f00 * Su * Dv

in which f00 is the lowest first column vector, and the level mapping operators Su and Dv are factored by components of the u and v vectors.

Su = Su0 * Su1 * ...
Dv = Dv0 * Dv1 * ...

The level mapping operator factors are constructed such that any combination of the listed u and v components yields an allowed first column vector.

Consider, for example, m=11, with u0=1, u1=1, and v0=0. The element in position 3 of this first column vector is

 fuv(3) = (f00 * Su0=1 * Su1=1 * Dv0=0)(3) = Dv0=0(Su1=1(Su0=1(f00(3)))) = Dv0=0(Su1=1(Su0=1(4))) = Dv0=0(Su1=1(9)) = Dv0=0(5) = 5

This level agrees with the one listed for the third position of this first column vector.

Note that other factoring schemes are possible.

The level mapping operator factor tables for m=prime are as follows.

m: m: m: m: m: u0: v0: u0: v0: u0: v0: u0: v0: u0: u1: v0: 2 3 5 7 11 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 1 0 1 2 0 1 2 0 1 2 3 4 0 1 3 2 4 0 1 2 3 4 0 1 2 3 4 5 6 0 1 4 5 2 3 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 8 9 10 0 1 8 5 9 4 7 2 6 3 10 0 1 2 3 4 5 6 7 8 9 10 0 1 6 4 3 9 2 8 7 5 10 0 1 2 3 4 5 6 7 8 9 10

m: m: u0: u1: v0: u0: u1: u2: v0: Su0: Su1: Dv0: 13 17 0 1 0 1 0 0 1 0 1 0 1 0 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 6 9 10 5 2 11 8 3 4 7 12 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 11 3 4 8 7 6 5 9 10 2 12 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 1 8 10 13 6 12 3 2 15 14 5 11 4 7 9 16 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 1 2 14 4 12 11 10 8 9 7 6 5 13 3 15 16 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 1 9 11 13 10 14 12 15 2 5 3 7 4 6 8 16 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

m: m: u0: u1: v0: u0: u1: v0: Su0: Su1: Dv0: Su0: Su1: Dv0: 19 23 0 1 0 1 2 0 0 1 0 1 2 3 4 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 0 1 13 15 17 9 5 11 12 16 3 7 8 14 10 2 4 6 18 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 0 1 14 2 6 16 9 7 8 4 15 11 12 10 3 13 17 5 18 0 1 3 14 9 17 4 7 8 6 13 11 12 15 2 10 5 16 18 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 13 2 8 17 3 5 12 4 14 7 16 9 19 11 18 20 6 15 21 10 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 9 13 12 20 2 17 16 8 19 5 18 4 15 7 6 21 3 11 10 14 22 0 1 8 4 18 10 9 21 6 16 11 20 3 12 7 17 2 14 13 5 19 15 22 0 1 16 12 3 19 8 14 2 6 5 10 13 18 17 21 9 15 4 20 11 7 22 0 1 6 18 13 11 16 15 9 2 20 19 4 3 21 14 8 7 12 10 5 17 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

### # Position Mapping Operators for m=prime

Listed below are the position mapping operators ^Su and ^Dv associated with the first column vectors fuv for prime values of m up to 23. These operators give the mapping

fuv = ^Muv * f00 = ^Su * ^Dv * f00

in which f00 is the lowest first column vector. Each column in a table below lists the u vector and corresponding ^Su operator, or the v vector and corresponding ^Dv operator. The values of q for which ^Su=dq also are listed in the ^Su columns. When multiple position mapping operators ^Su are possible, they are listed in the same order as the level mapping operators Su in a previous section. This order is that of ascending q.

Note that for prime values of m, v=0 and ^Dv=0+ the identity operator. This means that there is only one multiplication table for each prime m, and all the first column vectors yield that table. (This is the modulo m multiplication table.)

Also note that ^Su(i) gives the allowed positions of f00 which map to fu0(i) according to the fu0=f00(^Su) position mapping. Consider, for example, when m=11 and i=3. Then ^Su(3)=3, 7, 5, or 9. In particular, for

 u = 11 , fu0(3) = f00(^Su(3)) = f00(5) = 5

Finally, note that for prime m>2, position (m-1)/2+1 maps to itself. Thus for m=11,

fu0(6) = f00(^Su(6)) = f00(6) = 10, for all u.

The position mapping operator tables for m=prime are as follows.

m: m: m: m: m: u: v: u: v: u: v: u: v: u: v: q: q: q: q: q: 2 3 5 7 11 0 0 0 0 0 1 0 0 1 0 00 10 11 01 0 1 1 1 3 1 5 1 3 7 9 0 1 0 1 0 1 2 0 1 2 0 1 2 3 4 0 1 4 3 2 0 1 2 3 4 0 1 2 3 4 5 6 0 1 6 5 4 3 2 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 8 9 10 0 1 4 7 10 3 6 9 2 5 8 0 1 8 5 2 9 6 3 10 7 4 0 1 10 9 8 7 6 5 4 3 2 0 1 2 3 4 5 6 7 8 9 10

 m: m: u: v: u: v: q: q: ^Su: ^Dv: ^Su: ^Dv: 13 17 00 10 01 11 0 000 100 101 001 010 110 111 011 0 1 5 7 11 1 3 5 7 9 11 13 15 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 6 11 4 9 2 7 12 5 10 3 8 0 1 8 3 10 5 12 7 2 9 4 11 6 0 1 12 11 10 9 8 7 6 5 4 3 2 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 1 4 7 10 13 16 3 6 9 12 15 2 5 8 11 14 0 1 6 11 16 5 10 15 4 9 14 3 8 13 2 7 12 0 1 8 15 6 13 4 11 2 9 16 7 14 5 12 3 10 0 1 10 3 12 5 14 7 16 9 2 11 4 13 6 15 8 0 1 12 7 2 13 8 3 14 9 4 15 10 5 16 11 6 0 1 14 11 8 5 2 15 12 9 6 3 16 13 10 7 4 0 1 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

 m: m: u: v: u: v: q: q: ^Su: ^Dv: ^Su: ^Dv: 19 23 00 10 01 12 02 11 0 00 02 01 10 04 11 03 13 14 12 0 1 5 7 11 13 17 1 3 5 7 9 13 15 17 19 21 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 0 1 6 11 16 3 8 13 18 5 10 15 2 7 12 17 4 9 14 0 1 8 15 4 11 18 7 14 3 10 17 6 13 2 9 16 5 12 0 1 12 5 16 9 2 13 6 17 10 3 14 7 18 11 4 15 8 0 1 14 9 4 17 12 7 2 15 10 5 18 13 8 3 16 11 6 0 1 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 4 7 10 13 16 19 22 3 6 9 12 15 18 21 2 5 8 11 14 17 20 0 1 6 11 16 21 4 9 14 19 2 7 12 17 22 5 10 15 20 3 8 13 18 0 1 8 15 22 7 14 21 6 13 20 5 12 19 4 11 18 3 10 17 2 9 16 0 1 10 19 6 15 2 11 20 7 16 3 12 21 8 17 4 13 22 9 18 5 14 0 1 14 5 18 9 22 13 4 17 8 21 12 3 16 7 20 11 2 15 6 19 10 0 1 16 9 2 17 10 3 18 11 4 19 12 5 20 13 6 21 14 7 22 15 8 0 1 18 13 8 3 20 15 10 5 22 17 12 7 2 19 14 9 4 21 16 11 6 0 1 20 17 14 11 8 5 2 21 18 15 12 9 6 3 22 19 16 13 10 7 4 0 1 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

### # Position Mapping Operator Factors for m=prime

Listed below are the position mapping operator factors for prime values of m up to 23. These operators give the mapping

fuv = ^Muv * f00 = ^Su * ^Dv * f00

in which f00 is the lowest first column vector, and the position mapping operators ^Su and ^Dv are factored by components of the u and v vectors.

^Su = ^Su0 * ^Su1 * ...
^Dv = ^Dv0 * ^Dv1 * ...

The position mapping operator factors are constructed such that any combination of the listed u and v components yields an allowed first column vector.

Consider, for example, m=11, with u0=1, u1=1, and v0=0. The element in position 3 of this first column vector is

 fuv(3) = (^Su0=1 * ^Su1=1 * ^Dv0=0 * f00)(3) = f00(^Dv0=0(^Su1=1(^Su0=1(3)))) = f00(^Dv0=0(^Su1=1(7))) = f00(^Dv0=0(5)) = f00(5) = 5

This level agrees with the one listed for the third position of this first column vector.

Note that other factoring schemes are possible.

The position mapping operator factor tables for m=prime are as follows.

m: m: m: m: m: u0: v0: u0: v0: u0: v0: u0: v0: u0: u1: v0: q: q: q: q: 2 3 5 7 11 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 3 1 5 1 3 1 9 0 1 0 1 0 1 2 0 1 2 0 1 2 3 4 0 1 4 3 2 0 1 2 3 4 0 1 2 3 4 5 6 0 1 6 5 4 3 2 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 8 9 10 0 1 4 7 10 3 6 9 2 5 8 0 1 2 3 4 5 6 7 8 9 10 0 1 10 9 8 7 6 5 4 3 2 0 1 2 3 4 5 6 7 8 9 10

m: m: u0: u1: v0: u0: u1: u2: v0: q: q: q: 13 17 0 1 0 1 0 0 1 0 1 0 1 0 1 5 1 7 1 3 1 9 1 7 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 6 11 4 9 2 7 12 5 10 3 8 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 8 3 10 5 12 7 2 9 4 11 6 0 1 2 3 4 5 6 7 8 9 10 11 12 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 1 4 7 10 13 16 3 6 9 12 15 2 5 8 11 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 1 10 3 12 5 14 7 16 9 2 11 4 13 6 15 8 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 0 1 8 15 6 13 4 11 2 9 16 7 14 5 12 3 10 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

m: m: u0: u1: v0: u0: u1: v0: q: q: q: q: ^Su0: ^Su1: 19 23 0 1 0 1 2 0 0 1 0 1 2 3 4 0 1 5 1 7 13 1 7 1 5 3 15 9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 0 1 6 11 16 3 8 13 18 5 10 15 2 7 12 17 4 9 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 0 1 8 15 4 11 18 7 14 3 10 17 6 13 2 9 16 5 12 0 1 14 9 4 17 12 7 2 15 10 5 18 13 8 3 16 11 6 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 8 15 22 7 14 21 6 13 20 5 12 19 4 11 18 3 10 17 2 9 16 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 6 11 16 21 4 9 14 19 2 7 12 17 22 5 10 15 20 3 8 13 18 0 1 4 7 10 13 16 19 22 3 6 9 12 15 18 21 2 5 8 11 14 17 20 0 1 16 9 2 17 10 3 18 11 4 19 12 5 20 13 6 21 14 7 22 15 8 0 1 10 19 6 15 2 11 20 7 16 3 12 21 8 17 4 13 22 9 18 5 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

## First Column Vectors and Mapping Operators for m=prime power

### #Selected First Column Vectors for m=prime power

Listed below are selected first column vectors fuv for values of m which are prime powers. First column vectors are given for m=4, 8, 9, and 16. The first column vectors are listed starting with the lowest first column vector f00, in ascending order. The number of first column vectors listed for each value of m is as follows.

mNumber of First
Column Vectors Listed
42 of 2
810 of 48
912 of 12
1610 of 2688

The u and v vectors label the first column vectors according to the mapping operators given in the following sections. Each column in a table below lists

• the u vector,
• the v vector, and
• the corresponding fuv vector.

Note that the primitive elements are contained in positions 2 and m-1 (and sometimes other positions). Also note that for m=9 which is odd, position (m-1)/2+1=5 always contains the level 2.

The first column vector tables for m=prime power are as follows.

 m: m: u: u: v: v: fuv: fuv: 4 8 0 1 00 00 00 00 00 00 00 00 12 10 0 0 000 100 011 111 010 110 001 101 111 011 0 1 2 3 0 1 3 2 0 1 2 4 3 6 7 5 0 1 2 4 5 7 3 6 0 1 2 5 3 7 6 4 0 1 2 5 4 6 3 7 0 1 2 6 3 4 5 7 0 1 2 6 7 5 3 4 0 1 2 7 3 5 4 6 0 1 2 7 6 4 3 5 0 1 3 4 2 7 6 5 0 1 3 4 5 6 2 7

 m: m: u: u: v: v: fuv: fuv: 9 16 00 11 00 11 00 11 01 10 01 10 01 10 000 000 000 000 000 000 000 000 000 000 0 1 1 2 2 0 0 1 2 0 1 2 000000 200000 010000 210000 100000 400000 110000 410000 001000 201000 0 1 3 4 7 2 6 8 5 0 1 3 7 8 2 6 5 4 0 1 4 5 6 2 8 7 3 0 1 4 6 7 2 8 3 5 0 1 5 3 8 2 7 6 4 0 1 5 8 6 2 7 4 3 0 1 6 4 5 2 3 8 7 0 1 6 7 4 2 3 5 8 0 1 7 3 4 2 5 6 8 0 1 7 8 3 2 5 4 6 0 1 8 5 3 2 4 7 6 0 1 8 6 5 2 4 3 7 0 1 2 4 8 3 6 12 11 5 10 7 14 15 13 9 0 1 2 4 8 9 11 15 7 14 5 10 13 3 6 12 0 1 2 4 9 3 6 13 10 5 11 7 15 14 12 8 0 1 2 4 9 8 10 14 7 15 5 11 12 3 6 13 0 1 2 4 10 3 6 14 9 5 8 7 12 13 15 11 0 1 2 4 10 11 9 13 7 12 5 8 15 3 6 14 0 1 2 4 11 3 6 15 8 5 9 7 13 12 14 10 0 1 2 4 11 10 8 12 7 13 5 9 14 3 6 15 0 1 2 4 12 3 6 8 15 5 14 7 10 11 9 13 0 1 2 4 12 13 15 11 7 10 5 14 9 3 6 8

### # Selected Level Mapping Operators for m=prime power

Listed below are selected level mapping operators Su and Dv associated with the first column vectors fuv for values of m which are prime powers. Level mapping operators are given for m=4, 8, 9, and 16. These operators give the mapping

fuv = f00 * Muv = f00 * Su * Dv

in which f00 is the lowest first column vector. The number of level mapping operators listed for each value of m is as follows.

m Number of Su LevelMapping Operators Listed Number of Dv LevelMapping Operators Listed 4 2 of 2 1 of 1 8 6 of 6 8 of 8 9 4 of 4 3 of 3 16 8 of 8 10 of 336

Each column in a table below lists the u vector and corresponding Su operator, or the v vector and corresponding Dv operator. There are multiple level mapping operators Su for m=prime power. They are listed in the same order as the corresponding position mapping operators ^Su in a following section.

Note that for values of m which are prime powers, there can be more than one Dv level mapping operator. This means that there can be more than one multiplication table for each value of m. Each level mapping operator product

Muv = Su * Dv

maps f00 to a first column vector fuv which yields the multiplication table of

f0v = f00 * 0+ * Dv = f00 * Dv

Also note that Muv(h) gives the allowed levels fuv(i) mapped from f00(i) according to the fuv=Muv(f00)=Dv(Su(f00)) level mapping. Consider, for example, when m=9 and i=3. Then f00(3)=4=h. The h=4 position of the Su operators gives the allowed levels 4 and 8, which map to positions 4 and 8 of the Dv operators. The allowed levels of Dv are 4, 5, 3 and 8, 7, 6 for positions 4 and 8 respectively. Thus, the allowed levels for fuv(3) are 3, 4, 5, 6, 7, and 8. In particular, for

 u = 11 and v = 1, fuv(3) = Dv(Su(f00(3))) = Dv(Su(4)) = Dv(8) = 7

The level mapping operator tables for m=prime power are as follows.

 m: m: u: v: u: v: Su: Dv: Su: Dv: 4 8 0 1 0 00 01 10 02 12 11 000 001 010 011 100 101 110 111 0 1 2 3 0 1 3 2 0 1 2 3 0 1 2 3 4 5 6 7 0 1 4 5 6 7 2 3 0 1 3 4 5 6 7 2 0 1 6 7 2 3 4 5 0 1 7 2 3 4 5 6 0 1 5 6 7 2 3 4 0 1 2 3 4 5 6 7 0 1 2 3 7 6 5 4 0 1 2 3 6 7 4 5 0 1 2 3 5 4 7 6 0 1 2 5 4 6 7 3 0 1 2 6 7 5 4 3 0 1 2 7 6 4 5 3 0 1 2 4 5 7 6 3

 m: u: v: Su: Dv: 9 00 10 01 11 0 1 2 0 1 2 3 4 5 6 7 8 0 1 2 7 8 6 5 3 4 0 1 2 6 4 7 3 5 8 0 1 2 5 8 3 7 6 4 0 1 2 3 4 5 6 7 8 0 1 2 4 5 3 8 6 7 0 1 2 5 3 4 7 8 6

 m: u: v: Su: Dv: 16 000 100 010 001 110 111 011 101 000000 001000 010000 100000 110000 200000 201000 210000 400000 410000 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 4 5 3 2 7 6 12 13 8 9 15 14 11 10 0 1 3 2 5 4 6 7 15 14 12 13 10 11 9 8 0 1 11 13 9 14 6 7 12 5 8 3 15 2 4 10 0 1 5 4 2 3 7 6 10 11 15 14 8 9 13 12 0 1 14 9 11 13 7 6 8 3 10 4 12 5 2 15 0 1 13 11 14 9 6 7 10 4 15 2 8 3 5 12 0 1 9 14 13 11 7 6 15 2 12 5 10 4 3 8 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 12 13 14 15 8 9 10 11 0 1 2 3 4 5 6 7 9 8 11 10 13 12 15 14 0 1 2 3 4 5 6 7 10 11 8 9 14 15 12 13 0 1 2 3 4 5 6 7 11 10 9 8 15 14 13 12 0 1 2 9 4 14 11 10 8 12 5 7 15 6 13 3 0 1 2 13 4 10 15 14 12 8 5 7 11 6 9 3 0 1 2 8 4 15 10 11 9 13 5 7 14 6 12 3 0 1 2 11 4 12 9 8 10 14 5 7 13 6 15 3 0 1 2 10 4 13 8 9 11 15 5 7 12 6 14 3

### # Level Mapping Operator Factors for m=prime power

Listed below are the level mapping operator factors for values of m which are prime powers. Level mapping operator factors are given for m=4, 8, 9, and 16. These operators give the mapping

fuv = f00 * Muv = f00 * Su * Dv

in which f00 is the lowest first column vector, and the level mapping operators Su and Dv are factored by components of the u and v vectors.

Su = Su0 * Su1 * ...
Dv = Dv0 * Dv1 * ...

The level mapping operator factors are constructed such that any combination of the listed u and v components yields an allowed first column vector.

Consider, for example, m=9, with u0=1, u1=1, and v0=1. The element in position 3 of this first column vector is

 fuv(3) = (f00 * Su0=1 * Su1=1 * Dv0=1)(3) = Dv0=1(Su1=1(Su0=1(f00(3)))) = Dv0=1(Su1=1(Su0=1(4))) = Dv0=1(Su1=1(8)) = Dv0=1(8) = 7

This level agrees with the one listed for the third position of this first column vector.

The level mapping operator factor tables for m=prime power are as follows.

m: m: u0: v0: u0: u1: v0: v1: v2: Su0: Dv0: Su0: Su1: Dv0: 4 8 0 1 0 0 1 0 1 2 0 1 0 1 0 1 0 1 2 3 0 1 3 2 0 1 2 3 0 1 2 3 4 5 6 7 0 1 3 4 5 6 7 2 0 1 2 3 4 5 6 7 0 1 4 5 6 7 2 3 0 1 6 7 2 3 4 5 0 1 2 3 4 5 6 7 0 1 2 5 4 6 7 3 0 1 2 3 4 5 6 7 0 1 2 3 6 7 4 5 0 1 2 3 4 5 6 7 0 1 2 3 7 6 5 4

m: u0: u1: v0: Su0: Su1: Dv0: 9 0 1 0 1 0 1 2 0 1 2 3 4 5 6 7 8 0 1 2 7 8 6 5 3 4 0 1 2 3 4 5 6 7 8 0 1 2 6 4 7 3 5 8 0 1 2 3 4 5 6 7 8 0 1 2 4 5 3 8 6 7 0 1 2 5 3 4 7 8 6

 m: u0: u1: u2: v0: Su0: Su1: Su2: Dv0: 16 0 1 0 1 0 1 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 4 5 3 2 7 6 12 13 8 9 15 14 11 10 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 3 2 5 4 6 7 15 14 12 13 10 11 9 8 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 11 13 9 14 6 7 12 5 8 3 15 2 4 10 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 10 11 8 9 14 15 12 13 0 1 2 9 4 14 11 10 8 12 5 7 15 6 13 3 0 1 3 9 4 15 10 11 8 12 5 6 14 7 13 2 0 1 2 11 4 12 9 8 10 14 5 7 13 6 15 3 0 1 3 11 4 13 8 9 10 14 5 6 12 7 15 2 0 1 4 5 6 7 2 3 8 9 12 13 14 15 10 11

m: v1: v2: v3: v4: v5: Dv1: Dv2: Dv3: Dv4: Dv5: 16 (continued) 0 1 0 1 0 1 0 1 0 1 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 9 8 11 10 13 12 15 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 12 13 14 15 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 5 4 7 6 8 9 10 11 13 12 15 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 6 7 4 5 8 9 10 11 14 15 12 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 8 9 10 11 4 5 6 7 12 13 14 15 0 1 2 3 12 13 14 15 4 5 6 7 8 9 10 11

### #Selected Position Mapping Operators for m=prime power

Listed below are selected position mapping operators ^Su and ^Dv associated with the first column vectors fuv for values of m which are prime powers. Position mapping operators are given for m=4, 8, 9, and 16. These operators give the mapping

fuv = ^Muv * f00 = ^Su * ^Dv * f00

in which f00 is the lowest first column vector. The number of position mapping operators listed for each value of m is as follows.

m Number of ^Su PositionMapping Operators Listed Number of ^Dv PositionMapping Operators Listed 4 2 of 2 1 of 1 8 6 of 6 8 of 8 9 4 of 4 3 of 3 16 8 of 8 10 of 336

Each column in a table below lists the u vector and corresponding ^Su operator, or the v vector and corresponding ^Dv operator. The values of q for which ^Su=dq also are listed in the ^Su columns. There are multiple position mapping operators ^Su for m=prime power. They are listed in the same order as the level mapping operators Su in a previous section. This order is that of ascending q.

Note that for values of m which are prime powers, there can be more than one ^Dv position mapping operator. This means that there can be more than one multiplication table for each value of m. Each position mapping operator product

^Muv = ^Su * ^Dv

maps f00 to a first column vector fuv which yields the multiplication table of

f0v = 0+ * ^Dv * f00 = ^Dv * f00

Also note that ^Muv(i) gives the allowed positions of f00 which map to fuv(i) according to the fuv=f00(^Muv)=f00(^Dv(^Su)) position mapping. Consider, for example, when m=9 and i=3. The i=3 position of the ^Su operators gives the allowed levels 3 and 7, which map to positions 3 and 7 of the ^Dv operators. The allowed levels of ^Dv are 3, 8, 2 and 7, 4, 6 for positions 3 and 7 respectively. Thus, the allowed positions of f00 which map to fuv(3) are 2, 3, 4, 6, 7, and 8. In particular, for

 u = 11 and v = 1, fuv(3) = f00(^Dv(^Su(3))) = f00(^Dv(7)) = f00(4) = 7

The position mapping operator tables for m=prime power are as follows.

 m: m: u: v: u: v: q: q: ^Su: ^Dv: ^Su: ^Dv: 4 8 0 1 0 00 01 10 02 12 11 000 001 010 011 100 101 110 111 1 2 1 2 3 4 5 6 0 1 2 3 0 1 3 2 0 1 2 3 0 1 2 3 4 5 6 7 0 1 3 5 7 2 4 6 0 1 4 7 3 6 2 5 0 1 5 2 6 3 7 4 0 1 6 4 2 7 5 3 0 1 7 6 5 4 3 2 0 1 2 3 4 5 6 7 0 1 2 6 4 7 3 5 0 1 2 5 4 3 7 6 0 1 2 7 4 6 5 3 0 1 2 3 7 6 4 5 0 1 2 6 5 3 4 7 0 1 2 5 6 7 4 3 0 1 2 7 3 5 4 6

 m: u: v: q: ^Su: ^Dv: 9 00 10 01 11 0 1 2 1 3 5 7 0 1 2 3 4 5 6 7 8 0 1 4 7 2 5 8 3 6 0 1 6 3 8 5 2 7 4 0 1 8 7 6 5 4 3 2 0 1 2 3 4 5 6 7 8 0 1 3 8 6 5 7 4 2 0 1 8 2 7 5 4 6 3

 m: u: v: q: ^Su: ^Dv: 16 000 100 010 001 110 111 011 101 000000 001000 010000 100000 110000 200000 201000 210000 400000 410000 1 2 4 7 8 11 13 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 3 5 7 9 11 13 15 2 4 6 8 10 12 14 0 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 0 1 8 15 7 14 6 13 5 12 4 11 3 10 2 9 0 1 9 2 10 3 11 4 12 5 13 6 14 7 15 8 0 1 12 8 4 15 11 7 3 14 10 6 2 13 9 5 0 1 14 12 10 8 6 4 2 15 13 11 9 7 5 3 0 1 15 14 13 12 11 10 9 8 7 6 5 4 3 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 7 5 6 4 13 9 12 11 10 8 15 14 0 1 2 3 15 5 6 14 10 9 8 11 13 12 7 4 0 1 2 3 10 5 6 12 15 9 4 11 7 14 13 8 0 1 2 3 8 5 6 13 4 9 15 11 14 7 12 10 0 1 2 3 4 15 8 13 11 12 9 10 14 5 6 7 0 1 2 3 7 14 13 8 11 10 9 12 15 5 6 4 0 1 2 3 15 4 10 12 11 13 9 8 7 5 6 14 0 1 2 3 10 8 15 14 11 7 9 4 13 5 6 12 0 1 2 3 8 10 4 7 11 14 9 15 12 5 6 13

### # Position Mapping Operator Factors for m=prime power

Listed below are the position mapping operator factors for values of m which are prime powers. Position mapping operator factors are given for m=4, 8, 9, and 16. These operators give the mapping

fuv = ^Muv * f00 = ^Su * ^Dv * f00

in which f00 is the lowest first column vector, and the position mapping operators ^Su and ^Dv are factored by components of the u and v vectors.

^Su = ^Su0 * ^Su1 * ...
^Dv = ^Dv0 * ^Dv1 * ...

The position mapping operator factors are constructed such that any combination of the listed u and v components yields an allowed first column vector.

Consider, for example, m=9, with u0=1, u1=1, and v0=1. The element in position 3 of this first column vector is

 fuv(3) = (^Su0=1 * ^Su1=1 * ^Dv0=1 * f00)(3) = f00(^Dv0=1(^Su1=1(^Su0=1(3)))) = f00(^Dv0=1(^Su1=1(7))) = f00(^Dv0=1(7)) = f00(4) = 7

This level agrees with the one listed for the third position of this first column vector.

The position mapping operator factor tables for m=prime power are as follows.

m: m: u0: v0: u0: u1: v0: v1: v2: q: q: q: ^Su0: ^Dv0: 4 8 0 1 0 0 1 0 1 2 0 1 0 1 0 1 1 2 1 3 1 2 4 0 1 2 3 0 1 3 2 0 1 2 3 0 1 2 3 4 5 6 7 0 1 4 7 3 6 2 5 0 1 2 3 4 5 6 7 0 1 3 5 7 2 4 6 0 1 5 2 6 3 7 4 0 1 2 3 4 5 6 7 0 1 2 3 7 6 4 5 0 1 2 3 4 5 6 7 0 1 2 5 4 3 7 6 0 1 2 3 4 5 6 7 0 1 2 6 4 7 3 5

m: u0: u1: v0: q: q: ^Su0: 9 0 1 0 1 0 1 2 1 3 1 5 0 1 2 3 4 5 6 7 8 0 1 4 7 2 5 8 3 6 0 1 2 3 4 5 6 7 8 0 1 6 3 8 5 2 7 4 0 1 2 3 4 5 6 7 8 0 1 3 8 6 5 7 4 2 0 1 8 2 7 5 4 6 3

 m: u0: u1: u2: v0: q: q: q: ^Su0: ^Su1: ^Su2: ^Dv0: 16 0 1 0 1 0 1 0 1 2 3 4 5 6 1 2 1 4 1 7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 3 5 7 9 11 13 15 2 4 6 8 10 12 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 8 15 7 14 6 13 5 12 4 11 3 10 2 9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 10 5 6 12 15 9 4 11 7 14 13 8 0 1 2 3 4 15 8 13 11 12 9 10 14 5 6 7 0 1 5 3 4 15 10 12 6 13 9 8 14 2 11 7 0 1 2 3 10 8 15 14 11 7 9 4 13 5 6 12 0 1 5 3 10 8 4 7 6 14 9 15 13 2 11 12 0 1 3 6 4 9 2 12 14 11 7 5 10 8 13 15

m: v1: v2: v3: v4: v5: ^Dv1: ^Dv2: ^Dv3: ^Dv4: ^Dv5: 16 (continued) 0 1 0 1 0 1 0 1 0 1 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 15 5 6 14 10 9 8 11 13 12 7 4 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 7 5 6 4 13 9 12 11 10 8 15 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 9 4 5 11 14 8 3 10 6 13 12 7 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 6 4 5 3 12 8 11 10 9 7 14 13 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 4 3 5 10 7 11 15 6 8 12 13 14 9 0 1 2 7 3 5 12 4 11 14 6 13 10 8 15 9

### #Irreducible Monic Polynomials

The first column vectors for values of m which are prime powers can be associated with the irreducible monic polynomials used to construct Galois fields. The association is made by comparing the addition and multiplication tables given here with the Galois field tables. (See Appendix A of Orthogonal Arrays Theory and Applications1 for an introduction to the theory of Galois fields.)

The Galois field tables are given in terms of the variable x of an irreducible monic polynomial f(x). The association with the first column vectors is made by substituting the levels greater than p-1 for the powers of the variable x and then comparing the tables with those of the first column vectors. In this comparison the value of the u vector does not matter, because all first column vectors fuv with a particular v vector have the same addition and multiplication tables.

For example, Tables A.9 and A.10 of Appendix A1 give the addition and multiplication tables for m=9 using the irreducible monic polynomial

f3(x) = x2 + x + 2 .

Substitution of a level for x (say, x=5), and requiring the addition table A.9 be the same as the m=9 addition table here determines the levels for all the elements. In this case

 0 = 0 1 = 1 2 = 2 x = 5 x+1 = 3 x+2 = 4 2x = 7 2x+1 = 8 2x+2 = 6

Substitution of these levels into the multiplication table A.10 yields the same table as that for the lowest first column vector f00. Similar associations can be made for other values of x with this polynomial. Associations can be made with the two other irreducible monic polynomials for m=9 as well. For example the lowest first column vector f00 gives the powers of x in Table A.111 for f3(x=5), f5(x=4) and f6(x=3).

Listed below are the combinations of levels for the powers of x which associate the irreducible monic polynomials f(x) with the v vectors for m=4, 8, and 9. For m=4 and 9 (squares of primes), (x) levels are listed. For m=8=23, (x, x2) level pairs are listed.

m: v: f(x): (x): m: v: f(x): (x, x2): 4 0 x2+x+1 (2)(3) 8 000 001 010 011 100 101 110 111 x3+x+1 (2, 4)(4, 6)(6, 2) (2, 7)(5, 2)(7, 5) (2, 6)(4, 2)(6, 4) (2, 5)(5, 7)(7, 2) (3, 5)(5, 6)(6, 3) (3, 6)(5, 3)(6, 5) (3, 7)(4, 3)(7, 4) (3, 4)(4, 7)(7, 3) x3+x2+1 (3, 5)(5, 7)(7, 3) (3, 6)(4, 3)(6, 4) (3, 7)(5, 3)(7, 5) (3, 4)(4, 6)(6, 3) (2, 4)(4, 7)(7, 2) (2, 7)(4, 2)(7, 4) (2, 6)(5, 2)(6, 5) (2, 5)(5, 6)(6, 2) 9 0 1 2 x2+2x+2 (3)(7) (4)(6) (5)(8) x2+1 (4)(8) (5)(7) (3)(6) x2+x+2 (5)(6) (3)(8) (4)(7)

1. Appendix A: Galois Fields, Orthogonal Arrays Theory and Applications by A. S. Hedayat, N. J. A. Sloane, and John Stufken, 1999 Springer-Verlag.

## #First Column Vectors and Mapping Operators for m=prime power product and c=2

Any value of m>1 has a set of trivial first column vectors for c=2. These vectors contain the levels 0 and 1 in the zeroth and first positions respectively, and any permutation of the remaining levels in the remaining positions. There are (m-2)! first column vectors for c=2. In these cases the lowest first column vector f00=0+ the identity operator, so Su=^Su, Dv=^Dv, Muv=^Muv, etc.

Searches for first column vectors with c=3 were executed for values of m=6, 10, 14, and 18. In all cases the searches completed without finding a first column vector for c=3. A similar search for m=22 and c=3 was abandoned prior to completion, without finding a first column vector. Thus, for these values of m, the maximum value of c given here is 2.

Listed below are the position mapping operator factors for m=6. In this case there are 4!=24 first column vectors leading to 6 different multiplication tables.

m: u0: u1: v0: v1: q: q: ^Su0: ^Su1: 6 0 1 0 1 0 1 0 1 2 1 4 1 3 0 1 2 3 4 5 0 1 5 4 3 2 0 1 2 3 4 5 0 1 4 2 5 3 0 1 2 3 4 5 0 1 3 2 5 4 0 1 2 3 4 5 0 1 2 4 5 3 0 1 2 5 3 4

## First Column Vectors and Mapping Operators for m=prime power product and c>2

### # Selected First Column Vectors for m=prime power product and c>2

Listed below are selected first column vectors fuv for values of m which are prime power products, and for values of c>2. First column vectors are given for m=12, 15, 20, and 21. In these cases first column vectors were found for c=4, but searches with c=5 completed without finding a first column vector. The first column vectors are listed starting with the lowest first column vector f00, in ascending order. The number of first column vectors listed for each value of m is as follows.

mNumber of First
Column Vectors Listed
1210 of 24
1510 of 64
2010 of 3744
2110 of 12372

Where listed, the u and v vectors label the first column vectors according to the mapping operators given in the following section. A column in a table below lists

• the u vector,
• the v vector, and
• the corresponding fuv vector.

The first column vector tables for m=prime power product and c>2 are as follows.

 m: m: u: u: v: v: fuv: fuv: 12 15 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 00 10 20 30 40 20 50 40 41 51 0 1 2 3 4 5 6 7 8 9 0 1 2 3 6 10 4 9 11 8 7 5 0 1 2 4 10 9 8 11 3 6 7 5 0 1 2 10 11 4 7 6 8 5 9 3 0 1 2 10 11 9 3 7 4 6 5 8 0 1 3 8 2 6 9 10 11 7 5 4 0 1 3 9 5 8 6 7 4 11 10 2 0 1 4 3 2 8 10 11 7 5 6 9 0 1 4 5 7 11 10 9 6 2 8 3 0 1 4 5 10 2 7 9 3 11 8 6 0 1 4 6 11 8 7 2 10 5 3 9 0 1 2 6 3 14 9 12 11 4 10 8 13 5 7 0 1 2 11 4 10 8 13 5 7 6 3 14 9 12 0 1 2 13 4 11 10 3 6 8 5 9 14 12 7 0 1 3 8 14 13 2 11 4 5 12 9 7 10 6 0 1 3 9 2 12 6 13 11 8 7 10 14 4 5 0 1 3 9 7 12 6 13 2 5 4 14 10 11 8 0 1 4 3 7 9 14 5 13 10 2 11 12 8 6 0 1 4 9 2 3 14 8 10 7 5 11 6 13 12 0 1 5 3 6 13 10 9 4 12 2 11 7 8 14 0 1 5 4 7 14 12 6 8 3 9 2 13 10 11

 m: m: fuv: fuv: 20 21 0 1 2 3 7 6 13 18 17 15 11 5 8 16 19 14 4 10 12 9 0 1 2 3 10 6 5 18 16 9 15 19 11 13 8 17 14 4 12 7 0 1 2 3 11 6 19 12 4 8 14 9 18 16 5 15 17 13 10 7 0 1 2 3 16 13 19 8 4 9 12 10 18 7 11 5 15 17 14 6 0 1 2 3 16 15 9 4 14 7 11 8 10 6 18 13 19 17 5 12 0 1 2 3 19 7 5 4 14 9 6 12 16 15 17 11 18 10 13 8 0 1 2 3 19 12 5 4 18 17 9 7 13 15 10 14 11 8 16 6 0 1 2 4 5 3 15 11 14 18 12 19 7 13 8 17 10 9 16 6 0 1 2 4 5 12 15 13 7 11 14 10 19 16 8 18 3 9 17 6 0 1 2 4 5 15 13 17 10 3 9 18 7 19 14 11 8 16 12 6 0 1 2 4 3 9 17 11 6 19 10 7 5 14 18 8 15 20 13 16 12 0 1 2 4 7 12 16 10 17 14 9 8 20 18 11 3 13 19 6 15 5 0 1 2 4 7 12 20 9 8 3 18 14 11 15 13 6 19 10 17 5 16 0 1 2 4 7 13 11 20 10 17 6 18 12 16 3 8 5 19 15 14 9 0 1 2 4 7 15 9 19 16 11 17 10 14 6 5 12 3 20 18 8 13 0 1 2 4 7 16 13 20 11 10 8 18 3 17 12 6 14 19 15 5 9 0 1 2 4 8 17 13 10 20 5 16 15 6 19 3 18 11 9 12 7 14 0 1 2 4 8 19 5 18 6 11 17 16 9 12 7 3 15 13 10 20 14 0 1 2 4 9 12 3 11 17 15 19 5 16 10 7 20 8 18 14 13 6 0 1 2 4 9 18 3 14 7 5 20 11 10 6 19 8 16 13 17 12 15

### # Selected Position Mapping Operator Factors for m=prime power product and c>2

Listed below are the position mapping operator factors for values of m which are prime power products, and for values of c>2. Position mapping operator factors are given for m=12 and 15. These operators give the mapping

fuv = ^Muv * f00 = ^Su * ^Dv * f00

in which f00 is the lowest first column vector, and the position mapping operators ^Su and ^Dv are factored by components of the u and v vectors.

^Su = ^Su0 * ^Su1 * ...
^Dv = ^Dv0 * ^Dv1 * ...

The position mapping operator factors are constructed such that any combination of the listed u and v components yields an allowed first column vector.

Note that for both m=12 and m=15,

^Su0=1 = dm-2

so there are two first column vectors for each distinct multiplication table. For m=12 there are 12 multiplication tables and 24 first column vectors; for m=15 there are 32 multiplication tables and 64 first column vectors. However, each of first column vectors leads to a different standard form orthogonal array, because pairs of arrays from the same multiplication table include different sets of columns. (The columns are given by guv the first row vector.) Thus there are 24 and 64 standard form orthogonal arrays for m=12 and m=15 respectively.

The position mapping operator factor tables for m=prime power product and c>2 are as follows.

 m: u0: v0: v1: q: ^Su0: ^Dv0: ^Dv1: 12 0 1 0 1 2 3 4 5 0 1 1 10 0 1 2 3 4 5 6 7 8 9 10 11 0 1 11 10 9 8 7 6 5 4 3 2 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 6 5 7 9 8 3 4 10 11 0 1 2 5 8 6 10 4 9 11 7 3 0 1 2 5 8 7 3 10 6 4 11 9 0 1 3 9 2 4 7 5 8 10 11 6 0 1 6 3 2 9 5 8 10 11 4 7 0 1 2 3 4 5 6 7 8 9 10 11 0 1 8 4 3 10 6 7 2 9 5 11

 m: u0: v0: q: ^Su0: ^Dv0: m: v0: ^Dv0: 15 0 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 14 13 12 11 10 9 8 7 6 5 4 3 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 2 8 9 10 11 12 13 14 3 4 5 6 7 0 1 2 12 9 8 10 4 3 11 13 6 5 7 14 0 1 4 11 5 12 2 8 9 13 7 6 14 10 3 0 1 4 6 2 7 3 12 8 11 14 10 5 9 13 0 1 4 6 14 7 3 12 2 13 9 5 10 8 11 0 1 9 4 14 6 5 13 12 10 2 8 7 11 3 0 1 9 6 2 4 5 11 10 14 13 8 3 12 7 0 1 13 4 3 12 10 6 9 7 2 8 14 11 5 0 1 13 9 14 5 7 3 11 4 6 2 12 10 8 0 1 13 9 7 3 11 4 6 14 5 2 12 10 8 0 1 13 9 5 10 14 11 3 7 2 6 4 8 12 0 1 13 11 4 9 3 12 14 7 8 6 2 5 10 0 1 13 11 14 9 2 6 4 12 3 7 5 10 8 0 1 13 11 14 6 4 12 3 7 9 2 5 10 8 0 1 13 5 10 14 7 8 6 2 11 4 9 3 12 15 (continued) 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 0 1 3 2 7 13 5 4 6 10 11 14 9 8 12 0 1 3 4 9 8 13 14 2 10 11 5 12 6 7 0 1 3 4 5 12 9 8 13 14 2 10 11 6 7 0 1 3 11 7 8 5 6 14 4 9 12 13 2 10 0 1 14 13 11 10 9 6 2 4 5 8 3 12 7 0 1 14 11 9 12 4 8 3 13 2 6 7 10 5 0 1 14 8 7 6 9 4 3 2 10 11 12 13 5 0 1 11 3 7 14 6 4 8 10 5 9 13 2 12 0 1 11 8 3 14 7 10 9 4 6 13 12 2 5 0 1 6 14 9 13 8 10 12 4 5 3 11 2 7 0 1 6 14 12 4 5 3 11 8 10 9 13 2 7 0 1 10 2 14 13 12 9 11 6 7 8 3 4 5 0 1 10 2 14 13 12 6 7 8 3 4 9 11 5 0 1 10 4 12 6 5 2 9 8 11 14 13 3 7 0 1 7 6 9 4 3 14 8 2 10 11 12 13 5 0 1 12 2 10 3 7 8 13 4 11 6 9 14 5

### #Alternate Plus Vector Definitions

This section illustrates that the selection of the plus vectors can affect the structure of the mapping operator factors when m is a prime power product and c>2.

Consider two alternate level representation arrays R'', for m=12 and m=15. Their values are listed below in comparison to their original definitions of R.

 R''(0+) = R( 0 6 3 9 4 10 7 1 8 2 11 5 ) = 0 2 3 1 0 2 3 1 0 2 3 1 0 0 0 0 1 1 1 1 2 2 2 2 for m=12, and R''(0+) = R( 0 10 5 6 1 11 12 7 2 3 13 8 9 4 14 ) = 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 for m=15.

The alternate level representation arrays R'' lead to alternate addition tables and alternate plus vectors and plus operators, as follows for m=12

 + 0+ 1+ 2+ 3+ 4+ 5+ 6+ 7+ 8+ 9+ 10+ 11+ 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 1 0 3 2 5 4 7 6 9 8 11 10 2 3 0 1 6 7 4 5 10 11 8 9 3 2 1 0 7 6 5 4 11 10 9 8 4 5 6 7 8 9 10 11 0 1 2 3 5 4 7 6 9 8 11 10 1 0 3 2 6 7 4 5 10 11 8 9 2 3 0 1 7 6 5 4 11 10 9 8 3 2 1 0 8 9 10 11 0 1 2 3 4 5 6 7 9 8 11 10 1 0 3 2 5 4 7 6 10 11 8 9 2 3 0 1 6 7 4 5 11 10 9 8 3 2 1 0 7 6 5 4

and for m=15

 + 0+ 1+ 2+ 3+ 4+ 5+ 6+ 7+ 8+ 9+ 10+ 11+ 12+ 13+ 14+ 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1 2 0 4 5 3 7 8 6 10 11 9 13 14 12 2 0 1 5 3 4 8 6 7 11 9 10 14 12 13 3 4 5 6 7 8 9 10 11 12 13 14 0 1 2 4 5 3 7 8 6 10 11 9 13 14 12 1 2 0 5 3 4 8 6 7 11 9 10 14 12 13 2 0 1 6 7 8 9 10 11 12 13 14 0 1 2 3 4 5 7 8 6 10 11 9 13 14 12 1 2 0 4 5 3 8 6 7 11 9 10 14 12 13 2 0 1 5 3 4 9 10 11 12 13 14 0 1 2 3 4 5 6 7 8 10 11 9 13 14 12 1 2 0 4 5 3 7 8 6 11 9 10 14 12 13 2 0 1 5 3 4 8 6 7 12 13 14 0 1 2 3 4 5 6 7 8 9 10 11 13 14 12 1 2 0 4 5 3 7 8 6 10 11 9 14 12 13 2 0 1 5 3 4 8 6 7 11 9 10

Searches with c=4 again yielded 24 first column vectors for m=12 and 64 first column vectors for m=15. The lowest first column vectors are

 f''00 = 0 1 2 5 11 7 10 4 6 3 8 9 for m=12, and f''00 = 0 1 3 4 9 11 14 10 8 5 13 2 6 12 7 for m=15

They lead to the following multiplication tables for m=12

 x 0x 1x 2x 3x 4x 5x 6x 7x 8x 9x 10x 11x 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4 5 6 7 8 9 10 11 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 0 2 5 8 6 11 3 10 9 1 4 7 0 3 8 10 11 9 7 2 4 6 5 1 0 4 6 11 2 3 5 9 7 10 1 8 0 5 11 9 3 7 8 4 1 2 6 10 0 6 3 7 5 8 11 1 10 4 2 9 0 7 10 2 9 4 1 3 5 11 8 6 0 8 9 4 7 1 10 5 6 3 11 2 0 9 1 6 10 2 4 11 3 8 7 5 0 10 4 5 1 6 2 8 11 7 9 3 0 11 7 1 8 10 9 6 2 5 3 4

and for m=15

 x 0x 1x 2x 3x 4x 5x 6x 7x 8x 9x 10x 11x 12x 13x 14x 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 2 10 6 12 11 8 13 9 7 4 1 5 14 3 0 3 6 4 9 13 12 1 5 11 8 14 7 2 10 0 4 12 9 11 2 7 3 13 14 5 10 1 6 8 0 5 11 13 2 4 14 8 3 6 1 12 10 9 7 0 6 8 12 7 14 5 2 11 1 9 3 13 10 4 0 7 13 1 3 8 2 12 10 4 14 9 6 5 11 0 8 9 5 13 3 11 10 1 2 7 6 14 4 12 0 9 7 11 14 6 1 4 2 10 13 8 3 12 5 0 10 4 8 5 1 9 14 7 13 12 2 11 3 6 0 11 1 14 10 12 3 9 6 8 2 5 4 7 13 0 12 5 7 1 10 13 6 14 3 11 4 2 8 9 0 13 14 2 6 9 10 5 4 12 3 7 8 11 1 0 14 3 10 8 7 4 11 12 5 6 13 9 1 2

Once again the position mapping operator factors are constructed such that any combination of the listed u and v components yields an allowed first column vector.

Note that for both m=12 and m=15,

^Su0=1 = dm-2

so there are two first column vectors for each distinct multiplication table again.1 For m=12 there are 12 multiplication tables and 24 first column vectors; for m=15 there are 32 multiplication tables and 64 first column vectors. Again, each of first column vectors leads to a different standard form orthogonal array, because pairs of arrays from the same multiplication table include different sets of columns. And again there are 24 and 64 standard form orthogonal arrays for m=12 and m=15 respectively.

Although the ^Su operators are the same for the alternate choices of plus vectors, the structures of the ^Dv operators are different. As illustrated below, the ^Dv operators have more v components (factors) with fewer values, compared to those from the original plus vector definitions.

The alternate position mapping operator factor tables for m=prime power product and c>2 are as follows.

m: u0: v0: v1: v2: q: ^Su0: ^Dv0: ^Dv1: 12 0 1 0 1 2 0 1 0 1 1 10 0 1 2 3 4 5 6 7 8 9 10 11 0 1 11 10 9 8 7 6 5 4 3 2 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 8 7 9 11 10 3 4 5 6 0 1 4 10 5 11 3 6 9 2 8 7 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 11 5 4 8 10 6 9 7 3 0 1 2 3 4 5 6 7 8 9 10 11 0 1 9 3 6 8 4 7 5 2 10 11

 m: u0: v0: v1: q: ^Su0: ^Dv0: ^Dv1: 15 0 1 0 1 2 3 4 5 6 7 0 1 2 3 1 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 14 13 12 11 10 9 8 7 6 5 4 3 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 2 12 9 11 4 5 13 10 14 6 3 7 8 0 1 3 11 5 4 10 2 7 14 12 9 13 8 6 0 1 3 2 5 12 9 6 13 14 4 10 7 11 8 0 1 3 6 4 2 9 12 13 5 10 7 11 14 8 0 1 3 6 5 10 4 2 9 12 13 7 11 14 8 0 1 9 3 11 5 14 13 4 7 2 12 10 8 6 0 1 9 3 11 5 14 10 8 13 4 7 2 12 6 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 0 1 12 14 2 9 5 3 6 8 7 11 13 4 10 0 1 4 7 13 6 8 10 9 5 14 11 2 12 3 0 1 13 10 12 8 9 14 5 6 3 11 4 2 7

1. Recall that dm-2 means d-1mod m-1 here. The m-2 is unrelated to the alternate addition tables.

# Covering Arrays for Strength l=2

## Permutation Vectors

### Definitions

When m is a prime or a prime power, consider the mw levels h=0, 1, ..., mw-1, in which w=1, 2, ... As before, these levels form a group of order mw with the addition operation defined by the mw addition table. Here w is the log-order of the group because it is the base m logarithm of the order of the group:

w = logm(mw)

Each of the levels h can be expressed uniquely in base m notation:

 h = sumt=0w-1(ht x mw-t-1) = h0 x mw-1 + h1 x mw-2 + ... + hw-1

in which ht can take any of the values 0, 1, ..., m-1, and the + and x operations are given by the mw addition and multiplication tables.

This level (from the set of mw levels) also may be expressed as the vector h whose components are ht for t=0, 1, ..., w-1.

h = h0 h1 ... hw-1

The log-order w permutation vector of h is defined to be the vector product

wPh = productt=0w-1(ht .w-t-1 x .t +)

in which the dot operator exponent (w-t-1 or t) indicates the number of times the dot operator is applied. There are w-1 dot operators, one cross operator, and one plus operator applied to each ht level. Thus,

1Ph= h0 x+
2Ph= h0 .x+ * h1 x.+
3Ph= h0 ..x+ * h1 .x.+ * h2 x..+

and so forth.

The log-order 2 permutation vectors for m=3 are listed below, for example. Each column lists an h level in base m notation above the corresponding permutation vector. Here the permutation vectors are expressed as vectors of plus vectors.

h:000102101112202122
2Ph: 0+0+0+0+0+0+ 0+0+0+
0+0+0+1+1+1+ 2+2+2+
0+0+0+2+2+2+ 1+1+1+
0+1+2+0+1+2+ 0+1+2+
0+1+2+1+2+0+ 2+0+1+
0+1+2+2+0+1+ 1+2+0+
0+2+1+0+2+1+ 0+2+1+
0+2+1+1+0+2+ 2+1+0+
0+2+1+2+1+0+ 1+0+2+

### Isomorphic Groups

For each w, the mw permutation vectors form a group with the vector product operator. Each of these groups is isomorphic to the mw addition group. In the m=3, w=2 example, the vector product table is as follows.

Comparison with the m2=9 addition table yields the same structure.

For arbitrary values of m, the isomorphism can be shown for w=2 as follows.

2Ph * 2Ph' = (h0 .x+ * h1 x.+) * (h'0 .x+ * h'1 x.+) by definition by expansion of the dotand cross vectors intotheir components : : : : : : : : : : : : : : : : (h0 x0 + h'0 x0)+ * (h1 x0 + h'1 x0)+ by commuting themiddle two factors(vector products ofplus vectors are abelian) and by the plus vectors'isomorphism withaddition (h0 x1 + h'0 x1)+ * (h1 x0 + h'1 x0)+ : : : : (h0 xm-1 + h'0 xm-1)+ * (h1 x0 + h'1 x0)+ (h0 x0 + h'0 x0)+ * (h1 x1 + h'1 x1)+ (h0 x1 + h'0 x1)+ * (h1 x1 + h'1 x1)+ : : : : (h0 xm-1 + h'0 xm-1)+ * (h1 x1 + h'1 x1)+ : : : : (h0 x0 + h'0 x0)+ * (h1 xm-1 + h'1 xm-1)+ (h0 x1 + h'0 x1)+ * (h1 xm-1 + h'1 xm-1)+ : : : : (h0 xm-1 + h'0 xm-1)+ * (h1 xm-1 + h'1 xm-1)+ (h0 + h'0)x+ * (h1 x0 + h'1 x0).+ by addition of the crossvectors and collection oftheir components on the left, and by collection of thedot vector componentson the right (h0 + h'0)x+ * (h1 x1 + h'1 x1).+ : : (h0 + h'0)x+ * (h1 xm-1 + h'1 xm-1).+ (h0 + h'0).x+ * (h1 + h'1)x.+ by collection of the dotvector components on theleft, and by addition ofthe cross vectors andcollection of theircomponents on the right

### Reduced Permutation Vectors

Each of the permutation vectors is a vector of plus vectors, so a set of mw reduced permutation vectors wPh– can be defined. Here the minus operator is the inverse of the plus operator: It replaces each plus vector h+ with the corresponding level h=0, ..., m-1. In the m=3, w=2 example, the reduced permutation vectors are as follows. Each column lists an h level in base m notation above the corresponding reduced permutation vector.

h:000102101112202122
2Ph–: 000000 000
000111 222
000222 111
012012 012
012120 201
012201 120
021021 021
021102 210
021210 102

Selected permutation vectors are tabulated in an appendix as plus vectors. So the corresponding reduced permutation vectors are apparent from the same tables, by ignoring the plus operators.

A later section will use vector products of reduced permutation vectors. The products can be tabulated according to the vector product definition, and observation of the product tables suggests the identity

wPh– = wPh'– * wPh''–

in which

 h0 = h'0 x h''0 and ht = h't x h''0 + h''t if t>0

The vector product table for the m=3, w=2 reduced permutation vectors is as follows.

Note that the identity element for the vector product is

0.w-1+ = 1.w-1x = wPmw-1 = wP10–

(The dot operator exponent w-1 indicates the number of times the dot operator is applied. The 0 in the last expression wP10– is the w-1 order 0 vector, so the identity element is given in base m notation.) Elements with levels h greater than or equal to mw-1 form a group with the vector product.

Also note the following recursion relations for level h and its associated base m, w order vector h. (The expressions on the right are in base m notation. The last expression contains the w order 0 vector.)

wPh–.=w+1Ph–=w+1P0h–
wPh=w+1P(mw + h)–=w+1P1h–
h0.wx=w+1P(h0 x mw)–=w+1Ph00–

### Orthogonal Arrays with Index>1

Examination of the mw permutation vectors leads to the observation that they form an mw+1-by-mw orthogonal array1 of strength l=2 and index mw-1. The orthogonal array is given by

wP = wP0 wP1 ... wPmw-1

in which ascending permutation vectors form the array columns. In the m=3, w=2 example, expansion of the permutation vectors yields the following orthogonal array.

h:000102101112202122
2Ph: 0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
1
2
0
1
2
0
1
2
0
2
0
1
2
0
1
2
0
1
0
1
2
0
1
2
0
1
2
2
0
1
2
0
1
2
0
1
1
2
0
1
2
0
1
2
0
0
1
2
1
2
0
2
0
1
0
1
2
1
2
0
2
0
1
0
1
2
1
2
0
2
0
1
0
1
2
1
2
0
2
0
1
1
2
0
2
0
1
0
1
2
2
0
1
0
1
2
1
2
0
0
1
2
1
2
0
2
0
1
2
0
1
0
1
2
1
2
0
1
2
0
2
0
1
0
1
2
0
1
2
2
0
1
1
2
0
0
1
2
2
0
1
1
2
0
0
1
2
2
0
1
1
2
0
0
1
2
2
0
1
1
2
0
1
2
0
0
1
2
2
0
1
2
0
1
1
2
0
0
1
2
0
1
2
2
0
1
1
2
0
2
0
1
1
2
0
0
1
2
1
2
0
0
1
2
2
0
1

In this example, each pair of columns contains each pair of levels exactly 3 times.

1. An orthogonal array with number of rows r=mw+1 and index mw-1 has strength l=2 if every r-by-l subarray contains each l-tuple of levels (each pair) exactly mw-1 times as a row.

## Covering Arrays for m=prime or m=prime power and n=mw

The mw+1-by-mw orthogonal arrays resulting from the permutation vectors can be used to find r-by-mw covering arrays1, in which r<mw+1. The formula given here for strength l=2 covering arrays is the result of using the cats program from the Constrained Array Test System2 to remove redundant rows from the orthogonal arrays of permutation vectors. I.e. a logical derivation of the formula from the permutation vectors is not given here. The formula is instead a description of search results which fit the formula's pattern. The covering properties of the resulting arrays are illustrated below however.

The covering array wG is a w order vector of subarrays. The components wGs (s=1, ..., w) are

• an m2-by-mw subarray for s=1, and
• w-1 m(m-1)-by-mw subarrays for s>1.

Thus, wG is an m2+m(m-1)(w-1)-by-mw covering array:

 m2-by-mw subarray m(m-1)-by-mw subarray : m(m-1)-by-mw subarray

The component subarrays are

wGs=0(')+·s-1 x ·w-s+

in which

0(')+ if s=1, and if s>1.

The apostrophe after the 0 indicates the initial 0 level is omitted from the plus vector (because it leads to redundant rows). Thus,

0'+ 1 : m-1

Again, the dot operator exponent (s-1 or w-s) indicates the number of times the dot operator is applied. There are w-1 raised dot operators and one raised cross operator applied to each plus vector level. Finally the plus operator is applied to each of the resulting array elements.

In the m=3, w=2 example the formula is evaluated as follows.

2G=2G1
2G2
=0+x·+
0'+·x+
=0x·+
1x·+
2x·+
x+
x+
=+++
+++
+++
1x+1x+1x+
2x+2x+2x+
=0+0+0+ 0+0+0+ 0+0+0+
0+0+0+ 1+1+1+ 2+2+2+
0+0+0+ 2+2+2+ 1+1+1+
0+1+2+ 0+1+2+ 0+1+2+
0+2+1+ 0+2+1+ 0+2+1+
= 0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
1
2
0
2
0
1
0
1
2
0
1
2
0
1
2
2
0
1
1
2
0
0
1
2
1
2
0
2
0
1
0
1
2
0
1
2
0
1
2
1
2
0
2
0
1
1
2
0
2
0
1
0
1
2
1
2
0
2
0
1
2
0
1
1
2
0
0
1
2
2
0
1
1
2
0
0
1
2
0
1
2
0
1
2
2
0
1
1
2
0
1
2
0
2
0
1
0
1
2
2
0
1
1
2
0
2
0
1
1
2
0

The covering of the wG array is illustrated as follows. Consider the mw-1 subarrays formed from each set of m contiguous columns of wG. Each of these m-column subarrays covers the m2 level pairs because its first m rows from the wG1 subarray together with the last m(m-1) rows from the wGw subarray form an m2-by-m orthogonal array with index one.

Now consider the mw-2 m2-column subarrays formed from each set of m contiguous m-column subarrays. Each of the m2-column subarrays covers the m2 level pairs because

• any two columns from the same m-column subarray cover (as above), and
• any two columns from different m-column subarrays cover with the first m rows from the wG1 subarray together with the last m(m-1) rows from the wGw-1 subarray. (Any selection of one column from each of the m m-column subarrays contains the rows of the m2-by-m orthogonal array with index one.)

This process is repeated with fewer but wider subarrays until all mw columns are included. That is, for each of the mw-s ms-column subarrays (s=1, ..., w), pairs of columns from the m different ms-1-column subarrays cover the m2 level pairs using the first m rows from the wG1 subarray together with the last m(m-1) rows from the wGw-s+1 subarray.

1. An r-by-n covering array has strength l (greater than or equal to 0, and less than or equal to n) if every r-by-l subarray contains each l-tuple of levels at least once as a row.
2. Effective Testing of Factor Combinations, George Sherwood, Third International Conference on Software Testing, Analysis & Review, May 8-12, 1994, Washington, DC.

## Covering Arrays for m=prime or m=prime power and n=(mw+1-1)/(m-1)

It is possible to increase the number of wG covering array columns from mw to

n = sumt=0w(mt) = (mw+1-1)/(m-1)

without increasing the number of rows from

r = m2+m(m-1)(w-1) = wm2-(w-1)m

by including the solution at infinity (t=0) with solutions for tG, t=1, ..., w.1

The covering array wH is a w-by-w+1 array of subarrays wHs,t in which the row position is s=1, ..., w, and the column position is t=0, ..., w. The subarrays are given by

wHs,t = if sw-t.

Here

0('). if s=1. if s>1. if s=1. if s>1.

The apostrophe after the 0 indicates the initial 0 level is omitted from the dot vector and from the plus vector (because it leads to redundant rows). Thus,

0'. = and 1 : m-1

Again, the dot operator exponent (t, s+t-w-1, or w-s) indicates the number of times the dot operator is applied.

In the m=3, w=2 example the formula is evaluated as follows.

2H=2H1,02H1,1 2H1,2
2H2,02H2,1 2H2,2
=0.. 0+·. 0+x·+
0'+. 0'+x+ 0'+·x+
=0. 0·. 0x·+
0. 1·. 1x·+
0. 2·. 2x·+
1. 1x+ x+
2. 2x+ x+
=0. 0.0.0. 0+0+0+ 0+0+0+ 0+0+0+
0. 1.1.1. 0+0+0+ 1+1+1+ 2+2+2+
0. 2.2.2. 0+0+0+ 2+2+2+ 1+1+1+
1. 0+1+2+ 0+1+2+ 0+1+2+ 0+1+2+
2. 0+2+1+ 0+2+1+ 0+2+1+ 0+2+1+
= 0
0
0
0
0
0
0
0
0
1
1
1
2
2
2
0
0
0
1
1
1
2
2
2
0
1
2
0
1
2
0
0
0
1
1
1
2
2
2
1
2
0
2
0
1
0
0
0
1
1
1
2
2
2
2
0
1
1
2
0
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
0
1
2
1
2
0
2
0
1
0
1
2
0
1
2
0
1
2
2
0
1
1
2
0
0
1
2
1
2
0
2
0
1
0
1
2
0
1
2
0
1
2
1
2
0
2
0
1
1
2
0
2
0
1
0
1
2
1
2
0
2
0
1
2
0
1
1
2
0
0
1
2
2
0
1
1
2
0
0
1
2
0
1
2
0
1
2
2
0
1
1
2
0
1
2
0
2
0
1
0
1
2
2
0
1
1
2
0
2
0
1
1
2
0

For larger values of w, the wHs,t subarrays are arranged as follows.

 t: s: 0.. 0.·. ... 0 1 ... w-2 w-1 w 1 2 3 : w-1 w

Subarrays with s=w-t are shown on the shaded diagonal. Subarrays with s<w-t are above and to the left of the shaded diagonal; subarrays with s>w-t are below and to the right.

The covering of the wH array is illustrated as follows.

1. Pairs of columns from the same wHt subarray cover. Consider the w subarrays formed by the vector of subarrays
wH1,t
wHt =wH2,t
:
wHw,t

for t=1, ..., w. (t=0 is not considered because it has only one column.) Each of these mt-column subarrays covers the m2 level pairs because it contains all the rows of the tG covering array.

• t<w: To see this, first compare wHs,t with tGs+t-w when 0<t<w (t=1, ..., w-1) and s>w-t (s=w-t+1, ..., w). Since s>w-t,
wHs,t = 0(')+·s+t-w-1 x ·w-s+

and since only integer values of t<w are under consideration, the minimum value of w-t=1. Thus s>w-t implies s>1, and

wHs,t = 0'+·s+t-w-1 x ·w-s+

Now

tGs+t-w=0(')+·s+t-w-1 x ·w-s+
=0+·s+t-w-1 x ·w-s+ if s+t-w=1
or s=w-t+1
0'+·s+t-w-1 x ·w-s+ if s+t-w>1
or s>w-t+1

For values of s>w-t+1 (greater than the lowest value)

wHs,t = tGs+t-w

and wHs,t contains all the rows of the subarray tGs+t-w from the tG covering array. But for the lowest value of s=w-t+1, wHs,t contains all the rows of tGs+t-w except for those resulting from the initial 0 level of the plus vector in the

0+·s+t-w-1 x ·w-s+

expression. The missing rows are given by the

s+t-w-1 x ·w-s+ = 0x ·t-1+ = 0·t+

expressions. There are m missing rows consisting of mt columns. All the elements of each row are one of the m levels 0, 1, ..., m-1. Examination of the expressions in the wHs,t definition indicates:

• A row of zero elements is contained in the zeroth row of the wHs=1,t subarray.
• Each row of nonzero elements is contained in the wHs=w-t,t subarray (m times).

Thus for t<w, wHt contains all the rows of the tG covering array.

• t=w: Next, for the case of t=w, s>w-t, so
wHs,t=0(')+·s+t-w-1 x ·w-s+
=0(')+·s-1 x ·w-s+
=wGs

Since each of the w subarrays wHt (t=1, ..., w) contains the rows of the covering array tG, each wHt subarray is a covering array itself.

2. Pairs of columns from different wHt subarrays cover. The next step is to consider pairs of columns from different wHt subarrays, now with t=0, 1, ..., w. In this illustration the pairs are selected by choosing any column from a subarray wHt for t=0, 1, ..., w-1 and by pairing it with any column from each of the subarrays to its right, i.e. with wHt' for t'=t+1, ..., w.
• Nonzero levels of wHt: The subarray
wHs=w-t,t = 0(')+·t.

contains an m-by-mt subarray of each of the nonzero levels. Each column of a particular level is paired with a plus vector in the subarrays to the right:

wHs>w-t',t' = 0(')+·s+t'-w-1 x ·w-s+

(t'>t). Since the plus vectors contain all m levels, each nonzero level from any wHs=w-t,t column is paired with each of the levels in any column of the wHs>w-t',t' subarray.

• Zero levels of wHt:
• Zero levels of wHt': The zeroth row of wHt is zero, and the zeroth row of wHt' is zero, so the zero-zero level pair is covered by any pair of columns from the wHt and wHt' subarrays.
• Nonzero levels of wHt':
• t=w-1: When t=w-1, the subarray
wH1,t = 0+·t.

contains an m-by-mt subarray of the zero level. Each column of the subarray is paired with a plus vector in the subarray to the right (t'=w). Since the plus vectors contain all m levels, a zero level from any column of wH1,t=w-1 is paired with each of the nonzero levels in any column of the wH1,t'=w subarray.

• t<w-1: When t<w-1, there is a zero subarray
wHs=w-t-1,t = 0(')t.

whose last m(m-1) rows pair zero levels with each of the nonzero levels in any wHs=w-t-1,t' subarray as follows.

• t'=t+1: The subarray
wHs=w-t',t'=t+1 = 0(')+·t'.

contains rows of all the nonzero levels in its last m(m-1) rows. Thus any pair of columns from wHs=w-t-1,t and wHs=w-t',t'=t+1 will cover the zero-nonzero level pairs.

• t'>t+1: Because
s = w-t-1 > w-t'

the subarray

wHs=w-t-1,t' = 0(')+·s+t'-w-1 x ·w-s+

which consists of plus vectors. Thus, the zero levels from any column of wHs=w-t-1,t are paired with each of the m levels of any column of the wHs=w-t-1,t'>t+1 subarray.

Since all nonzero levels and zero levels from the wHt columns are paired with all levels from wHt' columns, all m2 level pairs are covered by columns from different wHt subarrays.

Because all pairs of columns within and between the wHt subarrays cover the m2 level pairs, wH is a covering array.

1. Katona and Kleitman and Spencer solved the problem of the minimal (most efficient) strength two covering arrays for m=2. The numbers of rows in their arrays generally are less than or equal to those for m=2 given here. See
Two applications (for search theory and truth functions) of Sperner type theorems, G. O. H. Katona, Periodica Math. Hung. 3 1973, 19-26, and
Families of k-independent sets, D. J. Kleitman and J.Spencer, Discr. Math. 6 1973, 255-262.

## Covering Arrays for m=prime power product

The earlier formulation for orthogonal arrays of strength l=2 and index one can be extended to w=1 covering arrays as follows.

1G = guv x+ = sort(fuvT {c/})x+

is an m2-by-c covering array. As before,

1H1,0 = 0+.

and

1H1,1 = 1G

so

1H = 1H1,0 1H1,1 = 0+. guv x+

is an m2-by-c+1 covering array. These formulas are general in that they apply to values of m which are prime power products.

For n>c+1, covering arrays for values of m which are not primes or prime powers can be constructed from covering arrays with more levels (m'>m) using a sliding levels technique described here.

Consider an m'>m order vector A. The m'-to-m sliding level operator is defined to be the level mapping operator which leaves levels less than m unchanged and which maps greater levels to m-1. The operator applied to A is

Am/m' = A * ( 0 1 : m-1 : m-1

The operator applied to an array of vectors Aik yields an array of vector products:

Aik m/m' = Aik * ( 0 1 : m-1 : m-1

When applied to a covering array (e.g. wG or wH), the sliding level operator also implies the omission of rows m to m'-1 from the top row of vectors, because these rows are the same as row m-1, and are therefore redundant. (Note the top row of vectors consists of 0. and 0+ vectors in the formulas given here.) The omission of rows m to m'-1 is explicitly noted with an apostrophe, using

0.' m/m' and 0+' m/m'

in the top row of vectors, as appropriate.

For a given value of m and an associated maximum number of columns n, consider a larger value m'>m for which there is a covering array with a number of columns n'>n. If wH is the covering array for m', wHm/m' is a covering array for m. Compared to wH, wHm/m' has m'-m fewer rows and the same number of columns.

Consider for example m=6. There is a 36-by-3 covering array 1H as follows.

1H = 0+. g00 x+ = 0+. 0+{2/}x+ = 0. 0+ 0+. 0+x{2/}+ = 0 0 0 0 0 0 0 1 2 3 4 5 0 1 2 3 4 5 1 1 1 1 1 1 0 1 2 3 4 5 1 2 3 4 5 0 2 2 2 2 2 2 0 1 2 3 4 5 2 3 4 5 0 1 3 3 3 3 3 3 0 1 2 3 4 5 3 4 5 0 1 2 4 4 4 4 4 4 0 1 2 3 4 5 4 5 0 1 2 3 5 5 5 5 5 5 0 1 2 3 4 5 5 0 1 2 3 4

Additional factors can be covered with a 48-by-8 covering array 1H6/7 as follows.

1H6/7 =0+. 6/70+x+ 6/7
=0.' 6/70+' 6/70+' 6/7 0+' 6/70+' 6/70+' 6/7 0+' 6/70+' 6/7 = 0
0
0
0
0
0
0
1
2
3
4
5
0
1
2
3
4
5
0
1
2
3
4
5
0
1
2
3
4
5
0
1
2
3
4
5
0
1
2
3
4
5
0
1
2
3
4
5
1. 6/70+ 6/71+ 6/7 2+ 6/73+ 6/74+ 6/7 5+ 6/76+ 6/7 1
1
1
1
1
1
1
0
1
2
3
4
5
5
1
2
3
4
5
5
0
2
3
4
5
5
0
1
3
4
5
5
0
1
2
4
5
5
0
1
2
3
5
5
0
1
2
3
4
5
0
1
2
3
4
5
2. 6/70+ 6/72+ 6/7 4+ 6/76+ 6/71+ 6/7 3+ 6/75+ 6/7 2
2
2
2
2
2
2
0
1
2
3
4
5
5
2
3
4
5
5
0
1
4
5
5
0
1
2
3
5
0
1
2
3
4
5
1
2
3
4
5
5
0
3
4
5
5
0
1
2
5
5
0
1
2
3
4
3. 6/70+ 6/73+ 6/7 6+ 6/72+ 6/75+ 6/7 1+ 6/74+ 6/7 3
3
3
3
3
3
3
0
1
2
3
4
5
5
3
4
5
5
0
1
2
5
0
1
2
3
4
5
2
3
4
5
5
0
1
5
5
0
1
2
3
4
1
2
3
4
5
5
0
4
5
5
0
1
2
3
4. 6/70+ 6/74+ 6/7 1+ 6/75+ 6/72+ 6/7 6+ 6/73+ 6/7 4
4
4
4
4
4
4
0
1
2
3
4
5
5
4
5
5
0
1
2
3
1
2
3
4
5
5
0
5
5
0
1
2
3
4
2
3
4
5
5
0
1
5
0
1
2
3
4
5
3
4
5
5
0
1
2
5. 6/70+ 6/75+ 6/7 3+ 6/71+ 6/76+ 6/7 4+ 6/72+ 6/7 5
5
5
5
5
5
5
0
1
2
3
4
5
5
5
5
0
1
2
3
4
3
4
5
5
0
1
2
1
2
3
4
5
5
0
5
0
1
2
3
4
5
4
5
5
0
1
2
3
2
3
4
5
5
0
1
6. 6/70+ 6/76+ 6/7 5+ 6/74+ 6/73+ 6/7 2+ 6/71+ 6/7 5
5
5
5
5
5
5
0
1
2
3
4
5
5
5
0
1
2
3
4
5
5
5
0
1
2
3
4
4
5
5
0
1
2
3
3
4
5
5
0
1
2
2
3
4
5
5
0
1
1
2
3
4
5
5
0

To cover more factors the process can be continued similarly. For m=6 a few of the arrays are as follows.

1H 36-by-3 48-by-8 62-by-9 78-by-10 90-by-57 118-by-73

Note that this sliding levels technique is general in that it depends on m being less than m', but there is no requirement for either m or m' to be a prime or a prime power. For example, there is a 24-by-6 covering array 1H4/5 for m=4; there is a 224-by-5 covering array 1H14/15 for m=14, etc.

# Covering Arrays for Strength l>2

## Zero Sum Arrays

A zero sum array is an ml-by-l+1 orthogonal array of index one and strength l, in which l and m can be any positive integers. The array can be constructed from an ml-by-l subarray of the ml rows of distinct l-tuples of levels, with an additional column whose elements are chosen so each row sums to zero.

Zero sum arrays can be constructed from the permutation vectors as follows. First generalize the permutation vector definition to include any positive integer m, and let

0P0 = 0+

so that w=0, 1, ... Next define the mw+1-by-w+2 array wE in terms of its elements wEjk for j=0, ..., mw+1-1 and k=0, ..., w+1:

 wEjk = wP0 j if k=0. wPmk j if 0

wE is a zero sum array for strength l=w+1.

In the m=3, w=2 example, with base 3 notation,

2E=2P002P012P10 0.
2.
1.
2.
1.
0.
1.
0.
2.
0+0+0+0.
0+0+1+2.
0+0+2+1.
0+1+0+2.
=0+1+1+1.
0+1+2+0.
0+2+0+1.
0+2+1+0.
0+2+2+2.

Generally wE can be expressed in terms of its column vectors wEk as described below. First, for each of the m levels h=0, 1, ..., m-1, define the zero sum vector h[w] by the vector sum

h[w] = h. - sumk=0w(0+)addition table

Note that the vector components are added according to the addition table, so

for j=0, 1, ..., m-1. Also, when w>m-1, the sum can stop at wmod m because all the elements in the addition table have orders dividing m. This means that for each level h, there are at most m zero sum vectors. And if m is a prime power (pa), the sum can stop at wmod p. In this case there are up to p zero sum vectors for each level h.

In the m=3 example, the zero sum vectors are:

 h: 0 1 2 h: 0 1 2 h: 0 1 2 0 2 1 1 0 2 2 1 0 0 1 2 1 2 0 2 0 1 0 0 0 1 1 1 2 2 2

The zero sum operator acts on an array to replace each element with its corresponding zero sum vector. The result is an array with m times the number of rows compared to the original array. Thus,

 0 = 021 = 0 2 1 2 1 0 1 0 2

Now the zero sum array wE is expressed in terms of its column vectors as follows.

wEk = 0.w + if k=0. if 0

Examples of zero sum arrays are given in the following table. The reference tables in an appendix give the associated formulas, vectors, and levels for these arrays.

Zero Sum Covering Arrays
StrengthNumber
of Levels
Number
of Rows
Number
of Columns
ArrayReference Tables
lmrn

22431E formulavectorslevels
23931E formulavectorslevels
241631E formulavectorslevels
32842E formulavectorslevels
332742E formulavectorslevels
346442E formulavectorslevels
3621642E formulavectorslevels
421653E formulavectorslevels
438153E formulavectorslevels
4425653E formulavectorslevels

Note that when m is a prime (p) or a prime power (pa), the addition table sum in the zero sum vector expression can be replaced with a product from the multiplication table:

 h[w]j = h - sumk=0w(j)addition table = h - (w+1)mod p x j

Moreover, the zero sum vectors h[w] are the columns in the array

0+[w] = ( -(w+1)mod p )x+

## Covering Arrays for l>2 and m=2

### # Covering Arrays for l=3 and m=2

This section describes a recursive covering array construction for strength l=3 and number of levels m=2.

Consider the array wI for w=0, 1, ... Define

0I = 2P and

w+1I and w+1I' are both 2-by-2 arrays of arrays given by

w+1I = and

Here the underline in wI' indicates that all the order 2 vectors in wI' are replaced by their vector products with the 1+ vector. The effect is a transposition of levels 0 and 1 because wI' is comprised of vectors 0+ and 1+ only.

The following examples illustrate the construction of wI for w=0, 1, and 2.

When w=0,

0I=2P
= 0+0+0+0+
0+0+1+1+
0+1+0+1+
0+1+1+0+

0I is a covering array for strength l=3 because in this case 2P=2E, a zero sum array.

When w=1,

1I=0I0I
0I'0I'

=2P2P
2G2G

= 0+0+0+0+ 0+0+0+0+
0+0+1+1+ 0+0+1+1+
0+1+0+1+ 0+1+0+1+
0+1+1+0+ 0+1+1+0+
0+0+0+0+ 1+1+1+1+
0+0+1+1+ 1+1+0+0+
0+1+0+1+ 1+0+1+0+

1I contains two subarrays consisting of the left four columns and the right four columns. Each of the subarrays

2P and

covers its four columns with strength l=3 because it contains 2P. Now the top three rows of vectors in 2P are the same as 2G, so they cover the subarrays with strength l=2 also. In each of the top three rows of vectors, each of the element pairs in 2G is associated with a level, 0 or 1, to form 3-tuples in the same row of the other subarray. To cover all the 3-tuples spanning the subarrays, each of the 2G pairs is combined with the other level of the other subarray in the bottom three rows of vectors. This is accomplished by applying 1+ mapping operators to the plus vectors of 2G to form 2G in the right subarray. The result is six rows of vectors in 1I are the same as those of

1G =0+
0+
0+
1+

with 0+ replaced by 2G and 1+ replaced by 2G:

2G2G
2G2G

This construction covers the 3-tuples spanning the left and right subarrays. Since all the 3-tuples within and spanning the subarrays are covered, 1I covers all eight columns with strength l=3.

When w=2,

2I=1I1I
1I'1I'

=2P2P 2P2P
2G2G 2G2G
2G2G 2G2G
0··+1··+ 1··+0··+

= 0+0+0+0+ 0+0+0+0+ 0+0+0+0+ 0+0+0+0+
0+0+1+1+ 0+0+1+1+ 0+0+1+1+ 0+0+1+1+
0+1+0+1+ 0+1+0+1+ 0+1+0+1+ 0+1+0+1+
0+1+1+0+ 0+1+1+0+ 0+1+1+0+ 0+1+1+0+
0+0+0+0+ 1+1+1+1+ 0+0+0+0+ 1+1+1+1+
0+0+1+1+ 1+1+0+0+ 0+0+1+1+ 1+1+0+0+
0+1+0+1+ 1+0+1+0+ 0+1+0+1+ 1+0+1+0+
0+0+0+0+ 0+0+0+0+ 1+1+1+1+ 1+1+1+1+
0+0+1+1+ 0+0+1+1+ 1+1+0+0+ 1+1+0+0+
0+1+0+1+ 0+1+0+1+ 1+0+1+0+ 1+0+1+0+
0+0+0+0+ 1+1+1+1+ 1+1+1+1+ 0+0+0+0+

2I contains four subarrays, each consisting of four contiguous columns. Each of the subarrays covers its four columns with strength l=3 because it contains 2P. Next note that 2I contains nine rows of vectors that are the same as those of

2G =0+
0+
0+
0+
0+
1+
0+
1+
0+
0+
1+
1+

with 0+ and 1+ replaced by 2G and 2G respectively:

2G2G2G2G
2G2G2G2G
2G2G2G2G

This construction covers the 3-tuples spanning pairs of subarrays because all pairs of subarrays contain 2G paired with 2G and with 2G.

Now consider the four rows of vectors in 2I from the first rows of the 2P, 2G, and 2G subarrays, and from the last row of vectors in 2I. These rows are

0··+0··+0··+0··+
0··+1··+0··+1··+
0··+0··+1··+1··+
0··+1··+1··+0··+

which (with rearrangement) are the same rows of vectors as those of 0I with 0+ and 1+ replaced by 0··+ and 1··+ respectively. This construction covers the 3-tuples spanning three subarrays because 0I covers four columns with strength three. Since all the 3-tuples spanning one, two, or three subarrays are covered, 2I covers all 16 columns with strength three.

Constructions for w=3 and w=4 are given in an appendix.

The typical efficiency of a wI array compares favorably with that of a covering array generated by the Constrained Array Test System. The following table shows cases in which the number of rows of the wI array is less than or equal to that of the array from the expand command with the -t option.

Number of Rows for l=3 and m=2
Number
of Columns
expand -twI
nrwr
4808
814114
1626222
3238332
64
444

### #Covering Array for l=4, m=2, and n=8

This section describes a similar covering array for strength l=4, number of levels m=2, and number of columns n=8.

The array consists of two subarrays of four columns each. The top eight rows of plus vectors in each subarray are columns from 3P. They are the left four columns from 3E, so they cover each of the subarrays with strength four.

The next four rows of plus vectors in the left subarray are the columns from 2P; in the right subarray they are the columns from 2P. Now each row of plus vectors from 2P (on the left) is the same as a row of plus vectors from the 3P columns above. Since each subarray contains 2P in the top eight rows of plus vectors, each subarray covers its 3-tuples in combination with individual levels (0 or 1) from the other subarray. And since the subarrays pair 2P with 2P in the next four rows of plus vectors, each covers its 3-tuples with the other level from the other subarray also. Thus, the 4-tuples consisting of 3-tuples from one subarray and one level from the other are covered.

The last eight rows of plus vectors are as given below. Their inclusion allows the array to cover the remaining 4-tuples.

3P0003P0013P0103P100 3P0003P0013P0103P100
2P002P012P102P11 2P002P012P102P11
0.··+0++·+
0.+·+0+··+
0.··+0+·++
0.·++0+··+

A formula, vectors, and levels are given for this array in an appendix. Note that rows of vectors are rearranged in the appendix, to allow a more concise formulation than the one given here.

The efficiency of this array does not compare favorably with a corresponding array from the Constrained Array Test System: This construction has 40 rows; the expand program with the -Q option yields an array with 33 rows, and other CATS runs have yielded as few as 31 rows in this case.

### More Covering Arrays for l=3 and m=2

Another way to find covering arrays for strength l=3 and number of levels m=2 depends on the arrays of permutation vectors wP covering with strength 3 when w>1. Here, the cats program from the Constrained Array Test System is used to remove redundant rows from wP. The resulting covering array wP§ typically has the same number or fewer rows than the corresponding w-2I array. (The section mark in wP§ denotes the removal of redundant rows by cats.) Note that different wP§ arrays can be found depending on the order of the rows of wP in the cats program input.

An appendix gives the wP§ arrays for w=2, w=3, w=4, w=5, and w=6. The table below summarizes the numbers of rows for the different arrays for l=3 and m=2.

Number of Rows for l=3 and m=2
Number
of Columns
expand -tw-2I wP§
nrwrr
48288
81431414
162642220
323853228
64
64434

### More Covering Arrays for l=4 and m=2

The approach described in the previous section works because wP covers with strength l=3 when w>1. Generally this is not the case. The 2w columns of wP do not cover with strength 4 when w>1. However when w>2, there are combinations of 3<n<2w columns from wP which cover with strength 4. For example, a search of the 8 3P vectors yields 56 combinations of 4 which cover and 14 combinations which do not. The lowest such covering array is

3P000 3P001 3P010 3P100

in which elements have decreasing significance from left to right. This array also is expressed as 3F3P in which

3F = 000 001 010 100

is an array of levels in base 2 notation, and the 3P operator acts on each element to replace it with its corresponding permutation vector. The 16-by-4 arrays derived from the 3P columns do not compare favorably with the 16-by-5 zero sum array 3E, which is given in an appendix.

Two other examples, for w=4 and w=5 respectively, are the 32-by-6 array 4F4P and the 64-by-7 array 5F5P in which

4F = 0000 0001 0010 0100 1000 1111

and

5F = 00000 00001 00010 00100 01000 01111 10000

As in the previous section, the cats program can be used to remove redundant rows. The results in these cases are the 30-by-6 array 4F4P§ and the 32-by-7 array 5F5P§ given in an appendix. The table below compares the numbers of rows for these arrays with those from the expand program with the -q option.

Number of Rows for l=4 and m=2
Number
of Columns
expand -qwFwP§
nrwr
416316
628430
730532

### Still More Covering Arrays for l=3 and m=2

A later section describes the use of permutation vectors which do not cover to construct covering arrays which may have more than one row of permutation vectors. For example, an array with z=2 rows of 2F2P arrays (with the same number of columns) may be found to cover for l=3. The notation w,zFwP is used to label such an array. Because the top plus vector in every permutation vector is 0+, (z-1)m rows are redundant in each w,zFwP array. These rows are removed, as indicated by the apostrophe in w,zFwP', without losing the covering property of w,zFwP.

These arrays, introduced later for m>2, can be found for m=2 as well. However, like the m=2 arrays already described, they typically are not as efficient as other known binary covering arrays. This observation is illustrated in the table below which summarizes the numbers of rows for the different arrays for l=3 and m=2.

Number of Rows for l=3 and m=2
Number
of Columns
expand -t2Ew-2I wP§ 2,zF2P(')2,zF2P§ Sloane1
nrrwrr zrrr
488288 1888
4 2148
81431414 3201412
162642220 4262617
323853228 25
6464434 32
(The notation 2,zF2P(') in the table heading means 2,1F2P if z=1; it means 2,zF2P' if z>1.)
• n=4, z=1: The 2,1F2P array is the same as 2P, and applying the cats program to remove redundant rows – to get 2,1F2P§ – leaves the array unchanged. This array is minimal.
• n=4, z=2: Each 2,2F2P' array has 14 rows. The second row of permutation vectors in each 2,2F2P array is completely redundant because the first row covers, as above. Applying the cats program to remove redundant rows – to get 2,2F2P§ – yields the 2,1F2P array.
• n=8, z=3: Each 2,3F2P' array has 20 rows. Applying the cats program to remove redundant rows from the lowest array yields the 2,3F2P§ array which has 14 rows and differs from the 1I and 3P§ array by only two rows.
• n=16, z=4: Each 2,4F2P' array has 26 rows. Applying the cats program to remove redundant rows from the lowest array leaves it unchanged.

The rightmost column in the table puts all of these results in the perspective of the best known results (in 1993) for l=3 and m=2. The results given here offer no improvement.

1. Covering Arrays and Intersecting Codes, N. J. A. Sloane, Journal of Combinatorial Designs 1 1993, 51-63.

### Still More Covering Arrays for l=4 and m=2

The techniques described in the previous section to construct strength l=3 2,zF2P' arrays also can be used to find strength l=4 3,zFzP' arrays. The table below summarizes the numbers of rows for the different arrays for l=4 and m=2.

Number of Rows for l=4 and m=2
Number
of Columns
expand -q3Ew,1FwP w,1FwP§ 3,zF3P(')3,zF3P§
nrrwrr zrr
41631616 11616
524116
62843230
73056432
840123030
834430
114045858
(The notation 3,zF3P(') in the table heading means 3,1F3P if z=1; it means 3,zF3P' if z>1.)
• n=4, z=1: The w,1FwP and 3,zF3P(') table elements for n=4 columns refer to the same 3,1F3P array. Applying the cats program to remove redundant rows – to get 3,1F3P§ – leaves the array unchanged. This array is minimal.
• n=8, z=2: Each 3,2F3P' array has 30 rows. Applying the cats program to remove redundant rows from the lowest array leaves it unchanged.
• n=8, z=3: Each 3,3F3P' array has 44 rows. Applying the cats program to remove redundant rows from the lowest array yields the 3,3F3P§ array which has 30 rows and is the same as the lowest 3,2F3P' array.
• n=11, z=4: Each 3,4F3P' array has 58 rows. Applying the cats program to remove redundant rows from the lowest array leaves it unchanged.

1. expand -Q is more efficient than expand -q for the cases of n=5 and n=8, yielding 16 and 33 rows respectively.

### Numbers of Arrays for l=3, l=4 and m=2

The numbers of w,zFwP(') covering arrays resulting from the searches described in the previous two sections are given in the following table. Later sections provide more detail on how this type of search is performed.
Number of w,zFwP(') Covering Arrays for m=2
Number of Columns
lwzn
345
89
11
1617
321410
322240
323138240
32421565440

431560
432107520
433433520640or more0
43410 or more

• l=3, z=1: Any 3 of the 4 permutation vectors cover to form an n=3 column covering array. All 4 vectors can form a 4 column covering array also. Repeating any of the permutation vectors will not yield a 5 column covering array.

• l=3, z=2: For n=4 columns only one row of permutation vectors is needed to cover, so any of the four permutation vectors can be placed in any column of the lower row to yield a covering array. (There are 44=256 such arrays.) Since this search looks only for permutations, it finds that all 4!=24 permutations of permutation vectors in the lower row yield covering arrays. No covering arrays are found with 5 columns.

• l=3, z=3: For n=8 columns 13824 covering arrays are found and counted. No covering arrays are found with 9 columns.

• l=3, z=4: For n=16 columns 2156544 covering arrays are found and counted. No covering arrays are found with 17 columns.

• l=4, z=1: For n=4 columns 56 covering arrays are found and counted. No covering arrays are found with 5 columns.

• l=4, z=2: For n=8 columns 10752 covering arrays are found and counted. No covering arrays are found with 9 columns.

• l=4, z=3: For n=8 columns only two rows of permutation vectors are needed to cover, so any of the eight permutation vectors can be placed in any column of the bottom row to yield a covering array. Since this search looks only for permutations, it should find that each of the 8! permutations of permutation vectors in the bottom row forms a covering array with each of 10752 covering arrays with z=2. Thus there should be at least 10752·40320=433520640 covering arrays. This search was not completed. The 10 lowest covering arrays were found.

For n=9 columns a similar search was completed, with a fixed zeroth row of vectors and with the zeroth column of the first row fixed as 03P. (A later section gives more detail on the search scope and method.) No covering arrays were found. This result for 03P in the eighth column of the zeroth row and for 03P in the zeroth column of the first row suggests that there are no covering arrays for any other permutation vectors in these positions either. If there were some other choice for the eighth column of the zeroth row, the inverse of that vector could be applied as a position mapping operator to the zeroth row, to yield a covering array with 03P in the eighth column. The other eight columns could be rearranged to increase with column number, to yield a covering array with a zeroth row which is the same as the fixed row in the search. And if this transformed array were to have a nonidentity vector in the zeroth column of the first row, the inverse of that vector could be applied as a position mapping operator to the first row, to yield a covering array with 03P in the zeroth column. Such an array would have been found in the completed search. Thus, there are no covering arrays of this form, with z=3 rows of vectors, n=9 columns, and one permutation vector repeated in each row.

• l=4, z=4: For n=11 the 10 lowest covering arrays were found. This search was not completed.

## Noncovering Combinations of Permutation Vectors

### Covering Arrays from Noncovering Combinations

Earlier sections illustrate the use of permutation vectors to form covering arrays with strength l>2. These sections describe the combinations of permutation vectors which do not cover. The tabulation of these noncovering vector combinations then can be used to find covering arrays (which may have z>1 rows of permutation vectors). The idea is to construct an array w,zF from the mw levels 0, ..., mw-1 such that each of the (nl) combinations of columns contains at least one covering combination of permutation vectors.

Consider, for example, the permutation vectors for w=2 and m=3. For strength l=3, the covering array uses combinations of the mw=9 permutation vectors taken l=3 at a time. There are 84 such combinations. 72 of them cover, and 12 do not. The noncovering combinations are given in the following rows (in base 3 notation).

2P002P012P02
2P102P112P12
2P202P212P22

2P002P102P20
2P012P112P21
2P022P122P22

2P002P112P22
2P012P122P20
2P022P102P21

2P002P122P21
2P012P102P22
2P022P112P20

Once the noncovering combinations are tabulated, the covering arrays are found by systematically testing combinations of l columns for including permutation vector combinations which are not noncovering. This type of search is faster than testing each combination of columns for coverage directly.

In this case the lowest covering array with one row of vectors and n=4 columns is

2P002P012P102P11

The formula, vectors, and levels for this 27-by-4 array are given in an appendix.

### Sets of Noncovering Permutation Vectors

For m=prime or m=prime power, and w>0, consider the mw+1-by-n arrays which can be formed from columns of wP. Also consider the strengths l=1, 2, ..., w+2. There is no need to consider larger values of l because the wP permutation vectors can cover with at most strength w+1: The permutation vectors have mw+1 rows, and ml are needed to cover. The wP permutation vectors cannot cover with strength l>w+1.

The strength also cannot exceed the number of wP permutation vectors. Since there are mw vectors to form l-tuples, l cannot exceed mw without repeated use of one or more permutation vectors. And such repetition does not improve coverage.

Now for n=l, the arrays which do not cover define the noncovering combinations of permutation vectors. These are the combinations of l columns selected to form the noncovering arrays. In the cases considered here, these combinations can be described in terms of a set of noncovering permutation vectors. Each set contains ml-2 of the mw elements 0, 1, ..., mw-1. The elements are selected such that any combination of l elements labels a combination of permutation vectors which does not cover. Thus each noncovering set is associated with

 ( ml-2l )

noncovering combinations.

In the w=2, l=3, m=3 example, there are 3 elements in each noncovering set, and 1 noncovering combination results. When l=4 and m=3, all 9 elements are in a noncovering set, and 126 noncovering combinations result.

### Collections of Noncovering Permutation Vector Sets

The sets of noncovering permutation vectors can be organized into collections of noncovering sets. Each collection is a set of a power of m (ma) noncovering sets. (Specific formulations for the collections are given below.) For l less than or equal to w+2, there are

 ( wl-2 )

collections. In particular, for l=1,

 ( w-1 ) = 0

so there are no collections and no noncovering sets. All wP permutation vectors cover with strength l=1.

In the cases considered here, the total number of noncovering sets is given by wel,m whose values are computed recursively in a manner similar to that of Pascal's triangle.

 1e2,m = m 1e3,m = 1 w+1el+1,m = mw-l+2 wel,m + m wel+1,m

In the triangle, rows are labeled by w, and shaded diagonals are labeled by l. Each element, corresponding to wel,m, is the sum of each of the two elements above multiplied by an appropriate power of m. Thus for w=2 and l=3, for example,

2e3,m = m2-3+2 1e2,m + m 1e3,m = m2 + m

And for m=3, m2+m=12. I.e. there are 2 collections, one with 9 sets of noncovering vectors, and one with 3.

l=2l=3
w=1m1l=4
w=2m2m2+m 1l=5
w=3m3m4+m3
+m2
m3+m2
+m
1l=6
w=4m4m6+m5
+m4+m3
m6+m5
+2m4
+m3+m2
m4+m3
+m2+m
1
 wel,m = mw-l+2 ( wl-2 )m

Tables of Gaussian binomial coefficients can be found in the On-Line Encyclopedia of Integer Sequences. Sequence A022167 gives the table for the m=3 example.

Finally the total number of noncovering combinations of permutation vectors is the product of the number of noncovering combinations per set and the number of noncovering sets:

 ( ml-2l ) wel,m = mw-l+2 ( ml-2l ) ( wl-2 )m

It is important to note that the noncovering combinations of permutation vectors included in the total may not be unique. While each set of noncovering permutation vectors contains distinct vectors – so the combinations for each set are unique – it is possible for a combination of l vectors to appear in more than one set. In the strength l=3 cases described here (with w=2), the noncovering combinations are unique, so the total represents distinct noncovering arrays. However for the l=4 cases (with w=3), the noncovering combinations are not unique when the number of levels m is greater than or equal to the strength l. A later section shows that for l=4 with m=4 or m=5, the number of distinct noncovering arrays is less than the total formulated here.

### Special Cases of Noncovering Permutation Vector Combinations

The expression for the total number of noncovering combinations of permutation vectors leads to the following special cases:

• l=2: When l=2 the number of noncovering combinations is
 ( m2-22 ) we2,m = ( 12 ) we2,m = 0

All permutation vector combinations cover for l=2.

• l=3 and m=2: When l=3 and m=2 the number of noncovering combinations is
 ( 23-23 ) we3,2 = ( 23 ) we3,2 = 0

All permutation vector combinations cover for l=3 and m=2.

• l=w+2: When l=w+2 the number of noncovering combinations is
 ( mwl ) wew+2,m = ( mwl )

When l=w+2 all permutation vectors are contained in a single noncovering set.

### Formulas for Collections of Noncovering Permutation Vector Sets

The noncovering permutation vectors are described in terms of the mw elements 0, 1, ..., mw-1 in base m notation. The wel,m-by-wml-2 array w,lQ~ describes these elements with each row corresponding to a set of noncovering permutation vectors. w,lQ~ contains w subarrays consisting of ml-2 contiguous columns. Each subarray contains the values for a particular base m component (h0, h1, etc.) of the elements. For example, when w=2, l=3, and m=3,

2,3Q~ = +
0+..
0+.
0+x+

The top row of vectors

+0+.

describes a collection of 3 noncovering sets. The bottom row of vectors

0+..0+x+

describes a collection of 9 noncovering sets. The left subarray

2,3Q~0 =+
0+..

contains the values for the h0 component (3's place), and the right subarray

2,3Q~1 =0+.
0+x+

contains the values for the h1 component (1's place). Expansion of the formula gives

2,3Q~ =+
0+..
0+.
0+x+
=0+
0..
0+
1..
0+
2..
0.
0x+
1.
1x+
2.
2x+

It is convenient to use the notation w,lQ (without the tilde) to mean the array of noncovering elements expressed in base m (or h vectors). This requires a simple rearrangement of w,lQ~ columns to yield the wel,m-by-ml-2 array w,lQ. In the example,

2,3Q =0+0.
0..0x+
0+1.
1..1x+
0+2.
2..2x+
=00
10
20
01
11
21
02
12
22
00
01
02
10
11
12
20
21
22
00
01
02
11
12
10
22
20
21
00
01
02
12
10
11
21
22
20

When the elements of this array are replaced with their corresponding permutation vectors, the array of noncovering combinations 2,3Q2P results. This array was given in a previous section.

Descriptions of w,lQ~ for selected values of w and l are listed below.

• l<3: w,l<3Q~ has no elements. All combinations of permutation vectors cover with strength l=1 and l=2.
• l=w+2: w,w+2Q~ is comprised of the subarrays w,w+2Q~t in which t=0, ..., w-1, and
w,w+2Q~t = 0·t + ·(w-t-1)

Thus,

1,3Q~ =0+
2,4Q~ =0+· 0·+
3,5Q~ =0+·· 0·+· 0··+

and so forth. w,w+2Q~ contains one set of all mw permutation vectors (which do not cover with strength l=w+2).

• w=2, l=3, and m>2:
2,3Q~ = +
0+..
0+.
0+x+

There are m elements in each set. There are 2 collections: One with m sets and one with m2 sets.

• w=3, l=3, and m>2:
3,3Q~ = +.
+..
0+....
0·.+
0+...
0+x+..
0+..
0+.x+
0+..x+

There are m elements in each set. There are 3 collections with a total of m2+m3+m4 sets.

• w=3, l=4:
3,4Q~ = 0··+
0+·..
0+·...
0+·.
0+·x+
+...
+.
+..
0+·.x+*0·+x.+

There are m2 elements in each set. There are 3 collections with a total of m+m2+m3 sets.

• w=4, l=3, and m>2: For m=3, 1080 sets of 3 elements have been found. And here,
m3+m4+m5+m6=1080
• w=4, l=4: For m=2, 140 sets of 4 elements have been found. An expression for 4,4Q~ containing the 6 collections has been found for this case.

## Covering Arrays for l>2 and m>2

This section describes results of searches for covering arrays using the technique described in the previous sections. The arrays consist of z rows of permutation vectors. Each search is to find arrays such that every combination of l columns contains at least one row of permutation vectors which is not noncovering. The notation w,zF is used to describe covering arrays which may have z>1 rows of permutation vectors.

### Covering Arrays for l=3 and m>2

The results for w=2, l=3, and m>2 are summarized in the following table.

Covering Arrays for w=2, l=3, and m>2
Number
of Rows
of Vectors
Number
of Levels
Number
of Rows
Number
of Columns
ArrayReference Tables
zmrn

132742,1F2P formulavectorslevels
146462,1F2P formulavectorslevels
1512562,1F2P formulavectorslevels
1734382,1F2P formulavectorslevels
18512102,1F2P formulavectors
19729102,1F2P formulavectors
1111331122,1F2P formulavectors
1132197142,1F2P formulavectors
235192,2F2P' formulavectorslevels
24124162,2F2P' formulavectorslevels
25245242,2F2P' formulavectors
27679312,2F2P' formulavectors
281016402,2F2P' formulavectors
291449392,2F2P' formulavectors
2112651442,2F2P' formulavectors
2134381392,2F2P' formulavectors
3375202,3F2P' formulavectors
34184282,3F2P' formulavectors

The reference tables in an appendix give the lowest arrays in terms of their permutation vector formulas, plus vectors, and levels. (Rows of permutation vectors have decreasing significance from top to bottom.)

Because the top plus vector in every permutation vector is 0+, (z-1)m rows are redundant in each array. These rows are removed, as indicated by the apostrophe in 2,zF2P'. Thus the number of rows is

r = zml - (z-1)m

Note that the sliding levels technique described for strength l=2 arrays can be applied for higher strength arrays as well. Thus an array for m=prime power product can be formulated in terms of an array for a larger value m'=prime power. Two examples for l=3, m=6, and m'=7, with z=1 and z=2, are given in an appendix.

### Numbers of Arrays for l=3

When the values of z and m are low, the searches can run to completion, so all the covering arrays 2,zF2P can be found. Also the maximum number of columns n can be found by executing searches with increasing n until one completes without finding a covering array. Tables in the following sections list the numbers of arrays (based on the lowest first column vectors) in these cases.

The results given here for higher values of z and m, i.e. for

 z=1 and m>9, z=2 and m>4, and z>2,

are from searches which yielded one or more covering arrays but which were abandoned prior to completion.

Note that where a maximum n is found, its value is greater than or equal to mz. In the cases listed with n<mz, searches with larger values of n were abandoned without finding an array and without completion. These results are consistent with the conjecture that there are covering arrays of this form

• for z=1 row of vectors with n=m+1 columns, and
• for z>1 row of vectors with n=mz columns.

#### z=1 Row of Permutation Vectors

When z=1 row of permutation vectors, the search is to find combinations of n vectors which cover. For each such array any permutation of the n vector columns also covers. So to narrow the search, candidate arrays are constrained to have vectors in ascending order with increasing column number. That is, the lowest permutation of each covering combination of vectors is found and counted. Each number of arrays is the number of covering combinations resulting from a completed search which spans the

 ( mwn )

total combinations.

Number of 2,1F2P Covering Arrays for w=2, l=3, and z=1
Number
of Levels
Number of Columns
mn
3456 7891011
2410
372540
448084028848 0
52000650066001000 0
716464127596444528460992 5174461740
83763240454421450244158336 1666560584640125440125440
9777601108080832809626290656 237945603411720239760233280

For the cases considered here the number of covering arrays can be described for selected values of n columns as follows. (Note that for z=1 the covering arrays are orthogonal arrays of index one.)

• n=3: The number of covering arrays is the total number of l=3 combinations minus the number of noncovering combinations:
 ( mwn ) - ( ml-2l ) wel,m = ( m23 ) - ( m3 ) (m+1)m
• n=4: The number of covering arrays is
 13 {( m-12 ) + 12 }( m2 )( m22 )
• n=m+1: The number of covering arrays is
 2m( m2 )2
except for m=8, which has 10 times the number of arrays suggested by this expression. Note that in a later section describing a recursive search, the number of orthogonal arrays found for l=3 with n=m+1 is m-1, except for m=8, which has 10(m-1)=70 arrays. Thus the ratio of the numbers of arrays found for the two types of searches is m2(m2). And this ratio holds for m=8 also.
• n=m+2: The number of covering arrays is zero unless the number of levels m=2a, a power of 2. When m is a power of 2, the number of covering arrays for n=m+2 is the number of arrays for n=m+1 divided by m+2.

Often the number of covering arrays is a multiple of mw. This property can be explained by associating each covering array with a set of mw arrays which differ only by a permutation of rows. For each covering array select one permutation vector from the set of mw. The permutation vector is applied to the row of permutation vectors in the array, from the left, as a position mapping operator. This operation has the effect of permuting the rows of all the permutation vectors, so the transformed array also covers. And the transformed array consists of a row of permutation vectors because they form a group with the vector product operator. Thus the transformed arrays can be found in the search, and the number of arrays can be a multiple of mw.

In the table above there are two exceptions to this observation: for m=2 with n=4, and for m=4 with n=4. Note that in the case of m=2, the transformation described here results in 4 permutations of the single combination of vectors, and not 4 different combinations.

#### z=2 Rows of Permutation Vectors

When z=2 rows of permutation vectors, the array is partitioned into subarrays of up to mw contiguous columns. Each row of vectors in each subarray consists of permutation vectors which are not repeated. That is, a permutation of the mw levels identifies the vectors in each row of the subarray. In addition, the zeroth row of vectors is fixed, so that in each subarray the permutation vectors are taken from the corresponding subarray columns 0, 1, ..., mw-1.

In this section two cases are considered for the number of columns n:

• n=m2: Here there is one subarray, and the zeroth row is fixed to be
(0 1 ... m2-1)2P
• n=m2+1: And here there are two subarrays, columns 0 to m2-1 and column m2. The zeroth row is fixed to be
(0 1 ... m2-1 0)2P

For z=2 rows of vectors, the search is to find permutation vectors for the first (lower) row of vectors which together with the zeroth (upper), fixed row of vectors will cover. In this case, different permutations of the vectors in the lower row of each subarray are counted separately. So for n=m2, the scope of the search is up to m2! arrays. And for m2+1, the scope is up to m2!m2 arrays.

The numbers of covering arrays resulting from completed searches are given in the following table.

Number of 2,2F2P' Covering Arrays for w=2, l=3, and z=2
Number
of Levels
Number of Columns
mn
45
9 10
1617
2240
3829440
42342131200

• m=2, n=4: For n=4 columns only one row of vectors is needed to cover, so any of the four permutation vectors can be placed in any column of the lower row to yield a covering array. (There are 44=256 such arrays.) Since this search looks only for permutations, it finds that all 4!=24 permutations of permutation vectors in the lower row yield covering arrays.
• m=2, n=5: No covering arrays are found with 5 columns.
• m=3, n=9: For n=9 columns 1152 arrays are found for each of the 72 permutations of vectors in the zeroth and first columns of the first row. Thus there is a total of 82944 covering arrays, all of which are found and counted in this case.
• m=3, n=10: For n=10 columns a search was completed as described above, with a fixed zeroth row of vectors. No covering arrays were found. This result for 02P in the ninth column of the zeroth row suggests that there are no covering arrays for any other permutation vector in the ninth column either. If there were some other choice, the inverse of that vector could be applied as a position mapping operator to the zeroth row, to yield a covering array with 02P in the ninth column. The other nine columns could be rearranged to increase with column number, to yield a covering array which would have been found in the completed search. Thus, there are no covering arrays of this form, with z=2 rows of vectors, n=m+1 columns, and one permutation vector repeated in each row.
• m=4, n=16: For n=16 columns 975888 arrays are found for each of the 15 permutations of first row vectors in which 02P is in the zeroth column and some other vector is in the first column. Thus there are 14638320 covering arrays found and counted with 02P in the zeroth column of the first row. This result implies there are 16·14638320 arrays of this form because any of the 15 nonidentity permutation vectors (not 02P) can be applied as a position mapping operator to the first row, to yield another covering array with a different permutation of vectors in the first row, and with a different permutation vector (not 02P) in the zeroth column. Similarly, any covering array of this form with a nonidentity vector in the zeroth column of the first row can be mapped to one of the arrays found in the search by applying the inverse of the vector in the zeroth column to the first row. The result is a covering array with 02P in the zeroth column of the first row, which would be found in the search. Thus there is a total of 234213120 covering arrays in this case.
• m=4, n=17: For n=17 columns a search was completed as described above, with a fixed zeroth row of vectors and with the zeroth column of the first row fixed as 02P. No covering arrays were found. This result for 02P in the sixteenth column of the zeroth row and for 02P in the zeroth column of the first row suggests that there are no covering arrays for any other permutation vectors in these positions either. If there were some other choice for the sixteenth column of the zeroth row, the inverse of that vector could be applied as a position mapping operator to the zeroth row, to yield a covering array with 02P in the sixteenth column. The other sixteen columns could be rearranged to increase with column number, to yield a covering array with a zeroth row which is the same as the fixed row in the search. And if this transformed array were to have a nonidentity vector in the zeroth column of the first row, the inverse of that vector could be applied as a position mapping operator to the first row, to yield a covering array with 02P in the zeroth column. Such an array would have been found in the completed search. Thus, there are no covering arrays of this form, with z=2 rows of vectors, n=m+1 columns, and one permutation vector repeated in each row.

Note that the number of covering arrays is a multiple of mw=m2. This property can be explained by associating each covering array with a set of mw arrays which differ only by a permutation of rows. For each covering array consisting of 2 rows of permutation vectors, select one permutation vector from the set of mw. This vector is applied to the lower row of permutation vectors in the array, from the left, as a position mapping operator. This operation has the effect of permuting the rows of this row of permutation vectors, so the transformed array also covers. And the transformed array consists of 2 rows of permutation vectors (with the upper row fixed) because the permutation vectors form a group with the vector product operator. Thus the transformed arrays are found in the search, and the number of arrays is a multiple of mw.

Of course a permutation vector could be applied to the upper row (as above for z=1), possibly leading to the number of arrays being a multiple of mwz. But there is no assurance that the transformed array would be unique within the search and counting rules given here. It turns out that for m=3 and m=4 with n=m2 the number of arrays actually is a multiple of m4: For each of the mw permutation vectors in the zeroth column of the lower row, the number of covering arrays is observed to be a multiple of m2. (m=2 is an exception to this pattern.)

### Covering Arrays for l=4 and m>2

This section describes results of searches for strength l=4 covering arrays using the technique described in the previous sections. The results for w=3, l=4, and m>2 are summarized in the following table.

Covering Arrays for w=3, l=4, and m>2
Number
of Rows
of Vectors
Number
of Levels
Number
of Rows
Number
of Columns
ArrayReference Tables
zmrn

138153F3P formulavectorslevels
1425653F3P formulavectorslevels
1562563F3P formulavectors
23159103,2F3P' formulavectorslevels
2450893,2F3P' formulavectors
251245113,2F3P' formula
33237163,3F3P' formulavectors

The reference tables in an appendix give the lowest arrays in terms of their permutation vector formulas, plus vectors, and levels.

The 3F3P array described earlier for m=2 has only four columns compared to the 3E zero sum array which has five. The 3F3P arrays in this table for m=3 and m=4 have the same numbers of rows and columns compared to the corresponding 3E zero sum arrays. For m=5 the 3F3P array has m+1=6 columns.

Arrays with additional columns are found when z>1. These results are consistent with the conjecture that there are covering arrays of this form

• for z=1 row of vectors with n=m+1 columns, and
• for z>1 row of vectors with n=mz columns.

### Numbers of Arrays for l=4

When z=1 row of permutation vectors, the search is to find combinations of n vectors which cover. For each such array any permutation of the n vector columns also covers. So to narrow the search, candidate arrays are constrained to have vectors in ascending order with increasing column number. That is, the lowest permutation of each covering combination of vectors is found and counted. Each number of arrays is the number of covering combinations resulting from a completed search which spans the

 ( mwn )

total combinations.

Number of 3,1F3P Covering Arrays for w=3, l=4, and z=1
Number
of Levels
Number of Columns
mn
456 7
2560
312636126360
448384019353600
5775000079050000620000000
(Note that for z=1 the covering arrays are orthogonal arrays of index one.)

For the n=4 cases described here, the number of covering arrays is the total number of l=4 combinations minus the number of unique noncovering combinations:

 ( mwn ) - {( ml-2l ) - ( ml )m2} wel,m = ( m34 ) - {( m24 ) - ( m4 )m2} (m2+m+1)m
Note that when m=4 or m=5, the number of distinct noncovering combinations is less than the total number of noncovering combinations
 ( ml-2l ) wel,m = ( m24 ) (m2+m+1)m

because the combinations in the total are not unique.

## Covering Array Searches for z>1

### # Preparation

This section describes in some detail the search technique for arrays with multiple rows of permutation vectors. An example with strength l=3, number of levels m=3, number of columns n=20, log-order w=2, and number of rows of vectors z=3 illustrates the search technique.

Throughout this discussion, candidate covering arrays are described in terms of the mw levels which label the permutation vectors, and to which the wP operator is applied. In the search itself there is no need to compute the permutation vectors explicitly. The application of the wP operator to compute the covering array is the last step, after the search is complete.

There is no need for base m to label the permutation vectors in the search program, so decimal integers are used. In this example, the mw permutation vectors are indicated by the integers 0, 1, ..., 8. The sets of noncovering permutation vectors are computed from the w,lQ~ formula, and each set is stored in ascending order. In this example, the noncovering sets are indicated by

012
345
678

036
147
258

048
156
237

057
138
246

The permutation vectors wP can be computed from their definition also.

To reduce the scope of the search and thus reduce execution times, search constraints are imposed:

• If the number of columns n is less than mw, the zeroth row of vectors is required to be in ascending order without repeating. Other rows of vectors may contain any permutation of the mw levels.
• If the number of columns n is greater than or equal to mw, two constraints are imposed:
1. The array is partitioned into subarrays of up to mw contiguous columns. Each row of vectors in each subarray consists of permutation vectors which are not repeated. That is, a permutation of the mw levels identifies the vectors in each row of the subarray. In the example, n>mw. Moreover, 2mw<n<3mw, so there are three subarrays, consisting of columns 0 to 8, 9 to 17, and 18 to 19. Each of the nine permutation vectors must occur in each row of vectors in columns 0 to 8 and in columns 9 to 17. Two different vectors are in each row in columns 18 to 19.
2. The zeroth row of vectors is fixed. In each subarray the permutation vectors are taken from the corresponding subarray columns 0, 1, ..., mw-1. In the example the zeroth row of vectors is given by

Within these constraints the lowest array in the example, from which the search is started, is given by

(The 2P operator is implied.) The search progresses to higher candidate arrays, in which increasing rows (top to bottom) have decreasing significance, and increasing columns (left to right) have decreasing significance.

Each candidate array is checked for coverage by consideration of each combination of l columns, which must contain at least one l-tuple of permutation vectors which is not noncovering. Column combinations are enumerated by an l-order vector

k0 k1 ... kl-1

in which the column numbers are placed in ascending order:

k0 < k1 < ... < kl-1

In the example the first column combination to check is 0 1 2. If it covers, the highest column k2 is incremented to 3, so the next three combinations,

 0 1 3, 0 2 3, and 1 2 3,

can be checked. If these combinations cover, k2 is incremented again, and

 0 1 4, 0 2 4, 1 2 4, 0 3 4, 1 3 4, and 2 3 4,

are checked.

It is important to note that for each highest column kl-1, all the associated

 ( kl-1l-1 )

combinations are checked together. Thus, as the candidate array changes, and kl-1 varies, it is easy to find which column combinations need to be rechecked.

A score array stores coverage results during the computation. This array contains z elements (one for each row of vectors) for each l order column combination. I.e. the score array has z(nl) elements, and in the example there are 3420 elements.

The value of each score array element is set according to the coverage of the corresponding row of vectors for this column combination. Three values are used:

ValueMeaning
0Coverage not checked yet
1Column combination covers for this row of vectors
-1Column combination does not cover for this row of vectors

Initially all the elements of the score array are set to zero. As coverage is checked, the results are recorded. This cache is used to reduce the need to recheck as the candidate covering array is varied. Thus, when a permutation vector in a particular row is changed, the score array elements for this row with the combinations including this column are reset to zero. But the other score array elements remain valid for the rest of the candidate array.

### # Checking Column Combinations for Coverage

Each column combination is checked for coverage as follows. First a loop over the rows of vectors is started.

• If the corresponding score array value is positive, the program breaks out of the loop because the combination is known to cover.
• If the corresponding score array value is negative, the program continues with the next row of vectors because the combination in this row is known not to cover.
• Otherwise the score array value is zero, and the coverage is checked as follows.
• In the candidate array the l permutation vectors for this row are checked for duplicates. If there are any repeats, the combination will not cover. So the score array value is set to -1, and the program continues with the next row of vectors. (Note that duplicates only occur in column combinations spanning more than one partition of the candidate array.)
• A loop over the sets of noncovering vectors is started. (Each iteration considers one set of noncovering vectors.) Each of the l permutation vectors from the candidate array is compared to each of the noncovering set elements, and the number of matches is counted.
• If the number of matches equals l for any noncovering set, the combination will not cover. So the score array value is set to -1, and the program continues with the next row of vectors.
• If the number of matches is less than l for all noncovering sets, this combination will cover. So the score array value is set to 1, and the coverage check is complete for this column combination.

If the row of vectors loop completes without finding coverage (if all rows have scores of -1), then this column combination does not cover, and a different candidate array is selected.

### # Varying the Candidate Covering Array

When a candidate array does not cover with a particular highest column kl-1, the next candidate covering array is found by incrementing the least significant element. This element is in the bottom row of vectors and column kl-1. The next permutation vector for this element is found by incrementing the level by one until it is different from the levels of the lower columns in this row and partition. (I.e. it must lead to a permutation in this row and partition.) Any remaining columns (above kl-1) in this row and partition are given the remaining levels in ascending order, so the partition contains the lowest of the remaining permutations in this row.

If the mw levels are exhausted for the given row and column kl-1, then the program selects the lowest level unused in this row in the lower columns of this partition. In this case, the next row up (the next more significant row) is incremented similarly. If the levels are exhausted in the first row, then the bottom row in the next more significant column (kl-1-1) is incremented (because the zeroth row is fixed). The process of selecting more significant rows and columns continues until the next higher candidate array is found. The score array elements corresponding to the incremented rows and columns are reset to zero. And the highest column kl-1 is set to the lowest column with incremented elements. There is no need to recheck combinations of unchanged columns.

When a covering array with the required number of columns is found, the same process is used to find the next candidate. The least significant element in the bottom row and the highest column kl-1 is incremented.

# Orthogonal Arrays of Index One

## Orthogonal Array Recursive Search

To find arrays with larger values of l or m, a narrower search can be used. The search described here is to find orthogonal arrays of index one, beginning with strength l=2 and working up to higher strengths recursively.

For m=prime or m=prime power, consider the vectors

1Nh = hx+ for h=0, ..., m-1.

The array

1N = 0+. 1N0 ... 1Nm-1

is an orthogonal array of index one and strength l=2. (1N is the same as 1H.)

In terms of the permutation vectors,

1N = 2P1– 1P0 ... 1Pm-1

because

2P1– by a reduced permutation vector recurrence relation

and

1Nh for h=0, 1, ..., m-1

## Orthogonal Arrays for l=3 and m>2

For l=3 the search is to find orthogonal arrays containing the vectors

2Nk = (1Nh * k.x)+

I.e. the search is to find a level h(k) for each column k>1 such that the vectors 2Nk cover for k=0, 1, ..., m-1.

Note that the vector for k=0 is independent of h:

2N0 = (1Nh * 0.x)+ = 0.x+ = 2P00

for h=0, ..., m-1. Also, to limit the scope of the search, the vector for k=1 is constrained to be

2N1 = (1N0 * 1.x)+ = 1.x+ = 2P10

The 2Nk vectors can be expressed in terms of the permutation vectors as follows (using base m notation).

2Nk = (1Ph * k.x)+ by the definition of 1Nh by the reduced permutation vector recurrence relations by the reduced permutation vector product identity

This result can be expressed as 2Pk x (m+h) also.

The strength l cannot exceed the number of columns m in the search, so the minimum value of m is l. Thus the search is constrained by the relation

l < m+1

With the reduced permutation vector 3P001– inserted as the leftmost column, the array becomes

2N = 3P001– 2N0 ... 2Nm-1

an orthogonal array of index one and strength l=3. The total number of columns n is m+1, so

l < m+1 = n

For the l=3 cases considered here, the search results include at least m-1 arrays, one of which is given by

2Nk = 2Ph

in which

 h0 = k and h1 = k x (k-1) or h = k x (m+k-1)

Thus, for example, for m=9, k-1 = k+2, so that

 h1(k=2) = 2 x (2+2) = 2 x 1 = 2 h1(k=3) = 3 x (3+2) = 3 x 5 = 1, etc.

and

2N = 3P001– 2P00 2P10 2P22 2P31 2P47 2P53 2P67 2P71 2P83

Moreover m-1 arrays are given by 2Ph in which

 h0 = k and h1 = k x (k-1) x h', with h' = any nonzero level = 1, ..., m-1

The search results are summarized in the following table.

Orthogonal Arrays for w=2, l=3, and m>2
Number
of Levels
Number
of Rows
Number
of Columns
Number
of Arrays
ArrayReference Tables
mrn

327422N formulavectorslevels
464532N formulavectorslevels
5125642N formulavectorslevels
7343862N formulavectorslevels
85129702N formulavectors
97291082N formulavectors
11133112102N formulavectors

Note that for m=8, the search results in 70 arrays, including the 7 described above.

The reference tables in an appendix give the arrays for h'=1 in terms of their permutation vector formulas, plus vectors, and levels.

## Orthogonal Arrays for l>3 and m>3

For successively larger values of l, the search is to find orthogonal arrays containing the vectors

w+1Nk = (wNh * k.w x)+

in which l=w+2, wNh is one of the m column vectors from an orthogonal array for l=w+1, and the dot operator exponent w indicates the operator is applied w times. Again the search is to find a level h(k) for each column k>1 such that the vectors w+1Nk cover for k=0, ..., m-1. Of the mw possible levels h, the search considers only the m levels which yield orthogonal array column vectors for the previous value of l=w+1. Also note that

wN0 = wP0

and

wN1 = wPmw-1

as before.

When w=1 and w=2, the orthogonal array column vectors wNh are permutation vectors, so for each of the m levels h, there is a level h'' such that

wNh = wPh''

If this is true for some value of w, then it is true for w+1 also:

w+1Nk = (wPh'' * k.w x)+
= (w+1P1h''– * w+1Pk0–)+
= (w+1Pk x (mw+h'') –)+
= w+1Pk x (mw+h'')

Thus the column vectors w+1Nk are permutation vectors.

The resulting orthogonal array is

w+1N = w+2P1– w+1N0 ... w+1Nm-1

which has index one and strength l=w+2. Again, the total number of columns n is m+1, so

l < m+1 = n

Searches for l=4 orthogonal arrays were performed using 2Nk columns from selected l=3 arrays found in previous searches. Arrays were found for values of m=4, 5, and 7. Each of the selected l=3 arrays yielded 6, 20, and 18 l=4 arrays for m=4, 5, and 7 respectively.

Moreover for l=5 and m=5, 24 orthogonal arrays were found using an l=4 array from a previous search.

## Orthogonal Array Formula for l<m+2

Some of the search results described in the previous sections suggest an orthogonal array formula as follows. For columns k=0, 1, ..., m-1, let

wLk = wPh

in which

 ht = products=0t(k-s), t=0, 1, ..., w-1

Then the index one orthogonal array is given by

wL = w+1P1– wL0 ... wLm-1

The strength l cannot exceed the number of columns n in the formula, so the minimum value of n is l.

l < n+1

The formula gives n=m+1 columns, so the relation

l < m+2 = n+1

results.

For a given value of m, the ht products are easily computed by starting with w=1 and working up to the desired strength l=w+1. Examples are given in the following table.

Orthogonal Array Formulas for l=w+1 and l<m+2
StrengthNumber
of Levels
Formulas
lmwL
22 2P01–1P0 1P1
32 3P001–2P00 2P10
23 2P01–1P0 1P11P2
33 3P001–2P00 2P102P22
43 4P0001–3P000 3P1003P220
24 2P01–1P0 1P11P2 1P3
34 3P001–2P00 2P102P21 2P31
44 4P0001–3P000 3P1003P210 3P311
25 2P01–1P0 1P11P2 1P31P4
35 3P001–2P00 2P102P22 2P312P42
45 4P0001–3P000 3P1003P220 3P3113P424
27 2P01–1P0 1P11P2 1P31P4 1P51P6
37 3P001–2P00 2P102P22 2P362P45 2P562P62
47 4P0001–3P000 3P1003P220 3P3663P453 3P5643P621
28 2P01–1P0 1P11P2 1P31P4 1P51P6 1P7
38 3P001–2P00 2P102P26 2P362P42 2P522P64 2P74
29 2P01–1P0 1P11P2 1P31P4 1P51P6 1P71P8
39 3P001–2P00 2P102P22 2P312P47 2P532P67 2P712P83
211 2P01–1P0 1P11P2 1P31P4 1P51P6 1P71P8 1P91PA
311 3P001–2P00 2P102P22 2P362P41 2P592P68 2P792P81 2P962PA2

(The symbol A represents 10 in base 11 notation.)

Selected orthogonal arrays following this formula are described in the table below.

Selected Orthogonal Arrays Following Formula for l=3 and l=4
StrengthNumber
of Levels
Number
of Rows
Number
of Columns
ArrayReference Tables
lmrn

32832L formulavectorslevels
332742L formulavectorslevels
346452L formulavectorslevels
3512562L formulavectorslevels
3734382L formulavectorslevels
3851292L formulavectors
39729102L formulavectors
3111331122L formulavectors
438143L formulavectorslevels
4425653L formulavectorslevels
4562563L formulavectors
47240183L formula

The reference tables in an appendix give these arrays in terms of their permutation vector formulas, plus vectors, and levels. Note that the 2L arrays for m>2 given here are the same as the 2N arrays given in a previous section.

Forward to Next Section