Bruck–Chowla–Ryser theorem
Encyclopedia
The Bruck–Ryser
–Chowla theorem is a result on the combinatorics
of block designs. It states that if a (v, b, r, k, λ)-design exists with v = b (a symmetric design
), then:
The theorem was proved in the case of projective planes in . It was extended to symmetric designs in .
, the theorem (which in this case is referred to as the Bruck–Ryser theorem) can be stated as follows: If a finite projective plane of order q exists and q is congruent to 1 or 2 (mod 4), then q must be the sum of two squares. Note that for a projective plane, the design parameters are v = b = q2 + q + 1, r = k = q + 1, λ = 1.
The theorem, for example, rules out the existence of projective planes of orders 6 and 14 but allows the existence of planes of orders 10 and 12. Since a projective plane of order 10 has been shown not to exist using a combination of coding theory and large-scale computer search, the condition of the theorem is evidently not sufficient for the existence of a design. However, no stronger general non-existence criterion is known.
R with elements 0 and 1 satisfying
where I is the v × v identity matrix and J is the v × v all-1 matrix. In essence, the Bruck–Ryser–Chowla theorem is a statement of the necessary conditions for the existence of a rational v × v matrix R satisfying this equation. In fact, the conditions stated in the Bruck–Ryser–Chowla theorem are not merely necessary, but also sufficient for the existence of such a rational matrix R. They can be derived from the Hasse–Minkowski theorem
on the rational equivalence of quadratic forms.
Herbert John Ryser
Herbert John Ryser was a professor of mathematics, widely regarded as one of the major figures in combinatorics in the 20th century...
–Chowla theorem is a result on the combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size , deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria ,...
of block designs. It states that if a (v, b, r, k, λ)-design exists with v = b (a symmetric design
Symmetric design
In combinatorial mathematics, a symmetric design is a block design with equal numbers of points and blocks. Thus, it has the fewest possible blocks given the number of points . They are also known as projective designs....
), then:
- if v is even, then k − λ is a square;
- if v is odd, then the following Diophantine equationDiophantine equationIn mathematics, a Diophantine equation is an indeterminate polynomial equation that allows the variables to be integers only. Diophantine problems have fewer equations than unknown variables and involve finding integers that work correctly for all equations...
has a nontrivial solution:- x2 − (k − λ)y2 − (−1)(v−1)/2 λ z2 = 0.
The theorem was proved in the case of projective planes in . It was extended to symmetric designs in .
Projective planes
In the special case of a symmetric design with λ = 1, that is, a projective planeProjective plane
In mathematics, a projective plane is a geometric structure that extends the concept of a plane. In the ordinary Euclidean plane, two lines typically intersect in a single point, but there are some pairs of lines that do not intersect...
, the theorem (which in this case is referred to as the Bruck–Ryser theorem) can be stated as follows: If a finite projective plane of order q exists and q is congruent to 1 or 2 (mod 4), then q must be the sum of two squares. Note that for a projective plane, the design parameters are v = b = q2 + q + 1, r = k = q + 1, λ = 1.
The theorem, for example, rules out the existence of projective planes of orders 6 and 14 but allows the existence of planes of orders 10 and 12. Since a projective plane of order 10 has been shown not to exist using a combination of coding theory and large-scale computer search, the condition of the theorem is evidently not sufficient for the existence of a design. However, no stronger general non-existence criterion is known.
Connection with incidence matrices
The existence of a symmetric (v, b, r, k, λ)-design is equivalent to the existence of a v × v incidence matrixIncidence matrix
In mathematics, an incidence matrix is a matrix that shows the relationship between two classes of objects. If the first class is X and the second is Y, the matrix has one row for each element of X and one column for each element of Y. The entry in row x and column y is 1 if x and y are related ...
R with elements 0 and 1 satisfying
- R RT = (k − λ)I + λJ
where I is the v × v identity matrix and J is the v × v all-1 matrix. In essence, the Bruck–Ryser–Chowla theorem is a statement of the necessary conditions for the existence of a rational v × v matrix R satisfying this equation. In fact, the conditions stated in the Bruck–Ryser–Chowla theorem are not merely necessary, but also sufficient for the existence of such a rational matrix R. They can be derived from the Hasse–Minkowski theorem
Hasse–Minkowski theorem
The Hasse–Minkowski theorem is a fundamental result in number theory which states that two quadratic forms over a number field are equivalent if and only if they are equivalent locally at all places, i.e. equivalent over every completion of the field...
on the rational equivalence of quadratic forms.