Bruck–Ryser–Chowla theorem
Template:Short description The Bruck–Ryser–Chowla theorem is a result on the combinatorics of symmetric block designs that implies nonexistence of certain kinds of design. It states that if a (v, b, r, k, λ)Script error: No such module "Check for unknown parameters".-design exists with v = bScript error: No such module "Check for unknown parameters". (implying k = rScript error: No such module "Check for unknown parameters". and λ(v − 1) = k(k − 1)Script error: No such module "Check for unknown parameters".), then:
- if Template:Mvar is even, then k − λScript error: No such module "Check for unknown parameters". is a square;
- if Template:Mvar is odd, then the following Diophantine equation has a nontrivial solution:
- x2 − (k − λ)y2 − (−1)(v−1)/2 λ z2 = 0Script error: No such module "Check for unknown parameters"..
The theorem was proved in the case of projective planes by Script error: No such module "Footnotes".. It was extended to symmetric designs by Script error: No such module "Footnotes"..
Projective planes
In the special case of a symmetric design with λ = 1, that is, a projective plane, 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. Thus, v is always odd in this case.
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,[1] 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 matrix R with elements 0 and 1 satisfying
- R RT = (k − λ)I + λJScript error: No such module "Check for unknown parameters".
where Template:Mvar 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.
References
<templatestyles src="Reflist/styles.css" />
- ↑ Script error: No such module "citation/CS1".
Script error: No such module "Check for unknown parameters".
- Script error: No such module "citation/CS1".
- Script error: No such module "citation/CS1".
- Script error: No such module "citation/CS1".
- van Lint, J.H., and R.M. Wilson (1992), A Course in Combinatorics. Cambridge, Eng.: Cambridge University Press.
External links
- Script error: No such module "Template wrapper".