Jan.27 Intro: basic definitions and questions.

Illustrated by Fano plane Π_2 of 7 "points" and 7 "lines"
(diagram again; get properties from class, including):

-- Each line has 3 points
-- Any 2 points on a unique line

That makes it a 2-(7,3,1) design.  In general:

Def. 1.1 (p.1) A t-design with parameters (v,k,λ), a.k.a. a
t-(v,k,λ) design, is a pair \D = (X,\B) where

@ X is a set of v "points"
@ \B is a collection of k-element "blocks", each a subset of X
@ any t points contained in exactly λ blocks.

E.g. Pi_2 is also a 1-(7,3,3) design, and Petersen is 1-(10,2,3);
Trivial example: any collection of b blocks is a 0-(v,k,b) design.
Is Pi_2 a 3-design?

Even more trivial: If v<k or k<t then λ=0 (and if v<t then λ
is undefined); we don't care about such examples, nor indeed of the
example where λ=0 because \B is empty.

We do care very much about the special case

λ=1 (as with Π_2);

that's a

Steiner system (a.k.a. S(t,k,v)).

[further examples: the S(2,3,81) of the game "Set";
after Prop. 1.4 and its Corollaries: the S(3,4,8) obtained
by adding a point to Π_2 etc. -- more on this later in the term]

Aim: describe all designs, up to equivalence.

But can be done, with interesting results, for many particular cases,
some of which will appear shortly.  E.g. 2-(7,3,1) is unique.

Constructing t-designs gets harder as t increases, with the exception of:

Only slightly less trivial: the set of all Bin(v,k) subsets is
a trivial design: S_v acts transitively on t-element subsets,
so each is contained in the same number (namely Bin(v-t,k-t)).
That's a complete block design; we're interested in incomplete ones.
The t-design condition says that the set of blocks is "balanced" among
all elements, pairs, ..., t-subsets.  This is sometimes called a

BIBD: balanced incomplete block design.

(At least when t≥2 -- t=1 is still too easy to satisfy without
additional conditions, e.g. k=2 just gives regular graphs;
more on that soon.)

Jan.29 Duality and the incidence matrix of a design; Fisher's theorem

Reminders: first HW due next Monday;
informal lecture notes on course webpage

[pep talk about duality in projective planes and elsewhere]

Def. 1.10 (p.4) Incidence matrix of design (or even t-structure):
columns ↔ points
rows ↔ blocks
entries = 1 if point in block, 0 else.

Example (the RED BUOY description of Π_2):

B D E O R U Y
BUD  1 1 0 0 0 1 0
BYE  1 0 1 0 0 0 1
DOE  0 1 1 1 0 0 0
DRY  0 1 0 0 1 0 1
ORB  1 0 0 1 1 0 0
RUE  0 0 1 0 1 1 0
YOU  0 0 0 1 0 1 1

warning: depends on order of X and \B; also, some authors use a
definition with rows and columns switched, resulting in transpose of
our matrix.

1.11 (p.4), generalized slightly:

If it's a t-(v,k,λ) design then:

@ each block has k points ⇔ each row dots with all-1's column to k
⇔ M * (all-1's column) = k*(all-1's column)

@ if t≥1: each point is in r=λ_1 blocks ⇔ each column dots with
all-1's row to r ⇔ (all-1's row) * M = r*(all-1's row)

The fact that rows and columns are interchangeable so far suggests
defining the dual \D\T of a design \D = (X,\B) [see p.5, I'm changing
the text's order of exposition] so that the incidence matrix of \D\T
is the transpose of the incidence matrix of \D (as the notation suggests).
Morally speaking \D\T is (\B,X).  Since X does not consist of subsets of \B,
we interpret this as

\D\T = (X\T, \B\T) = (\B, {beta_x : x \in X}) where

\beta_x := {B \in \B: x \in B}

NB in general this might be only a "structure", not a design.
A structure \D is a design if the adjacency matrix has no
repeated rows, and \D\T is a design if there are no repeated columns.
So, for instance, consider

1100
1100
0011
0011

(\D and \D\T are 1-(4,2,2) structures, both isomorphic with the
regular graph-with-multiplicity @=@ @=@), and

110000
001100
000011

(\D is the 1-(6,2,1) design @-@ @-@ @-@, and \D\T is a 1-(3,1,2)
structure; that's a degenerate example because it's twice the
complete design -- can you find a nondegenerate example?)
In any case the dual of a 1-structure is a 1-structure, and
-- as ought to be the case with a notion of duality --

(\D\T)\T is canonically isomorphic with \D.

OK: what if we actually have a 2-design, such as \Pi_2?  Check that
for \Pi_2 the dual \D\T is also a 2-design, indeed with the same parameters.
This isn't always true, but it does suggest something that is.  Let's see:

@ if also t=2: each pair of points in λ blocks ⇔ any two
*different* columns have dot product λ.  The dot product of a
column with itself is again r, so ...

1.11 iii) M\T M = (r-λ) I + λ J  (v*v matrices)

where J = all-1's matrix. (Likewise if t≥2, replacing λ by λ_2.)
Note that this excludes repeated columns unless r = λ, which is
(not surprisingly) impossible except in trivial cases as we soon see.

The first two properties in (1.11) can also be expressed in terms of J:

1.11 ii)  M J = k J (v*v matrices)
1.11 i)   J M = r J (b*b matrices)

That might seem like just bookkeeping, but (iii) lets us actually
do nontrivial things using linear algebra (and then (i) and (ii)
will help too).  We need:

Lemma 1.12 (p.4): for the identity and all-1 matrices I,J of order n
we have

det(xI+yJ) = (x+ny) x^(n-1).

In particular, xI+yJ has rank n iff x and x+ny are nonzero.

[NB it's a priori a homogeneous polynomial of degree n; also
det(I+yM) is a polynomial in y of degree rank(M), and since J has rank 1
it had to be linear in y.]

Pf.: xI+yJ symmetric ⇔ spectral theorem applies (orthonormal
eigenvectors, det = product of eigenvalues).  All-1's has eigenvalue x+ny
and its orth. complement has dimension n-1 and eigenvalue x, etc.

[Yes, Lemma 1.12 can also be obtained directly by row operations;
but we'll soon make similar applications of the spectral theorem
in settings where a more direct approach is not available.]

In our case x+ny is certainly nonzero: it's r+(v-1)λ and both terms
are positive.  What about x=r-λ?  Well we saw that

(1.9)  r (k-1) = (v-1) λ

so,

(r-λ) (k-1) = (v-1) λ - (k-1) λ = (v-k) λ

so as long as k>1 (remember we must have k≥t for nontriviality)
and k<v (it's not just the complete design (X,{X})) we have r-λ > 0.
Hence:

Theorem 1.14 (p.5) [Fisher's inequality] In a nonempty 2-design with k<v
we have b≥v.

Proof: We have written a nondegenerate v*v matrix as a product of two
matrices each of rank at most b.  QED

What if equality holds?  First of all M is a square matrix, and (1.8) bk=vr
means that b=v iff k=r, so (1.11) means M and J commute.  But then M
commutes with M\T M since that's a linear combination of I and J, so
M M\T M = M\T M M, and since M is invertible we conclude M M\T = M\T M,
which is already known (1.11 again) to be (r-λ) I + λ J.
But this means that every two *blocks* have λ points in common!
That in turn means that \D\T is also a 2-design.  To summarize:

Theorem 1.15 (p.5) In a 2-design with k<v, TFAE:
(a) b=v
(b) r=k
(c) any two blocks have λ points in common
(d) any two blocks have a constant number of points in common.
[(e) \D\T is a 2-design.]

Pf.  a ⇔ b  follows from bk=rv (b/v=r/k).  We've just shown that
these imply c, and c ⇒ d ⇔ e  are obvious.  Finally for  e ⇒ a,
if \D\T is a 2-design then it satisfies the hypotheses of Fisher's
inequality (notably the condition k<v becomes r<b, which is equivalent
because bk=rv), so we may apply Fisher to both \D and \D\T to get
b ≥ v ≥ b,  whence b=v.  QED

A 2-design satisfying these conditions is said to be square
(because the incidence matrix is square; again the book warns that
the literature also contains other terminology for this).  You might
find problem 2 on the homework easier now.

It's harder as t increases because

Cor. 1.6 (p.3): a t-(v,k,λ) design is automatically also an
s-(v,k,λ_s) design for each s \leq t, with λ_s given by:

Prop. 1.4: If S is a subset of X with s = |S| ∈ [0,t] then
the number of blocks containing S is

λ_s := (Bin(v-s,t-s) / Bin(k-s,t-s)) λ.

Proof: double count pairs (B,T) where B is a block and
S \subset T \subset X with |T|=t.

Cor. 1.7: If a t-(v,k,λ) design exists then

Bin(k-s,t-s)  |  Bin(v-s,t-s) λ

for each s=0,1,...,t-1.

Example:

b := λ_0 = # blocks and
r := λ_1 = # blocks containing a given point [if t>0...]

satisfy

b k = v r.

Likewise if t=2 then we have

r = (Bin(v-1,1) / Bin(k-1,1)) λ = (v-1)/(k-1) λ

so  (v-1)λ = r(k-1)  [p4, (1.9)].

Even for λ=1, infinitely many examples known with t=2,3
but only finitely many for 4,5 (we'll see all the "classical" ones)
and none known with 6 or more!  [Update: though thanks to Keevash,
as of 2014 we know they exist.]

What does "up to equivalence" mean?

p.3 isomorphism from (X,B) to (X',B'): bijection f: X → X'
that takes B to B'.

Automorphism of (X,B) = isomorphism (X,B) → (X,B);
these form a group.

If G is t-transitive, or even transitive on t-subsets, then
(X,B) is automatically a t-design.  Many t-designs explained
this way, including Π_2 (and Petersen).

Finally, as promised: why don't we work with "designs with multiplicity",
a.k.a. "t-structures" (see p.1)?  Even the bridges-of-Königsberg graph
has multiplicity...  But again it's too easy to construct t-structures:

Prop. 1.2 (p.2): If k ∈ (t,v-t) [that is, if t < k < v-t]
then there is a t-(v,k,λ) structure for some λ,
in which not every k-set is incident with a block.

Proof: more variables than Q-linear equations; clear denominators and
add the smallest multiple of the all-1's vector.

[another way to say this: the variables are the multiplicities m_B of the
Bin(v,k) k-subsets, plus λ itself; the equations are the Bin(v,t)
conditions that each t-subset be contained in λ blocks counted
with multiplicity; so there's a >1 dimensional space of solutions,
which includes the vector x_1 where all the m_B equal 1.  Let x_2
be an independent vector; multiply by a common denominator to get
all the coordinates of x_2 to be integers; and subtract m*x_1, where
m is the minimal coordinate m_B of x_2, to get a nonzero solution where
all the m_B are nonnegative and at least one vanishes.]

[The vector space of solutions with λ=0 may still be of interest
for the construction of irreducible representations of the symmetric group
of permutations of v objects, but that's a topic for a different kind of
Math 155r.]

Feb.1 More about square designs: BRC theorem; Fisher re-proved;
duality and polarity.

Recall: Fisher's inequality (1.14) says a 2-(v,k,λ) design with
k<v has b \geq v; proved using

1.11 iii) M\T M = (r-λ) I + λ J  (v*v matrices)

and the fact that the RHS is invertible.  We showed that equality holds
if the dual design \D\T is also a 2-design, and noted that in that case
M is a square matrix.  A further necessary condition (part of the
project of deciding which parameters v,k,λ are realized by a t-design):

Theorem 1.21 (Bruck-Ryser-Chowla; p.7)  Suppose there exists a
square 2-(v,k,λ) design.  Then:

i) v even ⇒ k-λ is a square
[NB *not* "k is square"; that's a typo for "n is square"
where CvL define n=k-λ]

ii) v odd ⇒ there exist nonzero integers x,y,z such that
z^2 = (k-λ) x^2 + (-1)^((v-1)/2) λ y^2.

As you can imagine from the statement, (i) is much easier.
We'll show only that case; you might base your final project on
one or more of the known proofs of (ii), about which we'll make some
remarks to give a bit of context to that strange-looking condition
(but you still needn't memorize it for an exam).

Proof of (i):  Recall that  det(xI+yJ) = (x+yn) x^(n-1) [Lemma 1.12].
If xI+yJ = M\T M for a square matrix M then

det(xI+yJ)  =  det M\T  det M  =  det M  det M  = (det M)^2

and since M is an integer matrix det(M) is an integer.  So, a
necessary condition is that det(xI+yJ) be a square.  Now in our case
n = v,  and  x + yn = r-λ + vλ = r + (v-1) λ, and we already
saw (1.9) that (v-1) λ = r(k-1) so it's rk which for a square design
is k^2 (recall 1.15b).  So  det(M) = k (k-λ)^((v-1)/2), which is
an integer iff v is odd or k-λ is a square.  So if v is even then
k-λ must be a square, as claimed.

As for (ii): the rows are vectors in Z^v whose Gram matrix of
inner products is the invertible matrix  (r-λ) I + λ J.
So a necessary condition is that such vectors exist in Q^v,
which is to say that the quadratic form with Gram matrix
(r-λ) I + λ J  be equivalent to the standard form with
Gram matrix I.  A necessary condition is square determinant,
condition (ii).  The names BRC are not in alphabetical order
because BR proved it in 1949 for the special case λ=1 of
square Steiner systems (= projective planes of order q=k-1),
and Chowla generalized in 1950 to arbitrary λ.
That condition can in turn be checked "locally" modulo powers of
primes dividing k-λ and λ; for instance if λ=1, so
(v,k) = (q^2+q+1, q+1), we find that (-1)^((v-1)/2) = (-1)^((q^2+q)/2)
is 1 if q is 0 or 3 mod 4, and -1 if q is 1 or 2 mod 4; in the former
case the condition is automatically satisfied (let x=0, y=z) and
in the latter we ask that q = (y/z)^2 + (x/z)^2, which by Fermat
is equivalent to q = sum of two integer squares and can be checked from
the prime factorization of q.  This condition is necessary but
not sufficient (q=10, apparently still the only known case where BRC
allows parameters that have been proved impossible).

We can re-prove Fisher without linear algebra as a special case of:

Thm. 1.20 (p.6): let B be a block of a 2-(v,k,λ) design.
Then there are at least  k(r-1)^2 / ((k-1)(λ-1) + (r-1))
blocks intersecting B nontrivially [other than B itself];
equality ⇔ every block other than B meets B in a constant
number of points, in which case that constant is 1 + (k-1)(λ-1)/(r-1).

[Note that for a square design, k=r simplifies that constant to λ
as expected.  To recover Fisher, show that the lower bound of Thm. 1.20
is at least b-1 using (1.8) bk=vr and (1.9) r(k-1)=(v-1)λ, see top
of page 7.]

Happily it's not the specific formula that we'll use (we won't cover
chapter 7) -- you certainly need not memorize that result for the exam!
-- but you should know the technique (called the "variance trick" by the
textbook's authors): obtain the first few "moments" sum(1), sum(i), sum(i^2)
(usually by some kind of double counting) to get at the mean and variance,
which must be positive (in other words, apply Cauchy-Schwarz); since we have
only a 2-design we can get only the zeroth, first, and second moment, but
in other contexts one may be able to calculate an exploit higher moments too.

Proof of Thm. 1.20: For a block B' other than B, let i(B') be the size of
the intersection of B with B'.  Let d ≤ b-1 be the number of B' for which
i(B') > 0, so the intersection is nonempty.  We'll find the sum of
1, i, i^2 over those B' to get the mean and variance.   (The book lets
n_i be the number of solutions of i(B)=i, and finds the sum over i of
n_i, in_i, and (i^2-i)n_i; that's the same as summing 1, i, i^2-i,
and thus yields the sum of 1, i, i^2 respectively).

@ The sum of 1 is of course d.
@ The sum of i is the number of pairs (B',x) with x contained in both B and B';
there are k choices of x, each giving r-1 choices of B', so the sum is k(r-1).
@ Likewise the sum of i^2-i is the number of triples (B',x,y) where x,y are
distinct elements of both B and B', so their number is (k^2-k)(λ-1).

Thus the sum of i^2 is (k^2-k)(λ-1) + k(r-1) = k ((k-1)(λ-1) + (r-1)).
Now Cauchy-Schwarz says

sum(1)sum(i^2) ≥ sum(i)^2,  with equality iff all i are equal.

Therefore  d = sum(1) ≥ sum(i)^2 / sum(i^2),  which is exactly what
we claimed; in the case of equality, the constant value of i is
sum(i^2) / sum(i) = k ((k-1)(λ-1) + (r-1)) / (k (r-1)),
which is exactly 1 + (k-1)(λ-1)/(r-1) as claimed.  QED

Duality and polarity of a square design (1.18, 1.19 on page 6):
If \D is a square design that is isomorphic with the dual design \D\T,
then we can call \D self-dual, and any such isomorphism is
called a duality of \D; explicitly, it consists of bijections
\sigma: X → \B,  \tau: \B → X such that x is in B iff
\tau(B) is in \sigma(x).  [NB the book uses exponential notation
B^\tau, x^\sigma, which switches the order of composition of bijections;
also there's a typo in the first display of p.6: each \B (the collection
of blocks) should be plain B (a single block of \D).]  In terms of
the incidence matrix M,  \sigma and \tau switch rows and columns;
alternatively, they are a permutation of the rows and columns
that takes M to M\T.  Composing two dualities (\sigma,\tau) and
(\sigma',\tau') yields an automorphism (\tau' \sigma, \sigma' \tau)
of \D = (X,\B); also, a duality can be composed from either side with
an automorphism of \D to yield another duality.  So the dualities of a
self-dual design \D extend Aut(\D) to a bigger group containing Aut(\D)
with index 2.

A duality that's an involution in this group, i.e. for which
\tau\sigma is the identity permutation of X (and thus \sigma\tau
is the identity permutation of B), is called a polarity.
In terms of M, there's a polarity iff we can permute the rows
(and columns), to get a symmetric matrix -- this makes the n-th block
the image under \sigma of the n-th point.  For example, Π_2 is polar
(HW2 hint!):

1 1 0 1 0 0 0
1 0 1 0 0 0 1
0 1 0 0 0 1 1
1 0 0 0 1 1 0
0 0 0 1 1 0 1
0 0 1 1 0 1 0
0 1 1 0 1 0 0

Feb.3 & 5 Important examples of designs I:
projective planes and higher-dimensional projective spaces

Usually when we introduce a new kind of mathematical structure
we give a selection of important examples, and transformations that
construct new examples from known ones.  But for t-designs,
so far we've given several necessary conditions on the parameters
but precious few examples with t>1 -- only Π_2, a couple of
similar designs relegated to the first problem set, and the
3-(8,4,1) design constructed from Π_2 -- and no
transformations except for the facts that a t-design is also an
s-design for each s<t, and the dual of a square 2-design is a
square 2-design, which have yet to give us any new examples.
Today we remedy this by introducing the first of several batches of
important examples of 2-designs: algebraic projective spaces, including
notably projective planes; and square designs coming from Hadamard matrices.

While there's (still?) only one example is known of parameters for
a square 2-design that pass the BRC condition (1.21, p.7) but
do not arise for any design, there's also (still!?) no value of
λ known to arise infinitely often -- except for λ=1.
A square 2-design with λ=1 (i.e. a square 2-design that's also
a Steiner 2-system) is called a (combinatorial) projective plane,
and its blocks are called lines, because (as with the prototypical
example of Π_2) any two of its points determine a unique line,
and any two lines meet in a unique point.  In a square 2-(t,k,1) design
let k=n+1, so t=n^2+n+1, either using r(k-1)=(v-1)λ or directly
because a point determines n+1 lines each of which contains n further
points and no two of these n(n+1) points coincide [that's actually
a special case of our argument for r(k-1)=(v-1)λ].  We then say that
the projective plane has order n; e.g. Π_2 has order 2.  (Not order
n+1 as might be expected; we already saw that n=r-λ is an important
parameter in Fisher's inequality (where it was the coefficient of I in
M\T M = (r-λ I) + λ J) and in the BRC theorem, and this is
even more decisively the case for projective planes.

n=1 is possible but yields the complete 2-(3,2,1) design.  For
n=2, n=3, n=4, and n=5 we shall show that there is a unique
projective plane of order n and determine its automorphism group.
These will all be special cases of the following construction, and
applicable whenever n is a prime power, producing a projective plane with
more than n^8 automorphisms.  Warning: for some such n it is known
that there are non-isomorphic projective planes of order n.
(It seems that the first example is for n=9, when there are four
such planes [Lam, Kolesova, and Theil 1988, computer-assisted]; see
http://www.uwyo.edu/moorhouse/pub/planes .)  It is a famous open
question whether there is a finite projective plane whose order is
not a prime power; the first open case is n=12 (BRC disposes of 6
but not 10).

Construction of Π_2 that exhibits all its automorphisms.
We claimed that there are 168 automorphisms, forming a group
isomorphic with GL_3(Z/2Z).  [Recall the formula for the size of
GL_n(k) for a finite field k; here that gives (8-1)(8-2)(8-4)
which indeed is 7*6*4 = 168.]  So, let k be the 2-element field Z/2Z,
and let V be a 3-dimensional space over k.  It has 2^3 = 8 vectors,
including zero.  So, the points X of Π_2 will be the 7 nonzero vectors,
and the lines will be triples {x,y,z} of vectors with x+y+z = 0.
Check by explicit identification that this is equivalent with our
initial picture of Π_2.  Because the definition uses only
the vector space structure, any automorphism of V yields the same
structure, and the group of these automorphisms is GL_3(Z/2Z).

Proof of uniqueness of the 2-(7,3,1) design: as is often the case
with highly symmetric combinatorial structures S, we can identify
any other structure S' with the same parameters with S even if we
specify some parts p, p' of S and S' respectively and require tha
the identification take p' to p.  Taking S'=S, this then shows that
the automorphism group Aut(S) "acts transitively on the p-s",
and lets us count the automorphisms.  In particular, if p pins down
S completely then the number of p-s equals the number of automorphisms
(which then "acts simply transitively" on the p-s).  If we already
have a group G acting on S, we can then check whether G=Aut(S) by
comparing cardinalities.

Here we argue as follows.  Let D be any 2-(7,3,1) design.  We'll show
D is isomorphic to Π_2.  Fix a point P of D, an ordering (l1,l2,l3)
of the three lines through P, and one of the other lines l' of D.
This can be done in 7*3!*4 = 168 ways.  Map them arbitrarily to
corresponding elements of Π_2.  This tells us the images of all
seven points: there's P itself; the points P1,P2,P3 where l' meets
l1,l2,l3 respectively; and the points Q1,Q2,Q3 of l1,l2,l3 which are
neither p nor on l'.  We've also found four of the lines, and readily
check that the others are {P1,Q2,Q3}, {Q1,P2,Q3}, {Q1,Q2,P3}.
This gives an isomorphism of D with Π_2 (and a construction of Π_2
if we don't know one already) and shows that |Aut(Π_2)| = 168.
Moreover we already know that Π_2 has automorphisms by GL_3(Z/2Z)
[the group of invertible 3*3 matrices mod 2 -- GL stands for
"General Linear"].  Thus these are all the automorphisms, and we're done.

On to projective planes of arbitrary prime-power order.  We define the
(algebraic) projective plane over any field k as follows.  [See pages
7-8 of the textbook. You may well have seen this already, as well as
projective spaces of other dimensions, at least over the real and
complex fields; projective spaces are ubiquitous in complex analysis,
algebraic topology, Lie groups, and of course algebraic geometry.
Before the end of the week we'll define projective space of dimension d
for all d.]

The plane is called \P^2(k) or k\P^2 (the latter notation is more
common when k is the field of real or complex numbers; please
don't use the textbook's PG(2,q)).  Fix a 3-dimensional vector space
V over k.  The "points" of \P^2(k) are the 1-dimensional subspaces of V
("lines through the origin", a.k.a. "nonzero vectors modulo scaling"),
and the "lines" are 2-dimensional subspaces of ("planes through the origin"),
each consisting of the "points" that are its 1-dimensional subspaces.
The design properties are then consequences of linear algebra in V:
any two distinct 1-dim. spaces are contained in a unique 2-dim. space
(their span), and any two distinct 2-dim. spaces W,W' intersect in
a 1-dim. space because

dim(W) + dim(W') = dim(W+W') + dim(W\cap W')

and here the LHS is 2+2=4 and the first term on the RHS is 3
(since W is distinct from W', the vector space sum W+W' is all of V).

Now suppose k is finite (see handout for basics about finite fields),
of order n=q.  Then we get a finite design, whose number v of points is
#(V-{0}) / #(1-dim. space - {0}) = (q^3-1) / (q-1) = q^2+q+1, while
Likewise k = (q^2-1)/(q-1) = q+1.  (We did this already when q=2
but didn't see the "modulo scaling" part because there q-1 was 1
so there was no nontrivial scaling!)  The fact that b=q^2+q+1=v
can then be obtained in several ways, but the nicest is to identify
\P^2(k) with its combinatorial dual via (yes!) the dual vector space.
Recall that for every finite-dimensional vector space V over a field k
we define a dual vector space

V* = Hom(V,k),

a k-vector space of dimension equal to dim(V), and thus isomorphic
(non-canonically) with V; and that the annihilator of any subspace
W of V is the subspace W\perp of V*, defined by

W\perp = {v* in V* : v*(w) = 0 for all w in W},

with

dim(W) + dim(W\perp) = dim(V)

(so the dimension of W\perp is the "codimension" of W and vice versa).
Duality reverses inclusions of subspaces:

W \subset W' ⇔ W\perp \superset W'\perp .

Now if V is 3-dimensional then so is V*; the 1- and 2-dimensional
subspaces of V correspond respectively [sic!] to 2- and 1-dimensional
subspaces of V*, with inclusions reversed.  So the projective plane
obtained from V* is the combinatorial dual of the one obtained from V.

V                                    V*

points p: 1-dim. subspaces   ↔   2-dim. subspaces (lines) p\perp
lines l: 2-dim. subspaces   ↔   1-dim. subspaces (points) l\perp
l contains p            ⇔   l\perp contained in p\perp

In particular the number of 2-dimensional subspaces of V equals the
number of 1-dimensional subspaces of V*, which is (q^3-1)/(q-1)=q^2+q+1

[Feb.5 interlude: visualizing the projective plane as an extension of
the familiar ("affine") plane, by intersecting lines through (0,0,0)
with the plane {(1,x1,x2) | x1,x2 in F}, when F = real numbers.
(What familiar topological surface is the complement of a small disc
in the real projective plane?) Generalization to higher n gets the
n-dimensional projective plane as the disjoint union of an n-dimensional
affine plane with an (n-1)-dimensional projective one "at infinity".]

We can get higher-dimensional projective spaces P^n(k) starting from
V of dimension n+1.  (n=0 and n=1 works too, but P^0 is not very
interesting -- just a point -- and P^1 isn't big enough to make
W of V yields an m-dimensional projective subspace P(W) = (W-{0})/k*
of the projective space P^n(k) = P(V).  For each m=2,3,...,n-1
the m-dimensional subspaces are the blocks of a 2-design whose
points are the points (0-dim. subspace) of V.  This design is
Steiner iff m=2 (two points determine a unique line), and square iff
m=n-1: the hyperplanes are again points of a dual projective space.

V                                    V*

points p: 1-dim. subspaces   ↔  (n-1) dim. proj. subspaces p\perp
lines l: 2-dim. subspaces   ↔  (n-2) dim. proj. subspaces l\per.
...
hyperplanes h: (n-1)-dim. subsp. ↔    points h\perp
P(W) contains P(W')       ↔   P(W\perp) contained in P(W'\perp)

The nice way to explain why these are all 2-designs is that all
pairs of distinct points in projective space are equivalent:
for any two pairs (p,p') and (q,q') of 1-dimensional subspaces of V,
there's an invertible linear map  T : V → V  such that A(p)=q and
A(p')=q'.  Since the projective space is defined using just the
linear structure, T yields an automorphism of each of our designs
(that is, the design obtained for each value of m=2,3,...,n-1),
and shows that there are as many blocks containing p and p'
as there are containing q and q'.  We say that the automorphism group
acts "2-transitively" on the points; more on this later.  For any d,m
we can also construct a design with points and blocks being d- and
m-dimensional projective subspaces, but for 1<d<m<n that's only a
1-design, not a 2-design, and indeed the automorphism group is
1-transitive but not 2-transitive; e.g. you can't map lines l,l' to
lines m,m' if l and l' intersect while m and m' are skew.  [Warning:
t-transitivity of Aut(D) on points is a sufficient condition for
a design D to be a t-design, but it is not necessary, though
it might look that way from the nice examples we'll show.]

Coordinates on projective space P^n(k):  (x_0,x_1,...,x_n)
[NB we start the index at 0, so n+1 coordinates], not all zero,
but regarded as the same as (x'_0,x'_1,...,x'_n) if proportional,
i.e. if there exists c in k* such that  x'_i = c x_i  for each i
(notation:  k* := {c in k: c \neq 0} = multiplicative group of k).
To emphasize that the coordinates are in effect a ratio, we use
colons rather than commas to separate them: (x_0 : x_1 : ... : x_n).
These are known as projective (or homogeneous) coordinates.
For example, n+1 points

(x0_0 : x0_1 : ... : x0_n),
(x1_0 : x1_1 : ... : x1_n),
...,
(xn_0 : xn_1 : ... : xn_n)

are on a projective hyperplane (of dimension n-1) ⇔ the corresponding
vectors in k^(n+1) are on a vector hyperplane (of dimension n) ⇔
the order-(n+1) determinant of xi_j vanishes.  NB this is well-defined:
changing any xi to ci*xi with nonzero ci multiplies the determinant by
c0 c1 c2 ... cn, but preserves the condition that it be zero.  Likewise
the coordinates of an arbitrary vector in x* in V* are (x0*,x1*,...,xn*),
acting on V via the usual inner product:

(x0*,x1*,...,xn*) (x0,x1,...,xn) = x0* x0 + x1* x1 + ... + xn* xn

and (x0* : x1* : ... : xn*) are homogeneous coordinates on the dual
projective space, and the hyperplane x* contains the point x iff x* x = 0
(again this makes sense even though "x* x" needn't be a well-defined
element of k).  One more example: a hypersurface of degree d in P^n
is the locus of P(x0,x1,...,xn) = 0  where P is a (usually irreducible
nonzero) homogeneous polynomial of degree d; this condition
(though not usually the value of P) is again invariant under scaling.
For example, a hypersurface of degree 1 is a hyperplane.

Automorphisms of P^2(k), and more generally any of the n-1
2-designs from P^n(k) (n>1): GL(V) = GL_{n+1}(k) acts, but
scalar matrices act trivially; indeed it's not hard to see that
these are the only matrices that act trivially -- that is, these
are the kernel of the map GL(V) → Aut(D).  (Indeed it's a normal
subgroup, isomorphic with k*.)  So we have an action of GL_{n+1}(k)/k*,
known as the projective general linear group PGL_{n+1}(k).  If
#k = q^f with f>1 we also get an action of the field automorphisms
(we'll later give more details about how these automorphisms interact
with PGL_{n+1}(k)).  That turns out to be the full automorphism group.
We won't prove it (except for projective planes of order 2, 3, 4, 5),
because it depends on results that the book cites (1.23 and 1.24
on page 8) but does not prove or even fully state.  Basically one
"coordinatizes" D, reconstructing the structure of k and coordinates
(x0:...:xn) from the combinatorics of D.  That could make a good
final project if you're interested.

Feb.5 and 8 Important examples of designs, II:
Hadamard matrices, particularly Sylvester and Paley

These can be viewed as another generalization of Π_2, from a different
viewpoint.  Take its intersection matrix and replace each 0 with a -1
(i.e. 2M-J).  All rows (or columns) now have norm [self-inner-product] 7,
and any two have inner product -1.  So if we extend with a row and
columns of +1's (and abbreviate +1 and -1 by just + and -):

+ + + + + + + +
+ + + - + - - -
+ + - + - - - +
+ - + - - - + +
+ + - - - + + -
+ - - - + + - +
+ - - + + - + -
+ - + + - + - -

we get an 8x8 matrix H with

(i)  all entries +1 or -1,
(ii)  any two columns' inner products equal 0.
(iii)  any two rows' inner products equal 0,

An nxn matrix with these properties is said to be a Hadamard matrix
or H-matrix for short (see 1.27 on p.9) [though Sylvester already
gave some examples 25 or so years earlier].  We already know (ii) means
H\T H = nI, so (as with M, but easier because no J's) readily deduce that
either (ii) or (iii) may be omitted because they are equivalent given (i).
Since the rows (or columns) of H are orthogonal, and all with the
same norm n, we see that H/sqrt(n) is an orthogonal matrix.
It follows that (as with M) we can find det(H) up to sign: it's
a square root of det(nI) = n^n.  That was the origin of Hadamard's
interest in such matrices:

If A is a real nxn matrix with entries of absolute value at most 1
then |det(A)| ≤ n^(n/2), with equality iff A is an H-matrix.

Pf. This follows from:

Thm. The absolute value of the determinant of any real matrix
is at most the product of the lengths of its row vectors,
with equality iff those vectors are pairwise orthogonal.

This might feel geometrically intuitive, but it requires proof, especially
as we shouldn't trust our geometric intuition of really high dimensions.

Pf. Let  v_1, v_2, ..., v_n  be the rows of the matrix.  Assume they are
linearly independent, else the determinant vanishes and the inequality
is vacuous.  Define u_1, u_2, ..., u_n as follows (cf. Gram-Schmidt):
u_1=v_1, and for each k the vector u_k is the projection of v_k to the
orthogonal span of the complement of {u_j | j=1,2,...,k-1}.  Then:

(a) u_k = v_k + linear combination of u_j with  j<k

(b) |u_k| ≤ |v_k| with equality iff u_k = v_k
(because u_k is an orthogonal projection of v_k)

(c) |det(u_1,u_2, ..., u_n)| = |u_1| |u_2| ... |u_n|
(by the A\T A trick)

The desired inequality now follows because (a) implies that
det(v_1,v_2, ..., v_n) = det(u_1,u_2, ..., u_n)  (row operations).

This also proves Theorem 1.26 .

Remark: Hadamard's inequality is true for complex matrices too,
with much the same proof; but complex Hadamard matrices are
much easier to construct, e.g. let the (i,j) entry be z^(i-j) where
z is an n-th root of unity (that's basically discrete Fourier series).
Real Hadamard matrices are more subtle.  A basic observation (p.9):

If H is a Hadamard matrix, so is any matrix H' obtained from it by
-- multiplying some subset of rows or columns by -1
-- permuting rows or columns
H' is said to be equivalent to H.  (NB we don't define H\T to be
equivalent to H [unless it can also be obtained from H by row and column
operations as above], even though H\T is also an H-matrix.)

So any H has an equivalent matrix (even without permuting) whose
first row and first column are the all-1's vector (a.k.a. J).

Lemma (unnumbered, p.9-10) if an H-matrix exists then either n=1, n=2, or 4|n.

Proof of lemma: assume n≥2.  Go to equivalent H-matrix with
top row J.  In rows 2,3 let a,b,c,d be the number of columns
of type ++, +-, -+, --.  Then:

a + b + c + d = n    (there are n columns)
a + b = c + d = n/2  (2nd row orthogonal to 1st)
a + c = b + d = n/2  (3nd row orthogonal to 1st)
a + d = b + c = n/2  (2nd row orthogonal to 3rd)

Equivalently, a = b = c = d = n/4, QED.

Now our construction of an 8x8 H-matrix from Π_2 worked because
it was a square 2-design with (k,v,λ) = (4m-1, 2m-1, m-1) with m=2.
Indeed, the above analysis shows:

Prop. 1.28 (p.10) there is a Hadamard design of order n=4m iff there is
a square 2-design with (k,v,λ) = (4m-1, 2m-1, m-1).

Pf.  ⇐ extend 2M-J with a row and column of +1's as before.
⇒ go to an equivalent H-matrix with first row and column of +1's,
delete them, and use a=b=c=d=m.

Definition: a square 2-(4m-1,2m-1,m-1) design is called a

Warning (Remark 1.29) isomorphic designs yield equivalent H,
but not (always) conversely [because of the extra choice of
which row and column to remove; we'll see that what H *does*
uniquely determine is a 3-design].

Example (1.31) [Sylvester 1867] The points and hyperplanes of
of order 2^(r+1).  Equivalently, if d=r+1 and V is a d-dimensional
vector space over F_2, the rows and columns of H are labeled by
vectors of V (this time including zero!), and the i,j entry is
1 or -1 according as the inner product of the i-th and j-th vector
is 0 or 1.  [We're exploiting the fact that q=2 so there's no
k* ambiguity in identifying a point or hyperplane with a nonzero
vector in V or V*.  Oh, sorry about the inevitable double use of
"*" for both "multiplicative group of k" and "dual vector space of V".
In more formal writing the latter * is a superscript, V*,
which you can make in TeX with "V^*" as usual.  The multiplicative group
should really be k× (TeX: k^\times) but often the * is used there too.
While I'm at it: "k" for German Körper = field.]

See also Problem 4 on the current problem set (= CvL p.25 Ex.2).

The next important example is presented in the text but not proved.
We'll supply the proof.

Example (1.30, still on p.10) [Paley 1933]  If  n = 4m = q+1
for some prime power q, and k is a finite field of order q,
then the set S of nonzero squares in k has size (q-1)/2 = 2m-1
and is a "perfect difference set" (in a sense naturally
extending what you saw in the first problem set): any nonzero
c in k can be written as s-s' for m-1 choices of s,s' in S.
Hence the collection of translates {S+x | x in k} of S
is the set of blocks of a Hadamard design.

The implication is proved as before: given distinct a,b in k,
the number of x such that S+x contains both a and b is
the number of s,s' in S s.t. s+x=a and s'+x=b.  Necessarily
s-s'=a-b, and given such s,s' we solve uniquely for x=a-s=b-s'.

To prove that S is a perfect difference set, recall the
following properties of squares in finite fields
(generalizing familiar results of Legendre etc.):

Proposition: Let k be a finite field of odd order q=2r+1.  Then:
(i) Every nonzero square s=x^2 in k is the square of exactly two
elements of k, namely x and -x.
(ii) The r-th power of any s in k* is either 1 or -1.
s is a square iff s^r = 1.

Proof:
(i) Certainly f s=x^2 then s=(-x)^2 also, and -x is distinct from x
because x is nonzero (this is where we use that q is odd); and
if y is any square root then x^2=y^2, so (x-y)(x+y)=0, which
in a field implies x-y or x+y vanishes so y is one of the known
square roots x and -x.
(ii) (s^r)^2 = s^(q-1) = 1 because s^q=s and s is nonzero.
So s^r is a root of X^2-1 = (X-1)(X+1), so equal to 1 or -1.
If s = x^2 then s^r = x^2r = x^(q-1) = 1 by the same argument.
This gives r solutions of the degree-r polynomial equation x^r=1,
so the squares in k are the only solutions of that equation.

Corollaries:

(i) r of the 2r=q-1 nonzero elements of k are squares of elements of k.
[Proof: the squaring map k* → k* is 2:1 onto its image.]

(ii) -1 is a square iff r is even.  [Proof: that's the condition on r
for (-1)^r to equal 1; note that, since q is odd, 1 and -1 are distinct.]

(iii) If -1 is not a square then for any nonzero c either c or -c
is a square but not both.

Remark: if q is even then every element of k has a unique square root
in k.  Proof: the map k → k taking x to x^2 is injective because
x^2-y^2 = (x-y)^2  so  x^2=y^2 iff x=y;  since k is finite it follows
that the map is surjective.

Now to prove that the Paley construction actually gives a Hadamard design.
In our setting q=4m-1 so r=2m-1 is odd and -1 is not a square.
Corollary (i) says |S|=2m-1 so our blocks are of the right size.
To prove it's a 2-design, we've seen already that we must show that
if a,b are distinct elements of k we must count solutions s,s' in S of
s-s'=a-b.  Let c be the nonzero field element a-b.  By part (i) of
the Proposition, the count is 1/4 the number of solutions in k* of
x^2-y^2=c.  Now there are q-1 solutions in k, because we have
x^2-y^2=(x-y)(x+y) and there are q-1 factorizations, each of which
yields unique (x,y) because 2 is invertible in k.  Of those we must
throw out solutions with x=0 or y=0.  The number of x=0 solutions is
2 or 0 according as -c is or is not a square; for y=0 the count is
2 or 0 according as +c is or is not a square.  But by (ii) exactly
one of these two happens.  Hence the number of solutions of x^2-y^2=c
in (k*)^2 is (q-1)-2 = q-3 = 4(m-1) and we're done.  QED

So for n other than 1 and 2 we have Hadamard matrices of order n if

@ n is a power of 2, or
@ n = q+1  for some prime power q congruent to -1 mod 4.

We shall see (Problem 4 = CvL p.25 again) that we also have
Hadamard matrices of order n = n_1 n_2 for any known n_1, n_2
for which we've constructed a Hadamard matrix (including 2).

This gives n=4m for m=1,2,4,8,16,... and powers of 2 times
1,2,3,5,6,7,8,11,12,15,17,18,...  so of m≤18 we're missing
only 9 and 13.  That's misleading: asymptotically 0% of m that
are not multiples of 4 arise, because either m is a power of 2
(very rare) or 4m-1 or 2m-1 must be a prime power and that happens
with probability asymptotic to 1/log(m).  [But as noted above,
other constructions are known, and Hadamard designs of order 4m
have been found for all m ≤ 166 (= 664/4).]

For  n = 4, 8, 32, 128, ..., 2^57885161, 2^74207281, ...(?),
we get two constructions (even without taking Kronecker products)
since n is both 2^e and q+1.  The resulting Hadamard matrices are
the same for n=4 and 8 (somewhat remarkably -- we'll return to this)
but not for higher n [CvL Ex.15 on p.27], nor is Paley_128 isomorphic
with  H_4 x Paley_32.  So Hadamard matrices of order n need not be unique
when they exist.  They are unique at least for n=1,2,4,8,12, and this
will be important to us when we study their automorphism groups.

Feb. 10 new designs from old:

NB again we choose a different (but still logical) order of
presentation from the textbook's.

Complementary design (p.13, eqs. 1.37-1.38 and Prop. 1.39):
if \D = (X,\B) is a t-(v,k,λ) design, let

\B@ = { X \ B : B in \B }

be the collection of complements of blocks, and define \D@ = (X,\B@),
the complementary design of \D.  (Of course \D@@ = \D: the
complement of the complement is the original design).  We claim
that this too is a t-design:

Prop. 1.39: \D@ is a t-(v,v-k,λ@) design where

1.37  λ@ = sum( (-1)^s Binomial(t,s) λ_s,  s = 0,1,...,t).

(Recall that λ_s is the number of blocks containing any s points of X,
and was computed on page 3, see (1.5)).

Proof: Certainly \D@ consists of blocks of size v-k.  We must show:
for any set T of t elements of X, the number of blocks of the original
design \B that are *disjoint* from T is the same, namely λ@.
This is done by inclusion-exclusion (see Appendix to chapter 1,
Thm. 1.56 and Cor. 1.57 on pages 24 and 25).  For any subset T' of T
let a(T') be the number of blocks B containing T'; inc-exc says that
that the number of blocks disjoint from T is the sum of (-1)^#(T') a(T')
over all 2^t subsets T'.  But a(T') is just λ_s where where s = #(T'),
and each s occurs Binomial(t,s) times, so we're done.

e.g. if t=2 then λ@ = λ - 2r + b  (1.38, see Prob.2 which you
just handed in); in any case the incidence matrix of \B@ is just
M@ = J - M  where M is the incidence matrix of \B and J is the
all-1's matrix of the appropriate size.  Of course \B@ is square
iff \B is.

Are there interesting self-complementary designs?  Interesting or not,
we must have v=2k (so in particular v had better be even).
There are various boring examples, and no square examples
exept the trivial 2-(2,1,0) design (since a square design has
(v-1)λ = k^2-k, and if v=2k then 2k-1 is a factor of k^2-k,
which doesn't happen for k>1).  But we get some self-complementary
3-designs by extending certain square 2-designs -- including indeed
our prototypical example Π_2.

Let \E be the following design: there are 8 points, X together with
a new point called 0; the blocks each consist of 4 points, and are
line complements in Π_2 together with sets of the form "line u {0}".

Claim: This is 3-(8,4,1) design (a.k.a. Steiner (3,4,8) system),
and is self-complementary by construction.

Proof: Self-complementarity is clear.  For the design property:
[NB we did this already in class, so didn't re-do it today;
but nor was it in the notes, so I recite the argument here.]
Let T be any 3-element set of X.  If T contains 0 then any block
containing T must be "line u {0}", and conversely such a line exists
and is unique, namely the line determined by the other two elements of T.
If T does not contain 0, we use our result from the 1st problem set:
either T contains a line or is disjoint from some line, but not both.
For starters this means T cannot be contained in both a line and
a line complement.  If T is in a line then it *is* that line, so
we get our block as  T u {0},  and it is clearly unique.  Otherwise
T is contained in a line complement, which is again unique because the
union of any two lines contains 3+3-1=5 points (a simple application of
inclusion-exclusion), so cannot be disjoint from the 3-element set T.  QED

Alternative description: X is a 3-dimensional vector space over k=Z/2Z;
the blocks are the 14 four-element subsets that sum to zero, or
equivalently the 14 affine planes (planes translated by a vector).
Either description generalizes to give a Steiner (3,4,2^d) system
for every d>2, but it's not self-complementary once d>3.

Right now we're more interested in self-complementarity than the
Steiner property, so instead we generalize as follows.  For any
starting from the Hadamard design of points and hyperplanes in P^(d-1) k,
obtaining a  3-(2^d, 2^(d-1), 2^(d-2) - 1)  design whose points are the
vectors in k^d and whose blocks are the 2^(d+1)-2 affine hyperplanes.

Automorphisms include (and will turn out to equal) the
affine linear group generated by GL_d(k) and translations by V,

In terms of the associated Hadamard-Sylvester matrix: if the first row
is (+1, +1, +1, ..., +1) then each of the n-1 other rows has n/2 +1's
and n/2 -1's, giving a complementary pair of blocks, for a total of 2(n-1).
We claim (p.12) that these form a  3-(n,n/2,(n/4)-1) design --
and this works for any Hadamard matrix of order n>4.  [Naturally
such designs are called "Hadamard 3-designs".]  This is a special case
of CvL Ex.5.  Another proof: choose any three columns; we want to show
that there are  (n/4) - 1   rows other than the first where these columns
give either +++ or ---.  Since the first row has +++, it is equivalent to
show that there are n/4 rows, including the first, with either +++ or ---.
Choose some other column, and multiply each row by 1 or -1 to make
that column all +1's (this does not change our design).  We've seen already
that in each pair of columns each of ++, +-, -+, and -- arises n/4 times.
This gives 12 linear conditions on 8 counts; they're not independent
but the only freedom is to add some constant c to each count with an
even number of minus sign, and subtract c from all the other four counts,
and this does not affect the sum of +++ and --- counts, etc.

DERIVED DESIGNS

Building up a 2-design to form a 3-design is quite special.
The other direction is easier -- we already saw that a t-design
is already a (t-1)-design, and more interestingly we can reverse our
above construction as follows (Def. 1.32, p.11): if \D = (X,\B)
is a t-(v,k,λ) design then for any point p in X we get a t-1 design
\D_p, the derived design with parameters (v-1, k-1, λ)  whose
point set is  X \ {p}  and whose blocks are  B \ {p}  for every
block B in \B that contains p.  Note that in general \D_p depends on p
(the main exception is when Aut(\D) acts transitively on X).

If a given t-design \D is derived from a (t+1)-design \E then
\E is said to be an extension of \D, necessarily with parameters
(v+1,k+1,λ).  For instance, a Hadamard 3-design is an extension of
each of the Hadamard 2-designs obtained from the same matrix.  Again,
extendability -- going from a t-design to a (t+1)-design -- is unusual;
applying to \E the identity bk=vr of (p.4, 1.8) already imposes a
nontrivial necessary condition (Prop. 1.33, p.11): k+1 must divide b(v+1).
[NB as noted already, there's a typo on p.11: the reference preceding
the statement of this proposition should refer to (1.8), not (1.7).
To prove it, note that \E's "r" is \D's "b".]

For example: Prop. 1.34- [p.11, Hughes 1961]: if a projective plane
of order n is extendable then n is 2, 4, or 10.

[n=2 we saw already.  n=10 is impossible -- and it turns out that it is
easier, though still not trivial, to prove there's no 3-(112,12,1)
design, but we won't even do that.  n=4 is possible, but we don't
know this yet, though the Proposition is written as if we do.]

Proof: n+2 must divide (n^2+n+1)(n^2+n+2).  But then n+2 divides the
value of the RHS at n = -2, which is 3*4 = 12, and we're done since we
don't allow n=1.

This Diophantine technique will recur several times in the course.

More generally:

Thm. (Cameron 1973, 1.35 on page 11) if \D is an extendable square
2-(v,k,λ) design then:

(b) v = (λ + 2) (λ^2 + 4λ + 2)  and  k = λ^2 + 3 λ + 1,
or
(c) (v,k,λ) = (495,39,3).

Example: in (b), λ=1 gives (v,k,λ) = (21,5,1): a projective plane
of order 4.  We'll see that all such planes are isomorphic, and that
they are extendable (which follows from the uniqueness result plus the
existence of a Steiner (3,6,22) system which you've proved in the last
problem set).  The next case is impossible (Bagchi's result cited on p.13);
beyond that I don't know.

[proof postponed]

Pf.: let \E be the purported extension, and redefine v,k to be those of \E
(so we'll have to decrement by 1 at the end).  If some \E_p is square
then every \E_p is square (same parameters).  So any two blocks are
either disjoint or meet in λ+1 points (if they both contain some p,
consider their residues in \E_p).  Conversely if \E satisfies this
condition then each \E_p is square by characterization 1.15d of
square designs (any two blocks have the same-sized intersection).
Also, since now (v-1,k-1,λ) are the parameters of a square design
the identity (1.9) becomes

(*)  (k-1)(k-2) = (v-2)λ.

Claim: fix a block, and consider \E^0 := (X^0, \B^0) where
X^0 = complement of B and \B^0 = blocks disjoint from B.
Then \B^0 is a 2-design.  Proof: fix p,q in X^0.  For each r
in B there are λ blocks B' containing p,q,r, and each r appears
in λ+1 of them.  So double-count pairs (B',r): for each of k
r's there are λ choices of B'; for each B' there are λ+1
choices of r, so the number of choices for B' is  k λ / (λ+1).
Hence the number of blocks containing p,q but disjoint from B is
constant, as claimed.  Indeed it is  λ_2  -  k λ / (λ+1),
and λ_2 = k-1  (apply (*) to the identity λ_2 = ((v-2)/(k-2)) λ
which holds in any 3-design); so the count is now
k-1 - k λ/(λ+1) = (k-λ-1) / (λ+1)  [I wish the book
spelled this out...].

We now apply Fisher's inequality to the 2-design \E^0, which has
parameters (v-k, k, (k-λ-1)/(λ+1)) and thus has

(v-k) (v-k-1) (k-λ-1) / (k (k-1) λ+1).

We must exclude the degenerate case v-k = k.  In this case
\D is a square design whose blocks have size (|X|-1)/2,
and is thus a Hadamard design; that's case (a).

Otherwise, some manipulation gives  k \geq (λ+1) (λ+2).
k = (λ+1) (λ+2)  gives case (b) after decrementing to
recover the parameters of \D (and then \E^0 is square too,
so we can hope to undertake further analysis; e.g. for λ=1
that's a square (16,6,2) design).

On the other hand, consider the integrality condition on the number
b = λ_0 of blocks of \E.  That number is v(v-1)(v-2) λ / k(k-1)(k-2),
which (*) simplifies to v(v-1)/k.  Using (*) to express this in terms of
k and λ rather than k and v we get

b = ((k-1)(k-2)+λ) ((k-1)(k-2)+2λ) / (kλ^2)

so k divides the numerator and thus divides 2(λ+1)(λ+2).
A factor of 2N that's at least as large as N is either N or 2N.
We've dealt with the former case already.  In the latter, we get
λ^2 b = 8λ^6 + ... + 9,  so λ | 9, and λ=9 yields
fractional b.  So λ=1 or 3.  The former case gives k=12, v=112
and thus an extension of a projective plane of order 10, which was
already known to be impossible in 1973.  The latter gives k=2*4*5=40,
v=496 and thus case (c).  QED

Feb. 12 -- intro to arcs and ovals; intersection triangles

You're already had to look up "oval" on page 17 to construct a
(3,6,22) Steiner system from the square Paley 2-(11,5,2) design.
An arc in a 2-design is a set S of points no three of which are
contained in a block.  (The book uses "n-arc" for an arc with
n points, and limits the definition to square designs.)
Equivalently, the intersection of S with any block B has size
0, 1, or 2.  For geometrically obvious reasons (at least in the
context of projective planes where the blocks are called "lines"),
B is said to be "tangent" to S if the intersection has size 1,
and "secant" if it has size 2; a block disjoint from S is said to be
"passant" to S.

Why do we care?  It turns out to be a useful notion in several contexts
when \D is a square design; in particular it will let us classify and
analyze projective planes of small order.  For starters (see p.18),
suppose we ask whether a projective plane \D = (X,\B) is extendable:
is there a 3-design \E such that \D is \E_p?  If so, we already know
the points of \E -- namely X u {p} -- and some of the blocks, namely
B u {p} for any B in \B.  Since B is square, any two blocks meet in
λ=1 point.  For each x in X, \E_x has the same parameters as \E_p,
so is also square with the same value of λ; hence any two of its blocks
meet in a unique point too.  Thus any two blocks of \E are either disjoint
or meet in 2 points.  (That's a special case of the argument at the
beginning of the proof of Cameron's Theorem 1.35 .)  So, any block of \E
that does not contain p is an arc.  Indeed we'll see it's an arc of
maximal size, which we'll call a "hyperoval".

How big can an arc be?

Prop. 1.46: A point of an n-arc in a square 2-(v,k,λ) design
lies on (n-1)λ secants and k-(n-1)λ tangents.  In particular
n ≤ 1 + (k/λ) [because the count of tangents is nonnegative].

Proof: let S be an arc and p be one of its points.  There are
n-1 other points of S, hence n-1 pairs {p,q} in S, each lying in
λ blocks B; each such B is a tangent, which determines q uniquely,
so there are indeed (n-1)λ such B's.  In a square design each point
is in a total of k blocks, and if such a block is not one of the
(n-1)λ secants then it's a tangent.  QED

An oval is an arc for which the tangent count is either 1 or 0;
that is, for which n is either  1 + (k-1)/λ  (an oval of Type I)
or  1 + kλ  (Type II) respectively.  You must know the distinction
but need not memorize which is which.  You should, however, remember that
ovals that have no tangents (and thus intersect each block in either
0 or 2 points) are called hyperovals.  Example: a line complement
in Π_2 is a hyperoval; removing any of its 4 points yields a Type I oval.
In the Paley 2-(11,5,2) design an oval has Type I and  1 + (5-1)/2 = 3
points; there are 11*10*3/3! = 55 ovals.  Type I is geometrically
familiar -- and we'll see (though not fully prove in class) that this
familiarity extends to algebraic projective planes P^2(k).

Observe that

Type I exists ⇒ k is 1 mod λ
Type II exists ⇒ k is 0 mod λ
Both exist ⇒ λ = 1 (so projective plane).

As usual, none of these is ⇔ !  For example:

Prop. 1.47 (p.18) If a square 2-(v,k,λ) design has a hyperoval,
and (v,k,λ) ≠ (3,2,1), then k ≡ λ mod 2.

Pf.: Fix a point p outside S -- such must exist, else S=X so k=2
and we have the trivial 2-(3,2,1) design (which indeed is an exception).
The number of secants containing p is  n λ / 2  (why?), which is
(λ + k) / 2,  so this must be an integer, QED.

Example: if a projective plane of order q has a hyperoval then 2|q.

In fact we can say more.  If there's a hyperoval in a projective plane
then removing any point yields an oval.  Conversely, an oval yields
a hyperoval iff all its tangents meet in a point.

Prop. 1.48 (p.18): If  k ≡ λ mod 2  and there's a Type I oval S
then any point on the design lies on either one or all tangents.

Cor.: in a projective plane with q even, all the tangents meet
in a unique point p (proof: intersect any two of them), called
its "center" (the book says "nucleus", which feels rarer to me,
or "knot", which I don't think I've seen elsewhere).  So we recover
a hyperoval  S u {p}.

Proof: We have  k(k-1) = (v-1) λ  (because it's a square 2-design)
and  n = 1 + (k-1)/λ.  Claim: k, λ, n are odd.  Proof: if λ
were even then k-1 would be odd, contradicting  λ | k - 1.
Since λ is odd, k-1 is even, so k is odd and so is n = 1 + (even)/(odd).
It follows that the number of tangents through each point is odd
(so in particular not zero).

Apply "variance trick" again, computing the first and second moments of
the numbers of tangents going through the points of X; this time it will
turn out that the variance must be as large as possible.  Let N_i be the
number of points that lie on exactly i tangents.  [NB the book calls it n_i,
which would lead to the monstrosity n_n.]  Then the N_i sum to v = #X;
i N_i  sums to  (# tangents) * (# points per tangent) = n k; and
i (i-1) N_i  sums to (# pairs of tangents) * (# points per pair) = (n^2-n) λ.
Rearranging yields  sum_i (i-1) (i-n) N_i = 0.  Since N_i = 0 for i=0 and i<n
it follows that the only nonzero N_i are N_1 and N_n, QED.

Exercise: use these counts to verify that N_n = λ, so one might say that
in general there are λ "nuclei".

Examples: in P^2, "conics" = zeros of "nonsingular quadratic forms" =
zeros of homogeneous quadratic polynomials P(x,y,z) over k that are
irreducible even over the algebraic closure.  [That's a necessary proviso:
consider x^2 + xy + y^2  mod 2,  or  x^2 + y^2  mod 3.]  Note/recall that
the set of zeros of a homogeneous P is well-defined even though its value
at a point of P^2 in general is not.  A conic is clearly an arc because
restricting to a line yields a homogeneous quadratic polynomial in two
variables that is not identically zero (else P had a linear factor).
In fact it is known -- though we will not prove this (yet another possible
paper topic) -- that:

(i) all conics are equivalent under PGL_3(k);
(ii) all conics are Type I ovals (that is, they have q+1 points);
and remarkably, one can prove in general that
(iii) if q is odd then every oval is a conic (Segre [1954]).

Given (i), we can prove (ii) by checking it for one conic, and it is
convenient to use the conic xz-y^2; indeed the general point is
(r^2:rs:s^2) for some (r:s) in P^1(k) (check that this makes sense;
algebraic geometers recognize this as the first nontrivial example of
a "rational normal curve", or the image of the "degree-2 Veronese map"
P^1 → P^2).  So a conic is identified with of the q+1 points of P^1.

When q is even: (iii) is true for q=2 and q=4 (we'll say more about
center, and remove some other point to get a non-conic oval; and for q>8
(except q=32) there are even hyperovals not of the form "conic + center".

Finally I owe you some words about "intersection triangles" (p.21).
That's a convenient way to do a bunch of inclusion-exclusion calculations
at once without an explicit sum of binomial coefficients etc.
The general setup is: we have a subset Y of X such that, for each
s up to l=#Y, the number of blocks containing any s-element subset S of Y
depends only on s; and we want to count the blocks whose intersection
with Y is exactly S.  The hypotheses always hold if \D is a t-design
with l ≤ t, and in some other cases, e.g. if Y is an arc, or notably
a block of a Steiner system, plus one other case explored in problems
6 and 7.  The method is as follows, and illustrates the paradox that
sometimes a problem is made easier by generalizing it (even though
one might expect that proving a more general result should be
at least as hard).  Here we ask: given nonnegative i and j with
j ≤ i ≤ l, an i-point subset I of Y, and a j-point subset J of I,
how many blocks intersect I in J?  (The problem we started with is
the special case I=Y.)  This depends only on i and j; the count ν_{i,j}
[ν = Greek letter nu] can be computed recursively by starting from
the known values ν_{i,i} (e.g. ν_{i,i} = λ_i  for i ≤ s) and then using

ν_{i,j} = ν_{i-1,j} - ν_{i,j+1}

to fill each row of a triangle from right to left.  See the example
on page 21 (Table 1.1); yes, the Gross responsible for Theorem 1.55 (1974)
on page 22 (which gives necessary conditions for the bottom row of such
a triangle in the Steiner case to contain a zero) is our recently retired
Benedict Gross.

Feb. 17 -- affine and inversive planes

There are two topics remaining in chapter 1 that we'll cover
(and several that we won't).  One is the construction of the
star examples of design theory: the Steiner systems whose
automorphism groups are the sporadic Mathieu groups (or, for
the (3,6,22) system, a group containing M_{22} with index 2).
This is described on pages 22-24, but requires various notions
that are postponed to later chapters (e.g. chapter 6 for the
uniqueness of Pi_4).  We'll get to them later in the course.
The other topic is our concern today (pages 13-15).

AFFINE PLANES

Recall that P^2(k) is obtained from the affine plane k^2
by adjoining a line at infinity.  It's called an "affine plane"
because there's no choice of origin -- imagine an unmarked blackboard
or flat sheet of paper extended out to infinity for the familiar case
of k=R, the real numbers.  Of course this means that we can recover k^2
by starting from P^2(k) and removing a line and all its points.
This is still a Steiner system: any two points in the affine plane
determine a unique line.  This follows just from the axioms of a
projective plane, so we don't need any algebra on k to check it.
If  \D = (X, \B)  is a combinatorial projective plane of order q,
and B is any of its lines, then the residual \D^B := {X \ B, \B \ {B}}
is a finite affine plane.  (More precisely, the collection of blocks
of \D^B isn't quite \B \ {B}, because a block other than B needn't be
a subset of X \ B; the blocks are  B' \ B  for blocks B' of \B other
than B itself.)  This \D^B is a 2-(q^2, q, 1) design with q^2+q blocks,
called an affine plane of order q.  If the projective plane was algebraic
then we recover the affine plane k^2, an "algebraic affine plane"
(which the book will call AG(2,q), a notation I'm deprecating).

We can try this for any design \D and block B, but for \D^B to be
itself a design we must have each B'\B of the same size, and if that's
to be true for all B then \D must be a square design.  Conversely,
the residual of a square 2-(v,k,λ) design is a 2-(v-k, k-λ, λ) design.

Warnings:

(i) Different choices of B may yield non-isomorphic residuals \D^B
with the same parameters.

(ii) \D^B could have repeated blocks  But then two blocks of \D meet in
at least k-λ points, whence k ≤ 2λ.  But since k(k-1)=vλ, this means
v \leq 2(k-1)  [the book has the slightly weaker bound 2k-1, which is
good enough], and this cannot hold for both a design and its complement.
So either \D or its complement \D@ (whichever has the smaller blocks) has
a residual design without repeated blocks.

Writing  (v-k, k-λ, λ) =: (v^B, k^B, λ^B)  we solve for
λ = λ^B,  k = k^B + λ^B,  v = v^B + k^B + λ^B.
Then the condition  k(k-1) = (v-1)λ  on the parameters of
the square design \D becomes

k^B (k^B + λ^B - 1) = v^B λ^B

(p.13; check this manipulation, and that it works for the parameters
(v^B, k^B, λ^B) = (q^2, q, 1) of a finite affine plane of order q).

A 2-design satisfying these constraints is said to be quasi-residual.
Not every such design need be the residual of an actual square 2-design,
but nicely enough the case of affine planes (with λ=1) always works!
See p.14, Prop. 1.40.  The proof: in such a design, any two lines
meet in either 0 or 1 points.  If the design is \D^B then two lines are
disjoint iff they were obtained from lines that meet at a point of B.
To reconstruct \D, we need an equivalence relation || on affine lines L
such that L||L' iff L||L' came from projective lines through the same
point of B.  So we've seen L||L' iff L=L' or L,L' are disjoint.
We say that L,L' are parallel in this case.  Reflexivity and
symmetry are clear, but why is this transitive?

Lemma: for every line L and point p of a finite affine plane
there's a unique line L' containing p and parallel to L.
(That is, "Playfair's axiom" holds for finite projective planes.)

Pf.: if p in L then L'=L works, and no other line does because then
two distinct parallel lines would meet.  (We use n>1 here; if n=1
there's only one choice for L' anyhow...)  If p not in L, there are
q+1 lines through p, of which q meet L (one for each point of L),
so a unique line not meeting it.

Corollary: || is an equivalence relation.

Pf.: The only nontrivial case is three distinct lines L,L',L" with
L||L'||L".  If L and L" were not parallel they would meet at some point
p which has two parallels to L', namely L and L", contradiction.

Thus: Prop. 1.40 -- a quasi-residual Steiner 2-design (=affine plane)
is residual; thus there's a finite projective plane of order q
iff there is a finite affine plane of the same order.

INVERSIVE PLANES

Remarkably k^2 always extends to a Steiner 3-design; this gives us
our second infinite examples of Steiner 3-designs, and again with a
3-transitive automorphism group.  The necessary condition (1.33)
[p.11: k+1 must divide b(v+1)] is always satisfied by a combinatorial
affine plane [q+1 | (q^2+q)(q^2+1)] but we already know that such
integrality conditions are rarely sufficient.

Again the construction is nicely motivated by a classical geometrical
picture over the real numbers.  The (2-)sphere S can be considered a
3-design whose blocks are the circles (not just "great circles").
Stereographic projection from the north pole P identifies this with
the classical inversive plane: the blocks become Euclidean circles
as well as lines ("circles through infinity" -- NB this is a different
compactification of R^2, with just one point at infinity rather than
a whole line).  It's called the "inversive plane" because inversions
are automorphisms, taking any block (circle of the sphere) to another
block.  You've seen that S is also the "Riemann sphere" C u {infinity},
which we now know is also \P^1(C), the "projective line over C".
The circles are just the images of its subset \P^1(R) under PGL_2(C).
This works just as well over a finite field k = F_q, since there is
a quadratic extension k' = F_{q^2} to take the place of C: the images
of \P^1(k) under PGL_2(k) are the blocks, and the blocks through the
point at infinite (0:1) are just the affine k-lines on k' which may be
identified with k^2 by an arbitrary choices of k-basis for k'.

The same construction works for any d>1 to give a 3-(q^d+1,q+1,1)
design whose points are the points of the projective line over
a field of q^d elements and whose derived design is affine d-dimensional
space over a field of q elements.  Your first problem on the next
problem set is to prove that this actually works.

The book notes another description via "ovoids" in P^3(k).  This
then you might do your final project on that construction, and maybe
also the Suzuki-Tits ovoids for q=8,32,128,... noted on page 16.

Mild warning: the 3-(q^d+1,q+1,1) designs coming from P^1(F_{q^d})
are sometimes called "spherical geometries".  Indeed over R
there are inversive spaces of all dimensions d, each of which
gives an infinite Steiner 3-design -- namely, the d-sphere with
its circles -- and the derived 2-design is R^d with its lines.
But once d>2 there's no directly analogous construction in the
finite case: R has no algebraic extension of degree d, while
quadratic forms in d+2>4 variables over a finite field don't work
because they have isotropic lines whereas the Euclidean sphere
contains no Euclidean lines.

Feb. 22 -- intro to strongly regular graphs (chapter 2)

Def. 2.1 (p.29): graph G = (V,E) where V is a finite set of "vertices"
(singular = "vertex") and E is a collection of two-element
subsets of V ("edges").  Equivalently, a finite set with a
relation that is symmetric and never reflexive.  So we're
dealing only with undirected graphs -- edge {v,v'} is the same as
{v',v} -- without loops {v,v'} or multiple edges.  We say v is
adjacent to v', or a neighbor of v', in the graph iff
{v,v'} is an edge; the latter term suggests neighborhood of v =
set of all vertices v' adjacent to v, denoted G(v).  Also we can say
v is "incident" with an edge e iff v is one of its two vertices.
[Isomorphism and automorphism of graphs as expected: isomorphism
G=(V,E) → G'=(V',E') is a bijection V → V' that induces a bijection
E → E'; if G=G' this is an automorphism, and automorphisms form a group.]

So a graph is at least a 0-(n,2,#E) design, and never a 2-(n,2,λ)
design except in the trivial cases of the null graph (E is empty, λ=0)
or the complete graph (E consists of all 2-element subsets, λ=1).
Graphs that are 1-(n,2,d) designs are called regular of degree d.
(In general the  degree  of a vertex v of G is the number of edges
containing it; the text calls this the "valency" (p.30), which makes
some sense if you think about organic chemistry and forget double bonds.
So a graph is regular iff all vertices have the same degree.)  But
we already know that we don't expect to do much with 1-designs.
How to impose more structure than t=1 (too flabby, except for degree
1 or 2 and their complements) but less than t=2 (only trivial examples)?

As suggested by the Petersen graph:

Def. 2.4 (p.32) a graph G that is neither null nor complete is
strongly regular iff the number of common neighbors of any two
vertices v,v' depends only on whether v and v' are equal, adjacent or

In the first case that number is just deg(v) so the graph must be
regular.  So we have two parameters: n=#V, k=degree.  The other two
cases give us two more parameters.  We say the graph is regular with
parameters (n,k,λ,μ) if:

n vertices;
regular of degree k;
any two adjacent vertices have λ common neighbors;
any two non-adjacent vertices have μ common neighbors.

[NB: i) excluding null or complete graphs relieves us from the
conundrum of an ill-defined λ or μ respectively.
ii) The book uses Γ, and you're welcome to do so too, but
G is easier to type or TeX (though no easier to handwrite).
iii) I use American spellings but you won't be penalized for
using the text's British spellings such as "neighbours" ;-) ]

Examples:

The complement of G@ of a graph G = (V,E) is (V,E@) where
E@ is the set of all two-element subsets of V not in E.
(Same as the complement of a t-design.)  G is regular of degree k
iff G@ is regular of degree #V-k-1.  G is strongly regular with
parameters (n,k,λ,μ) iff G@ is strongly regular with parameters
(n, n-k-1, λ@, μ@) with

λ@ = n-2 + μ - 2k,
μ@ =  n + λ - 2k

on the present problem set.  As the text notes, since λ@ and μ@ are
nonnegative we must have n ≥ 2k-λ, n ≥ 2k - μ + 2.)

(2.8)
i) The "triangular graph" T(m) has (m^2-m)/2 vertices, indexed by
2-element subsets of an m-element set S; two are adjacent iff
they have an element in common.  (So the complement has two pairs
adjacent if disjoint.)  Parameters: ((m^2-m)/2, 2m-4, m-2, 4) [why?].
We must take m≥4, else the graph is complete (and also null if m<3...).
T(4) is the octahedron, complement of 3.K_2:  12--34  13--24  14--23.
T(5) is the complement of the Petersen graph, as you can check from
its labeling in the introductory handout.
These examples may be misleading: for m large enough T(m) has smaller
degree than its complement (how large is large enough?).  See the
second picture on p.35 (Fig. 2.3) for T(9), and note the convention
(p.34) for drawing this graph so the picture doesn't become an ugly clutter.
Automorphism group contains S_m, and usually equal to it, though with a
couple of exceptions -- trivial for m=2, a bit more interesting for m=4.
We'll use this to study the structure of S_m later in the course.

ii) "square lattice graph" L_2(m): vertices = S x S with #S = m;
adjacent iff common coordinate; parameters (m^2, 2m-2, m-2, 2).
Why doesn't S x T work if #S does not equal #T?  Must have m>1;
L_2(2) is a 4-cycle and the complement of 2.K_2 (the only cycles
that are strongly regular with our definitions are the 4- and 5-cycle);
for L_2(3) see Figure 2.2 (p.34); this graph is its own complement
(Problem 5ii = page 45, exercise 4ii).  Automorphism group?
It contains (and we'll soon easily show it equals) the wreath product
of S_m with S_2, with 2*m!^2 elements.

iii) (2.9, p.34-35) for r>1 and m>1 the disjoint union r.K_m of
r complete graphs of order m is strongly regular with parameters
(rm, m-1, m-2, 0) -- the only strongly regular graphs with μ = 0
(problem 2).  See page 34-35 for some further quaint terminology
involving some of these graphs and their complements.

iv) (2.10, p.35: what happens to Paley's construction of Hadamard
matrices when q is 1 mod 4?)  If q is a prime power congruent to 1 mod 4:
Paley graph P(q) with vertices V=k=F_q and x,y adjacent iff x-y is
a nonzero square (recall -1 is a square here so this relation is symmetric).
Strongly regular with parameters (q, (q-1)/2, (q-5)/4, (q-1)/4).  Proof is
problem 5 of homework 4 (= CvL problem 6 on page 45).  First few examples:
P(5) = pentagon; P(9) = L_2(3).

[in class we did this in the order iii, i, ii, and postponed iv = Paley
till Wednesday.]

As with 2-designs, we aim to describe, at least in some cases,
which parameters (n,k,λ,μ) are feasible, and to describe
an easy algebraic condition:

Proposition 2.6 (p.33): If a strongly regular graph has parameters
(n,k,λ,μ) then

k (k-λ-1) = (n-k-1) μ.

Proof: double count, of course.  Fix x, count edges {y,z} where
y is a neighbor of x but z isn't (and does not equal x either).
There are k choices for y; for each of them there are k neighbors,
of which one is x and λ are the common neighbors of x and y,
so there are k-λ-1 choices for z.  On the other hand there are
n-k-1 choices for z, and for each of them there are μ choices for y, QED.

You should verify that the parameters of G@ satisfy this necessary condition
iff those of G do, and that the parameters of the graphs we've seen so far
(triangular, square lattice, r.K_m, and Paley) satisfy it as well.

Next time we'll introduce an adjacency matrix of a graph, and use it
to obtain a further necessary condition on n,k,λ,μ that is
considerably subtler and quite powerful -- e.g. it's the source of the
result noted in the introductory lecture that if there is a Moore graph
of degree d then d is in {2, 3, 7, 57}.

Feb. 24 -- the adjacency matrix and the integrality condition (p.36-38)

Let G=(V,E) be a graph with n vertices.  Choose a labeling v_1,...,v_n
of the vertices.  A basic construction for much of graph theory:
The adjacency matrix A=A(G) is the matrix whose (i,j) entry a_{i,j}
is the number of edges from v_i to v_j.  As with the incidence matrix
of a design, this will turn out to be much more than mere bookkeeping.
Strictly speaking A depends not just on G but on the labeling, but
different labelings yield similar matrices  P^{-1} A P  for some
permutation matrix P (more on this below).  Also:

The entries a_{i,j} are nonnegative integers (this might change for
weighted graphs, but we're not going in that direction).

No loops: the diagonal entries a_{i,i} are all zero.  (In particular
the trace of A is zero.)

Edges are undirected:  A is symmetric.  So we can use results special to
real symmetric matrices, notably the decomposition of R^n as an
orthogonal direct sum of eigenspaces.

No multiple edges: each a_{ij} is either 0 or 1.

Since we use {1,2,...,n} to index both vertices and rows/columns,
it's useful to think of the (i,j) entry a_{i,j} as being really the
(x,y) entry where  x = v_i,  y = v_j.  This makes it canonical:
A is really a linear operator (self-transformation) on a vector space R^V
with an orthogonal basis e_x (x in V), and it takes e_x to the sum of e_y
over y in the neighborhood of x -- morally speaking it takes x to G(y).
For example, the degree of x is the inner product of Ae_x with the
all-1's vector \j, which (since A is symmetric) is also the inner product
of e_x in A\j.  A graph is regular of degree k iff A\j=k\j, i.e. \j is a
k-eigenvector.  The adjacency matrix of the complementary graph G@ is
J-I-A (where J is the all-1's square matrix of order n, as before).

So what does A^2 do?  It takes e_x to the sum of e_y, and then each
e_y to a sum of its e_z's; so the (x,z) entry is the number of paths
(x,y,z) of length 2 (note that x=z is possible).  Likewise the (x,x')
entry of A^3 is the number of length-3 paths (x,y,z,x') (again with
repeats and trackbacks allowed), etc.  For that matter the (x,y) entry
of A^1 is the number of length-1 paths, i.e. the number of edges {x,y};
and the (x,y) entry of A^0 is 1 if x=y and 0 else, so it does behave
like the number of "length-0 paths"...  For an undirected graph, the
length-m paths from x to x' are in bijection with the length-m paths from
x' to x (just retrace the path backwards), so A^m is symmetric, as
it should be since A is.

Now we know from linear algebra that we can analyze A^k via the
"spectrum" (i.e. eigenvalues) and eigenspaces of A.  This is one reason
why the adjacency matrix and its spectrum is such an important graph invariant.
[Note that the spectrum really is an invariant: reindexing the vertices
changes A to a similar matrix but does not change the spectrum; equivalently,
it's just a different indexing of the coordinates for the linear operator
on R^V.]  A further example: the diagonal entries of A^m are the number of
closed paths (x_1,x_2,...,x_m) of length m going through a given vertex x_1;
thus the sum is the number of closed paths with no restriction on the x_m
(and with a choice of initial point x_1 and direction, e.g. each pentagon
counts 10 times).  But the sum of the diagonal entries of a matrix is its
trace, and the trace of A^m is the sum of the m-th powers of its eigenvalues
counted with multiplicity.

There's even a remarkably fruitful analogy with the spectrum of the
Laplacian in analysis (the motivation is that the Laplacian can be
visualized as taking x to a(x)-x, where a(x) is the average of an
infinitesimal neighborhood of x); this connection has been productive
in both directions, with ideas and results in graph theory suggesting
analogues in analysis -- some proved, some open -- and vice versa.

===

Back to the adjacency of a graph and its spectrum.
It's particularly nice when A is a strongly regular graph.  We already saw
that A is regular of degree k iff A\j=k\j; as happened in Chapter 1, this
is tantamount to AJ=kJ, and since here A and J are symmetrical we deduce

(p.37, 2.14)  A J = J A = k J.

If G is strongly regular then we also get to describe A^2: its (x,z) entry
is the number of paths (x,y,z), which is just the number of common neighbors
y of x and z.  And we already know what that is:

k if x=z;
λ if x is adjacent to z; and
μ if x is disjoint from z.

This means

(p.37, 2.13)  A^2 = k I + λ A + μ (J-I-A).

Conversely a graph is strongly regular iff it satisfies (2.13) and (2.14)
(and is neither complete nor null).  Applying (2.13) to \j yields

k^2 = k + λ k + μ (n-k-1),  i.e.  k (k-λ-1) = μ (n-k-1)

as seen already (2.6).  Since \j is an eigenvector and A is symmetric,
A acts on the orthogonal complement of \j (recall the usual argument:
if ⟨u,\j⟩ = 0 then ⟨Au,\j⟩ = ⟨u,A\j⟩ = 0 because A\j is a multiple of \j).
This orthogonal complement is sometimes denoted R^V_0: it's the space of
vectors in R^V whose coordinates sum to zero.

What could be the eigenvalues of this operator on R^V_0?
Since the letter λ is already in use, let ρ be an eigenvalue, and u
a (nonzero) eigenvector, so  Au = ρu.  Since R^V_0 is the kernel of J
we have Ju=0, so (2.13) yields

ρ^2 u = (k + λρ - μ(ρ+1)) u

and since u is nonzero this is equivalent to the quadratic equation

ρ^2 - (λ-μ) ρ + (μ-k) = 0.

let r and s be the roots.  Note that they are always real -- as they
must be for a self-adjoint transformation -- because  r s = μ - k ≤ 0.
Moreover they're distinct, else λ=μ=0 and we have a null graph.
So we may, and always do without loss of generality, order them so r>s:

r = (λ - μ + \sqrt(D)) / 2,
s = (λ - μ - \sqrt(D)) / 2.

where  D = (λ-μ)^2 + 4 (k-μ).

Let f and g be the multiplicities.  We compute them by solving
linear equations: since R^V_0 is the direct sum of the r- and s-eigenspaces,
we compare dimensions to get  f + g = n - 1;  and since A has trace zero,
fr + gs + k = 0  (remember that A also has the 1-dimensional k-eigenspace
spanned by j).  These equations are independent because r and s are
distinct, and we find an elementary if somewhat offputting formula
(bottom of page 37):

f, g = (1/2) ( n - 1 ± ((n-1)(μ-λ) - 2k) / sqrt(D) )

with D as above.

Theorem (p.37, 2.16 = integrality condition)  f and g are
nonnegative integers.

[Check that this is the case in each of our arsenal of examples so far.
How are the eigenvalues r,s and multiplicities f,g of the complementary
graph related with those of G?]

It almost follows that D is a square; that is already a strong
condition, and already implies that f and g are rational -- which is
why Theorem 2.16 is sometimes called the rationality condition.
Why "almost"?  Because it could be that the numerator vanishes,
i.e. that (n-1)(μ-λ) = 2k !  This can indeed happen, and
already is the case for the pentagon with (n,k,λ,μ)=(5,2,0,1)
(and indeed for all Paley graphs, of which the pentagon is the first
example).  In that case we say G is of Type I.  We then have

n = 1 + 2k/(μ-λ)

but also (since G is not complete)

n > 1 + k

so the denominator μ - λ is positive but less than 2.
Hence  λ = μ - 1  and  n = 1+2k; the condition
k (k-λ-1) = μ (n-k-1) then yields  k = 2μ  so

Type I ⇔ (4μ + 1,  2μ,  μ - 1,  μ)

(and D = n = 4μ+1,  f=g=2μ), as with Paley.  Similar to BRC (Bruck-Ryser Chowla,
Thm. 1.21 on p.7), we then have (but don't prove) a further condition,
here due to Van Lint and Seidel 1966, that forces n=4μ+1 to be a sum of
two squares -- so for n<45 we get 5, 9, 13, 17, 25, 29, 37, 41, all
prime powers so there are Paley graphs, while 21 and 33 are excluded;
but 45 is allowed, and -- unlike the situation with finite projective planes
-- actually arises (Mathon 1975).

If not Type I then D is a square; such graphs are said to be of Type II.
These are not mutually exclusive: already L_2(3) = P(9) has both
properties (in general Type I is also Type II iff n is a square).

Feb. 26 -- Moore graphs; two more conditions: "absolute" and Krein (pages 41-42)

Moore graphs: Suppose G is a regular graph of degree k on n vertices.  Then:

G has diameter at most 2 ⇒ n ≤ k^2 + 1;
G has girth at least 5 ⇒ n ≥ k^2 + 1;
Equality in either implies both conditions hold.

In the case of equality we say G is a Moore graph
of girth 5.  (In the last problem of PS3 we gave a similar
analysis of minimal graphs of degree d and girth 6.
For similar results for other values of the girth, see e.g.
Bollobás's book Extremal Graph Theory.)  Equivalently,
a Moore graph of degree 5 is a strongly regular graph with
parameters (k^2+1, k, 0, 1).

Recall: the adjacency matrix A of a strongly regular graph with
parameters (n,k,λ,μ) satisfies A\j = k\j and

(p.37, 2.13)  A^2 = k I + λ A + μ (J-I-A).

Thus any eigenvalue ρ of an eigenvector orthogonal to \j is

ρ^2 u = (k + λ ρ - μ(ρ+1)) u

whence the eigenvalues are the distinct real numbers

r = (λ - μ + \sqrt(D)) / 2,
s = (λ - μ - \sqrt(D)) / 2.

where  D = (λ-μ)^2 + 4 (k-μ),

with  multiplicities

f, g = (1/2) ( n - 1 ± ((n-1)(μ-λ) - 2k) / sqrt(D) )

with D as above.  Hence

Theorem (p.37, 2.16 = integrality condition)  f and g are
nonnegative integers.

Example (see exercise 10, page 46): a Moore graph (of girth 5)
is strongly regular with parameters (k^2+1, k, 0, 1).  So Type I
iff k=2 (seen already), and otherwise D = (0-1)^2 + 4(k-1) = 4k-3 is
a square, necessarily odd so 4k-3=(2m+1)^2 and k=m^2+m+1 for some m>1.
m=1 and m=2 yield k=3 (Petersen) and k=7 (Hoffman-Singleton) respectively.
Any m is allowed by rationality, but integrality limits us to m=1,2,7
so k=3, 7, or 57.  Here the numerator  n - 1 + ((n-1)(μ-λ) - 2k) is
k^2 - 2k = (m^2+m+1)(m^2+m-1), while sqrt(D) = 2m+1, so we need

2m + 1 | (m^2+m+1)(m^2+m-1).

We've already seen the technique: write the RHS as a multiple of the LHS plus
a remainder, which is a constant of which 2m+1 must be a factor.  Trouble is
the remainder here is -15/16 (the value at the root m=-1/2).  OK, but if we
multiply the RHS by 16 then it's still a multiple, and then

16(m^2+m+1)(m^2+m-1) = (8m^3+12m^2+2m-1) (2m+1) - 15

so  15 | 2m+1,  whence 2m+1 is 1, 3, 5, or 15, so m = [0,] 1, 2, or 7
as claimed.  We can check that in each case the division by 16, and
later by 2, introduces no denominators -- indeed the division by 16
had to work because 2m+1 is odd -- so the integrality criterion allows
any of 2, 3, 7, 57 and as noted already the first three are known to
arise, each uniquely up to automorphisms, and the last is a famous
open problem.

======================================================================

Two more conditions.  The first arises from the observation that
we can project the n standard unit vectors to the r- and s-eigenspaces,
obtaining a configuration of vectors of the same length with only
two different inner products (other than the squared length), depending
on whether the corresponding vertices are adjacent or disjoint.
(The text outlines a difference construction.)  Indeed if we write each
e_x as (1/n) \j + u_x + v_x  with u,v in the r- and s-eigenspace we have

1 = ⟨e_x,e_x⟩  =  1/n  +   ⟨u_x,u_x⟩ +  ⟨v_x,v_x⟩
0 = ⟨e_x,Ae_x⟩ =  k/n  +  r⟨u_x,u_x⟩ + s⟨v_x,v_x⟩

which determines ⟨u_x,u_x⟩ and ⟨v_x,v_x⟩ likewise for distinct x and y

0    = ⟨e_x,e_y⟩  =  1/n  +   ⟨u_x,u_y⟩ +  ⟨v_x,v_y⟩
a_{x,y} = ⟨e_x,Ae_y⟩ =  k/n  +  r⟨u_x,u_y⟩ + s⟨v_x,v_y⟩

(where the entry a_{x,y} of A is 1 or 0 according as x,y are adjacent or
disjoint), and this determines ⟨u_x,u_y⟩ and ⟨v_x,v_y⟩ in terms of a_{x,y}.

Theorem (2.23+, p.14) [Delsarte-Goethals-Seidel 1977]: if there is
a set S of unit vectors in some inner product space R^f for which
⟨v,v'⟩ (v,v' distinct) takes on only two distinct values then #S ≤ f(f+3)/2.

Proof: Let b,c the two values of ⟨v,v'⟩; necessarily b,c < 1.
[The text uses Greek letters β, γ for our b,c.]
Let f_v be the quadratic polynomial functions on R^f:

f_v(x) = (⟨v,x⟩ - b) (⟨v,x⟩ - c) + b c (⟨x,x⟩ - 1)

on R^f.  Thanks to the last term they live in a space of dimension
f(f+3)/2 [the constant term vanishes].  But evaluation on v' in S
shows that they are linearly dependent.  Hence their number |S|
is at most f(f+3)/2 as claimed.

[Similarly, for m distinct inner products there's an upper bound on |S|
that grows as f^m/m!.  The best bound of this form requires some
finesse with adjustments analogous to "+ b c (⟨x,x⟩ - 1)"
but more involved and we won't say more about it here.

Yet another variant: suppose we have a set S of n pairs {v,-v} of
unit vectors in R^f, with only one pair {c,-c} of inner products
other than 1 and -1.  Then  f_v(x) = ⟨v,x⟩^2 - c^2 + c^2 (⟨x,x⟩ - 1)
is an even quadratic polynomial without constant term (and thus
homogeneous) that vanishes on all of S except {v,-v}, so the number of
such pairs is at most the dimension (f^2+f)/2 of the space of
homogeneous quadratic polynomials in f variables.  Here there are
more examples of configurations attaining the bound, starting with the
3 opposite pairs of vertices of a regular hexagon (f=2) or the 6 of
a regular icosahedron (with f=3).

Back to strongly regular graphs...]

Corollary ("absolute bound"): in a strongly regular graph n is at most
min(f(f+3)/2, g(g+3)/2).

Proof: apply 2.23 to the normalized vectors ⟨u_x⟩/|u_x| in R^f and
⟨v_x⟩/|v_x| in R^g.

Example: the pentagon gives an example of equality with f=2
(it really is a regular pentagon or pentagram in R^2 !).
The text gives another example where otherwise plausible
parameters are excluded.  In general equality is rare because
f and g are typically both near their average (n-1)/2.
I think only two further examples are known: (f,n)=(6,9)
[the Schläfli graph or its complement, related with the
exceptional E6 root system -- coming attraction] and (22,275)
[the McLaughlin graph or its complement, related with a sporadic
simple group in the Conway/Leech family; that's too exotic for us].

The Krein condition or Krein bound (Thm. 2.26, p.42) exploits:

(i) a formula for the projection  E_r: x → u_x  as a linear
combination of J, I, and A, and

(ii) a trick involving Kronecker products.

These are individually of interest but I have no special wisdom to
impart on the final result, except that it lets us exclude a few more
possible parameters as you're doing for Exercise 3 on page 45 (= prob.4).
For the record the bound says  (r+1) (k+r+2rs) ≤ (k+r) (s+1)^2
and likewise with r and s switched.

(i) since we have

Je_x = \j
Ie_x = (1/n) \j + u_x + v_x
Ae_x = (k/n) \j + r u_x + s v_x

and r,s are distinct, we can extract the map  E_r: x → u_x  as an
explicit linear combination of J, I, A, namely

[((k-s)/n) J + (sI-A)] / (s-r).

In particular the (v,v') entry again depends only on whether v,v' are
the same, adjacent, or disjoint.  But this matrix is positive semidefinite:
⟨v, E_r v⟩ ≥ 0 for all v (equality iff v in the span of \j and the s-eigenspace).
Now use:

Lemma 2.25 (p.42): if a matrix M=(m_{ij}) is positive semidefinite then
so is  M o M = (m_{ij}^2).

Proof: M o M is symmetric, and the self-adjoint linear transformation
associated to it is the restriction to a coordinate subspace of the
tensor square of the transformation M, QED.

Now write M o M as a linear combination of J, I, A and compute its
eigenvalues (it acts on each eigenspace of A by scalar multiplication),
obtaining the Krein bound from the condition that these eigenvalues
be nonnegative.

Hint / Word to the wise: the decomposition  x = (1/n) \j + u_x + v_x
and the associated inner-product computations have other uses; e.g. try
the sum of u_x or v_x over x in a (co-)clique.