Orthogonal array

An orthogonal array with N runs, k factors, s symbols and strength t is a set of N k-tuples (called runs) with elements from $\{0,\dots ,s-1\}$ such that for every set of t coordinates every combination of symbols in these coordinates appears equal number of times across the runs. Such orthogonal array are commonly denoted by $OA(N,k,s,t)$. It is easy to see that N is divisible by $s^{t}$ — the number of all possible symbol combinations in the t coordinates. The number ${\tfrac {N}{s^{t}}}$ is called the index of the orthogonal array.

Statistical applications

Orthogonal arrays are often used in statistics. Experiments based on orthogonal arrays require less tests and yet provide a lot of info.

Particular cases

Some mathematical constructions are particular cases of orthogonal arrays. For example, Latin squares are $OA(n^{2},3,n,2)$. In order to see this, consider all triples $(i,j,a(i,j))$ where $s(i,j)$ denotes the symbol in the i-th row and j-th column in the Latin square. Then the $n^{2}$ triples constructed thus for all $i,j\in {0,\dots ,s-1}$ form an orthogonal array with strength 2: there is a single cell with given coordinates, single cell with given row and symbol in the cell and a single cell with given column and symbol in the cell. Here is a simple example:

Latin square	Orthogonal array
0 1 2 2 0 1 1 2 0	(0,0,0) (0,1,1) (0,2,2) (1,0,2) (1,1,0) (1,2,1) (2,0,1) (2,1,2) (2,2,0)

A set of k orthogonal Latin square can be converted to $OA(n^{2},k,n,2)$ in a similar way.

Adamar matrices of size $4N\times 4N$ give an example of $OA(4N,4N-1,2,2)$. You just need to remove a column of 1's from the matrix:

Adamar matrix	Orthogonal array
1 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0	(1,1,1) (0,0,1) (0,1,0) (1,0,0)

Another example is a linear error-correcting code. All codewords of the dual code form a linear orthogonal array with strength $d-1$ where $d$ is a distance of the code. Here is an example:

Code	Dual code	Orthogonal array
000 111	000 011 101 110	(0,0,0) (0,1,1) (1,0,1) (1,1,0)

Main bounds

The main result in the theory of orthogonal arrays is the lower linear programming bound on the number of runs in the orthogonal array.

Generalizations

There is several useful generalizations of the definition of orthogonal array. We can allow different factors have a different number of symbols. We can assign unequal probabilities to the symbols and require that each combination of symbols appears in the fraction of runs given by the product of probabilities of symbols in the combination. And we can combine these generalizations, allowing different number of symbols and different symbol probabilities for different factors.