E    
  D  
    T

Encyclopaedia of DesignTheory: Glossary

The label "Topics" or "Encyc" against a glossary entry is a link to either a topic essay or an encyclopaedia entry for this subject; the label "Example" points you to an example, and "External" to a page on the Web with more information. (Of course we are not responsible for the availability or content of external web pages.)

WARNING This Warning sign is used for terms where there are conflicting meanings in the literature, or other problems of terminology. This is not infrequent in design theory, partly because the combinatorial and statistical aspects of the subject have developed with relatively little interaction.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z


A
Abelian group (Topics)
A group satisfying the commutative law ab = ba.

absolute point of a polarity
An absolute point of a polarity is a point which is incident with its image.

additive group of field or vector space
The group consisting of the elements of the field or vector space, with the operation of addition.

adjacency matrix of graph
The usual adjacency matrix of a simple graph has rows and columns indexed by the vertices of the graph, with (v,w) entry equal to 1 if the vertices v and w are adjacent in the graph and 0 otherwise.

Many variations are possible. For example, in a multigraph we can take the (v,w) entry to be the number of edges incident with v and w. In a digraph we can take it to be the number of edges with initial vertex v and terminal vertex w.

affine
A resolvable design is affine (or affine resolvable) if the number of points common to two blocks in different classes of the resolution is constant. The points and hyperplanes of an affine space form an example.

affine plane (Topics)
A 2-(n2,n,1) design (necessarily affine). The points and lines of an affine space of dimension 2 form an example. An affine plane is a special kind of net.

affine resolvable
A synonym for "affine".

affine space
An affine space of dimension n over a field F is constructed from the vector space of dimension n over F as follows: the objects are all the cosets of the subspaces of the vector space, two objects being incident if one contains the other. Cosets of subspaces with dimension 0, 1, n-1 (as vector spaces) are called points, lines, and hyperplanes respectively.

algebra
An algebra is a structure A which is a vector space over a field F, which also has an operation of multiplication, with some obvious rules connecting the scalar multiplication with the algebra multiplication.

If the ring multiplication satisfies the associative law, we have an associative algebra. Similarly, if the commutative law holds, we have a commutative algebra. The prototypical example of an associative algebra is the set of all n×n matrices over the field F. Other kinds of algebra such as Lie algebras and Jordan algebras can be defined by different laws.

alphabet
The alphabet of a code or an orthogonal array is the set of symbols used in the codewords or the array entries.

Sometimes we allow the use of different symbols in different coordinate positions, in which case there is an alphabet associated with each coordinate.

alternating bilinear form
A bilinear form B is alternating if B(x,x)=0 for all vectors x.

alternating group
The alternating group An is the group consisting of all even permutations of the set {1,...,n} (those which are the product of an even number of transpositions). The group operation is composition of permutations. The order of An is n!/2 . The alternating group is simple for n>4.

anallagmatic pavement
This is Sylvester's term for a Hadamard matrix.

ancestral set
An ancestral set in a partially ordered set is a set A with the property that, if a is in A and b > a, then b is in A.

antichain
An antichain in a partially ordered set is a set of pairwise incomparable elements.

association scheme (Example, Topics, External1, External2)
A set of symmetric zero-one matrices, containing the identity, having sum equal to the all-one matrix, and having the property that the product of any two matrices is a linear combination of the matrices in the set. It can also be regarded as a partition of X² such that the matrices describing the sets in the partition have the above properties. In other words, it is a symmetric coherent configuration.

WARNING Some authors use the term "association scheme" for any coherent configuration. Others use the term for a homogeneous configuration, that is, one for which the identity is one of the matrices. Yet others don't require the matrices to be symmetric but do require that they commute. In view of this confusion, we strongly advocate using the term association scheme in the sense defined here, and using the terms commutative coherent configuration, homogeneous coherent configuration, and coherent configuration for the more general concepts.
If a permutation group is stratifiable, then its symmetrised basis matrices form an association scheme. If it is generously transitive, then the basis matrices form an association scheme.

associative law
The law a(bc) = (ab)c. In additive notation, this is written as a+(b+c) = (a+b)+c.

atomic Latin square
A Latin square is atomic if every conjugate of it is row-Hamiltonian. The Cayley table of a cyclic group of prime order is an example.

automorphism
An automorphism of a mathematical object is a one-to-one mapping from the object to itself which preserves all the relevant structure.

Sometimes, different choices of what the "relevant structure" is lead to different concepts of automorphism (which may be distinguished as strong automorphism, weak automorphism, etc.) For example, given a resolved design, we could define a weak automorphism to preserve the design and the resolution, while a strong automorphism fixes every parallel class in the resolution.

autoparatopy
An autoparatopy of a Latin square is a paratopy from the square to itself.

autotopy
An autotopy of a Latin square is an isotopy from the square to itself.

Top

B

balance for designs
WARNING Another of those words used differently in combinatorics and statistics. See D. A. Preece, Balance and designs: Another terminological tangle, Utilitas Math. 21C (1982), 85-186.

In combinatorics, pairwise balance means that two points are contained in a constant number of blocks. This obviously generalises to t-wise balance.

In statistics, there are various different kinds of balance (variance balance, efficiency balance, etc.), none of which are equivalent to the combinatorialist's pairwise balance, but become equivalent to it if some extra conditions are satisfied (e.g. in binary equireplicate uniform block designs, aka 1-designs). To add to the complication, the combinatorialist's 3-design is called "doubly balanced"(!)

"Balance" also arises in other types of designs such as weighing matrices.

basis
A basis (for example, in a vector space) is a set of elements with the property that any element of the space can be written uniquely as a linear combination of elements of the basis.

A basis of a matroid is a maximal independent set.

basis matrices for a permutation group
Let G be a permutation group on the set {1,...,n}. Then G has a natural action on the set of ordered pairs (i,j), for i,j in {1,...,n}. Each orbit in this action can be represented by a n × n matrix with (i,j) entry 1 if the pair lies in the orbit, 0 otherwise. These are the basis matrices of the permutation group.

BIBD
Short for "balanced incomplete-block design", a binary block design with v treatments, block size k<v, and any two treatments occurring together in lambda blocks. Otherwise known as a 2-design (with k<v).

bilinear form
A bilinear form on a vector space is a function of two variables which is linear in each variable if the other is kept constant.

A bilinar form B can be represented by a matrix A:

B(x,y) = xAyT.

binary
This term has several meanings, associated with the number 2 or the set {0,1} in some way. (To a logician, the number 2 and the set {0,1} are the same thing!)
  1. In statistical design theory, a block design is binary if no treatment occurs more than once in a block (that is, a part of the treatment partition and a part of the block partition meet in at most one plot). If this holds, then a block can be thought of as a set (rather than a multiset) of treatments, and the block design can be represented as an incidence structure.
  2. In coding theory, a code is binary if the alphabet of the code is the set {0,1} (or the Galois field GF(2) of integers modulo 2.)
  3. A relation or operation is binary if it has two arguments. (So composition in a group is a binary operation, and adjacency in a graph is a binary relation.)

bipartite graph
A graph is bipartite if the vertices are partitioned into two subsets (the bipartite blocks) so that any edge joins vertices in different parts. Thus, a synonym for 2-partite graph.

block
In experimental design, a block is a subset of the set of plots or experimental units such that, typically, the units of the block are more alike than they are like units outside.

In incidence structures, "point" and "block" are the usual terms for the two types of element. Often a block is identified with a subset of the set of points, namely, those points incident with it. If the same set of points arises from more than one block, we say that the structure has repeated blocks.

block design (Topics)
In statistics, a block design is a set (of "plots") carrying two partitions, a partition into "treatments" and a partition into "blocks". If it is binary, it can be represented as an incidence structure; if it also has no repeated blocks, it can be represented as a hypergraph.

WARNING Be warned that some combinatorialists use the term as a synonym for "2-design" (see t-design).

block-transitive
See transitive.

blocking set
A blocking set, in a hypergraph or family of sets, is one of two things: either a set which intersects every edge of the hypergraph (every set in the family); or else a set which intersects every edge of the hypergraph and contains no edge. Blocking sets in the second sense may or may not exist.

Bose-Mesner algebra
The Bose-Mesner algebra of an association scheme is the span (over the real numbers) of the matrices of the scheme. It follows from the definition of an association scheme that this set is closed under multiplication, and is a commutative and associative algebra.

building
A special type of chamber system. Most buildings are associated with algebraic groups. Projective spaces are examples of buildings.

Top

C

cartesian product
The cartesian product A × B of two sets A and B is the set of all ordered pairs (a,b), for a in A and b in B. This is extended in the obvious way to more than two sets.

If the sets A and B carry some structure, for example if they are groups or graphs, then we would expect that their cartesian product would carry the same kind of structure, defined coordinatewise. Indeed, the direct product of groups, or the direct sum of abelian groups or vector spaces, is defined in exactly this way. However, for various reasons, the coordinatewise product of graphs is called the categorical product; the cartesian product of graphs is defined differently.

Other graph products include the lexicographic product and the strong product.

cartesian product of graphs
The cartesian product of graphs A and B is defined as follows. The vertex set is the cartesian product of the sets A and B. Two vertices (a,b) and (a',b') are adjacent if and only if either

categorical product of graphs
The categorical product of graphs A and B is defined as follows. The vertex set is the cartesian product of the sets A and B. Two vertices (a,b) and (a',b') are adjacent if and only if a is adjacent to a' and b is adjacent to b'.

Cayley graph (Topics)
The Cayley graph of a group G with respect to a subset S (which should be closed under taking inverses and not contain the identity) is the graph with vertex set G and an edge joining g to sg for all g in G and s in S. It is vertex-transitive; indeed, it admits the group G acting by right multiplication. (This is the action in Cayley's Theorem: hence the name.)

Not every vertex-transitive graph is a Cayley graph; the Petersen graph is an exception.

Cayley table
Given a set of n elements x1, ..., xn, with a binary operation ("composition", "multiplication", etc.), we can represent the operation by a Cayley table. This is an n x n array with (i,j) entry xi o xj, where o denotes the binary operation. Sometimes we take the entry to be the index k for which xi o xj = xk.

For some structures (groups, or more generally loops or quasigroups), the Cayley table is a Latin square.

Cayley's Theorem
Cayley's Theorem states that every group is isomorphic to a permutation group. The permutations are the rows of the Cayley table of the group.

chain
A chain in a partially ordered set is a subset which is totally ordered (that is, any pair of elements is comparable).

chamber system (Topics)
A chamber system is a set carrying a collection of partitions. The standard method of constructing a chamber system from an incidence geometry works as follows. Let {1,2,...,r} be the types. Then the chambers are the maximal flags containing one variety of each type; two chambers are i-adjacent (that is, equivalent in the ith relation) if they have the same varieties of all types except possibly i.

character table (Example)
A character of an Abelian group A is a homomorphism from A to the multiplicative complex numbers, that is, a function X satisfying X(gh)=X(g)X(h). There are equally many characters as group elements. The characters themselves form a group under the operation of multiplication, which is isomorphic to the original group A. The character table is a square table giving the values of the characters on the group elements.

For an arbitrary group, a representation is a homomorphism to the group of n×n complex matrices, and the corresponding character is the function which takes any element to the trace of the representing matrix. A character is called irreducible if the representing matrices have no proper invariant subspace. A character is constant on the conjugacy classes of the group, and the numbers of irreducible characters and conjugacy classes are equal; the character table is the square table which gives the values of characters on conjugacy classes.

circulant graph
A graph is circulant if its vertices can be labelled with the integers 1,...,v-1 (mod v) in such a way that the cyclic shift x->x+1 (mod v) is an automorphism. A circulant graph is a Cayley graph for the cyclic group.

WARNING A circulant graph is a graph which is also a cyclic design. The cyclic graph is a circulant graph, but not every circulant graph is cyclic!

circuit
A circuit in a matroid is a minimal dependent set.

class-uniform resolvable design
A resolvable design in which the multiset of block sizes in each parallel class of the resolution is the same.

classical group
This term refers to a special linear, symplectic, orthogonal, or unitary group, or to the "projective" version of one of these (the factor group by the group of scalar matrices.)

Classification of the Finite Simple Groups
The finite simple groups have all been classified. The theorem (referred to as CFSG for short) asserts that a finite simple group is of one of the following types:

code (Example)
A code of length n is a set of codewords, each codeword being an n-tuple of symbols taken from some fixed set A called the alphabet of the code.

coherent configuration
A set of zero-one matrices having sum equal to the all-one matrix, having the identity matrix as the sum of a subset of its elements, closed under transposition, and having the property that the product of any two matrices is a linear combination of the matrices in the set. It can also be regarded as a partition of X² such that the matrices describing the sets in the partition have the above properties.

An association scheme is a symmetric coherent configuration.

The basis matrices of a permutation group form a coherent configuration. Such a configuration is called Schurian.

WARNING Some authors use the term "association scheme" for any coherent configuration. Others use the term for a homogeneous configuration, that is, one for which the identity is one of the matrices. Yet others don't require the matrices to be symmetric but do require that they commute. In view of this confusion, we strongly advocate using the term association scheme for a coherent configuration all of whose matrices are symmetric, and using the terms commutative coherent configuration, homogeneous coherent configuration, and coherent configuration for the more general concepts.

column-complete Latin square
A Latin square is column-complete if each ordered pair of distinct symbols occurs precisely once in consecutive positions in a column of the square.

column-quasi-complete Latin square
A Latin square is column-quasi-complete if each unordered pair of distinct symbols occurs precisely twice in consecutive positions in a column of the square.

commutative law
The law ab = ba. In additive notation, this is written as a+b = b+a.

complement of a graph
The complement of a simple graph G is the graph G' with the same vertex set as G, in which two vertices are joined if and only if they are not joined in G.

complete bipartite graph
A bipartite graph in which any two vertices in different bipartite blocks are joined by an edge. Thus, a special case of a complete multipartite graph.

complete-block design
A block design in which every treatment occurs in every block.

complete graph
The simple graph in which every pair of vertices is joined by an edge. The complete graph on n vertices is denoted by Kn.

complete Latin square (Example)
A Latin square is complete if it is both row-complete and column-complete.

complete multipartite graph
A multipartite graph in which every pair of vertices lying in different multipartite blocks is joined by an edge.

completely symmetric matrix
A square matrix is completely symmetric if all its diagonal entries are equal and all its off-diagonal entries are equal; in other words, if it has the form aI+bJ, where I and J are the identity and the all-1 matrices.

composition of functions permutations
The composition of two mappings (functions or permutations) is the mapping obtained by applying the first and then the second of the given mappings.

concurrence matrix
The concurrence matrix of a block design is the matrix NN', where N is the incidence matrix. In the case of a binary design, its (i,j) entry is the number of blocks containing the points i and j.

connected
A graph is connected if there is a path joining any two of its vertices.

A block design is connected if its incidence graph is.

conjugacy class
Two elements g and h of a group G are conjugate if h=x-1gx for some element x of G. Conjugacy is an equivalence relation whose equivalence classes are called conjugacy classes.

conjugate of a Latin square
A conjugate of a Latin square is a Latin square obtained by permuting the roles of "rows", "columns", and "symbols". For example, if L is a Latin square, then there is a conjugate whose (i,j) entry is k if and only if the k,j entry of L is i.

coset
A left coset of a subgroup H of a group G is a set of the form gH for some element g of G; a right coset is of the form Hg.

If the group happens to be Abelian, or if H is a normal subgroup of G, then the left and right cosets coincide and we simply speak of "cosets". In any case, the numbers of left and right cosets are equal; this number is the index of H in G.

Distinct left cosets are disjoint, and each has the same cardinality as the subgroup H; so they form a partition of the group. The same applies to right cosets. This is the basis of Lagrange's Theorem.

covering design (External)
A (v,k,t)-covering design is a collection of k-element subsets, called blocks, of {1,2,...,v}, such that any t-element subset is contained in at least one block.

See also tight single-change covering design.

covering radius
The covering radius of a code C is the smallest integer r such that every n-tuple over the alphabet of C lies at Hamming distance r or less from some codeword of C.

critical set
A critical set in a Latin square is a set of entries in a square grid which can be embedded in precisely one Latin square, with the property that if any entry of the critical set is deleted, the remaining set can be embedded in more than one Latin square.

If the second condition is deleted, the set is a uniquely completable set.

crossing
Let A and B be sets carrying collections of binary relations. The structure obtained by crossing A and B has the cartesian product A × B as its point set; for each relation R on A, and each relation S on B, there is a relation (R,S) which holds between pairs (a,b) and (a',b') precisely when a and a' are in the relation R and b and b' are in relation S.

The analogous concept for permutation groups is the direct product.

cubic lattice design
See lattice design.

cyclic design
A design is cyclic if we can label its points with 0,...,v-1 (the integers mod v) in such a way that the cyclic shift x->x+1 (mod v) is an automorphism. Equivalently, a design is cyclic if it has an automorphism permuting the points in a single cycle. Compare 1-rotational design.

cyclic graph
The graph whose vertices are the integers mod v, two vertices being adjacent if their difference is 1 (mod v). It is distance-regular.

cyclic group
A group which is generated by a single element - thus, it consists of all powers of this element (if it is written multiplicatively), or all multiples (if written additively). Any cyclic group is Abelian.

cyclic scheme
The association scheme derived from the distance-regular cyclic graph.

Top

D

degree of a (hyper)graph
A synonym for valency.

Desargues' Theorem
A configuration theorem for projective planes, which holds in a plane if and only if it can be coordinatised by a field (possibly with non-commutative multiplication).

diameter of a connected graph
The maximum distance between two vertices of the graph.

difference set
Let G be a group, with the operation + (so that -x is the inverse of x). A difference set in G is a subset D of G with the property that each non-identity element g of G can be written in precisely lambda different ways in the form x-y for x,y in D, where x-y is short for x+(-y), and lambda is some constant.

If D is a difference set in G with |G|=v and |D|=k, then the translates of D (the sets D+x, for x in G) are the blocks of a square 2-(v,k,lambda) design.

digraph
Short for directed graph.

dihedral group
A dihedral group is a group of order 2n generated by two elements a and b satisfying the relations an=b2=(ab)2=1. The group of symmetries of a regular n-gon is a dihedral group of order 2n.

WARNING Some people write this group as D2n, others as Dn.

dimension
The dimension of a vector space is the number of vectors in a basis of the space.

direct sum or direct product
An algebraic object built from two (or more) objects: its element set is the cartesian product of the element sets of the factors, and operations are defined componentwise. We usually use direct sum for additive structures such as Abelian groups, and direct product for multiplicative structures. The direct product of G and H is denoted by G×H.

If Gi is a permutation group acting on a set Xi for i=1,2, there are two natural actions of the direct product G1×G2:

directed graph
A variant of a graph in which an edge is an ordered pair of vertices. Thus, each edge has an initial vertex and a terminal vertex (which may be equal, if the edge is a loop).

directed terrace in a group (Example)
A directed terrace in a finite group G of order n is an ordering (h1,h2,,...,hn) of the elements of G such that the elements hi-1hi+1, for i=1,...,n-1, are all distinct and different from the identity. Directed terraces arise from sequencings, and are used to construct complete Latin squares.

distance in a graph
The distance between two vertices of a connected graph is the smallest number of edges in a path joining the two vertices.

distance-regular graph
A connected simple graph of diameter d is distance-regular if, when we define two vertices to be ith associates if their distance is i, for i=0,...,d, we obtain an association scheme.

A distance-regular graph of diameter 2 is strongly regular, and any connected strongly regular graph is distance-regular with diameter 2.

distance-transitive graph
A connected simple graph is distance-transitive if, whenever two pairs of vertices have the same distance, there is an automorphism of the graph which carries the first pair to the second.

Any distance-transitive graph is distance-regular.

distributive lattice
A distributive lattice is a lattice (in the first meaning) which satisfies the distributive laws, where addition and multiplication are interpreted as join and meet (or vice versa).

Any distributive lattice can be represented as the lattice of all ancestral subsets of some partially ordered set, where the order is set-theoretic inclusion and the operations of meet and join are union and intersection.

distributive laws
In a structure with addition and multiplication, such as a ring or an algebra, the two distributive laws relate the operations as follows: a(b+c)=ab+ac (left distributive law) and (b+c)a=ba+ca (right distributive law).

If the multiplication satisfies the commutative law, then the two distributive laws are equivalent.

dual of an incidence structure
An incidence structure consists of a set of points and a set of blocks, with a relation of incidence between points and blocks. To form the dual, we re-label the points as blocks and the blocks as points, and reverse the direction of the incidence relation.

duality of an incidence structure
A duality is an isomorphism from an incidence structure to its dual.

dual code of a linear code
The set of all vectors orthogonal to all codewords in the code (with respect to the standard inner product).

dual group of an Abelian group
The group of characters of the given Abelian group, with the operation of multiplication. It is isomorphic to the original group.

Top

E

edge-colouring of a graph
A proper edge-colouring of a graph is an assignment of colours to the edges of the graph so that two edges meeting at a vertex are assigned different colours. A 1-factorisation is a special kind of edge-colouring.

edge-transitive
See transitive.

efficiency balance
A block design is efficiency balanced if the matrix R-1/2LR-1/2, where L is the information matrix of the design and R the diagonal matrix whose diagonal entries are the replication numbers, has the property that it has eigenvalue 0 with multiplicity 1 and all its other eigenvalues are equal.

elliptic quadric
See quadric.

equidistant code
A code with the property that the Hamming distance between any two codewords is constant.

The rows of a Hadamard matrix form an equidistant code, since any two agree in exactly half of their entries and disagree in the remainder.

equidistant permutation array
A set of permutations of the set {1,...,n} with the property that the Hamming distance between any two is constant. (We regard a permutation in passive form, as a word over the alphabet {1,...,n}.)

equireplicate block design
A block design is called equireplicate if each treatment occurs in the same number of plots. In other words, if we sum the number of occurrences of a given treatment in each block, the result is independent of the treatment chosen.

If the block design is binary, then this condition is equivalent to regularity of the corresponding hypergraph; in other words, each point is in a constant number of blocks.

equivalence class
The equivalence class [x] of an equivalence relation R is the set of all y such that R(x,y) holds.

equivalence relation
An equivalence relation is a binary relation which is Equivalence relations correspond precisely to partitions of the underlying set; the equivalence classes of an equivalence relation form a partition of the set, and any partition is the set of equivalence classes of a unique equivalence relation.

estimation (Topics)
An experimenter measures the response of each of a set of plots assigned various treatments. A statistical model assumes a certain form for this response, depending on the treatment and nuisance factors. The purpose of the experiment is to estimate the parameters associated with the treatment factors. It is important that estimators should be functions of the data only!

Euclid's parallel postulate
In an incidence structure of points and lines, Euclid's parallel postulate is the assertion that, given a line l and a point p not incident with it, there is a unique line l' which is incident with p and disjoint from l.

If this holds, then the relation on lines of being equal or disjoint is an equivalence relation called parallelism, and each parallel class of lines covers the point set exactly (that is, each point is incident with just one line of each parallel class).

So an incidence structure satisfying Euclid's parallel postulate is resolvable.

Top

F

factorial design
A factorial design is one where the treatment set consists of combinations of a number of factors, each of which can take several different levels. (In an experiment on plants, the factors may be planting time, fertiliser, watering regime, etc.)

Because the total number of treatment combinations (the product of the numbers of levels of the factors) may be very large, we may only be able to test some of these combinations, giving a fractional factorial design. A suitable fraction may be an orthogonal array, or a subgroup of the direct product of abelian groups of orders equal to the number of levels of each factor.

field
A field is a structure in which the arithmetic operations (addition, subtraction, multiplication, and division except by zero) are defined and satisfy the usual laws (commutative, associative, distributive, etc.)

filter
The term "filter" is sometimes used in the same sense as "ancestral set", that is, a subset F of a partially ordered set such that, if a is in F and b > a, then b is in F. However, the term has a more specialised meaning in set theory: a filter in a lattice is an ancestral set which contains the meet of any two of its elements. Because of this ambiguity, we have preferred the term "ancestral set".

A filter (in the strong sense) in a finite lattice must be "principal", that is, the set of all elements b satisfying b >= a for some fixed element a.

finite field
See Galois field.

Fisher's inequality
Fisher's inequality asserts that a non-trivial 2-design (or BIBD) has at least as many blocks as points. A design meeting the bound is called square (or sometimes "symmetric").

flag
A flag in an incidence geometry is a set of mutually incident objects or varieties. In an incidence structure with just two types (points and blocks), a flag is usually an incident point-block pair.

flag-transitive
See transitive.

flat
A flat in a matroid is a maximal subset of given rank. The flat spanned by a subset S consists of all points whose addition to S does not increase the rank.

Frobenius automorphism
In the Galois field of order pn, the Frobenius automorphism is the function which maps each element to its pth power. It generates the automorphism group of the field (which is thus a cyclic group).

Top

G

Galois field (Example, Topics)
Galois showed that the number of elements in any finite field must be a power of a prime number; and moreover, for every number which is a prime power, there is a finite field of that order, and it is unique up to isomorphism. These fields are called Galois fields in his honour, and the Galois field with q elements is denoted by GF(q).

The Galois field of prime order p consists of the integers modulo p.

general linear group
The group of all non-singular linear transformations of a vector space.

generalized inverse
The generalized inverse, or Moore-Penrose inverse, of a symmetric real matrix L is the matrix L- such that LL-=L-L is the orthogonal projection onto the row space of L.

generalized polygon
A generalized n-gon is an incidence structure satisfying the following three conditions: A generalized 3-gon is a projective plane, while a generalized 4-gon is a generalized quadrangle.

generalized quadrangle
A generalized quadrangle or GQ is a special case of a partial geometry. It is a partial linear space satisfying the following three conditions: The constants in the first two conditions are usually denoted by s+1 and t+1; s and t are the parameters of the GQ.

generator matrix
A generator matrix of a linear code is a matrix (with linearly independent rows) whose row space is the given code.

generously transitive permutation group
A permutation group is generously transitive if its basis matrices are symmetric; equivalently, if every two points in the domain can be interchanged by some group element.

gerechte design
A gerechte design is a Latin square L of order n where the cells are divided into n regions, each containing n cells, such that each symbol occurs once in each region.

If n=9 and the regions are 3×3 subsquares, this is precisely the solution to a Sudoku puzzle.

If the regions are the symbol positions in another Latin square L', then the condition asserts that L and L' are orthogonal.

Golay codes
Two remarkable perfect codes (a binary code of length 23 and a ternary code of length 11) associated with the Mathieu groups and the Witt designs.

GQ
See generalized quadrangle.

graph
The term "graph" has several meanings. In the most general form, it is an incidence structure consisting of a set of vertices and a set of edges, each edge incident with one or two vertices. An edge incident with one vertex is called a loop, and an edge incident with two vertices is called a link. Multiple edges (incident with the same set of vertices) are allowed.

A more restricted concept, sometimes called a simple graph, has no loops and no multiple edges. In this case, an edge can be identified with an unordered pair of vertices. Two vertices are called adjacent if there is an edge incident with that pair of vertices.

In a directed graph or digraph, edges are ordered (rather than unordered) pairs.

graph products
A graph product takes two graphs A and B and produces a graph whose vertex set is the cartesian product of the vertex sets of A and B. The most important types of graph product are the cartesian product, categorical product, strong product, and lexicographic product.

greatest lower bound
The greatest lower bound of two elements x and y in a poset is an element z with the properties The definition extends to more than two elements.

group (Topics)
A set with an associative operation having an identity element and inverses of each of its elements. The set of automorphisms of any mathematical structure is a group (the operation is composition of mappings).

group action
An action of a group G on a set X is a function from X×G to X taking (x,g) to xg, satisfying the two conditions The map taking x to xg is a permutation of X, and the map taking g to this permutation is a homomorphism from G to the symmetric group on X.

group-divisible design
WARNING This is a term which has different meanings to different people!

Originally, a group divisible design was one in which we are given a partition of the set of points into "groups", all of the same size (the term here has no connection with the algebraic sense) so that two points in the same group lie in lambda1 blocks, while any two points in different groups lie in lambda2 blocks. Such a design (assuming constant block size) is partially balanced (that is, a PBIBD), with respect to the association scheme whose classes are "equal", "in same group but not equal", and "in different groups".

In combinatorial design theory, the conditions of constant group size and constant block size are very often relaxed, but it is often assumed that lambda1=0, that is, a block and a group share at most one common point.

Top

H

Hadamard matrix (Topics, External )
An n×n matrix H with entries +1 and -1 satisfying HHT=nI.

Hall's marriage theorem
Hall's marriage theorem asserts that a family of sets has a system of distinct representatives if and only if any k of the sets in the family contain among them at least k elements, for all k.

Hall triple system
A Hall triple system is a Steiner triple system in which any three points not forming a triple are contained in a (unique) 9-point subsystem.

Hamming bound
A term used in coding theory for the sphere-packing bound.

Hamming codes (Example)
A family of perfect 1-error-correcting codes defined over arbitrary Galois fields GF(q). The length of such a code is (qn-1)/(q-1), for some integer n.

Hamming distance
The Hamming distance between two n-tuples x and y is the number of positions i for which xi and yi are different.

Hamming scheme (Example)
The Hamming scheme H(n,q) is the association scheme whose elements are all n-tuples over an alphabet of q symbols, where two elements are ith associates if and only if their Hamming distance is i, for i=1,...,n.

Hermitian form
A Hermitian form is a sesquilinear form B satisfying B(y,x)=B(x,y)a, where a is the associated field automorphism.

homomorphism
A map from one algebraic structure to another preserving the algebraic operations. Thus, in structures with addition, a homomorphism satisfies F(a+b) = F(a)+F(b), with a similar equation in structures with multiplication.

A map between relational structures of the same type is said to be a homomorphism if it preserves the relations. For example, a graph homomorphism is a map which takes edges to edges (with no assumption about what happens to non-edges).

Howell design
A Howell design H(s,m) (for m even) is an s×s array with the properties A Room square is a Howell design with m=s+1.

hyperbolic quadric
See quadric.

hypergraph
A hypergraph consists of a set V of vertices and a collection of subsets of V called edges (or hyperedges). If every edge contains two vertices, it is a (simple) graph.

Top

I

IBD
See incomplete-block design.

identity element
An identity element of a ring is an element 1 satisfying 1a=a1=a for all a in R.

incidence geometry
An incidence geometry consists of a set V of varieties, a set T of types, a type map t from V to T and symmetric incidence relation on V such that two varieties of the same type are incident if and only if they are equal. Sometimes, additional conditions are imposed: for example, that a maximal set of pairwise incident varieties contains exactly one variety of each type.

If there are just two types (traditionally called "points" and "blocks"), we usually speak of an incidence structure.

incidence graph
The incidence graph of an incidence structure (also called the Levi graph) is the graph whose vertices are the points and blocks of the structure, with an edge joining a point and a block if and only if they are incident. It is bipartite, the points and blocks providing the bipartition.

The incidence graph of an incidence geometry has all the varieties as vertices, two distinct varieties being joined if they are incident. It is a multipartite graph; the parts of the multipartition are the types of varieties.

incidence matrix
The incidence matrix of an incidence structure is the matrix with rows indexed by points and columns by blocks, the (p,B) entry being 1 if p and B are incident and 0 otherwise. For a non-binary block design, the (p,B) entry is the number of occurrences of treatment p on plots in block B (which may be greater than one).

WARNING Sometimes the transpose of this matrix is used (especially in coding theory).

incidence structure
An incidence structure consists of a set of points and a set of blocks with a relation of incidence between points and blocks.

inclusion-exclusion principle
A form of the Möbius inversion principle for subsets of a set. If we know the size of the intersection of a any subfamily of a family of sets, we can calculate the number of points lying in none of the sets (or in a specified subfamily but no others).

incomplete-block design
A block design in which not every treatment occurs in a block.

index
This term has two quite different meanings.
  1. The index of a subgroup H of a group G is the order of G divided by the order of H. This is an integer, by Lagrange's Theorem; it is equal to the number of cosets of H in G.
  2. The index of an orthogonal array of strength t is the number of rows in which prescribed elements occur in t given columns.

information matrix of block design (Topics)
The information matrix of a block design is the matrix
L=XT'(I-XBK-1XB')XT
where XT and XB are the plot-treatment and plot-block incidence matrices respectively, and K is the diagonal matrix whose entries are the block sizes.

inner product
An inner product on a vector space over the real numbers is a real-valued function of two variables (we write the inner product of u and v as u·v) which is If u=(u1,...,un) and v=(v1,...,vn) are written in coordinate form, then the standard inner product is given by
u·v = u1v1 + ... + unvn.
In coding theory we speak of the standard inner product on a vector space over a finite field; it is given by the above formula and satisfies the first two conditions (but not of course the third).

intercalate
An intercalate in a Latin square is a subsquare of order 2; that is, a pair of rows and a pair of columns in whose four positions just two different symbols occur, each twice.

intransitive action
See direct product of permutation groups.

inversive plane
An inversive plane is a 3-(q2+1,q+1,1) design. The classical example is the set of points and non-trivial plane sections of an elliptic quadric in projective 3-space over GF(q).

isomorphism
An isomorphism is a homomorphism which is also a bijection (one-to-one and onto). In other words, it is a one-to-one correspondence between two objects which preserves all their mathematical structure. Two objects connected by an isomorphism are called isomorphic, and are identical from the algebraic point of view.

WARNING Sometimes it is not clear exactly what structure is being preserved. For example, for Latin squares, are the roles of rows, columns and symbols interchangeable? If not, then the relation is called "isotopy", and the classes are "isotopy classes"; if they are, the classes are called "main classes". Other terminology is also used. A topic essay discusses the many different notions of equivalence for Latin squares.

isotopy
Isotopy is an equivalence relation on Latin squares: two squares are isotopic if one can be obtained from the other by permuting rows, columns and symbols. This is one of the many notions of isomorphism for Latin squares; see the topic essay for further details.

The term "isotopy" also describes a triple of bijections from the sets of rows, columns, and symbols of the first square to those of the second which demonstrates that the squares are isotopic.

Top

J

Johnson scheme
The Johnson scheme J(v,k) is the association scheme whose elements are the k-element subsets of a set of size v, where two elements are ith associates if their intersection has size k-i.

join
The least upper bound of two elements of a lattice (in meaning 1).

Jordan algebra
A Jordan algebra is an algebra over the real numbers satisfying the commutative law x o y = y o x and the "Jordan identity"
x o (y o x2) = (x o y) o x2.
The most familiar example is the space of real symmetric matrices of given order n, with the operation
A o B = (AB+BA)/2.

Top

K

kernel
The kernel of a homomorphism from one algebraic structure A to another structure B is the set of elements of A which are mapped to the zero or identity element of B.

Kirkman triple system (Example)
A resolvable Steiner triple system. (The existence of such a design of order 15 is Kirkman's Schoolgirl Problem.)

Kronecker product of matrices
The Kronecker product of matrices A and B is obtained from the matrix A=(aij) by replacing the (i,j) entry by the block matrix aijB, for all i,j.

Top

L

Lagrange's Theorem
Lagrange's Theorem asserts that the order of a subgroup of a group divides the order of the group.

Laplacian matrix of a graph
For a graph with vertices v1,...,vn, the Laplacian matrix is the n×n matrix whose (i,i) entry is equal to the degree of vi, and whose (i,j) entry for distinct i and j is equal to -1 if i and j are adjacent, 0 otherwise. It is symmetric and positive semi-definite.

Latin cube
There are several definitions of a Latin cube (information on this is coming!) The simplest, and easiest to generalise, is an n×n×n array over an alphabet of n symbols such that each symbol occurs once in each "line"; in other words, an orthogonal array of strength 3 and index 1 having four columns, over an alphabet of n symbols.

Latin rectangle
A Latin rectangle is an m×n rectangular array of symbols from an alphabet of size n, such that each symbol occurs once in each row and at most once in each column.

It follows from Hall's marriage theorem that any Latin rectangle can be extended (by the addition of n-m extra rows) to a Latin square.

WARNING Sometimes it is permitted that the size of the alphabet is greater than the number of columns, and required that each symbol occurs at most once in each row or column. Such an object is a special type of partial Latin square.

Latin square (Encyc, Example)
A Latin square is an n×n array with entries from an alphabet of size n, such that each symbol in the alphabet occurs once in each row and once in each column.

Association scheme or strongly regular graph of Latin square type
A set of mutually orthogonal Latin squares gives rise to an association scheme as follows: the points are the cells of the squares; two points are first associates if they lie in the same row or column or contain the same entry in one of the squares, and are second associates otherwise.

The graph whose adjacent pairs are first associates is a strongly regular graph of Latin square type.

lattice
There are two unrelated meanings:

1. A lattice is a partially ordered set in which any two elements have a greatest lower bound and a least upper bound. Typical examples are the lattice of all subsets of a set, and the lattice of all subgroups of a group, ordered by inclusion in each case.

2. A lattice is a discrete subgroup of the additive group of a Euclidean space. This means that the lattice is closed under addition and negation, and that there is a non-zero minimum distance between two points of the lattice. An example is the integer lattice consisting of all points with integer coordinates.

Based on the second meaning, various combinatorial and statistical designs have the word lattice in their names, suggesting the regular arrangement of points in a low-dimensional integer lattice.

lattice design
Lattice designs are particular kinds of resolved incomplete-block design.

For a square lattice design, there are n2 treatments in rn blocks of size n. The treatments are allocated to the cells of an n × n square array. The blocks of the first two replicates are the rows and columns, respectively, of the array. The remaining replicates, if any, are defined by r-2 mutually orthogonal latin squares of order n; the letters of each square define the blocks in the corresponding replicate. The lattice design is simple if r=2. Square lattice designs are also called nets. They are partially balanced with respect to an association scheme of Latin square type; first associates concur once in blocks, second associates never.

For a rectangular lattice design, there are n(n - 1) treatments in rn blocks of size n-1. The construction is similar to that for a square lattice design, except that n cells are removed from the square array. The removed cells should form a transversal to all the Latin squares used in the construction. A rectangular lattice design is partially balanced if r=2, n-1 or n, but not otherwise.

For a cubic lattice design, there are n3 treatments in 3n2 blocks of size n. The treatments form a cube of order n; the blocks are the 1-dimensional slices.

lattice square
This is a design for n2 treatments in r blocks, each of which is a n × n square array. The construction uses a square lattice design in 2r replicates. Pairs of replicates in the old design are combined so that their blocks form the rows and columns, respectively, of squares in the new design.

least upper bound
The least upper bound of two elements x and y in a poset is an element z with the properties The definition extends to more than two elements.

length of a code
The length of a code is the number of symbols in each of its codewords.

Levi graph
The Levi graph of an incidence structure (also called the incidence graph) is the graph whose vertices are the points and blocks of the structure, with an edge joining a point and a block if and only if they are incident.

lexicographic product of graphs
The lexicographic product B[A] of graphs A and B is defined as follows. The vertex set is the cartesian product of the sets A and B. Two vertices (a,b) and (a',b') are adjacent if and only if either This construction is analogous to nesting.

group of Lie type
These groups are related to certain groups of matrices, and account for most of the finite simple groups. They include the classical groups.

The best-known and commonest example is PSL(2,p), the group of unimodular linear fractional transformations over the integers modulo p (where p is prime): the elements are mappings of the form

z -> (az+b)/(cz+d),
where a,b,c,d are integers mod p and ad-bc = 1.

line graph
The line graph L(G) of a simple graph G is the graph whose vertices are the edges of G, where two vertices of L(G) are adjacent if and only if the corresponding edges of G share a vertex.

linear code
A linear code is a code one whose alphabet is a Galois field, such that the code is a subspace of the vector space of all n-tuples over the field.

linear space
A linear space is an incidence structure in which the blocks are called "lines", having the properties that every line is incident with at least two points, and any two points are incident with exactly one line.

loop
Note the two different meanings!

A loop in a graph is an edge whose two vertices are the same.

A loop is a quasigroup containing an element e which is an identity for the operation (that is, ae=ea=a holds for all elements a.) If the elements are 1,...,n, with e=1, then the Cayley table is a normalised Latin square.

Top

M

MacWilliams relation
A relation between the weight enumerator of a linear code and that of its dual.

main class of Latin squares
Two Latin squares lie in the same main class if one can be obtained from the other by permuting rows, columns and symbols, and possibly by exchanging the classes of rows, columns and symbols among themselves. Such a transformation is called a paratopy. It is one of several notions of isomorphism for Latin squares; see the topic essay for further details.

Markov chain (Topics)
A stochastic process with a set S of states, where at each discrete time step, if the system is in state si, then it moves to state sj with a given probability pij. A random walk on a graph is an example.

Mathieu groups
The Mathieu groups are five sporadic simple groups discovered by É. Mathieu in the nineteenth century. They are denoted by M11, M12, M22, M23 and M24. They are groups of automorphisms of interesting t-designs with parameters 4-(11,5,1), 5-(12,6,1), 3-(22,6,1), 4-(23,7,1), 5-(24,8,1) respectively; these are referred to as the Witt designs.

matroid (External)
A matroid is a combinatorial structure which abstracts the idea of linear independence in a vector space. A family of subsets of a set is the family if independent sets of a matroid if it is closed under taking subsets and satisfies the exchange property.

In a matroid, a basis is a maximal independent set (all bases have the same size); a circuit is a minimal dependent set; the rank of a subset is the size of the largest independent set it contains; and a flat is a maximal subset of given rank.

maximum-distance separable code
A code attaining the Singleton bound.

MDS
Short for "maximum-distance separable".

meet
The greatest lower bound of two elements of a lattice (in meaning 1).

microarray
A microarray is a block design with blocks of size 2. The concept arose in DNA testing, where each array is probed with two DNA samples.

minimum distance
The minimum distance of a code is the smallest Hamming distance between two distinct codewords. If a code has minimum distance 2e+1 or greater, then it can correct up to e errors.

minimum weight
The minimum weight of a linear code is the smallest weight or number of non-zero coordinates in any non-zero codeword. The minimum weight is equal to the minimum distance of the code.

Möbius function of poset
The Möbius function of the poset P on a set X is the function µ of two variables, given by It is the inverse of the zeta function.

Möbius inversion
Let P be a poset on X with Möbius function µ. If f and g are functions of two variables on X which satisfy
f(x,y) = Sum g(x,z),
then
g(x,y) = Sum f(x,z)µ(z,y),
where both summations run over all elements z with x<=z<=y.

MOLS
Short for mutually orthogonal Latin squares.

Moore-Penrose inverse
See generalized inverse.

multipartite graph
A multipartite graph is one having a partition of the vertices so that any edge joins vertices in different parts. If the number of parts is r, the graph is called r-partite.

multiplicative group of field
The group consisting of the non-zero elements of the field, with the operation of multiplication.

multiplicity-free permutation group
A permutation group is multiplicity-free if its basis matrices commute.

multiply-transitive permutation group
A permutation group is t-transitive if any t-tuple of distinct points of the domain can be mapped to any other such t-tuple by some permutation in the group. If this holds for ti>=2, the group is said to be multiply-transitive.

multiset
A multiset is a generalisation of a set, in which elements occur with multiplicities which may be greater than one. It can be regarded also as a list in which the order of the list items is irrelevant.

mutually orthogonal Latin squares (Encyc)
A set of Latin squares, any two of which are orthogonal. MOLS for short. Also called "pairwise orthogonal Latin squares" (POLS).

Top

N

Strongly regular graph of negative Latin square type
A strongly regular graph is of negative Latin square type NLs(n) if its parameters are formally those of L-s(-n) (see pseudo-Latin square type): that is,
v=n2, k=s(n+1), lambda=s2+3s-n, mu=s(s+1).

neighbour design (Example)
In general terms, a neighbour design is a design in which there is a concept of elements of a block being "neighbours", so that every pair of elements occur as neighbours in a block the same number of times.

For example, Rees defined a neighbour design to be a 1-design with a circular structure on each block satisfying this condition; these have subsequently been called "Rees neighbour designs" or "balanced Ouchterlony neighbour designs".

nested block design
A nested block design, also called a split-plot design, is one in which the set of plots is partitioned into blocks, each of which is partitioned into sub-blocks.

nesting
Let A and B be sets carrying collections of binary relations. The structure obtained by nesting A in B has as its point set the union of copies of A indexed by B. For each relation R on A, there is a corresponding relation which holds within each copy of A; and for each relation S on B, there is a corresponding relation which holds between two elements if the indices of the copies of A containing them satisfy the relation S.

The analogous concept for permutation groups is the wreath product.

net (Encyc)
A net of order n and degree r is a partial linear space in which each line has n points, each point is on r lines, and Euclid's parallel postulate holds. A net is equivalent to a set of r-2 mutually orthogonal Latin squares of order n. It is a special kind of partial geometry.

normal subgroup
A subgroup H of a group G is normal if g-1Hg=H for any element g of G. A subgroup is normal if and only if it is a union of conjugacy classes. A normal subgroup is the same thing as the kernel of a group homomorphism.

normalised Latin square
A Latin square with symbol set 1,...,n, in which the first row and column contain the symbols in their usual order. Any Latin square can be normalised by permuting rows and columns.

null polarity
A polarity of an incidence structure is null if every point is absolute. A symplectic polarity of projective space is an example.

Top

O

1-factorisation of graph
A partition of the edge set of the graph into classes, each of which forms a partition of the vertex set of the graph. This is the same thing as a resolution, if we think of the graph as an incidence structure with blocks of size 2.

A necessary condition for a graph to have a 1-factorisation is that it is regular. It follows from Hall's marriage theorem that, for bipartite graphs, this condition is also sufficient.

1-rotational design
A block design is 1-rotational if it has an automorphism fixing one point and permuting the others in a single cycle. Compare cyclic design.

order of a group, design, etc.
WARNING One of those words with many different meanings. Be especially careful of the first two.
To make things worse, the word "order" is also used as a synonym for (partially) ordered set!

The order of a finite group or field is the number of elements it contains.

The order of an element g of a finite group is the smallest positive number m such that gm=1. It follows from Lagrange's Theorem that the order of any element of a group divides the order of the group.

The order of a Latin square is the number of its rows (or columns or symbols).

The order of a projective (resp. affine) plane is the number n such that the plane has n2+n+1 (resp. n2) points.

Sometimes, the order of another type of design (such as a Steiner triple system) is used to mean the number of points of the design.

orthogonal
WARNING The word "orthogonal" has many different meanings. See, for example, D. A. Preece, "Orthogonality and designs: a terminological muddle", Utilitas Math 12 (1977), 201-223.

Two vectors v and w are orthogonal if v·w=0, where v·w denotes the inner product. Two subspaces V and W are orthogonal if every vector in V is orthogonal to every vector in W.

Two partitions P1 and P2 of a set X are said to be orthogonal if, for any parts Y1 and Y2 of P1 and P2, the size of their intersection is equal to |Y1|·|Y2|/|X|. In other words, the proportion of elements of each part of P1 which belong to a given part Y2 of P2 is constant.

Two Latin squares L1 and L2 are orthogonal if, for each pair (k,l) of symbols, there is a unique cell (i,j) in which L1 has symbol k and L2 has symbol l.

The term orthogonal design has two entirely different meanings.

An orthogonal array is different again - see below.

orthogonal array (Example)
An orthogonal array of strength t and index l over an alphabet A is a rectangular array with elements from A having the property that, given any t columns of the array, and given any t elements of A (equal or not), there are exactly l rows of the array where those elements appear in those columns.

There is a more general definition which permits using alphabets of different cardinalities in the different coordinate positions. The requirement is that the number of rows where given elements occur in t prescribed columns is constant over all choices of the elements, but is allowed to vary for different sets of columns. Such an orthogonal array does not have an index. The example is of this "mixed alphabet" type.

orthogonal block structure
A set carrying a family of partitions such that Simple orthogonal block structures and poset block structures are examples.

orthogonal design
This term has two quite unrelated meanings.
  1. An orthogonal design is a square matrix A, whose entries are either 0 or ±xi, where x1, ..., xs are indeterminates, such that AAT is diagonal.
  2. An orthogonal design is, roughly speaking, one where the various factors in the design are orthogonal in the sense of partitions. (More on this later?)

orthogonal group
The group of linear transformations preserving a non-singular quadratic form.

orthogonal polarity
A polarity of projective space defined by a symmetric bilinear form.

Top

P

pairwise balanced design
An incidence structure in which any two points are incident with lambda blocks (but block size is not assumed to be constant). Sometimes it is assumed that lambda=1.

Pappus' Theorem
A configuration theorem for projective planes, which holds in a plane if and only if it can be coordinatised by a (commutative) field.

parabolic quadric
See quadric.

parallel class
A class in a resolution. It is a set of blocks which form a partition of the point set, in other words a spread.

paratopy
A paratopy of a Latin square (sometimes called a main class equivalence) is a transformation which is a combination of an isotopy (independent permutations of the sets of rows, columns and symbols) and a permutation of the classes "rows", "columns" and "symbols".

The word also refers to the equivalence relation thus generated on the set of Latin squares.

parity check matrix
A parity check matrix of a linear code is a matrix (with linearly independent rows) whose null space is the given code. It is a generator matrix for the dual code.

partial geometry
A partial geometry is a partial linear space satisfying the following three conditions: Nets and generalized quadrangles are examples of partial geometries.

partial Latin square
An n×n array whose cells are either empty or contain a symbol from an alphabet of size n, such that each symbol occurs at most once in each row or column. A Latin rectangle is an example.

A theorem of Ryser asserts that if all the symbols in a partial Latin square are confined to i rows and j columns, where i+j <= n, then the array can be completed to a Latin square (by putting symbols in the blank cells).

partial linear space
A partial linear space is an incidence structure in which the blocks are called "lines", having the properties that every line is incident with at least two points, and any two points are incident with at most one line.

partially balanced design (partially balanced incomplete-block design, or PBIBD) (Example)
A design is partially balanced with respect to an association scheme if the number of blocks containing two points depends only on which class of the partition contains the given pair of points.

partially ordered set (Topics)
A partially ordered set (for short, a poset) is a set X with a binary relation < satifying the conditions

partition
A partition of a set X is a collection of non-empty subsets of X such that every element of X lies in exactly one set of the partition.

PBIBD
Short for partially balanced incomplete-block design.

perfect code
A code which attains the sphere-packing bound with respect to Hamming distance.

perfect matroid design
A matroid with the property that, for any number k not exeeding the rank of the matroid, all flats of rank k have the same cardinality.

permutation
A permutation can be thought of in two ways: in passive form, it is an arrangement of the elements of a set in order; in active form, it is a one-to-one and onto function from the set to itself (so that the passive form is the image of the "natural" order of the set). For example, the permutation whose passive form is (2,4,1,3) is, in active form the function which maps 1 to 2, 2 to 4, 3 to 1, 4 to 3.

Permutations in active form are functions and can be composed. This composition is the group operation in the symmetric group.

permutation group (Topics)
A permutation group on a set X is a group whose elements are permutations of X and whose operation is composition of permutations.

In other words, it is a subgroup of the symmetric group on X.

Petersen graph
The Petersen graph is the graph whose vertices are the 2-element subsets of {1,2,3,4,5}, two vertices adjacent if and only if they are disjoint. In other words, it is the complement of the triangular graph T(5).

Among its many remarkable properties, it is strongly regular and vertex-transitive.

PIE (Principle of Inclusion and Exclusion)
See inclusion-exclusion principle.

plot
An experimental unit, to which a single treatment is applied.

plot structure
The need for experimental design, even when comparing an unstructured set of treatments, is caused by inhomogeneity in the set of plots.

A common form of structure consists of one or more partitions. In the case of a single partition, we use a block design. For a pair of partitions, we use a nested block design or a row-column design if the partitions are nested or crossed respectively. More complicated structures are possible!

There may be further structure as well, such as a neighbour relation, for which we use a neighbour design.

PMD
See perfect matroid design.

point-transitive
See transitive.

polarity of an incidence structure (Example)
A polarity is a duality of order 2; that is, a map t from points to blocks which preserves incidence such that, if p is incident with qt, then q is incident with pt.

If we order the points as p1,...,pn, and the blocks as p1t,...,pnt, then the incidence matrix of the incidence structure is symmetric.

POLS
Same as MOLS.

poset
Short for partially ordered set.

poset block structure
Poset block structures are a special class of orthogonal block structures which include the simple orthogonal block structures. The points form the cartesian product of a family of sets with trivial structure indexed by a partially ordered set, and there is a partition corresponding to each ancestral set in the poset.

The poset block structures corresponding to the 2-element antichain and chain correspond respectively to crossing and nesting.

prime power canonical form
An expression of a finite Abelian group as a direct sum of cyclic groups, where the order of each cyclic group is a power of a prime.

prime subfield of field
The prime subfield is the unique smallest subfield of a field. In the case of a Galois field with pn elements, the prime subfield has p elements, and is isomorphic to the integers mod p.

primitive permutation group (Topics)
A permutation group is said to be primitive if there is no partition of the domain which is preserved by the group apart from the trivial partitions (the partition into singletons, and the partition with just one part). It is customary to require a primitive group to be transitive -- this excludes the trivial group acting on two points, which would otherwise qualify as primitive.

primitive root
An element in a Galois field (or in the integers modulo n) which generates the multiplicative group (so that any non-zero element of the field, or any unit of the integers mod n, is a power of the primitive root). Every Galois field has a primitive root; there is a primitive root modulo n if and only if n is pa, 2pa, or 4, where p is an odd prime.

Principle of Inclusion and Exclusion
See inclusion-exclusion principle.

projective plane (Topics)
A 2-(n2+n+1,n+1,1) design (necessarily square). The points and lines of the projective space of dimension 2 form an example.

product action
See direct product of permutation groups.

projective space
A projective space of dimension n over a field F is constructed from the vector space of dimension n+1 over F as follows: the objects are all the subspaces of the vector space, two objects being incident if one contains the other. Subspaces with dimension 1, 2, n (as vector spaces) are called points, lines, and hyperplanes respectively.

proper block design
A block design is proper if all blocks have the same cardinality, that is, contain the same number of plots. For binary designs, this just means that all blocks contain the same number of points.

The corresponding term for hypergraphs is uniform.

Strongly regular graph of pseudo-Latin square type
A strongly regular graph is of pseudo-Latin square type Ls(n) if its parameters are those which would arise from s-2 MOLS of order n: that is,
v=n2, k=s(n-1), lambda=s2-3s+n, mu=s(s-1).

Top

Q

quadratic residue, quadratic non-residue
A quadratic residue is an element (of a Galois field, for example), which is the square of some element; a quadratic non-residue is one which is not. In a Galois field of odd order, half of the non-zero elements are quadratic residues (all the even powers of a primitive root), and half are not.

quadratic form
A quadratic form is a function on a vector space which, when written out in terms of coordinates, is a polynomial of degree 2. Alternatively, it is a function Q satisfying

quadric
A quadric is the set of points in projective space whose coordinates are the zeros of some quadratic form.

Quadrics in finite projective space are classified as elliptic, parabolic or hyperbolic according to the dimension of the largest subspace of the projective space contained in the quadric. If this dimension is r and the quadric is in n-dimensional space, then n=2r+3 for an elliptic quadric, n=2r+2 for a parabolic quadric, and n=2r+1 for a hyperbolic (or ruled) quadric.

In odd characteristic, the set of absolute points of an orthogonal polarity is a quadric.

quasi-complete Latin square (Example)
A Latin square is quasi-complete if it is both row-quasi-complete and column-quasi-complete.

quasigroup
A quasigroup is a set with a binary operation whose operation table (or Cayley table) is a Latin square.

In other words, left and right division by any element are possible and give a unique result. This means that the equation ax=b has a unique solution x, given a and b; and similarly the equation ya=b has a unique solution y.

Top

R

random walk
A Markov chain defined on a graph (possibly directed), where the states are the vertices, and at each time step, the state changes to a vertex adjacent to the previous one. In the simplest case, all neighbours are equally likely.

rank
The rank of a matrix is equal to the dimension of its row space (or of its column space: the two dimensions are equal).

The rank of a subset of a matroid is equal to the size of the largest independent set which it contains.

The rank of a permutation group is equal to the number of orbits of the group on the set of ordered pairs of points; in other words, the number of basis matrices for the group.

rectangular lattice design
See lattice design.

Rees neighbour design
A neighbour design in which blocks have a circular structure so that each pair of elements occurs as neighbours in a circle exactly once.

reflexive
A binary relation R is reflexive if R(x,x) holds for all x. For example, equality is a reflexive relation.

regular hypergraph
A hypergraph is regular if the number of edges incident with a vertex is constant. This constant is called the valency, or the degree, of the hypergraph.

The analogous term for block designs is equireplicate.

regular graph
A graph is regular if the number of edges incident with a vertex is constant. This constant is called the valency, or the degree, of the graph.

repeated blocks (Example)
An incidence structure of points and blocks has repeated blocks if there are two blocks incident with exactly the same points.

replicate
A synonym for a resolution class or parallel class of blocks in a resolution of a design.

replication number
The replication number of a treatment in a block design is the number of times the treatment occurs in the design. In the case of a binary design, this is equal to the number of blocks in which the treatment occurs. In a resolvable design, it is equal to the number of replicates or parallel classes in a resolution.

The corresponding term for a hypergraph is valency.

resolution
See resolvable design.

resolvable
An incidence structure of points and blocks is resolvable if there is a equivalence relation on the set of blocks of the structure with the property that each point is incident with exactly one block from each equivalence class. Such an equivalence relation is called a resolution of the structure.

More generally, an incidence structure is r-resolvable if its blocks can be partitioned into sets such that each point lies in r blocks of each set.

resolved
A resolved design is a design with a given resolution.

ring
A ring is a set R of elements with two binary operations, called addition and multiplication, with the properties Some authorities require a ring to contain an identity element, an element 1 satisfying 1a=a1=a for all a in R.

Room square
A Room square of (odd) side n is an n×n array with the properties It is a special kind of Howell design.

round-dance neighbour design (Example)
A neighbour design in which blocks are complete (each treatment occurs once in each block) and have a circular structure so that each pair of elements occurs as neighbours in a circle exactly once.

row-column design
A row-column design is one in which the set of plots has the structure of a rectangle, in which two plots may be in the same row, or in the same column, or neither. We may, for example, wish to assign treatments to the plots in order to fulfil some balance requirement between treatments and rows, and/or treatments and columns.

row-complete Latin square
A Latin square is row-complete if each ordered pair of distinct symbols occurs precisely once in consecutive positions in a row of the square.

row-Hamiltonian Latin square
A Latin square is row-Hamiltonian if, for any two distinct rows, the permutation taking the first row of the pair to the second consists of a single cycle.

row-quasi-complete Latin square
A Latin square is row-quasi-complete if each unordered pair of distinct symbols occurs precisely twice in consecutive positions in a row of the square.

ruled quadric
See quadric.

Top

S

Schurian coherent configuration
A coherent configuration formed by the basis matrices of a permutation group.

SDR
Short for system of distinct representatives.

self-dual incidence structure
An incidence structure is self-dual if it is isomorphic to its dual. Equivalently, the incidence matrix can be transformed into its transpose by row and column permutations.

self-orthogonal Latin square (Example)
A Latin square cannot be orthogonal to itself. So, unfortunately, the term "self-orthogonal" is used of a Latin square which is orthogonal to its transpose.

self-polar incidence structure
An incidence structure is self-polar if it admits a polarity. Equivalently, its rows and columns can be ordered so that the incidence matrix is symmetric.

semi-Latin square (Example, External)
A semi-Latin square with parameters (n,k) is an n×n array, each of whose entries is a k-element subset of an alphabet of size nk, such that each symbol in the alphabet occurs once in each row and once in each column.

semilinear
A function f on a vector space is semilinear (with respect to a field automorphism a) if

sequencing of a group (Example)
A sequencing of a finite group G of order n is an ordering (g1,g2,,...,gn) of the elements of G such that the partial products g1, g1g2, ..., g1g2···gn are all distinct. The sequence of partial products is called a directed terrace. Sequencings give rise to complete Latin squares.

sesquilinear form
A sesquilinear form on a vector space is a function of two variables which is linear in the first variable and semilinear in the other.

sharply transitive set of permutations
A set of permutations of {1,...,n} is sharply transitive if, given any two symbols i and j, there is a unique permutation in the set carrying i to j.

This is equivalent to saying that the permutations form the rows of a Latin square.

simple graph
A graph with no loops or multiple edges.

simple group
A simple group is a group whose only normal subgroups are itself and the identity.

The finite simple groups have been classified.

simple incidence structure
An incidence structure of points and blocks is simple if it has no repeated blocks.

simple orthogonal block structure
A set carrying a family of partitions, obtained from sets with trivial structure (carrying only the relation of equality and the universal relation) by repeated crossing and nesting.

It is a special kind of orthogonal block structure.

Singleton bound
The Singleton bound asserts that a code with length n and minimum distance d over an alphabet of q symbols has at most qn-d+1 codewords.

A code meeting this bound is called maximum-distance separable.

Smith canonical form
An expression of a finite Abelian group as a direct sum of cyclic groups, where the order of each cyclic group divides the order of the next.

SOLSSOM
Short for self-orthogonal Latin square with symmetric orthogonal mate (that is, having a symmetric Latin square which is orthogonal to both the given square and its transpose).

SOMA (External )
A SOMA (simple orthogonal multi-array) with parameters (n,k) is a semi-Latin square with these parameters having the further property that the sets of entries in different cells of the array have at most one symbol in common.

special linear group
The group of all linear transformations of a vector space having determinant 1.

sphere-packing bound
In a space where the distances are all integers, if a set of points have mutual distances at least 2e+1, then the spheres of radius e with centres at these points are pairwise disjoint, and so the number of points cannot exceed the number of points in the space divided by the least number of points in a sphere (or ball) of radius e. This is the sphere-packing bound, also known as the Hamming bound.

In coding theory, a code which attains this bound is called a perfect code.

split-plot design
Another term for a nested block design.

sporadic group
One of twenty-six simple groups which do not fit into an infinite family in a natural way. They include the multiply-transitive Mathieu groups.

spread
A spread in an incidence structure of points and blocks is a set of blocks which partition the point set (that is, each point lies in exactly one block of the spread).

Each parallel class in a resolution is a spread.

square design (Example)
A design is square if it has equally many points and blocks. The points and hyperplanes of a projective space form an example.

WARNING Square 2-designs (BIBDs) are often called "symmetric" in the literature, though there is no requirement that the incidence matrix should be symmetric. (The latter condition is equivalent to the existence of a polarity of the design.)

square lattice design
See lattice design.

square lattice graph
The square lattice graph L2(n) is the line graph of the complete bipartite graph with two bipartite blocks containing n vertices each. We can regard it as an n × n grid, with two vertices adjacent if they lie in the same row or column. Alternatively, it is the categorical product of two complete graphs with n vertices each. It is strongly regular.

SQS
Short for Steiner quadruple system.

Steiner quadruple system
A 3-(v,4,1) design. See t-design.

Steiner system
A t-design with lambda=1.

Steiner triple system (Encyc)
A 2-(v,3,1) design. See t-design.

stratifiable permutation group
A permutation group is stratifiable if its symmetrised basis matrices commute. (The set of basis matrices is closed under transposition; we replace each pair A, AT by their sum.)

strength
The strength of a proper block design is the maximum value of t for which it is a t-design; the strength of an orthogonal array is the maximum value of t for which any t symbols occur in any t distinct coordinates a constant number of times.

strong product of graphs
The strong product of graphs A and B is defined as follows. The vertex set is the cartesian product of the sets A and B. Two vertices (a,b) and (a',b') are adjacent if and only if one of the following holds: In other words, it has the edges of both the cartesian and categorical products of the two graphs.

strongly regular graph
A (simple) graph is strongly regular if the identity matrix, the adjacency matrix of the graph, and the adjacency matrix of its complement form an association scheme. Equivalently, the graph is regular, the number of common neighbours of two adjacent vertices is constant, and the number of common neighbours of two non-adjacent vertices is constant.

It is common to use the parameter v for the number of vertices, and the numbers k,lambda,mu for neighbours of, respectively, one vertex, two adjacent vertices, and two non-adjacent vertices.

STS
Short for Steiner triple system.

subgroup
A subgroup of a group is a subset which forms a group in its own right (with respect to the same operations).

Sudoku
The popular Sudoku puzzle involves a uniquely completable set in a 9 × 9 square grid divided into nine 3 × 3 subsquares, where "completion" involves filling the grid to form a gerechte design for this partition of the grid (that is, each digit occurs once in each row, column or subsquare).

Hadamard matrix of Sylvester type
A Hadamard matrix of order 2n formed by taking the n-fold Kronecker product of the Hadamard matrix of order 2:
+1+1
+1-1

symmetric
A binary relation R is symmetric if R(x,y) implies R(y,x) for all (x,y). A typical example is adjacency in a graph.

A matrix is symmetric if it is equal to its transpose. Thus, the adjacency matrix of a graph is symmetric.

For further meanings of the term, see below.

symmetric bilinear form
A bilinar form B is symmetric if B(y,x)=B(x,y) for all vectors x,y.

symmetric design
Another term for a square 2-design.

symmetric group
The symmetric group Sn is the group consisting of all permutations of the set {1,...,n}. The group operation is composition of permutations. The order of Sn is n! .

symplectic group
The group of linear transformations preserving a non-singular alternating bilinear form.

symplectic polarity
A polarity of projective space defined by an alternating bilinear form.

syndrome decoding (Example)
A decoding method where one computes a linear function (called the syndrome) of a received word with the properties that the syndrome of a codeword is zero while different error patterns have different syndromes. Thus the syndrome determines the error pattern and hence the transmitted word.

system of distinct representatives (Topics)
Let A1, ..., An be sets. A system of distinct representatives (or SDR) is an n-tuple (a1, ..., an) of distinct elements with the property that ai in Ai for i=1,...,n.

Hall's marriage theorem gives a necessary and sufficient condition for a family of sets to have a SDR.

Top

T

t-design (Encyc)
A t-(v, k, lambda) design is an incidence structure with the properties that there are v points; every block is incident with k points; and any t points are incident with lambda blocks.

ternary
A ternary code is one whose alphabet is {0,1,2} (or the Galois field with three elements).

terrace in a group
A terrace in a finite group G of order n is an ordering (h1,h2,,...,hn) of the elements of G such that, among the elements hi-1hi+1, for i=1,...,n-1, each element of order 2 occurs once, and each inverse pair of elements of order greater than 2 is represented twice. Terraces are used to construct quasi-complete Latin squares.

tight single-change covering design (Example)
A tight single-change covering design is an array with k rows, each entry taken from a set of size v, such that

trade
A trade is a pair of collections of blocks of a block design, or rows of an array, such that some property of the design or array is preserved if the first set of blocks is removed and replaced by the second. For example, a trade for a Steiner triple system would consist of two sets of triples which both form partial Steiner triple systems and cover exactly the same set of pairs of points: for example, {123,145,246,356} and {124,135,236,456}.

transitive
1. A permutation group is transitive if, for any two points in the domain, there is a permutation in the group carrying one to the other. This notation is extended as follows: a mathematical object (or its group of automorphisms) is said to be thing-transitive if the group acts transitively on the set of things in the object. Thus a graph may be vertex-transitive or edge-transitive; a design may be point-transitive, block transitive, or flag-transitive.

2. A binary relation R is transitive if, whenever R(x,y) and R(y,z) hold, then R(x,z) also holds. Typical examples of transitive relations are equivalence relations and order relations in partially ordered sets.

transpose
The transpose of a matrix A is the matrix (usually written as A' or AT) whose entry in row i and column j is equal to the entry in row j and column i of A.

transposition
A transposition is a permutation which swaps two points of the domain and leaves all the others fixed.

The word "transposition" also refers to the action of replacing a matrix by its transpose.

transversal
A transversal to a partition of a set is a subset which contains exactly one member of each part. The word is used in other contexts with similar but slightly varying meaning:

transversal design
A transversal design is a group-divisible design in which every block is a transversal to the groups (that is, it contains one point from each group).

triangular graph
The triangular graph T(n) is the line graph of the complete graph Kn. It is strongly regular.

Trojan square
A semi-Latin square formed by superimposing a family of mutually orthogonal Latin squares using pairwise disjoint sets of symbols.

Top

U

uniform hypergraph
A hypergraph is uniform if all its edges have the same cardinality. If this cardinality is k, we call it a k-uniform hypergraph. Thus, a graph is a 2-uniform hypergraph.

The corresponding term for binary block designs is proper.

uniform partition
A partition, all of whose parts have the same size.

uniquely completable set
A uniquely completable set in a Latin square is a set of entries in a square grid which can be embedded in precisely one Latin square.

Uniquely completable sets can be defined for other classes of designs as well; see the entry on Sudoku.

unit
This term has two quite unrelated meanings:
  1. An element which has an inverse. In the integers mod n, an element m is a unit if and only if it is coprime to n. In a field, every non-zero element is a unit.
  2. A synonym for plot in a design.

unital
A unital is a 2-(q3+1,q+1,1) design. The "classical" example is the set of isotropic points and non-isotropic points of a unitary polarity of the projective plane over GF(q).

unitary group
The group of linear transformations preserving a non-singular Hermitian form.

unitary polarity
A polarity of projective space defined by a Hermitian form.

Top

V

(v,k,lambda) graph (Example)
A strongly regular graph with lambda=mu; that is, any two vertices have lambda common neighbours. Such a graph is associated with a polarity of a square 2-design with no absolute points.

valency of a (hyper)graph
The valency, or degree, of a vertex of a graph (or hypergraph) is the number of edges containing that vertex. If all vertices have the same valency, the graph or hypergraph is regular, and this number is the valency, or degree, of the graph (or hypergraph).

For a block design, this parameter is called replication number.

variance balance
A block design is variance-balanced if the variances of the best estimators of all the normalised treatment contrasts are equal. Equivalently, the generalized inverse of its information matrix is completely symmetric. (See the Topic essay on "Estimation and variance in block designs".)

For a connected, proper, equireplicate block design, variance balance coincides with the combinatorial condition of pairwise balance. See also balance.

vector space
A vector space over a field F is a structure whose elements can be added to one another or multiplied by scalars (elements of F). The standard model of a vector space is the set of all n-tuples of elements of F, with pointwise addition and scalar multiplication.

vertex-colouring of a graph
A (proper) vertex-colouring of a graph is an assignment of colours to the vertices so that two adjacent vertices are assigned different colours.

vertex-transitive
See transitive.

Top

W

weight of a codeword
Assuming that the alphabet contains a zero element, the weight of a word is the number of non-zero entries in the word. If the alphabet is a field, the Hamming distance between two words is the weight of their difference.

weight enumerator of a code
The weight enumerator of a code is the generating function for the number of codewords of given weight in the code.

Witt designs
Five interesting t-designs with parameters 4-(11,5,1), 5-(12,6,1), 3-(22,6,1), 4-(23,7,1), 5-(24,8,1) respectively. Their automorphism groups involve the Mathieu groups, and they are also closely connected with the Golay codes.

wreath product of permutation groups
If Gi is a permutation group acting on a set Xi for i=1,2, the wreath product of G1 and G2 can be defined as the permutation group on the cartesian product X1×X2 generated by the following two types of permutations: Wreath product is analogous to nesting, but note that the operands are written in the opposite order: a design theorist would say that X1 is nested in X2 here.

Top

X

Top

Y

Youden "square" (Example)
A Youden "square" can be obtained from the incidence matrix of a square 2-(v,k,lambda) design by replacing the non-zero entries by the symbols 1,...,k in such a way that each symbol occurs exactly once in each row and once in each column.

Another representation is as a k×v Latin rectangle with v different symbols, having the properties that the sets of symbols used in the columns of the rectangle are the blocks of a square 2-(v,k,lambda) design.

A Youden "square" is equivalent to a 1-factorisation of the incidence graph of a square 2-design. Hall's marriage theorem implies that any square 2-design can be represented as a Youden "square".

Top

Z

zeta function of poset
The zeta function of a poset P on a set X is the function Z of two variables given by Its inverse is the Möbius function.

Top


Table of contents | Glossary | Topics | Bibliography | History

Peter J. Cameron
4 August 2006