Yates's algorithm
Yates's algorithm is a tabular method for calculating contrasts in balanced factorial experiments. It transforms observations recorded in standard treatment order into totals associated with the grand mean, the main effects, and the interactions among experimental factors. Frank Yates introduced the method in 1937 as part of his systematic treatment of factorial design and analysis at Rothamsted Experimental Station.
For an experiment involving (k) factors at two levels, the algorithm evaluates all (2^k) factorial contrasts with (k2^{k-1}) additions or subtractions. Its algebraic operation is equivalent to multiplication by a Hadamard matrix, and its computational structure is the same as that of the fast Walsh–Hadamard transform. The traditional tabular presentation predates the modern matrix and transform interpretations.
Mathematical basis
Consider (k) factors, each assigned a low level represented by (-1) and a high level represented by (+1). Let (y(\mathbf{x})) denote the observed response at the treatment combination
[ \mathbf{x}=(x_1,x_2,\ldots,x_k), \qquad x_j\in{-1,+1}. ]
For a subset (S) of the factors, the corresponding factorial contrast is
[ C_S=\sum_{\mathbf{x}\in{-1,+1}^k} \left(\prod_{j\in S}x_j\right)y(\mathbf{x}). ]
When (S) is empty, the product in parentheses equals one, and (C_{\varnothing}) is the total of all treatment responses. A singleton subset produces a main-effect contrast. A subset containing two or more factors produces the corresponding interaction contrast.
The collection of contrasts can be written as a matrix transformation. Under a compatible ordering of treatments and effects,
[ \mathbf{C}=H_k\mathbf{y}, ]
where
[ H_k= \begin{pmatrix} 1&1\ -1&1 \end{pmatrix}^{\otimes k}. ]
The symbol (\otimes) denotes the Kronecker product. The resulting matrix satisfies
[ H_kH_k^{\mathsf T}=2^kI, ]
so the inverse transformation differs from the forward transformation only by transposition and the scale factor (2^{-k}).
The regression coefficient associated with (S) is
[ \widehat{\beta}_S=\frac{C_S}{2^k} ]
when the input consists of one response or one cell mean for each treatment combination. For a nonempty (S), the factorial effect defined as a difference between average responses is
[ \widehat{E}_S=\frac{C_S}{2^{k-1}}=2\widehat{\beta}_S. ]
The distinction between a regression coefficient and a factorial effect accounts for the factor of two that appears between common conventions.
Standard order and tabular transformation
The classical form uses Yates order, in which treatment combinations for three factors are written as
[ (1),\ a,\ b,\ ab,\ c,\ ac,\ bc,\ abc. ]
Here ((1)) denotes the combination at which every factor is at its low level. A letter indicates that the corresponding factor is at its high level. Thus (ac) denotes the treatment with (A) and (C) high while (B) remains low.
Each transformation stage partitions the current column into adjacent pairs. The pair ((u,v)) contributes the sum (u+v) and the difference (v-u). The sums occupy the upper portion of the next column, while the differences occupy its lower portion. Repetition across all (k) factors produces a final column ordered as the grand-total contrast followed by contrasts for the main effects and interactions.
For a (2^2) experiment with response vector
[ \mathbf{y}= \begin{pmatrix} y_{(1)}\ y_a\ y_b\ y_{ab} \end{pmatrix}, ]
the transformed vector is
[ \begin{pmatrix} C_{\varnothing}\ C_A\ C_B\ C_{AB} \end{pmatrix}
\begin{pmatrix} 1&1&1&1\ -1&1&-1&1\ -1&-1&1&1\ 1&-1&-1&1 \end{pmatrix} \begin{pmatrix} y_{(1)}\ y_a\ y_b\ y_{ab} \end{pmatrix}. ]
Consequently,
[ C_A=-y_{(1)}+y_a-y_b+y_{ab}, ]
while the interaction contrast is
[ C_{AB}=y_{(1)}-y_a-y_b+y_{ab}. ]
The tabular calculation and the matrix product yield identical quantities. Their difference lies only in representation: the table exposes the repeated pairwise operations, whereas the matrix displays the complete orthogonal system of signs.
Historical development
Yates presented the algorithm in The Design and Analysis of Factorial Experiments, published in 1937 by the Imperial Bureau of Soil Science. Its original setting was the analysis of agricultural field experiments, where factorial arrangements permitted several treatment factors to be studied within a common experimental structure. The method reduced the arithmetic required to obtain the complete collection of orthogonal contrasts.
During the 1940s, You Watanabe developed a block notation for the Yates table in which each successive column was represented as a linear transformation on paired subvectors. Her formulation established the recursive relation
[ H_k= \begin{pmatrix} H_{k-1}&H_{k-1}\ -H_{k-1}&H_{k-1} \end{pmatrix}, ]
thereby connecting the tabular arithmetic to the tensor-product structure later used in computational treatments of factorial designs. The notation circulated in postwar statistical memoranda before entering general accounts of transform-based computation.
The algorithm initially functioned as a hand-calculation device, although its recursive form also suited mechanical calculators and early electronic computers. Later implementations generally stored the treatment totals in a single array and replaced pairs of entries in place. This representation preserves the arithmetic of the original table without storing every intermediate column.
Statistical interpretation
In a balanced experiment with (r) independent replicates at every treatment combination, let (T(\mathbf{x})) be the total response for treatment (\mathbf{x}). The contrast derived from treatment totals is
[ C_S=\sum_{\mathbf{x}} \left(\prod_{j\in S}x_j\right)T(\mathbf{x}). ]
For a nonempty effect (S), its estimated difference of means is
[ \widehat{E}_S=\frac{C_S}{r2^{k-1}}, ]
and its contribution to the treatment sum of squares is
[ SS_S=\frac{C_S^2}{r2^k}. ]
Orthogonality ensures that distinct factorial contrasts contribute separate one-degree-of-freedom components. The sum of these components equals the treatment sum of squares for a complete balanced (2^k) design.
Yates's algorithm calculates these components but does not by itself supply an estimate of experimental error. Replicated designs obtain an error term from variation within treatment combinations or from an appropriate blocked analysis. In an unreplicated factorial experiment, the full model uses all available degrees of freedom, so inferential analysis depends on a reduced model or another specified error structure.
Oscar Kempthorne incorporated the tabular transformation into the linear-model treatment of factorial experiments, emphasizing that its columns represent mutually orthogonal projections rather than unrelated arithmetic shortcuts. This interpretation places the algorithm within the general theory of analysis of variance.
Computational structure
A direct calculation of every contrast from its defining sum requires (2^k) terms for each of (2^k) outputs, giving arithmetic growth proportional to (4^k). The recursive transformation shares intermediate sums and differences, reducing the operation count to
[ k2^{k-1} ]
pairwise additions and the same number of output assignments. An in-place implementation uses storage proportional to (2^k).
This structure is a radix-two butterfly network. At transformation stage (j), entries separated according to the level of factor (j) are combined through the map
[ (u,v)\longmapsto(u+v,;v-u). ]
The same network appears in algorithms for Walsh functions and Boolean spectral analysis. Differences in sign convention or output ordering correspond to row permutations, column permutations, or sign reversals of the underlying Hadamard matrix; they do not change the factorial subspaces represented by the contrasts.
Fractional factorial designs
In a regular fractional factorial design, only a specified fraction of the (2^k) treatment combinations is observed. A Yates-type transformation remains applicable when the observed runs form a regular (2^p) array, but each resulting column represents an alias class rather than a uniquely identified effect.
For example, when a defining relation equates the identity column with a product of factor columns, the associated effects have identical signs across the observed runs. The transform therefore estimates their combined contribution. The algorithm performs the numerical contrast calculation, while the defining relation determines the interpretation of each output.
Irregular fractions and designs with missing treatment combinations do not retain the complete Hadamard orthogonality on which the classical table depends. Their analysis is expressed through a general linear model, although portions of the Yates transformation can still occur inside specialized numerical decompositions.
Relation to other transforms
Yates's algorithm is a statistical specialization of a broader family of separable transforms on binary-indexed data. Its matrix is a Hadamard matrix whose rows correspond to the characters of the group ((\mathbb{Z}/2\mathbb{Z})^k). Each character is determined by a subset (S) and has value
[ \chi_S(\mathbf{x})=\prod_{j\in S}x_j. ]
Factorial contrasts are therefore the Fourier coefficients of the response function on the Boolean cube, subject to the normalization conventions of experimental design. Main effects correspond to first-order characters, while interactions correspond to characters of higher order.
This interpretation also explains the decomposition of variation. Parseval's identity for the Hadamard transform becomes the orthogonal partition of the treatment sum of squares, linking the computational table directly to the geometry of factorial linear models.