Orthogonal Arrays: Theory and Applications


A. S. Hedayat, N. J. A. Sloane and John Stufken

This is the web site for our book, which was published by Springer-Verlag, New York in 1999

Extracts from reviews.
About the book.
Table of orthogonal arrays of strength 2 with up to 100 runs (in a separate file).
Tables of explicit examples of orthogonal arrays (in a separate file).
Tables of explicit examples of Hadamard matrices (in a separate file).
Updates and corrections to the book
Further references dealing with orthogonal arrays
How to order the book
Table of Contents of Book
The authors

Extracts from Reviews.

About the book (an extract from the Preface).

Who should read this book? Anyone who is running experiments,
whether in a chemistry lab or a manufacturing plant (trying to make
those alloys stronger), or in agricultural or medical research. Anyone
interested in one of the most fascinating areas of discrete mathematics,
connected to statistics and coding theory, with applications
to computer science and cryptography. This is the first book on the
subject since its introduction more than fifty years ago, and can be
used as a graduate text or as a reference work. It features all of the
key results, many very useful tables, and a large number of exercises
and research problems. Most of the arrays that can be obtained by
the methods in this book are available electronically.

Orthogonal arrays are beautiful and useful. They are essential in statistics and they are used in computer science and cryptography. In statistics they are primarily used in designing experiments, which simply means that they are immensely important in all areas of human investigation: for example in medicine, agriculture and manufacturing.

Your automobile lasts longer today because of orthogonal arrays ["The new mantra: MVT", Forbes, Mar. 11, 1996, pp. 114-118.]

The mathematical theory is extremely beautiful: orthogonal arrays are related to combinatorics, finite fields, geometry and error-correcting codes. The definition of an orthogonal array is simple and natural, and we know many elegant constructions - yet there are at least as many unsolved problems.

Here is an example of an orthogonal array of strength 2:

0 0 0 0 0 0 0 0 0 0 0
1 1 1 0 1 1 0 1 0 0 0
0 1 1 1 0 1 1 0 1 0 0
0 0 1 1 1 0 1 1 0 1 0
0 0 0 1 1 1 0 1 1 0 1
1 0 0 0 1 1 1 0 1 1 0
0 1 0 0 0 1 1 1 0 1 1
1 0 1 0 0 0 1 1 1 0 1
1 1 0 1 0 0 0 1 1 1 0
0 1 1 0 1 0 0 0 1 1 1
1 0 1 1 0 1 0 0 0 1 1
1 1 0 1 1 0 1 0 0 0 1

Pick any two columns, say the first and the last:

0 0
1 0
0 0
0 0
0 1
1 0
0 1
1 1
1 0
0 1
1 1
1 1

Each of the four possible rows we might see there,

0 0,       0 1,       1 0,       1 1,

does appear, and they all appear the same number of times (three times, in fact). That's the property that makes it an orthogonal array.

Only 0's and 1's appear in that array, but for use in statistics

0       or       1

in the first column might be replaced by

"butter"       or       "margarine" ,

and in the second column by

"sugar"       or       "no sugar" ,

and so on. Or

"slow cooling" or "fast cooling",
"catalyst" or "no catalyst",

etc., depending on the application.

Since only 0's and 1's appear, this is called a 2-level array. There are 11 columns, which means we can vary the levels of up to 11 different variables, and 12 rows, which means we are going to bake 12 different cakes, or produce 12 different samples of the alloy. In short, we call this array an OA(12,11,2,2) The first "2" indicates the number of levels, and the second "2" the strength, which is the number of columns where we are guaranteed to see all the possibilities an equal number of times. In an orthogonal array of strength 3 (with two levels), in any three columns we would see each of the eight possibilities

000, 001, 010, 011, 100, 101, 110, 111

equally often. (The formal definition is given in the first chapter.)

As already mentioned, the main applications of orthogonal arrays are in planning experiments. The rows of the array represent the experiments or tests to be performed - cakes to be baked, samples of alloy to be produced, integrated circuits to be etched, test plots of crops to be grown, and so on.

The columns of the orthogonal array correspond to the different variables whose effects are being analyzed. The entries in the array specify the levels at which the variables are to be applied. If a row of the orthogonal array reads

110100 ...

this could mean that in that test the first, second, fourth variables (where the 1's occur) are to be set at their "high" levels, and the third, fifth, sixth variables (where the 0's occur) at their "low" levels.

By basing the experiment on an orthogonal array of strength t we ensure that all possible combinations of up to t of the variables occur together equally often.

The aim here is to investigate not only the effects of the individual variables (or factors) on the outcome, but also how the variables interact. Obviously, even with a moderate number of factors and a small number of levels for each factor, the number of possible level combinations for the factors increases rapidly. It may therefore not be feasible to make even one observation at each of the level combinations. In such cases observations are made at only some of the level combinations, and the purpose of the orthogonal array is to specify which level combinations are to be used. Such experiments are called "fractional factorial" experiments. While there are nowadays other applications of orthogonal arrays in statistics (for example in computer experiments and survey sampling), the principal application is in the selection of level combinations for fractional factorial experiments.

Since the rows of an orthogonal array represent runs (or tests or samples) - which require money, time, and other resources - there are always practical constraints on the number of rows that can be used in an experiment. Finding the smallest possible number of rows is a problem of eminent importance. On the other hand, for a given number of runs we may want to know the largest number of columns that can be used in an orthogonal array, since this will tell us how many variables can be studied. We also want the strength to be large, though in many real-life applications this is set at 2, 3 or 4.

Then the main questions we ask are:

How to order the book:

Please contact Springer-Verlag directly. The ISBN number is 0-387-98766-5, and the publication date was June 1999.

The Authors:

Professor A.S. Hedayat
Department of Mathematics, Statistics and Computer Science
University of Illinois at Chicago
851 South Morgan Street
Chicago, IL 60607-7045 USA
Home page
Email: hedayat(AT)uic.edu

Dr. N.J.A. Sloane
Information Sciences Research Center
AT&T Shannon Labs
180 Park Avenue
Florham Park, NJ 07932-0971 USA
Home page
Email: njasloane@gmail.com

Professor John Stufken
Department of Statistics
Snedecor Hall
Iowa State University
Ames, IA 50011 USA
Current address:
Professor and Head of Statistics,
University of Georgia,
204A Statistics Buikding,
Athens GA, USA
Home page
Email: jstufken(AT)uga.edu

Updates and Corrections:

Selected new references dealing with orthogonal arrays (or earlier references that were omitted)

  1. J. Bierbrauer (2002). Direct construction of additive codes. J. Combin. Designs 10, 207-216.
  2. Brouwer, Andrie E., Cohen, Arjeh M. and Nguyen, V. M. (2006). Orthogonal arrays of strength 3 and small run sizes. Journal of Statistical Planning and Inference 136, pp. 3268-3280
  3. Chai, Feng Shun, Mukerjee, Rahul and Suen, Chung-yi, Further results on orthogonal arrays plus one run plans. J. Statist. Plann. Inference, 106 (2002), 287-301.
  4. Chateauneuf, M. and Kreher, D.L. (2002). On the state of strength-three covering arrays. J. Combin. Designs 10, 217-238.
  5. D. De Cock and J. Stufken (2000). On Finding Mixed Orthogonal Arrays of Strength 2 With Many 2-Level Factors. Statistics and Probability Letters, 50, 383-388.
  6. A. Dey and R. Mukerjee (1998). Techniques for constructing asymmetric orthogonal arrays. J. Combin. Inform. System Sc. 23, 351-366.
  7. Wiebke S. Diestelkamp, The decomposability of simple orthogonal arrays on 3 symbols having t+1 rows and strength t, Journal of Combinatorial Designs, Vol. 8 (2000), 442-458. [Author's home page].

  8. Wiebke S. Diestelkamp, Parameter inequalities for orthogonal arrays with mixed levels. Designs, Codes and Cryptography, Vol. 33 (2004), 187-197. [Author's home page].

  9. Wiebke S. Diestelkamp and Jay H. Beder, On the decomposition of orthogonal arrays, Utilitas Mathematica, Vol. 61 (2002), 65-86. [Diestelkamp's home page].

  10. Y. Edel (1996), Eine Verallgemeinerung von BCH-Codes (Dissertation).

  11. Longcheen Huwang, C. F. J. Wu, and C. H. Chen (2002). The idle column method: design construction, properties and comparisons. Technometrics, 44, 347-355.

  12. S. Kageyama and K. Urata, (2000). Bounds on orthogonal arrays, Bulletin Fac. Educ. Hiroshima Univ. , Part II, 49, 25-32.

  13. Kamali, F., Kharaghani, H., and Khosrovshahi, G.B. (2003). Some Bush-type Hadamard matrices. J. Statistical Planning and Inference, Vol. 113, pp. 375-384.
  14. A. V. Khalyavin, Estimates of the capacity of orthogonal arrays of large strength, Moscow University Mathematics Bulletin, Volume 65, 2010, Number 3, 130-131.
  15. V. C. Mavron: A Construction Method for Complete Sets of Mutually Orthogonal Frequency Squares, Electronic J. Combin., #N5, 2000.

  16. Klaus Metsch, Improvement of Bruck's completion theorem. Des. Codes Cryptogr. 1 (1991), no. 2, 99--116.

  17. Mishima, Miwako, Jimbo, Masakazu, Shirakura, Teruhiro (2000). On the optimality of orthogonal arrays in case of correlated errors. J. Statist. Plann. Inference 88, 319-338.

  18. Max D. Morris, Leslie M. Moore and Michael D. McKay. Using Orthogoanl Arrays in the Sensitivity Analysis of Computer Models, Technomtrics, Vo. 50, No. 2, 2008, pp. 205-215.
  19. E. M. Rains, N. J. A. Sloane and J. Stufken, The Lattice of N-Run Orthogonal Arrays, J. Statist. Plann. Inference, 102 (2002), 477-500 [Abstract, ps, pdf].

  20. Eric D. Schoen, Pieter T. Eendebak, Man V.M. Nguyen (2009). Complete Enumeration of Pure-level and Mixed-level Orthogonal Arrays. Journal of Combinatorial Designs, to appear.
  21. K. Sinha, V. Dhar, G. M. Saha and S. Kageyama (2002). Balanced arrays of strength two from block designs. J. Combinatorial Designs, 10, 303-312.
  22. Street, Deborah J. (1998). Orthogonal arrays as designed experiments. Bull. Inst. Combin. Appl. 24, 81--101.

  23. Suen, Chung-yi (2005). Orthogonal arrays of strength three and size 2^r. Statist. Sinica 15, 731-749

  24. Suen, C.-Y, Das, A., and Dey, A. (2001). On the construction of asymmetric orthogonal arrys. Statist. Sinica, 11, 241-260.

  25. Suen, C.-Y. and Dey, A. (2003). Construction of asymmetric orthogonal arrays through finite geometries. J. Statist. Plann. Inference, 115, 623-635.

  26. Suen, Chung-yi, Das, Ashish, and Dey, Aloke (2001). On the construction of asymmetrical orthogonal arrays. Statistica Sinica 11, 241-260.
  27. Yu. Tarannikov, P. Korolev, A. Botev. Autocorrelation coefficients and correlation immunity of Boolean functions, Proceedings of Asiacrypt 2001, Gold Coast, Australia, December 9--13, 2001, Lecture Notes in Computer Science, V. 2248, pp. 460--479, Springer-Verlag, 2001. [Bound on OA's of large strength.]

  28. V. D. Tonchev (2003), Affine designs and linear orthogonal arrays, preprint.

  29. H. Xu (2002), An Algorithm for Constructing Orthogonal and Nearly-Orthogonal Arrays with Mixed Levels and Small Runs, Technometrics, 44, 356-368.

  30. S. Yamammoto, Y. Hyodo, M. Mitsuoka, H. Yumiba and T. Takahashi (1998). Algorithm for the construction and classification of orthogonal arrays and its feasibility. J. Combin. Inform. System Sc. 23, 71-84.

  31. Y. Zhang (2007), Orthogonal arrays obtained by repeating-column difference matrices, Discrete Math., 307, 246-261.

  32. J.-Z. Zhang, Z.-S. You and Z.-L. Li (2000), Enumeration of binary orthogonal arrays of strength 1, Discrete Math., 239 191-198.

  33. Y. Zhang, L. Duan, Y. Lu and Z. Zheng (2002), Construction of generalized Hadamard matrices D(r^m(r+1), r^m(r+1); p), Journal of Statistical Planning and Inference, 104, 239-258

  34. Y. Zhang, S. Pang and Y. Wang, (2001), Orthogonal Arrays Obtained by Generalized Hadamard Product, Discrete Math., 238 151-170. Note however that there are errors in the 72-run OAs as printed in the journal. See the web page Library of orthogonal arrays for corrected versions of these OAs.

Table of Contents of Book:

Preface         vii

Foreword by C. R. Rao         xv

List of symbols         xxiii

1 Introduction         1

2 Rao's Inequalities and Improvements         11

3 Orthogonal Arrays and Galois Fields         37

4 Orthogonal Arrays and Error-Correcting Codes         61

5 Construction of Orthogonal Arrays from Codes         87

6 Orthogonal Arrays and Difference Schemes         113

7 Orthogonal Arrays and Hadamard Matrices         145

8 Orthogonal Arrays and Latin Squares         167

9 Mixed Orthogonal Arrays         199

10 Further Constructions and Related Structures         223

11 Statistical Application of Orthogonal Arrays         247

12 Tables of Orthogonal Arrays         317

Appendix: Galois Fields         341

Bibliography         363

Up [ Return to top of page ]