Orthogonal array
In mathematics, an orthogonal array is a "table" whose entries come from a fixed finite set of symbols, arranged in such a way that there is an integer t so that for every selection of t columns of the table, all ordered t-tuples of the symbols, formed by taking the entries in each row restricted to these columns, appear the same number of times. The number t is called the strength of the orthogonal array. Here is a simple example of an orthogonal array with symbol set and strength 2:
Notice that the four ordered pairs formed by the rows restricted to the first and third columns, namely,, and are all the possible ordered pairs of the two element set and each appears exactly once. The second and third columns would give,,, and ; again, all possible ordered pairs each appearing once. The same statement would hold had the first and second columns been used. This is thus an orthogonal array of strength two.
Orthogonal arrays generalize the idea of mutually orthogonal Latin squares in a tabular form. These arrays have many connections to other combinatorial designs and have applications in the statistical design of experiments, coding theory, cryptography and various types of software testing.
Definition
A t- orthogonal array is a λvt × k array whose entries are chosen from a set X with v points such that in every subset of t columns of the array, every t-tuple of points of X appears in exactly λ rows.In this formal definition, provision is made for repetition of the t-tuples and the number of rows is determined by the other parameters.
In many applications these parameters are given the following names:
An orthogonal array is simple if it does not contain any repeated rows.
An orthogonal array is linear if X is a finite field of order q, Fq and the rows of the array form a subspace of the vector space k.
Every linear orthogonal array is simple.
[|Examples]
An example of a 2- orthogonal array; a strength 2, 4 level design of index 1 with 16 runs.| 1 | 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 2 | 2 |
| 1 | 3 | 3 | 3 | 3 |
| 1 | 4 | 4 | 4 | 4 |
| 2 | 1 | 4 | 2 | 3 |
| 2 | 2 | 3 | 1 | 4 |
| 2 | 3 | 2 | 4 | 1 |
| 2 | 4 | 1 | 3 | 2 |
| 3 | 1 | 2 | 3 | 4 |
| 3 | 2 | 1 | 4 | 3 |
| 3 | 3 | 4 | 1 | 2 |
| 3 | 4 | 3 | 2 | 1 |
| 4 | 1 | 3 | 4 | 2 |
| 4 | 2 | 4 | 3 | 1 |
| 4 | 3 | 1 | 2 | 4 |
| 4 | 4 | 2 | 1 | 3 |
An example of a 2- orthogonal array :
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 2 |
| 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 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 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 |
| 0 | 0 | 0 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 2 | 2 | 0 | 0 | 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 |
Trivial examples
Any t- orthogonal array would be considered trivial since they are easily constructed by simply listing all the t-tuples of the v-set λ times.Mutually orthogonal latin squares
A 2- orthogonal array is equivalent to a set of k − 2 mutually orthogonal Latin squares of order v.Index one, strength 2 orthogonal arrays are also known as Hyper-Graeco-Latin square designs in the statistical literature.
Let A be a strength 2, index 1 orthogonal array on a v-set of elements, identified with the set of natural numbers. Chose and fix, in order, two columns of A, called the indexing columns. All ordered pairs with 1 ≤ i, j ≤ v appear exactly once in the rows of the indexing columns. Take any other column of A and create a square array whose entry in position is the entry of A in this column in the row that contains in the indexing columns of A. The resulting square is a Latin square of order v. For example, consider the 2- orthogonal array:
| 1 | 1 | 1 | 1 |
| 1 | 2 | 2 | 2 |
| 1 | 3 | 3 | 3 |
| 2 | 1 | 2 | 3 |
| 2 | 2 | 3 | 1 |
| 2 | 3 | 1 | 2 |
| 3 | 1 | 3 | 2 |
| 3 | 2 | 1 | 3 |
| 3 | 3 | 2 | 1 |
By choosing columns 3 and 4 as the indexing columns, the first column produces the Latin square,
while the second column produces the Latin square,
The Latin squares produced in this way from an orthogonal array will be orthogonal Latin squares, so the k − 2 columns other than the indexing columns will produce a set of k − 2 mutually orthogonal Latin squares.
This construction is completely reversible and so strength 2, index 1 orthogonal arrays can be constructed from sets of mutually orthogonal Latin squares.
Latin squares, Latin cubes and Latin hypercubes
Orthogonal arrays provide a uniform way to describe these diverse objects which are of interest in the statistical design of experiments.Latin squares
As mentioned in the previous section a Latin square of order n can be thought of as a 2- orthogonal array. Actually, the orthogonal array can lead to six Latin squares since any ordered pair of distinct columns can be used as the indexing columns. However, these are all isotopic and are considered equivalent. For concreteness we shall always assume that the first two columns in their natural order are used as the indexing columns.Latin cubes
In the statistics literature, a Latin cube is an n × n × n three-dimensional matrix consisting of n layers, each having n rows and n columns such that the n distinct elements which appear are repeated n2 times and arranged so that in each layer parallel to each of the three pairs of opposite faces of the cube all the n distinct elements appear and each is repeated exactly n times in that layer.Note that with this definition a layer of a Latin cube need not be a Latin square. In fact, no row, column or file need be a permutation of the n symbols.
A Latin cube of order n is equivalent to a 2- orthogonal array.
Two Latin cubes of order n are orthogonal if, among the n3 pairs of elements chosen from corresponding cells of the two cubes, each distinct ordered pair of the elements occurs exactly n times.
A set of k − 3 mutually orthogonal Latin cubes of order n is equivalent to a 2- orthogonal array.
An example of a pair of mutually orthogonal Latin cubes of order three was given as the 2- orthogonal array in the Examples section above.
Unlike the case with Latin squares, in which there are no constraints, the indexing columns of the orthogonal array representation of a Latin cube must be selected so as to form a 3- orthogonal array.
Latin hypercubes
An m-dimensional Latin hypercube of order n of the rth class is an n × n ×... ×n m-dimensional matrix having nr distinct elements, each repeated nm − r times, and such that each element occurs exactly n m − r − 1 times in each of its m sets of n parallel -dimensional linear subspaces. Two such Latin hypercubes of the same order n and class r with the property that, when one is superimposed on the other, every element of the one occurs exactly nm − 2r times with every element of the other, are said to be orthogonal.A set of k − m mutually orthogonal m-dimensional Latin hypercubes of order n is equivalent to a 2- orthogonal array, where the indexing columns form an m- orthogonal array.
History
The concepts of Latin squares and mutually orthogonal Latin squares were generalized to Latin cubes and hypercubes, and orthogonal Latin cubes and hypercubes by. generalized these results to strength t. The present notion of orthogonal array as a generalization of these ideas, due to C. R. Rao, appears in.Other constructions
Hadamard matrices
If there exists a Hadamard matrix of order 4m, then there exists a 2- orthogonal array.Let H be a Hadamard matrix of order 4m in standardized form. Delete the first row and take the transpose to obtain the desired orthogonal array.
The order 8 standardized Hadamard matrix below,
| + | + | + | + | + | + | + | + |
| + | + | + | + | − | − | − | − |
| + | + | − | − | + | + | − | − |
| + | + | − | − | − | − | + | + |
| + | − | + | − | + | − | + | − |
| + | − | + | − | − | + | − | + |
| + | − | − | + | + | − | − | + |
| + | − | − | + | − | + | + | − |
produces the 2- orthogonal array:
| + | + | + | + | + | + | + |
| + | + | + | − | − | − | − |
| + | − | − | + | + | − | − |
| + | − | − | − | − | + | + |
| − | + | − | + | − | + | − |
| − | + | − | − | + | − | + |
| − | − | + | + | − | − | + |
| − | − | + | − | + | + | − |
Using columns 1, 2 and 4 as indexing columns, the remaining columns produce four mutually orthogonal Latin cubes of order 2.
Codes
Let C ⊆ n, be a linear code of dimension m with minimum distance d. Then C⊥ is a - orthogonal array whereλ = qn − m − d + 1.
Applications
Threshold schemes
consists of methods for distributing a secret amongst a group of participants, each of whom is allocated a share of the secret. The secret can be reconstructed only when a sufficient number of shares, of possibly different types, are combined together; individual shares are of no use on their own. A secret sharing scheme is perfect if every collection of participants that does not meet the criteria for obtaining the secret, has no additional knowledge of what the secret is than does an individual with no share.In one type of secret sharing scheme there is one dealer and n players. The dealer gives shares of a secret to the players, but only when specific conditions are fulfilled will the players be able to reconstruct the secret. The dealer accomplishes this by giving each player a share in such a way that any group of t or more players can together reconstruct the secret but no group of fewer than t players can. Such a system is called a -threshold scheme.
A t- orthogonal array may be used to construct a perfect -threshold scheme.
Factorial designs
A factorial experiment is a statistically structured experiment in which several factors are applied to each experimental unit at varying levels. In a full factorial experiment all combinations of levels of the factors need to be tested, but to minimize confounding influences the levels should be varied within any experimental run.An orthogonal array of strength 2 can be used to design a factorial experiment. The columns represent the various factors and the entries are the levels that the factors can be applied at. An experimental run is a row of the orthogonal array, that is, apply the corresponding factors at the levels which appear in the row. When using one of these designs, the treatment units and trial order should be randomized as much as the design allows. For example, one recommendation is that an appropriately sized orthogonal array be randomly selected from those available, then randomize the run order.
Quality control
Orthogonal arrays played a central role in the development of Taguchi methods by Genichi Taguchi, which took place during his visit to Indian Statistical Institute in the early 1950s. His methods were successfully applied and adopted by Japanese and Indian industries and subsequently were also embraced by US industry albeit with some reservations.Testing
Orthogonal array testing is a black box testing technique which is a systematic, statistical way of software testing. It is used when the number of inputs to the system is relatively small, but too large to allow for exhaustive testing of every possible input to the systems. It is particularly effective in finding errors associated with faulty logic within computer software systems. Orthogonal arrays can be applied in user interface testing, system testing, regression testing and performance testing.The permutations of factor levels comprising a single treatment are so chosen that their responses are uncorrelated and hence each treatment gives a unique piece of information. The net effect of organizing the experiment in such treatments is that the same piece of information is gathered in the minimum number of experiments.