View source for User:Wcherowi/sandbox

{{User sandbox}}
<!-- EDIT BELOW THIS LINE -->

An example of a diff is {{Diff2|777838720|this}}.

[[File:Degenerate_planes_wec.svg | thumb|(Non-empty) Degenerate Projective Planes]]

<math>{d^2 \over dx^2}\operatorname{FANO}(x) = x \cdot \operatorname{KLEIN}(x)</math>

==References==

*{{Citation
   | last = Cherowitzo | first = William
   | title = Hyperovals in Desarguesian planes of even order
      | journal =Ann. Discrete Math.
      | volume=37
   | year =1988
    | pages= 87–94
  | mr = 931308 }}

*{{Citation |
   last1=Cherowitzo | first1 = W.
 |  title=Hyperovals in Desarguesian planes: an update
 |  journal=Discrete Math.
 |  volume=155
 |  year = 1996
 |  issue = 1-3
 |  pages =31–38
  | mr = 1401356 | doi= 10.1016/0012-365X(94)00367-R }}

*{{Citation | last1=Cherowitzo | first1=W. | title= α-flocks and hyperovals | mr= 1647703| year = 1998|  journal=Geom. Dedicata | volume = 72 | issue=3 |pages=221–246 |doi=10.1023/A:1005022808718 }}
*{{Citation
   | last1 = Cherowitzo | first1 = William E.
   | last2 = O'Keefe  | first2 = Christine M.
   | last3 = Penttila | first3 = Tim
   | title= A unified construction of finite geometries associated with ''q''-clans in characteristic 2
   | journal= Adv. Geom.
   | volume= 3
   | year = 2003
   | issue =1
   | pages= 1–21
    | mr= 1956585| doi= 10.1515/advg.2003.002}}

*{{Citation
   | last1 =Cherowitzo | first1 = W.
   | last2 =Penttila | first2 =  T.
   | last3 = Pinneri | first3 = I.
   | last4 = Royle | first4 = G. F.
  |  title=Flocks and ovals
   | journal= Geom. Dedicata
   | volume=60
   | year =1996
   | issue =1
   | pages= 17–37
   | mr= 1376478| doi= 10.1007/BF00150865 }}

*{{Citation
   | last=Glynn | first =  David G.
   | contribution =Two new sequences of ovals in finite Desarguesian planes of even order
      |title = (Combinatorial mathematics, X) Lecture Notes in Math.
      | volume=1036
      | publisher= Springer
      | place= Berlin
   |year= 1983
   |pages= 217–229
  | mr = 731584 }}   
			
*{{Citation
   |last = Hirschfeld | first = J. W. P.
   | title= Projective geometries over finite fields
   | edition= 2nd
   |publisher= The Clarendon Press Oxford University Press
   |place= New York
   |year=1998
   |pages= xiv+555
   |isbn= 0-19-850295-8
  | mr = 1612570 }}

*{{Citation
   | last1 = Korchmáros | first1 = G.
   | title= Collineation groups transitive on the points of an oval &#91;''q+2''-arc&#93; of S<sub>2,q</sub> for ''q'' even
   | language= Italian, with English summary
    | journal= Atti Sem. Mat. Fis. Univ. Modena
   | volume= 27
   | year=1978
    | issue =1
   | pages= 89–105 (1979)
  | mr = 551092 }}

*{{Citation
   |last=Korchmáros | first= G.
   |contribution=Old and new results on ovals in finite projective planes
      |title = (Surveys in combinatorics, 1991) London Math. Soc. Lecture Note Ser.
      |volume= 166
      |publisher=Cambridge Univ. Press
      |place=Cambridge
   |year=1991
   |pages= 41–72
  | mr = 1161460 }}

*{{Citation
   |  last1 =O'Keefe | first1 = Christine M.
   | last2 = Penttila | first2 =  Tim
  |  title= A new hyperoval in  PG(2,32)
   | journal=J. Geom.
  |  volume= 44
  |  year =1992
   | issue = 1-2
   | pages= 117–139
  | mr = 1169414 | doi= 10.1007/BF01228288}}
	
*{{Citation
   | last1 = Payne | first1 = Stanley E.
   | title= A new infinite family of generalized quadrangles
   | journal= Congressus Numerantium
   | volume= 49
   | year= 1985
   | pages= 115–128
   |mr= 830735}}

*{{Citation
   | last1 = Penttila | first1 = Tim
   | last2 = Pinneri  | first2 = Ivano
   | title=  Irregular hyperovals in  PG(2,64)
   | journal= J. Geom.
   | volume= 51
   | year=1994
   | issue= 1-2
   | pages= 89–100
  | mr = 1298348 | doi= 10.1007/BF01226860}}

*{{Citation
   | last1 = Penttila | first1 = Tim
   | last2 = Royle  | first2 = Gordon F.
   | title= Classification of hyperovals in  PG(2,32)
   | journal= J. Geom.
   | volume=50
   | year = 1994
   | issue = 1-2
   | pages= 151–158
    | mr = 1280636 | doi= 10.1007/BF01222672}}

*{{Citation
   | last1 = Penttila | first1 = Tim
   | last2 = Royle  | first2 = Gordon F.
   | title=  On hyperovals in small projective planes
   | journal= J. Geom.
   | volume= 54
   | year =1995
   | issue=1-2
   | pages= 91–104
  | mr = 1358279 | doi= 10.1007/BF01222857}}

*{{Citation
   | last1 = Segre  | first1 = Beniamino
   | title= Ovali e curve σ nei piani di Galois di caratteristica due.
   |   language= Italian
   | journal= Atti Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Nat. (8)
   | volume=32
   | year =1962
   | pages= 785–790
  | mr = 0149361 }}

*{{Citation
   | last1= Segre | first1 = B.
   | last2 = Bartocci | first2 = U.
   | title= Ovali ed altre curve nei piani di Galois di caratteristica due
   | language= Italian
   | journal=Acta Arith.
   | volume=18
   | year =1971
   | pages= 423–449
  | mr = 0295201}}

----
{{Wiktionary}}

[[Permutation#k-permutations of n|k-permutations]]

In [[Geometry]], '''collinearity''' is a property of a set of points, specifically, the property of lying on a single [[Line (geometry)|line]].<ref>The concept applies in any geometry {{harvtxt|Dembowski|1968 |loc=pg. 26}}, but is often only defined within the discussion of a specific geometry {{harvtxt|Coxeter|1969|loc=pg. 168}}, {{harvtxt|Brannan|Esplen|Gray|1998|loc=pg.106}}</ref> A set of points with this property is said to be '''collinear''' (often misspelled as, but should not be confused with, '''co-linear''' or '''colinear'''). The term ''collinear'' has been used, in a generalized sense, both in mathematics and in its application areas, as a [[synonym]] for "aligned" or the expression "in a row".

==Points on a line==

In most geometries a [[Line (geometry)|line]] is a [[Primitive notion|primitive (undefined) object type]]. A [[Mathematical model|model]] for the geometry supplies an interpretation of what points, lines and other object types are. This abstract point of view requires a richer vocabulary to describe its concepts than does [[Euclidean geometry]]. Thus, in [[spherical geometry]] where lines are represented in the standard model by great circles of a sphere, sets of collinear points are those which lie on the same great circle. Such points do not lie on a "straight line" in the Euclidean sense and would not be thought of as being "in a row". Of course, if the geometry is [[Euclidean geometry|Euclidean]], then collinear points will lie on a ''straight line''.

[[Linear map|Linear maps (or linear functions)]], as geometric maps, are those which preserve the collinearity property (that is, they map collinear point sets to collinear point sets) which is another way to say that they map lines to lines.

==Concurrency (plane dual)==
In various [[Plane (geometry)|plane geometries]] the notion of interchanging the roles of "points" and "lines" while preserving the relationship between them is called [[Duality (projective geometry)|plane duality]]. Given a set of collinear points, by plane duality we obtain a set of lines all of which meet at a common point. The property that this set of lines has (meeting at a common point) is called '''concurrency''', and the lines are said to be [[concurrent lines]]. Thus, concurrency is the plane dual notion to collinearity.

==Collinear vs. co-linear==
{{main|Colinear map}}
[[Duality (mathematics)|Duality]] has a broader meaning in mathematics than it has in just geometry. Often, the prefix "co-" is used to indicate that an object is the dual, in some sense, of some other object. Over time, the hyphen in this usage tends to disappear. Thus we find that in [[coalgebra]] theory, the notion of a [[colinear map]] (or co-linear map) is dual to the notion of a [[linear map]] for [[vector space]]s.

==Collinearity graph==
Given a [[partial geometry]] ''P'', where two points determine at most one line, a '''collinearity graph''' of ''P'' is a [[Graph (mathematics)|graph]] whose vertices are the points of ''P'', where two vertices are [[adjacent vertex|adjacent]] if and only if they determine a line in ''P''.

==Usage in statistics and econometrics==
{{main|Multicollinearity}}

In [[Statistics]], '''collinearity''' refers to a linear relationship between ''two'' [[explanatory variable]]s. Two variables are ''perfectly collinear'' if there is an exact linear relationship between the two. For example, <math> X_{1} </math> and <math> X_{2} </math> are perfectly collinear if there exist parameters <math>\lambda_0</math> and <math>\lambda_1</math> such that, for all observations ''i'', we have

: <math> X_{2i} = \lambda_0 + \lambda_1 X_{1i}. </math>

'''Multicollinearity''' refers to a situation in which two or more explanatory variables in a [[multiple regression]] model are highly linearly related. We have ''perfect multicollinearity'' if, for example as in the equation above, the correlation between two independent variables is equal to 1 or -1. In practice, we rarely face perfect multicollinearity in a data set. More commonly, the issue of multicollinearity arises when there is a strong linear relationship among two or more independent variables.

Mathematically, a set of variables is perfectly multicollinear if there exist one or more exact linear relationships among some of the variables.

==Usage in other areas==

===Antenna arrays===
[[Image:Antenna-tower-collinear-et-al.jpg|thumb|130px|An antenna mast with four colinear directional arrays.]]

In [[telecommunication]]s, a [[Collinear antenna array|collinear (or co-linear) antenna array]] is an [[tower array|array]] of [[dipole antenna]]s mounted in such a manner that the corresponding elements of each [[antenna (radio)|antenna]] are parallel and aligned, that is they are located along a common line or axis.

===Photography===
The [[collinearity equation]]s are a set of two equations, used in [[photogrammetry]] and [[remote sensing]] to relate [[coordinates]] in an image ([[sensor]]) plane (in two dimensions) to object coordinates (in three dimensions). In the photography setting, the equations are derived by considering the [[Projection (mathematics)|central projection]] of a point of the [[3D modeling|object]] through the [[Cardinal point (optics)#Principal planes and points|optical centre]] of the camera to the image in the image (sensor) plane. The three points, object point, image point and optical centre, are always collinear. Another way to say this is that the line segments joining the object points with their image points are all concurrent at the optical centre.<ref>It would be more mathematically natural to refer to these equations as the "concurrency equations", but this terminology is not used in the photogrammetry literature.</ref>

==Notes==
{{reflist}}

==References==
* {{citation|last=Brannan|first=David A.|last2=Esplen|first2=Matthew F.|last3=Gray|first3=Jeremy J.|title=Geometry |year=1998|publisher=Cambridge University Press|location=Cambridge| isbn = 0-521-59787-0 }}
*{{citation
| last=Coxeter
| first=H. S. M.
| title=Introduction to Geometry
| location=New York
| publisher=John Wiley & Sons
| year=1969
| isbn=0-471-50458-0}}
* {{Citation | last1=Dembowski | first1=Peter | title=Finite geometries | publisher=[[Springer-Verlag]] | location=Berlin, New York | series=[[Ergebnisse der Mathematik und ihrer Grenzgebiete]], Band 44 | mr= 0233275| year=1968 | isbn=3-540-61786-8}}

----

In [[combinatorics|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 (by [[Fisher's inequality]]). They have also been referred to as ''projective designs''<ref name="assmus" /> or ''square designs''.<ref>These alternatives have been used in an attempt to replace the term "symmetric", since there is nothing symmetric (in the usual meaning of the term) about these designs. The use of ''projective'' is due to P.Dembowski (''Finite Geometries'', Springer, 1968) in analogy with the most common example, projective planes, while ''square'' is due to P. Cameron (''Designs, Graphs, Codes and their Links'', Cambridge, 1991) and captures the implication of v = b on the incidence matrix. Neither term has caught on as a replacement and these designs are still universally referred to as ''symmetric''.</ref>

That is, a symmetric design is a (''v'',''b'',''r'',''k'',λ)-design with ''b'' = ''v'' and ''r'' = ''k''.  Either of the latter two equations implies the other.  In fact, the parameters of a symmetric design satisfy
:<math> \lambda (v-1) = k(k-1). </math>
Clearly, this imposes strong restrictions on ''v'', so the number of points is far from arbitrary.  The [[Bruck–Ryser–Chowla theorem]] gives necessary but not sufficient conditions.

A theorem of [[Herbert Ryser|Ryser]] gives a different combinatorial condition for an [[incidence structure]] to be symmetric.  If ''X'' is a ''v''-element set (the "point set"), and ''B'' is a ''v''-element class of ''k''-element subsets (called "blocks"), and any two blocks have exactly λ points in common, then (''X, B'') is a symmetric design.<ref>{{harvnb|Ryser|1963|loc = pp. 102-104}}</ref>

== Examples ==
Examples include finite [[projective plane]]s (λ = 1) and [[biplane geometries]] (λ = 2).

The '''order''' of a symmetric design is defined to be <math>N = k - \lambda</math>;<ref name="assmus">[http://www.jstor.org/stable/2321792 Nonexistence Proofs for Projective Designs], E. F. Assmus, Jr and David P. Maher, The American Mathematical Monthly, Vol. 85, No. 2 (Feb., 1978), pp. 110–112</ref> For example, an order ''N'' projective plane has <math>k = N+1;</math> the terminology is because the projective plane over a field of ''q'' elements has lines with <math>q+1</math> points.

==See also==
*[[Association scheme]]
*[[Block design]]
*[[Combinatorial design]]
*[[Design of experiments]]
*[[Analysis of variance|Variance analysis]]

==Notes==
{{reflist}}

==References==
* {{citation|last=Lander|first=E. S.|title=Symmetric Designs: An Algebraic Approach|year=1983|publisher=Cambridge University Press|location=Cambridge}}
* {{citation|last=Ryser|first=Herbert John|title=Combinatorial Mathematics (Carus Monograph #14)|year=1963|publisher=Mathematical Association of America|chapter=Chapter 8: Combinatorial Designs}}
*  {{cite book|last=Stinson|first=Douglas R.|title=Combinatorial Designs|year=2003|publisher=Springer-Verlag|location=New York|chapter=Chapter 2: Symmetric BIBDs|isbn=0-387-95487-2}}
*{{cite book
|author=Street, Anne Penfold and Street, Deborah J.
|title=Combinatorics of Experimental Design
|publisher=Oxford U. P. [Clarendon]
|year=1987
|pages=400+xiv
|isbn=0-19-853256-3
}}

* van Lint, J.H., and R.M. Wilson (1992), ''A Course in Combinatorics''.  Cambridge, Eng.: Cambridge University Press.

==External links==
*[http://batman.cs.dal.ca/~peter/designdb/ Design DB]: A database of combinatorial, statistical, experimental block designs
<!-- 
{{Experimental design|state=expanded}}

[[:Category:Design of experiments]]
[[:Category:Analysis of variance]]
[[:Category:Design theory]]
[[:Category:Set families]]

{{combin-stub}} -->

In [[projective geometry]], a '''von Staudt conic''' is the point set defined by all the absolute points of a polarity that has absolute points. In the [[real projective plane]] a von Staudt conic is a [[conic section]] in the usual sense. In more general [[projective plane]]s this is not always the case. [[Karl Georg Christian von Staudt]] introduced this definition in ''Geometrie der Lage'' (1847) as part of his attempt to remove all metrical concepts from projective geometry.

==Polarities==
A '''polarity''', {{pi}}, of a projective plane, {{mvar|''P''}}, is an involutory (i.e., of order two) [[bijection]] between the points and the lines of {{mvar|''P''}} that preserves the [[Incidence (geometry)|incidence relation]]. Thus, a polarity relates a point {{mvar|''Q''}} with a line {{mvar|''q''}} and, following [[Gergonne]], {{mvar|''q''}} is called the '''polar''' of {{mvar|''Q''}} and {{mvar|''Q''}} the '''pole''' of {{mvar|''q''}}.<ref>{{harvnb|Coxeter|1964|page=60}}</ref> An '''absolute point''' ('''line''') of a polarity is one which is incident with its polar (pole).<ref>{{harvnb|Garner|1979|page=132}}</ref><ref>Coxeter and several other authors use the term ''self-conjugate'' instead of absolute.</ref>

A polarity may or may not have absolute points. A polarity with absolute points is called a '''hyperbolic polarity''' and one without absolute points is called an '''elliptic polarity'''.<ref name=Coxeter72>{{harvnb|Coxeter|1964|page=72}}</ref> In the [[complex projective plane]] all polarities are hyperbolic but in the [[real projective plane]] only some are.<ref name=Coxeter72 />

A classification of polarities over arbitrary fields follows from the classification of sesquilinear forms given by Birkhoff and von Neumann.<ref>{{citation|first1=G.|last1=Birkhoff|first2=J.|last2=von Neumann|title=The logic of quantum mechanics|journal=Ann. Math.|volume=37|year=1936|pages=823–843}}</ref> Orthogonal polarities, corresponding to symmetric bilinear forms, are also called ''ordinary polarities'' and the locus of absolute points forms a non-degenerate conic (set of points whose coordinates satisfy an irreducible homogeneous quadratic equation) if the field does not have [[characteristic (field)|characteristic]] two. In characteristic two the orthogonal polarities are called ''psuedopolarities'' and in a plane the absolute points form a line.<ref>{{citation|first1=Susan|last1=Barwick|first2=Gary|last2=Ebert|title=Unitals in Projective Planes|publisher=Springer|year=2008|isbn=978-0-387-76364-4|pages=16–18}}</ref>

==Finite projective planes==
If {{pi}} is a polarity of a finite projective plane (which need not be desarguesian), {{mvar|''P''}}, of order {{mvar|''n''}} then the number of its absolute points (or absolute lines), {{mvar|''a''({{pi}})}} is given by:
: {{math|1=''a''({{pi}}) = ''n'' + 2''r''{{sqrt|''n''}} + 1}},
where {{mvar|''r''}} is a non-negative integer.<ref>{{citation|first=R.W.|last=Ball|title=Dualities of Finite Projective Planes|journal=Duke Mathematics Journal|volume=15|year=1948|pages=929–940}}</ref>
Since {{mvar|''a''({{pi}})}} is an integer, {{math|1=''a''({{pi}}) = ''n'' + 1}} if {{mvar|''n''}} is not a square, and in this case, {{pi}} is called an ''orthogonal polarity''.

R. Baer has shown that if {{mvar|''n''}} is odd, the absolute points of an orthogonal polarity form an [[oval (projective plane)|oval]] (that is, {{math|1=''n'' + 1}} points, no three [[collinear]]), while if {{mvar|''n''}} is even, the absolute points lie on a non-absolute line.<ref>{{citation|first=Reinhold|last=Baer|title=Polarities in Finite Projective Planes|journal=Bulletin of the American Mathematical Society|volume=52|year=1946|pages=77–93}}</ref>

In summary, von Staudt conics are not ovals in finite projective planes (desarguesian or not) of even order.<ref>{{harvnb|Garner|1979|page=133}}</ref><ref>{{harvnb|Dembowski|1968|pages=154–155}}</ref>

==Relation to other types of conics==
{{main|Non-Desarguesian plane#Conics}}

In a [[Pappus's hexagon theorem|pappian plane]] (i.e., a projective plane coordinatized by a [[field (algebra)|field]]), if the field does not have [[characteristic (field)|characteristic]] two, a von Staudt conic is equivalent to a [[Steiner conic]].<ref>{{harvnb|Coxeter|1964|page=80}}</ref> However, R. Artzy has shown that these two definitions of conics can produce non-isomorphic objects in (infinite) [[Moufang plane]]s.<ref>{{citation|first=R.|last=Artzy|title=The Conic y = x<sup>2</sup> in Moufang Planes|journal=Aequationes Mathematica|volume=6|year=1971|pages=30–35}}</ref>

==Notes==
{{reflist}}

==References==
* {{Citation | last1=Dembowski | first1=Peter | title=Finite geometries | publisher=[[Springer-Verlag]] | location=Berlin, New York | series=[[Ergebnisse der Mathematik und ihrer Grenzgebiete]], Band 44 | mr= 0233275| year=1968 | isbn=3-540-61786-8}}
* {{citation|first=Cyril W L.|last=Garner|title=Conics in Finite Projective Planes|journal=Journal of Geometry|year=1979|volume=12|issue=2|pages=132–138}}

==Further reading==
* {{citation|first=T.G.|last=Ostrom|chapter=Conicoids: Conic-like figures in Non-Pappian planes|editor1-first=Peter|editor1-last=Plaumann|editor2-first=Karl|editor2-last=Strambach|title=Geometry - von Staudt's Point of View|publication-date=1981|publisher=D. Reidel|pages=175–196|isbn=90-277-1283-2}}

==French quote==
Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long.

[[is:Samlínuleiki]]
[[pt:Colinearidade]]

==History==

The birth of the concept of constructible numbers is inextricably linked with the history of the three impossible compass and straightedge constructions: duplicating the cube, trisecting an angle and squaring the circle. The restriction of using only compass and straightedge in geometric constructions is often credited to [[Plato]] due to a passage in [[Plutarch]]. According to Plutarch, Plato gave the duplication of the cube (Delian) problem to [[Eudoxus of Cnidus|Eudoxus]] and [[Archytas]] and [[Menaechmus]], who solved the problem using mechanical means, earning a rebuke from Plato for not solving the problem using [[pure geometry]] (Plut., ''Quaestiones convivales'' [http://ebooks.adelaide.edu.au/p/plutarch/symposiacs/chapter8.html#section80 VIII.ii], 718ef). However, this attribution is challenged,<ref>{{harvnb|Kazarinoff|2003|loc=p. 28}}</ref> due, in part, to the existence of another version of the story (attributed to [[Eratosthenes]] by [[Eutocius of Ascalon]]) that says that all three found solutions but they were too abstract to be of practical value.<ref>{{citation|title=The Ancient Tradition of Geometric Problems|series=Dover Books on Mathematics|first=Wilbur Richard|last=Knorr|authorlink=Wilbur Knorr|publisher=Courier Dover Publications|year=1986|isbn=9780486675329|page=4|url=https://books.google.com/books?id=sgQS5BaTWl4C&pg=PA4}}.</ref> Since [[Oenopides]] (circa 450 BCE) is credited with two ruler and compass constructions, by [[Proclus]]&ndash; citing [[Eudemus of Rhodes|Eudemus]] (circa 370 - 300 BCE)&ndash;when other methods were available to him, has lead some authors to hypothesize that Oenopides originated the restriction. 

The restriction to compass and straightedge is essential in making these constructions impossible. Angle trisection, for instance, can be done in many ways, several known to the ancient Greeks. The [[Quadratrix of Hippias|Quadratrix]] of [[Hippias of Elis]], the [[conic section|conics]] of Menaechmus, or the marked straightedge ([[Neusis construction|neusis]]) construction of [[Archimedes]] have all been used and we can add a more modern approach via [[mathematics of paper folding|paper folding]] to the list.
 
Although not one of the classic three construction problems, the problem of constructing regular polygons with straightedge and compass is usually treated alongside them. The Greeks knew how to construct regular {{mvar|n}}-gons with {{math|1=''n'' = 2<sup>''h''</sup>, 3, 5}} (for any integer {{math|''h'' ≥ 2}}) or the product of any two or three of these numbers, but other regular {{mvar|n}}-gons eluded them. Then, in 1796, an eighteen-year-old student named [[Carl Friedrich Gauss]] announced in a newspaper that he had constructed a regular 17-gon with straightedge and compass.<ref>{{harvnb|Kazarinoff|2003|loc=p. 29}}</ref> Gauss' treatment was algebraic rather than geometric, in fact, he did not actually construct the polygon, but rather showed that the cosine of a central angle was a constructible number. The argument was generalized in his 1801 book ''[[Disquisitiones Arithmeticae]]'' giving the ''sufficient'' condition for the construction of a regular {{mvar|n}}-gon. Gauss claimed, but did not prove, that the condition was also necessary and several authors, notably [[Felix Klein]],<ref>{{citation|first=Felix|last=Klein|title=Famous Problems of Elementary Geometry|year=1956|origyear=1930|publisher=Dover|page=16}}</ref> attributed this part of the proof to him as well.<ref>{{harvnb|Kazarinoff|2003|loc=p. 30}}</ref> 

In a paper from 1837,<ref>{{Citation|first = P. L.|last = Wantzel|title = Recherches sur les moyens de reconnaître si un Problème de Géométrie peut se résoudre avec la règle et le compas |journal = Journal de Mathématiques Pures et Appliquées|year = 1837|volume = 1|issue = 2|pages = 366–372|url = http://visualiseur.bnf.fr/ConsulterElementNum?O=NUMM-16381&Deb=374&Fin=380&E=PDF}}</ref> [[Pierre Laurent Wantzel]] proved algebraically that the problems of
* doubling the cube, and
* trisecting the angle
are impossible to solve if one uses only compass and straightedge. In the same paper he also solved the problem of determining which regular polygons are constructible:
* a regular polygon is constructible [[if and only if]] the number of its sides is the product of a [[power of two]] and any number of distinct [[Fermat prime]]s (i.e. that the sufficient conditions given by Gauss are also necessary)

An attempted proof of the impossibility of squaring the circle was given by [[James Gregory (astronomer and mathematician)|James Gregory]] in ''Vera Circuli et Hyperbolae Quadratura'' (The True Squaring of the Circle and of the Hyperbola) in 1667. Although his proof was faulty, it was the first paper to attempt to solve the problem using algebraic properties of {{pi}}. It was not until 1882 that [[Ferdinand von Lindemann]] rigorously proved its impossibility, by extending the work of [[Charles Hermite]] and proving that {{pi}} is a [[transcendental number]].

==Combinatorics==

'''Combinatorics''', it has been said, "may rightly be called the [[mathematics]] of counting."<ref>{{harvnb|Mazur|2010|loc = pg. vii}}</ref> Few, however, would take this as a definition without a great deal of further amplification. Agreement on how this amplification should proceed is lacking and, according to {{harvtxt|Ryser|1963|loc=p. 2}}, a definition of this subject is difficult because it crosses so many mathematical subdivisions. In so far as an area can be described by the types of problems it addresses, combinatorics is involved with
* the ''enumeration'' (counting) of specified [[Mathematical structure|structures]], sometimes referred to as arrangements or configurations, associated with [[finite set]]s,
* the ''existence'' of such structures that satisfy certain given criteria,
* the ''construction'' of these structures, perhaps in many ways, drawing upon ideas from several areas of mathematics, and
* ''optimization'', finding the "best" structure or solution among several possibilities, be it the "largest",  "smallest" or satisfying some other optimality criterion.

Perhaps the easiest way to give an accounting of what combinatorics is, is to describe its subdivisions with their problems and techniques as is done below. However, even this approach is not completely satisfactory since it does not capture the purely historical reasons for including or not including some topics under the combinatorics umbrella.

Although primarily concerned with finite sets, some combinatorial questions and techniques can be extended to an infinite (specifically, [[Countable set|countable]]) but [[Discrete mathematics|discrete]] setting. This concentration on finite sets implies that techniques used in combinatorial arguments are more likely to be drawn from [[algebra]] than [[Mathematical analysis|analysis]].  


'''Combinatorics''' is a branch of [[mathematics]] concerning the study of finite or [[Countable set|countable]] [[Discrete mathematics|discrete]] [[Mathematical structure|structures]]. Aspects of combinatorics include counting the structures of a given kind and size ([[enumerative combinatorics]]), deciding when certain criteria can be met, and constructing and analyzing objects 
meeting the criteria (as in [[combinatorial design]]s and [[matroid]] theory), finding "largest", "smallest", or "optimal" objects ([[extremal combinatorics]] and [[combinatorial optimization]]), and studying combinatorial structures arising in an [[algebra]]ic context, or applying algebraic techniques to combinatorial problems ([[algebraic combinatorics]]).

______________________________________________
<blockquote>
'''Combinatorics''' is an area of [[mathematics]] primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of [[finite set|finite]] [[Mathematical structure|structures]].  It is closely related to many other areas of mathematics and has many applications ranging from [[logic]] to [[statistical physics]], from [[evolutionary biology]] to [[computer science]], etc.  

To fully understand the scope of combinatorics requires a great deal of further amplification, the details of which are not universally agreed upon.<ref>{{cite web|first=Igor|last=Pak|title=What is Combinatorics?|url= //www.math.ucla.edu/~pak/hidden/papers/Quotes/Combinatorics-quotes.htm|access-date=1 November 2017}}</ref> According to [[H. J. Ryser]], a definition of the subject is difficult because it crosses so many mathematical subdivisions.<ref>{{harvnb|Ryser|1963|loc=p. 2}}</ref> In so far as an area can be described by the types of problems it addresses, combinatorics is involved with
* the ''enumeration'' (counting) of specified structures, sometimes referred to as arrangements or configurations in a very general sense, associated with finite systems,
* the ''existence'' of such structures that satisfy certain given criteria,
* the ''construction'' of these structures, perhaps in many ways, drawing upon ideas from several areas of mathematics, and
* ''optimization'', finding the "best" structure or solution among several possibilities, be it the "largest",  "smallest" or satisfying some other optimality criterion.

[[Leon Mirsky]] has said: "combinatorics is a range of linked studies which have something in common and yet diverge widely in their objectives, their methods, and the degree of coherence they have attained."<ref>{{citation|first=Leon|last=Mirsky|title=Book Review|journal=Bulletin (New Series) of the American Mathematical Society|volume=1|year=1979|url=//www.ams.org/journals/bull/1979-01-02/S0273-0979-1979-14606-8/S0273-0979-1979-14606-8.pdf|pages=380-388}}</ref> One way to define combinatorics is, perhaps, to describe its subdivisions with their problems and techniques. This is the approach that is used below. This approach is not completely satisfactory since it does not capture the purely historical reasons for including or not including some topics under the combinatorics umbrella.  Although primarily concerned with finite systems, some combinatorial questions and techniques can be extended to an infinite (specifically, [[Countable set|countable]]) but [[Discrete mathematics|discrete]] setting. 

Combinatorial problems arise in many areas of [[pure mathematics]], notably in [[algebra]], [[probability theory]], [[topology]], and [[geometry]],<ref>Björner and Stanley, p. 2</ref> as well as in its many application areas. Many combinatorial questions have historically been considered in isolation, giving an ''ad hoc'' solution to a problem arising in some mathematical context. In the later twentieth century, however, powerful and general theoretical methods were developed, making combinatorics into an independent branch of mathematics in its own right. One of the oldest and most accessible parts of combinatorics is [[graph theory]], which by itself has numerous natural connections to other areas.  Combinatorics is used frequently in computer science to obtain formulas and estimates in the [[analysis of algorithms]].

A [[mathematician]] who studies combinatorics is called a ''{{dfn|combinatorialist}}'' or a ''{{dfn|combinatorist}}''.
</blockquote>
{{talkref}}

==Affine transformation==
[[File:Fractal fern explained.png|thumb|right|200px|An image of a [[Barnsley fern|fern]]-like [[fractal]] that exhibits affine [[self-similarity]]. Each of the leaves of the fern is related to each other leaf by an affine transformation. For instance, the red leaf can be transformed into both the dark blue leaf and any of the light blue leaves by a combination of reflection, rotation, scaling, and translation.]]

In [[geometry]], an '''affine transformation''', or an '''affinity''' (from the Latin, ''affinis'', "connected with") is an automorphism of an [[affine space]]. More specifically, it is a function mapping an affine space onto itself that preserves the dimension of any [[affine subspace]]s (meaning that it sends points to points, lines to lines, planes to planes, and so on) and also preserves the ratio of the lengths of parallel line segments. Consequently, sets of [[Parallel (geometry)|parallel]] affine subspaces remain parallel after an affine transformation. An affine transformation does not necessarily preserve angles between lines or distances between points, though it does preserve ratios of distances between points lying on a straight line.

If {{mvar|X}} is the point set of an affine space, then every affine transformation on {{mvar|X}} can be represented as the [[Composition of functions|composition]] of a linear transformation on {{mvar|X}} and a translation of {{mvar|X}}. Unlike a purely linear transformation, an affine transformation need not preserve the origin of the affine space. Thus, every linear transformation is affine, but not every affine transformation is linear.

Examples of affine transformations include [[Translation (geometry)|translation]], [[Scaling (geometry)|scaling]], [[Homothetic transformation|homothety]], [[Similarity transformation (geometry)|similarity transformation]], [[Reflection (mathematics)|reflection]], [[Rotation (mathematics)|rotation]], [[shear mapping]], and compositions of them in any combination and sequence.

Viewing an affine space as the compliment of a [[hyperplane at infinity]] of a [[projective space]], the affine transformations are the [[projective transformations]] of that projective space that leave the hyperplane at infinity invariant, restricted to the compliment of that hyperplane.

A generalization of an affine transformation is an '''affine map'''{{sfn|Berger|1987|p=38}} (or '''affine homomorphism''' or '''affine mapping''') between two affine spaces, over the same field {{mvar|k}}, which need not be the same. Let {{math|(''X'', ''V'', ''k'')}} and {{math|(''Z'', ''W'', ''k'')}} be two affine spaces with {{mvar|X}} and {{mvar|Z}} the point sets and {{mvar|V}} and {{mvar|W}} the respective associated vector spaces over the field {{mvar|k}}. A map {{math|''f'': ''X'' → ''Z''}} is an affine map if there exists a [[linear map]] {{math|''m''<sub>''f''</sub> : ''V'' → ''W''}} such that {{math|1=''m''<sub>''f''</sub> (''x'' − ''y'') = ''f'' (''x'') − ''f'' (''y'')}} for all {{mvar|x, y}} in {{mvar|X}}.{{sfn|Samuel|1988|p=11}}

==Definition==
Let {{math|(''X'', ''V'', ''k'')}} be an affine space of dimension at least two, with {{mvar|X}} the point set and {{mvar|V}} the associated vector space over the field {{mvar|k}}. A ''semiaffine transformation'' {{mvar|f}} of {{mvar|X}} is a [[bijection]] of {{mvar|X}} onto itself satisfying:{{sfn|Snapper|Troyer|1989|p=65}}
#If {{mvar|S}} is a {{math|''d''}}-dimensional [[affine subspace]] of {{mvar|X}}, {{math|''f'' (''S'')}} is also a {{math|''d''}}-dimensional affine subspace of {{mvar|X}}.
#If {{mvar|S}} and {{mvar|T}} are parallel affine subspaces of {{mvar|X}}, then {{math|''f'' (''S'') {{!}}{{!}} ''f'' (''T'')}}.
These two conditions express what is precisely meant by the expression that "{{mvar|f}} preserves parallelism".

These conditions are not independent as the second follows from the first.{{sfn|Snapper|Troyer|1989|p=66}} Furthermore, if the field {{mvar|k}} has at least three elements, the first condition can be simplified to: {{mvar|f}} is a [[collineation]], that is, it maps lines to lines.{{sfn|Snapper|Troyer|1989|p=69}}

If the dimension of the affine space {{math|(''X'', ''V'', ''k'')}} is at least two, then an '''affine transformation''' is a semiaffine transformation {{mvar|f}} that satisfies the condition: If {{math|''x'' ≠ ''y''}} and {{math|''p'' ≠ ''q''}} are points of {{mvar|X}} such that the line segments {{overline|{{mvar|xy}}}} and {{overline|{{mvar|pq}}}} are parallel, then{{sfn|Snapper|Troyer|1989|p=71}}
:<math>\frac{\|\overline{pq}\|}{\|\overline{xy}\|} = \frac{\|\overline{f(p)f(q)}\|}{\|\overline{f(x)f(y)}\|}.</math>

===Affine lines===
If the dimension of the affine space is one, that is, the space is an affine line, then any [[permutation]] of {{mvar|X}} would automatically satisfy the conditions to be a semiaffine transform. So, an affine transformation of an affine line is ''defined'' as any permutation {{mvar|f}} of the points of {{mvar|X}} such that if {{math|''x'' ≠ ''y''}} and {{math|''p'' ≠ ''q''}} are points of {{mvar|X}}, then{{sfn|Snapper|Troyer|1989|p=72}}
:<math>\frac{\|\overline{pq}\|}{\|\overline{xy}\|} = \frac{\|\overline{f(p)f(q)}\|}{\|\overline{f(x)f(y)}\|}.</math>

==Structure==
By the definition of an affine space, {{mvar|V}} acts on {{mvar|X}}, so that, for every pair {{math|(''x'', '''''v''''')}} in {{math|''X'' × ''V''}} there is associated a point {{mvar|y}} in {{mvar|X}}. We can denote this action by {{math|1={{vec|''v''}}(''x'') = ''y''}}. Here we use the convention that {{math|1={{vec|''v''}} = '''''v'''''}} are two interchangeable notations for an element of {{mvar|V}}.  By fixing a point {{mvar|c}} in {{mvar|X}} one can define a function {{math|''m''<sub>''c''</sub> : ''X'' → ''V''}} by {{math|1=''m''<sub>''c''</sub>(''x'') = {{vec|''cx''}}}}. For any {{mvar|c}}, this function is one-to-one, and so, has an inverse function {{math|''m''<sub>''c''</sub><sup>-1</sup> : ''V'' → ''X''}} given by {{math|1=''m''<sub>''c''</sub><sup>-1</sup>('''''v''''') = {{vec|''v''}}(''c'')}}. These functions can be used to turn {{mvar|X}} into a vector space (with respect to the point {{mvar|c}}) by defining:{{sfn|Snapper|Troyer|1989|p=59}}
:* <math>x + y = m_c^{-1}\left(m_c(x) + m_c(y)\right),\text{ for all } x,y \text{ in } X,</math> and
:* <math>rx = m_c^{-1}\left(r m_c(x)\right), \text{ for all } r \text{ in } k \text{ and } x \text{ in } X.</math>
This vector space has origin {{mvar|c}} and formally needs to be distinguished from the affine space {{mvar|X}}, but common practice is to denote it by the same symbol and mention that it is a vector space ''after'' an origin has been specified. This identification permits points to be viewed as vectors and vice versa.

For any [[linear transformation]] {{mvar|λ}} of {{mvar|V}}, we can define the function {{math|''L''(''c'', ''λ'') : ''X'' → ''X''}} by
:<math>L(c, \lambda)(x) = m_c^{-1}\left(\lambda (m_c (x))\right) = c + \lambda (\vec{cx}).</math>

Then {{math|''L''(''c'', ''λ'')}} is an affine transformation of {{mvar|X}} which leaves the point {{mvar|c}} fixed.{{sfn|Snapper|Troyer|1989|p=76,87}} It is a linear transformation of {{mvar|X}}, viewed as a vector space with origin {{mvar|c}}.

Let {{mvar|σ}} be any affine transformation of {{mvar|X}}. Pick a point {{mvar|c}} in {{mvar|X}} and consider the translation of {{mvar|X}} by the vector <math>\bold{w} = \overrightarrow{c \sigma (c)}</math>, denoted by {{math|''T''<sub>'''w'''</sub>}}. Translations are affine transformations and the composition of affine transformations is an affine transformation. For this choice of {{mvar|c}}, there exists a unique linear transformation {{mvar|λ}} of {{mvar|V}} such that{{sfn|Snapper|Troyer|1989|p=86}} 
:<math>\sigma (x) = T_{\bold{w}} \left( L(c, \lambda)(x) \right).</math>
That is, an arbitrary affine transformation of X is the composition of a linear transformation of {{mvar|X}} (viewed as a vector space) and a translation of {{mvar|X}}.

This representation of affine transformations is often taken as the definition of an affine transformation (with the choice of origin being implicit).{{sfn|Wan|1993|pp=19-20}}{{sfn|Klein|1948|p=70}}{{sfn|Brannan|Esplen|Gray|1999|p=53}}
****************
All Euclidean spaces are affine, but there are affine spaces that are non-Euclidean. In [[affine coordinates]], which include [[Cartesian coordinates]] in Euclidean spaces, each output coordinate of an affine map is a [[Linear function (calculus)|linear function (in the sense of calculus)]] of all input coordinates. Another way to deal with affine transformations systematically is to select a point as the [[Origin (mathematics)|origin]]; then, any affine transformation is equivalent to a [[linear transformation]] (of [[Position (vector)|position  vectors]]) followed by a [[Translation (geometry)|translation]].

==Cosets==

In [[mathematics]], specifically [[group theory]], a [[subgroup]] {{mvar|H}} of a [[group (mathematics)|group]] {{math|''G''}} may be used to decompose the underlying set of {{mvar|G}} into [[disjoint sets|disjoint]] equal size pieces called '''cosets'''. There are two types of cosets, ''left cosets'' and ''right cosets''. Cosets (of either type) have the same number of elements ([[cardinality]]) as does {{mvar|H}}. Furthermore, {{mvar|H}} itself is a coset, which is both a left coset and a right coset. The number of left cosets of {{math|''H''}} in {{math|''G''}} is equal to the number of right cosets of {{math|''H''}} in {{math|''G''}}. The common value is called the [[Index of a subgroup|index]] of {{math|''H''}} in {{math|''G''}} and is usually denoted by {{math|[''G'' : ''H'']}}.

Cosets are a basic tool in the study of groups; for example they play a central role in [[Lagrange's theorem (group theory)|Lagrange's theorem]] that states that for any [[finite group]] {{math|''G''}}, the number of elements of every subgroup {{math|''H''}} of {{mvar|''G''}} divides the number of elements of {{mvar|''G''}}. Cosets of a particular type of subgroup ([[normal subgroup]]) can be used as the elements of another group called a [[quotient group|quotient group or factor group]]. Cosets also appear in other areas of mathematics such as [[vector space]]s and [[error-correcting code]]s.

==Definition==
Let {{mvar|H}} be a subgroup of the group {{mvar|G}} whose operation is written multiplicatively (juxtaposition means apply the group operation). Given an element {{math|''g''}} of {{mvar|G}}, then a '''left coset''' of {{mvar|H}} in {{mvar|G}} is obtained by multiplying each element of {{mvar|H}} by the fixed element {{mvar|g}} (where {{mvar|g}} is the left factor). In symbols this is,  
:{{math|1=''gH'' = {&thinsp;''gh'' : ''h'' an element of ''H''&thinsp;}}}.
'''Right cosets''' are defined similarly, except that the element {{mvar|g}} is now a right factor, that is, 
:{{math|1=''Hg'' = {&thinsp;''hg'' : ''h'' an element of ''H''&thinsp;}}}.

If the group operation is written additively, as is often the case when the group is [[abelian group|abelian]], the notation used changes to {{math|''g'' + ''H''}} or {{math|''H'' + ''g''}}, respectively.

==Properties==

Because {{math|''H''}} is a subgroup, it contains the group's [[identity element]], with the result that the element {{math|''g''}} belongs to the coset {{math|''gH''}}. If {{math|''x''}} belongs to {{math|''gH''}} then {{math|1=''xH''=''gH''}}. Thus every element of {{math|''G''}} belongs to exactly one left coset of the subgroup {{math|''H''}}. 

Elements {{math|''g''}} and {{math|''x''}} belong to the same left coset of {{math|''H''}}, that is, {{math|1=''xH'' = ''gH''}} if and only if {{math|''g''<sup>-1</sup>''x''}} belongs to {{math|''H''}}. More can be said here. Define two elements of {{mvar|G}}, say {{mvar|x}} and {{mvar|y}}, to be equivalent with respect to the subgroup {{mvar|H}} if {{math|''x''<sup>-1</sup>''y''}} belongs to {{mvar|H}}. This is then an [[equivalence relation]] on {{mvar|G}} and the [[equivalence classes]] of this relation are the left cosets of {{mvar|H}}. As with any set of equivalence classes, they form a [[Partition (set theory)|partition]] of the underlying set.

Similar statements apply to right cosets.

If {{math|''G''}} is an [[abelian group]], then {{math|1=''gH'' = ''Hg''}} for every subgroup {{math|''H''}} of {{math|''G''}} and every element {{math|''g''}} of {{math|''G''}}. In general, given an element {{mvar|''g''}} and a subgroup {{math|''H''}} of a group {{mvar|''G''}}, the right coset of {{math|''H''}} with respect to {{math|''g''}} is also the left coset of the [[conjugate subgroup]] {{math|''g''<sup>−1</sup>''Hg''&thinsp;}} with respect to {{math|''g''}}, that is, {{math|1=''Hg'' = ''g''&thinsp;(&thinsp;''g''<sup>−1</sup>''Hg''&thinsp;)}}. 

A subgroup {{math|''N''}} of a group {{math|''G''}} is a [[normal subgroup]] of {{math|''G''}} if and only if for all elements {{math|''g''}} of {{math|''G''}} the corresponding left and right cosets are equal, that is, {{math|1=''gN'' = ''Ng''}}. Furthermore, the cosets of {{math|''N''}} in {{math|''G''}} form a group called the [[quotient group|quotient group or factor group]].

==An application from coding theory==
{{main|Standard array}}
A binary linear code is an {{mvar|n}}-dimensional subspace {{mvar|C}} of an {{mvar|m}}-dimensional vector space {{mvar|V}} over the binary field GF(2). As {{mvar|V}} is an additive abelian group, {{mvar|C}} is a subgroup of this group. Codes can be used to correct errors that can occur in transmission. When a ''codeword'' (element of {{mvar|C}}) is transmitted some of its bits may be altered in the process and the task of the receiver is to determine the most likely codeword that the corrupted ''received word'' could have started out as. This procedure is called ''decoding'' and if only a few errors are made in transmission it can be done effectively with only a very few mistakes. One method used for decoding uses an arrangement of the elements of {{mvar|V}} (a received word could be any element of {{mvar|V}}) into a [[standard array]]. A standard array is a coset decomposition of {{mvar|V}} put into tabular form in a certain way. Namely, the top row of the array consists of the elements of {{mvar|C}}, written in any order, except that the zero vector should be written first. Then, an element of {{mvar|V}} with a minimal number of ones that does not already appear in the top row is selected and the coset of {{mvar|C}} containing this element is written as the second row (namely, the row is formed by taking the sum of this element with each element of {{mvar|C}} directly above it). This element is called a [[coset leader]] and there may be some choice in selecting it. Now the process is repeated, a new vector with a minimal number of ones that does not already appear is selected as a new coset leader and the coset of {{mvar|C}} containing it is the next row. The process ends when all the vectors of {{mvar|V}} have been sorted into the cosets.

An example of a standard array for the 2-dimensional code {{mvar|C}} = {00000, 01101, 10110, 11011} in the 5-dimensional space {{mvar|V}} (with 32 vectors) is as follows:

:{| class="wikitable"
|-
! 00000
! 01101
! 10110
! 11011
|-
| 10000 
| 11101
| 00110
| 01011
|-
| 01000
| 00101
| 11110
| 10011
|-
| 00100 
| 01001
| 10010
| 11111
|-
| 00010 
| 01111
| 10100
| 11001
|-
| 00001
| 01100
| 10111
| 11010
|-
| 11000
| 10101
| 01110
| 00011
|-
| 10001
| 11100
| 00111
| 01010
|}

The decoding procedure is to find the received word in the table and then add to it the coset leader of the row it is in. Since in binary arithmetic adding is the same operation as subtracting, this always results in an element of {{mvar|C}}. In the event that the transmission errors occurred in precisely the non-zero positions of the coset leader the result will be the right codeword. In this example, if a single error occurs, the method will always correct it, since all possible coset leaders with a single one appear in the array.

[[Syndrome decoding]] can be used to improve the efficiency of this method. It is a method of computing the correct coset (row) that a received word will be in. For an {{mvar|n}}-dimensional code {{mvar|C}} in an {{mvar|m}}-dimensional binary vector space, a [[parity check matrix]] is an {{math|(''m'' − ''n'') × ''m''}} matrix {{mvar|H}} having the property that {{mvar|H}} {{vec|{{mvar|x}}}} = {{vec|0}} [[if and only if]] {{vec|{{mvar|x}}}} is in {{mvar|C}}. The vector {{mvar|H}} {{vec|{{mvar|x}}}} is called the ''syndrome'' of {{vec|{{mvar|x}}}}, and by [[linearity]], every vector in the same coset will have the same syndrome. To decode, the search is now reduced to finding the coset leader that has the same syndrome as the received word.<ref>{{harvnb|Rotman|2006|loc=p. 423}}</ref>

==Mutually orthogonal Latin squares (MOLS)==
A set of Latin squares of the same order such that every pair of squares are orthogonal (that is, form a Graeco-Latin square) is called a set of '''mutually orthogonal Latin squares''' and usually abbreviated as '''MOLS''' or '''MOLS(''n'')''' when the order is made explicit.

For example, a set of MOLS(4) is given by:<ref name=CD160>{{harvnb|Colburn|Dinitz|2007|loc=p. 160}}</ref>
:<math>\begin{matrix} 1&2&3&4 \\ 2&1&4&3\\ 3&4&1&2\\4&3&2&1 \end{matrix}\qquad\qquad \begin{matrix} 1&2&3&4 \\ 4&3&2&1 \\2&1&4&3 \\3&4&1&2 \end{matrix}\qquad\qquad\begin{matrix}1&2&3&4 \\3&4&1&2\\4&3&2&1\\2&1&4&3\end{matrix}.</math>
And a set of MOLS(5):<ref>{{harvnb|Colburn|Dinitz|2007|loc=p. 163}}</ref>
:<math>\begin{matrix}1&2&3&4&5 \\2&3&4&5&1\\3&4&5&1&2\\4&5&1&2&3\\5&1&2&3&4\end{matrix} \qquad\begin{matrix}1&2&3&4&5\\3&4&5&1&2\\5&1&2&3&4\\2&3&4&5&1\\4&5&1&2&3\end{matrix}
\qquad\begin{matrix}1&2&3&4&5\\5&1&2&3&4\\4&5&1&2&3\\3&4&5&1&2\\2&3&4&5&1\end{matrix}
\qquad\begin{matrix}1&2&3&4&5\\4&5&1&2&3\\2&3&4&5&1\\5&1&2&3&4\\3&4&5&1&2\end{matrix}.</math>
While it is possible to represent MOLS in a "compound" matrix form similar to the Graeco-Latin squares, for instance,
:{| class="wikitable"
|-
| 1,1,1,1
| 2,2,2,2
| 3,3,3,3
| 4,4,4,4
| 5,5,5,5
|-
| 2,3,5,4
| 3,4,1,5
| 4,5,2,1
| 5,1,3,2
| 1,2,4,3
|-
| 3,5,4,2
| 4,1,5,3
| 5,2,1,4
| 1,3,2,5
| 2,4,3,1
|-
| 4,2,3,5
| 5,3,4,1
| 1,4,5,2
| 2,5,1,3
| 3,1,2,4
|-
| 5,4,2,3
| 1,5,3,4
| 2,1,4,5
| 3,2,5,1
| 4,3,1,2
|}
for the MOLS(5) example above, it is more typical to compactly represent the MOLS as an orthogonal array (see below).

===Orthogonal array===
{{main|Orthogonal array}}
An '''orthogonal array''', OA({{mvar|k,n}}), of strength two and index one is an {{math|''n''<sup>2</sup> × ''k''}} array {{mvar|A}} ({{mvar|k}} ≥ 2 and {{mvar|n}} ≥ 1, integers) with entries from a set of size {{mvar|n}} such that within any two columns of {{mvar|A}}, every ordered pair of symbols appears in exactly one row of {{mvar|A}}.<ref name=Stinson>{{harvnb|Stinson|2004|loc=p. 140}}</ref>

An OA({{mvar|s}} + 2, {{mvar|n}}) is equivalent to {{mvar|s}} MOLS({{mvar|n}}).<ref name=Stinson />
For example, the MOLS(4) example given above and repeated here,
:<math>\begin{matrix} 1&2&3&4 \\ 2&1&4&3\\ 3&4&1&2\\4&3&2&1\\& L_1&& \end{matrix}\qquad\qquad \begin{matrix} 1&2&3&4 \\ 4&3&2&1 \\2&1&4&3 \\3&4&1&2 \\& L_2&&\end{matrix}\qquad\qquad\begin{matrix}1&2&3&4 \\3&4&1&2\\4&3&2&1\\2&1&4&3\\& L_3&&\end{matrix}</math>
can be used to form an OA(5,4):
:{| class="wikitable"
|-
! r
! c
! L<sub>1</sub>
! L<sub>2</sub>
! L<sub>3</sub>
|-
| 1
| 1
| 1
| 1
| 1
|-
| 1
| 2
| 2
| 2
| 2
|-
| 1
| 3
| 3
| 3
| 3
|-
| 1
| 4
|4
|4
|4
|-
| 2
| 1
| 2
| 4
| 3
|- 
|2 
|2
|1
|3
|4
|- 
|2
|3
|4
|2
|1
|- 
|2
|4
|3
|1
|2
|- 
|3
|1
|3
|2
|4
|- 
|3
|2
|4
|1
|3
|- 
|3
|3
|1
|4
|2
|- 
|3
|4
|2
|3
|1
|- 
|4
|1
|4
|3
|2
|- 
|4
|2
|3
|4
|1
|- 
|4
|3
|2
|1
|4
|- 
|4
|4
|1
|2
|3
|}
where the entries in the columns labeled ''r'' and ''c'' denote the row and column of a position in a square and the rest of the row for fixed ''r'' and ''c'' values is filled with the entry in that position in each of the Latin squares. This process is reversible; given an OA({{mvar|s}},{{mvar|n}}) with {{mvar|s}} ≥ 3, choose any two columns to play the ''r'' and ''c'' roles and then fill out the Latin squares with the entries in the remaining columns.

==Pencil (mathematics)==
{{about|a class of geometric objects|other uses|Pencil (disambiguation)}}
[[File:Apollonian circles.svg|thumb|The [[Apollonian circles]], two orthogonal pencils of circles]]

In [[geometry]], a '''pencil''' is a family of geometric objects with a common property, for example the set of lines that pass through a given point in a [[plane (mathematics)|plane]], or the set of circles that pass through two given points in a plane.

Although the definition of a pencil is rather vague, the common characteristic is that the pencil is completely determined by any two of its members. Analogously, a set of geometric objects that are determined by any three of its members is called a ''bundle''.<ref name=Young40>{{harvnb|Young|1971|loc=p. 40}}</ref> Thus, the set of all lines through a point in three-space is a bundle of lines, any two of which determine a pencil of lines. To emphasize the two dimensional nature of such a pencil, it is sometimes referred to as a ''flat pencil''.

Any geometric object can be used in a pencil. The common ones are lines, planes, circles, conics, spheres and general curves. Even points can be used. A '''pencil of points''' is the set of all points on a given line.<ref name=Young40 /> A more common term for this set is a ''range'' of points.

==Pencil of lines==
In a [[plane (geometry)|plane]], let {{mvar|u}} and {{mvar|v}} be two distinct intersecting lines. For concreteness, suppose that {{mvar|u}} has the equation, {{math|1=''aX'' + ''bY'' + ''c'' = 0}} and {{mvar|v}} has the equation {{math|1=''a'X'' + ''b'Y'' + ''c′'' = 0}}. Then
::{{math|1=λ{{mvar|u}} + μ{{mvar|v}} = 0}},
represents, for suitable scalars {{mvar|λ}} and {{mvar|μ}}, any line passing through the intersection of {{mvar|u}} = 0 and {{mvar|v}} = 0. This set of lines passing through a common point is called a '''pencil of lines'''.<ref>{{harvnb|Pedoe|1988|loc=p. 106}}</ref> The common point of a pencil of lines is called the ''vertex'' of the pencil.

In an [[affine plane]] with the [[parallel (geometry)#Reflexive variant|reflexive variant of parallelism]], a set of parallel lines forms an [[equivalence class]] called a '''pencil of parallel lines'''.<ref>{{harvnb|Artin|1957|loc=p. 53}}</ref> This terminology is consistent with the above definition since in the unique projective extension of the affine plane to a [[projective plane]] a single point ([[point at infinity]]) is added to each line in the pencil of parallel lines, thus making it a pencil in the above sense in the projective plane.

==Pencil of planes==
A '''pencil of planes''', is the set of planes through a given straight line in three-space, called the ''axis'' of the pencil. The pencil is sometimes referred to as a '''fan''' or a [[Sheaf of planes|sheaf]].<ref>{{harvnb|Woods|1961|loc=p. 12}}</ref> For example, the [[meridian (geography)|meridian]]s of the globe are defined by the pencil of planes on the axis of Earth's rotation.

Two intersecting planes meet in a line in three-space, and so, determine the axis and hence all of the planes in the pencil.

In higher dimensional spaces, a '''pencil of hyperplanes''' consists of all the hyperplanes that contain a subspace of codimension 2. Such a pencil is determined by any two of its members.

==Pencil of circles==
Any two circles in the plane have a common [[radical axis]], which is the line consisting of all the points that have the same [[power of a point|power]] with respect to the two circles. A '''pencil of circles''' (or '''coaxial system''') is the set of all circles in the plane with the same radical axis.<ref>{{harvnb|Johnson|2007|loc=p. 34}}</ref> To be inclusive, concentric circles are said to have the [[line at infinity]] as a radical axis.

There are five types of pencils of circles,<ref>Some authors combine types and reduce the list to three. {{harvtxt|Schwerdtfeger|1979|pp=8–10}}</ref> the two families of Apollonian circles in the illustration above represent two of them. Each type is determined by two circles called the ''generators'' of the pencil. When described algebraically, it is possible that the equations may admit imaginary solutions. The types are:
*An ''elliptic pencil'' (red family of circles in the figure) is defined by two generators that pass through each other in exactly ''two'' points. Every circle of an elliptic pencil passes through the same two points. An elliptic pencil does not include any imaginary circles.
*A ''hyperbolic pencil'' (blue family of circles in the figure) is defined by two generators that do not intersect each other at ''any'' point. It includes real circles, imaginary circles, and two degenerate point circles called the ''Poncelet points'' of the pencil. Each point in the plane belongs to exactly one circle of the pencil. 
*A ''parabolic pencil'' (as a limiting case) is defined where two generating circles are tangent to each other at a ''single'' point. It consists of a family of real circles, all tangent to each other at a single common point. The degenerate circle with radius zero at that point also belongs to the pencil.
*A family of concentric circles centered at a common center (may be considered a special case of a hyperbolic pencil where the other point is the point at infinity). 
*The family of straight lines through a common point; these should be interpreted as circles that all pass through the point at infinity (may be considered a special case of an elliptic pencil).<ref>{{harvnb|Johnson|2007|loc=p. 36}}</ref><ref>{{harvnb|Schwerdtfeger|1979|pp=8–10}}</ref>

===Properties===
A circle that is orthogonal to two fixed circles is orthogonal to every circle in the pencil they determine.<ref name=Jo37>{{harvnb|Johnson|2007|loc=p. 37}}</ref>

The circles orthogonal to two fixed circles form a pencil of circles.<ref name=Jo37 />

Two circles determine two pencils, the unique pencil that contains them and the pencil of circles orthogonal to them. The radical axis of one pencil consists of the centers of the circles of the other pencil. If one pencil is of elliptic type, the other is of hyperbolic type and vice versa.<ref name=Jo37 />

===Projective space of circles===

There is a natural correspondence between circles in the plane and points in three-dimensional [[projective space]]; a line in this space corresponds to a one-dimensional continuous family of circles, hence a pencil of points in this space is a pencil of circles in the plane.

Specifically, the equation of a circle of radius {{math|''r''}} centered at a point ({{math|''p'',''q''}}),
:<math> (x-p)^2 + (y-q)^2 = r^2,</math>
may be rewritten as
:<math> \alpha(x^2 + y^2) - 2\beta x - 2\gamma y + \delta = 0,</math>
where {{math|1=α&nbsp;=&nbsp;1, β&nbsp;=&nbsp;''p'', γ&nbsp;=&nbsp;''q'', and δ&nbsp;=&nbsp;''p''<sup>2</sup>&nbsp;+&nbsp;''q''<sup>2</sup>&nbsp;&minus;&nbsp;''r''<sup>2</sup>}}. 
In this form, multiplying the quadruple ({{math|α,β,γ,δ}}) by a [[Scalar (mathematics)|scalar]] produces a different quadruple that represents the same circle; thus, these quadruples may be considered to be [[homogeneous coordinates]] for the space of circles.<ref>{{harvnb|Pfeifer|Van Hook|1993}}.</ref> Straight lines may also be represented with an equation of this type in which {{math|1=α&nbsp;=&nbsp;0}} and should be thought of as being a degenerate form of a circle. When {{math|α&nbsp;≠&nbsp;0}}, we may solve for {{math|1=''p''&nbsp;=&nbsp;β/α, ''q''&nbsp;=&nbsp;γ/α}}, and {{math|1=''r''&nbsp;=√(''p''<sup>2</sup>&nbsp;+&nbsp;''q''<sup>2</sup>&nbsp;&minus;&nbsp;δ/α)}};  the latter formula may give {{math|1=''r''&nbsp;=&nbsp;0}} (in which case the circle degenerates to a point) or {{math|''r''}} equal to an [[imaginary number]] (in which case the quadruple ({{math|α,β,γ,δ}}) is said to represent an ''imaginary circle'').

The set of [[affine combination]]s of two circles ({{math|α<sub>1</sub>,β<sub>1</sub>,γ<sub>1</sub>,δ<sub>1</sub>}}), ({{math|α<sub>2</sub>,β<sub>2</sub>,γ<sub>2</sub>,δ<sub>2</sub>}}), that is, the set of circles represented by the quadruple
:<math> z(\alpha_1,\beta_1,\gamma_1,\delta_1)+(1-z)(\alpha_2,\beta_2,\gamma_2,\delta_2)</math>
for some value of the parameter {{math|''z''}},
forms a pencil; the two circles being the generators of the pencil.

=== Cardioid as envelope of a pencil of circles ===

[[File:Kardioide-kreise.svg|thumb|cardioid as envelope of a pencil of circles]]
{{main|Cardioid#Cardiod as envelope of a pencil of circles}}
Another type of pencil of circles can be obtained as follows. Consider a given circle (called the ''generator circle'') and a distinguished point P on the generator circle. The set of all circles that pass through P and have their centers on the generator circle form a pencil of circles. The [[Envelope (mathematics)|envelope]] of this pencil is a [[cardioid]].

==Pencil of conics==

A (non-degenerate) conic is completely determined by [[Five points determine a conic|five points]] in general position (no three collinear) in a plane and the system of conics which pass through a fixed set of four points (again in a plane and no three collinear) is called a '''pencil of conics'''.<ref>{{harvnb|Faulkner|1952|loc=pg. [https://books.google.com/books?id=3TwCIg_O2yMC&lpg=PP1&hl=cs&pg=PA64 64]}}.</ref> The four common points are called the ''base points'' of the pencil. Through any point other than a base point, there passes a single conic of the pencil. This concept generalizes a pencil of circles.

In a [[projective plane]] defined over an [[algebraically closed field]] any two conics meet in four points (counted with multiplicity) and so, determine the pencil of conics based on these four points. Furthermore, the four base points determine three line pairs ([[degenerate conic]]s through the base points, each line of the pair containing exactly two base points) and so each pencil of conics will contain at most three degenerate conics.<ref>{{harvnb|Samuel|1988|loc=pg. 50}}.</ref>

A pencil of conics can be represented algebraically in the following way. Let {{math|''C''<sub>1</sub>}} and {{math|''C''<sub>2</sub>}} be two distinct conics in a projective plane defined over an algebraically closed field {{math|''K''}}. For every pair {{math|''λ'', ''μ''}} of elements of {{math|''K''}}, not both zero, the expression:

::<math>\lambda C_1 + \mu C_2</math>

represents a conic in the pencil determined by {{math|''C''<sub>1</sub>}} and {{math|''C''<sub>2</sub>}}. This symbolic representation can be made concrete with a slight abuse of notation (using the same notation to denote the object as well as the equation defining the object.) Thinking of {{math|''C''<sub>1</sub>}}, say, as a ternary [[quadratic form]], then {{math|1=''C''<sub>1</sub> = 0}} is the equation of the "conic {{math|''C''<sub>1</sub>}}". Another concrete realization would be obtained by thinking of {{math|''C''<sub>1</sub>}} as the [[#Homogeneous coordinates|3×3 symmetric matrix]] which represents it. If {{math|''C''<sub>1</sub>}} and {{math|''C''<sub>2</sub>}} have such concrete realizations then every member of the above pencil will as well. Since the setting uses homogeneous coordinates in a projective plane, two concrete representations (either equations or matrices) give the same conic if they differ by a non-zero multiplicative constant.

==Pencil of plane curves==
More generally, a '''pencil''' is the special case of a [[linear system of divisors]] in which the parameter space is a [[projective line]]. Typical pencils of curves in the [[projective plane]], for example, are written as 

: <math> \lambda C + \mu C' = 0 \, </math>

where {{math|1=''C'' = 0}}, {{math|1=''C''′ = 0}} are plane curves.

==History==

Desargues is credited with inventing the term "pencil of lines" (''ordonnance de lignes'').<ref>{{citation|title=Earliest Known Uses of Some Words of Mathematics|url=http://jeff560.tripod.com/p.html|access-date=July 14, 2020}}</ref>

An early author of modern projective geometry [[G. B. Halsted]] introduced many terms, most of which are now considered to be archaic. For example, "Straights with the same cross are copunctal." Also "The aggregate of all coplanar, copunctal straights is called a ''flat-pencil''" and "A piece of a flat-pencil bounded by two of the straights as ''sides'', is called an ''angle''."<ref>[[G. B. Halsted]] (1906) [https://archive.org/details/syntheticproject00halsuoft Synthetic Projective Geometry], page 9, via [[Internet Archive]]</ref>

"The aggregate of all planes on a straight is called an ''axial-pencil''." 

==See also==
* [[Pencil beam]]
* [[Lefschetz pencil]]
* [[Matrix pencil]]

==Notes==
{{Reflist}}

==References==
*{{citation|first=E.|last=Artin|author-link=Emil Artin|title=Geometric Algebra|year=1957|publisher=Interscience Publishers}}
* {{citation|first=T. E.|last=Faulkner|title=Projective Geometry|edition=2nd|url=https://books.google.com/books?id=3TwCIg_O2yMC&printsec=frontcover|publisher=Oliver and Boyd|place=Edinburgh|year=1952}}
*{{citation|first=Roger A.|last=Johnson|title=Advanced Euclidean Geometry|year=2007|origyear=1929|publisher=Dover|isbn=978-0-486-46237-0}}
*{{citation|first=Dan|last=Pedoe|title=Geometry /A Comprehensive Course|year=1988|origyear=1970|publisher=Dover|isbn=0-486-65812-0}}
*{{citation
 | doi=10.2307/2691113
 | title=Circles, Vectors, and Linear Algebra
 | first1=Richard E. | last1=Pfeifer
 | first2=Cathleen | last2=Van Hook
 | journal=Mathematics Magazine
 | volume=66 | issue=2 | year=1993 | pages=75–86 | jstor=2691113}}
* {{citation|first=Pierre|last=Samuel|authorlink=Pierre Samuel|title=Projective Geometry|publisher=Springer-Verlag|place=New York|year=1988|series=[[Undergraduate Texts in Mathematics]] (Readings in Mathematics)|isbn=0-387-96752-4|url-access=registration|url=https://archive.org/details/projectivegeomet0000samu}}
*{{citation
 | last=Schwerdtfeger | first=Hans | authorlink = Hans Schwerdtfeger
 | title=Geometry of Complex Numbers: Circle Geometry, Moebius Transformation, Non-Euclidean Geometry
 | title-link = Geometry of Complex Numbers
 | publisher=Dover | year=1979 |origyear=1962| pages=8–10}}.
*{{citation|first=John Wesley|last=Young|year=1971|origyear=1930|title=Projective Geometry|publisher=Mathematical Association of America|series=Carus Monograph #4}}
*{{citation|first=Frederick S.|last=Woods|title=Higher Geometry / An introduction to advanced methods in analytic geometry|year=1961|origyear=1922|publisher=Dover}}

==External links==
*{{MathWorld|title=Pencil|urlname=Pencil}}

[[:Category:Algebraic geometry]]
[[:Category:Projective geometry]]