Deza M.M., Laurent M. Geometry of Cuts and Metrics
Подождите немного. Документ загружается.
334
Introduction
for all
i,
j E V
n
. We also say
that
the
sets
AI,
.
..
,An
form
an
h-labeling of
d.
Clearly, if M
is
an
h-realization
matrix
of
d,
we
can
assume
without
loss
of
generality
that
a row
of
M is
the
zero vector.
This
amounts
to
assuming
that
one
of
the
points
is
labeled by
the
empty
set in
the
corresponding h-Iabeling of
d.
Let B
denote
the
collection
of
subsets of
Vn
whose incidence vectors are
the
columns
of
M; B
is
a multiset, i.e., it
may
contain several
times
the
same
member.
Then,
(a)
is
equivalent to
(c)
d = L 8(B).
BEB
This
shows
again
(recall
Proposition
4.2.4)
that
hypercube
embeddable
semi-
metrics
are exactly
the
semimetrics
that
can
be
decomposed as a nonnegative
integer
combination
of
cut
semimetrics.
If
(c) holds,
we
also say
that
I:BEB
8(B)
is a Z+-realization
of
d.
It
will
be
convenient to use
both
representations (a) (or
(b))
and
(c) for a
hypercube
embeddable
semimetric
d.
So, we
shall
speak
of
a
hypercube
embedding
(or of
an
h-Iabeling of d),
and
of a Z+-realization of
d.
This
amounts
basically to looking either to
the
rows,
or
to
the
columns of
the
matrix
M.
Recall
that
d is said to
be
h-rigid if d has a unique Z+-realization or, equiv-
alently, if
d has a unique (up to a
certain
equivalence)
hypercube
embedding.
Equivalent
embeddings
were defined in Section 4.3;
we
remind
the
definition
below. Let
B
be
a collection of subsets of
Vn
satisfying (c).
If
we
apply
the
following
operations
to
B:
(i) delete or
add
to B
the
empty
set
or
the
full set V
n
,
(ii) replace some B E B by its complement
Vn
\
B,
then
we
obtain
a new set family
B'
satisfying again (c). We
then
say
that
Band
B' are equivalent (or define equivalent hypercube embeddings), as
they
yield
the
same
Z+-realization of
d.
M.M. Deza, M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics 15,
DOI 10.1007/978-3-642-04295-9_22, © Springer-Verlag Berlin Heidelberg 2010
Chapter
22.
Rigidity
of
the
Equidistant
Metric
In
this
chapter
we
study
h-rigidity of
the
equidistant metric 2t1
n
for
n,
t integers,
n
~
3, t
~
1.
As was already mentioned, 2t1
n
is hypercube embeddable. Indeed,
a
hypercube
embedding
of 2t1
n
is
obtained
by labeling
the
n
points
by
pairwise
disjoint sets, each of cardinality
t.
This
embedding is called
the
star embedding
of
2t1
n
;
it
corresponds
to
the
following Z+-realization:
(22.0.1)
2t1
n
= L t8({i}),
l:'Oi:'On
called
the
star realization of 2t1
n
•
The
word "star" is used since each
cut
semi-
metric
8(
{i})
takes nonzero values
on
the
pairs (i,
j)
for j E
{I,
...
,n}
\ {i}, i.e.,
on
the
edges of a
star.
Let us call a hypercube embedding of
2t1
n
nontrivial if
it
is
not
equivalent
to
the
star
embedding, i.e., if it provides a Z+-realization of
2t1
n
distinct
from
the
star
realization (22.0.1). Hence,
the
metric
2t1
n
is h-rigid
if
it
has no nontrivial hypercube embedding.
For
n = 3,
the
equidistant
metric
2t13 is h-rigid.
It
is,
in
fact, f1-rigid since
the
cut
cone
CUT
3
is a simplex cone (indeed, CUT3 is generated
by
the
three
linearly
independent
vectors 8( {i}) for i =
1,2,3).
For n =
4,
the
metric
2t14 is
not
h-rigid. Indeed, besides
the
star
realization from (22.0.1), 2t14
admits
the
following Z+-realization:
(22.0.2)
2t14
=
t(8({1,2})
+ 8({1,3}) + 8({1,4}));
214 has no
other
Z+-realization.
In
fact, 2t1
n
is not f1-rigid for any n
~
4 as,
for instance,
2t1
n
=
_t_
L
8({i,j})
n - 2 l:'Oi<j:'On
is a decomposition of 2t1
n
as a nonnegative
sum
of
cut
semimetrics which is
distinct
from
the
decomposition
in
relation (22.0.1).
On
the
other
hand,
as
we
see below, if n is large
with
respect
to
t,
then
2t1
n
is h-rigid.
There
is
an
easy way of constructing nontrivial hypercube embeddings for
the
metric
2t1
n
,
using (partial) projective planes. Let us first recall
their
definition.
A (finite)
projective plane
of
order t, commonly
denoted
by
PG(2,
t),
consists
of a
pair
(X,
.c),
where X is
the
set
of points
and
.c
is a collection of subsets
of
X,
called lines, satisfying:
336
Chapter
22.
Rigidity
of
the
Equidistant Metric
(i) each line
L E £ has cardinality t +
1,
(ii) each point
of
X belongs to t + 1 lines, and
(iii) any two distinct points of
X belong to exactly one common line.
Hence, there is the same number
t
2
+ t + 1 of lines and points in
PG(2,
t).
Moreover,
(iv) any two distinct lines
in
£ intersect in exactly one point.
In
the
case t 1 there are three points and three lines which are the possible
pairs of points.
We
shall consider projective planes of order t
~
2.
It
is well-
known
that
projective planes exist
of
any order t
that
is
a prime power.
It
is
one of
the
major open problems
in
combinatorics to determine what are the
possible values for the order of a projective plane.
It
is
known
that
no projective
plane exists
with
order 6 or
10;
the case t =
10
was settled using computer by
Lam, Thiel
and
Swierzc
[1989].
(See, e.g., Hall
[1967]
for more information on
projective planes.)
A
partial projective plane
of
order t
is
a
pair
P =
(X,
£)
satisfying (i)
and
(iv) above.
We
assume
that
every point lies on
at
least one line and P is said
to
be trivial if there exists a point lying on every line.
It
is
easy
to
see
that,
if
P
is
nontrivial,
then
1£1
:S
t
2
+ t + 1
with
equality if
and
only
if
P is a projective
plane (of order
t);
moreover, every point is on
at
most t + 1 lines. Clearly, a
nontrivial
partial
projective plane of order t 1 has
1£1
:S
3 lines.
Hall
[1977]
shows
that
every nontrivial
partial
projective plane
with
suffi-
ciently many lines can be extended to a projective plane. Namely,
Theorem
22.0.3.
Let
P =
(X,
£)
be
a nontrivial partial projective plane
of
order t
~
2 with
1£1
~
t2
- 1 lines. Then, P can
be
extended to a projective plane
Pl
(Xl,£l)
of
order t; that is, X
~
Xl
and £
~
£1. I
Let P =
(X,
£)
be a
partial
projective plane of order t
with
n
:=
1£1
lines.
Then,
P yields a hypercube embedding
of
2tll
n
;
namely, by labeling the elements
of
Vn
by
the
lines in
£.
Note
that
this embedding
is
nontrivial precisely if P
is nontriviaL Therefore, the existence of a nontrivial partial projective plane of
order
t ensures
that
the metric 2tnn is not h-rigid. (Recall
that
n
:S
t
2
+ t + 1 in
this
case.)
It
ensures, moreover,
that
the metric
2tln+l
is
not h-rigid. Indeed,
let
Z be a set
of
cardinality t - 1 disjoint from
X.
If
we
label the elements
of
Vn
by
the
sets L U Z for L E £ and the remaining element of Vn+l \
Vn
by the
empty set,
then
we
obtain a nontrivial hypercube embedding of 2tn
n
+l.
In
fact, for n large enough, the existence of a nontrivial hypercube embedding
of
2t1
n
depends only on the existence of a (partial) projective plane
of
order t
with
a suitable number of lines.
The
following two theorems were proved by Hall
[1977].
Theorem
22.0.4.
Let
n
~
t
2
~
4.
The
metric
2t1
n
is
not
h-rigid
if
and only
if
n
:S
t
2
+ t + 2
and
there exists a projective plane
of
order t.
Chapter
22.
Rigidity
of
the
Equidistant
Metric
337
Theorem
22.0.5.
Let n
2:
!(t
+
2)2
with t
2:
2.
If
2tln
is not h-rigid then
there exists a nontrivial partial projective plane
of
order t with n - 1 lines.
In
fact,
Theorem
22.0.4
can
be
derived easily from
Theorems
22.0.3
and
22.0.5,
as we
indicate
below. As
an
application
of
Theorem
22.0.5
we
have
the
following
Theorems
22.0.6
and
22.0.7 which were
obtained
earlier, respectively, by Deza
[1973b]
and
van
Lint
[1973].
(The
case t = 1
in
Theorem
22.0.6 is
not
covered
by
Theorem
22.0.5
but
can
be
very easily checked directly.)
Another
case of
h-rigidity for
the
metric
2tln
will
be
given
later
in
Corollary 23.2.5.
Theorem
22.0.6.
If
n
2:
t
2
+ t + 3 and t
2:
1, then
2tln
is h-rigid, i.e., the
only Z+-realization
of
2t1
n
is the star realization from (22.0.1). I
Theorem
22.0.7.
Let n = t
2
+ t + 2 with t
2:
3.
If
the metric
2tln
is
not
h-rigid, then there exists a projective plane
of
order t.
I
Proof
of
Theorem 22.0·4.
Let
n
2:
t
2
2:
4
and
suppose
that
2tln
is
not
h-rigid.
We show
that
there
exists a projective
plane
of order
t.
If
t
2:
5,
this
follows
immediately
from
Theorems
22.0.3
and
22.0.5, as t
2
2:
!(t
+ 2)2;
on
the
other
hand,
projective planes
are
known
to
exist for
any
order
t E
{2,3,4}.
We now
verify
that
n
::;
t
2
+ t +
2.
For this, note
that
n
2:
t
2
+ t + 3 implies n
2:
!(t
+ 2)2;
then
a
nontrivial
partial
projective plane of
order
t
with
n - 1 lines exists (by
Theorem
22.0.5), which implies
that
n - 1
::;
t
2
+ t + 1, yielding a
contradiction.
Conversely,
it
is
immediate
to
verify
that
a projective
plane
of
order
t yields a
nontrivial
hypercube
embedding
of 2t1
n
when
n
2:
t
2
•
I
We now
turn
to
the
proof
of
Theorem
22.0.5.
We
will use
the
following
notation.
Let
M
be
a
binary
n x m
matrix
which is
an
h-realization
matrix
of
2tln'
Without
loss of generality,
we
can
suppose
that
the
first row of M is
the
zero vector.
Then,
every
other
row
of
M has 2t
units
and
any two rows
(other
than
the
first one) have t
units
in
common. Given a nonzero row
Uo
of
M,
M
EfJ
Uo
denotes
the
matrix
obtained
from M by replacing each row by
its
sum
modulo
2
with
uo.
Clearly, M
EfJ
Uo
is again
an
h-realization
matrix
of 2t1
n
with
one zero row. Moreover, M
EfJ
Uo
provides a nontrivial
hypercube
embedding
of
2t1
n
if
and
only if
the
same
holds for
M.
We
start
with
a
preliminary
result
on
the
number
r of
units
in
the
columns
of
M;
the
inequality
r(n
- r)
::;
nt
in
Lemma
22.0.8 was proved
by
Deza [1973b]
and
the
equality
case was
analyzed
by Hall [1977].
Lemma
22.0.8.
Let r denote the number
of
units in a column
of
M.
Then,
r(n
-
r)
::;
nt,
implying that
min(r,n
- r)
::;
~(n
-
Jn
2
-
4nt).
Moreover, r
= I = 2t
if
r(n
- r) =
nt.
338
Chapter
22.
Rigidity
of
the
Equidistant Metric
Proof. Let w
be
a column of
M,
let r denote the number
of
l's
in
w, and
let
p denote
the
number
of
columns
of
M identical
to
w.
Let
M'
denote
the
n x (m -
p)
denote
the
submatrix obtained from M by deleting these p columns,
and let
d'
denote
the
distance on n points defined
by
letting
d~j
denote
the
Hamming distance between the
i-th
and
j-th
rows
of
M'.
We
can suppose
that
the
first n - r entries of
ware
equal
to
0 and its last r entries are equal
to
1.
Then,
if
1
.::;
i < j
.::;
n
r,
or n - r + 1
.::;
i < j
.::;
n,
if 1
.::;
i
.::;
n r < j
.::;
n.
Consider
the
inequality
of
negative type:
(a)
Qn(-r,
...
,-r,n
L r2Xij +
19<j:S;n-r
r,
...
,n
L
n-r+l9<j:S;n
r(n
-
r)xij
.::;
O.
As
d'
is
hypercube embeddable by construction, d' satisfies the above inequality
(recall Section 6.1).
We
deduce from it
that
pr(n - r)
.::;
nt, which implies
r(n-r)'::;nt.
From
the
latter
relation follows immediately
that
min(r,n
- r)
.::;
~(n
-
Jn
2
-
4nt).
Suppose now
that
r(n
r) =
nt.
Then, p =
1.
For each column v of M distinct
from
w, let a
v
(resp. b
v
)
denote its number
of
units in
the
first n r rows (resp.
in
the
last r rows). From
the
fact
that
d' satisfies the inequality (a)
at
equality,
we
deduce
that
ra
v
= (n - r)b
v
.
Note
that
Lav(n-r-a
v
)=
L
d~j=2t(n2r),
v
l~i<j~n-r
L bv(r - b
v
) = L
d~j
2t
(;)
,
v
n-r+l~i<j::::n
where
the
sums are taken over all columns v
of
M distinct from w. As
L~(l
v
n-r
we
obtain
that
(n~tr),.,(n2r)
=
~G),
which yields r
~.
Finally,
r(n
r)
nt,
implying n = 4t. I
Proof
of
Theorem 22.0.5. Note first
that
we
can clearly assume
that
n >
~(t+2)2
when t = 2 (as a projective plane of order 2 does exist). Let M be
an
h-realization
Chapter
22. Rigidity of
the
Equidistant
Metric
339
matrix
of
2tln
providing a nontrivial hypercube
embedding
of
2tl
n
.
We assume
that
the
first row of M
is
the
zero vector. Let T denote
the
maximum
value
taken
by min( r, n - r), where r is
the
number
of
units
in a
column
of
M.
Hence,
each
column
of M
has
either::;
T units,
or
2:
n - T units. Call a
column
heavy
if it
has
2:
n - T
units
and
light otherwise. We know from
Lemma
22.0.8
that
T(n -
T)
::;
nt, i.e., T
::;
~(n
-
vn
2
- 4nt).
Note
that
(a)
and
equality holds simultaneously in
both
inequalities. We will use
this
fact
later
in
the
proof.
Let us suppose for a contradiction
that
there
does not exist a nontrivial
partial
projective plane
of
order t
with
n - 1 lines. We claim:
(22.0.9)
1
1fT
::;
t + 1,
then
n
::;
2'(t
2
+
3t
+ 4),
(22.0.10)
1
n::;2'(t+2)2.
We first show
that
(22.0.9) holds. For this, suppose
that
T ::; t + 1
and
n >
~(t2
+
3t
+ 4).
Then,
(
c)
there
are
at
most t + 1 heavy columns.
For, suppose
that
there
are
at
least t + 2 heavy columns in
M.
Consider
the
submatrix
Y
of
M consisting
of
t + 2 heavy columns.
Then,
the
total
number
f
of
units
in Y satisfies: f
2:
(t + 2)(n -
T)
2:
(t
+ 2)(n - t -
1)
(by
counting
units
per
columns). We now count
the
units
in Y
per
rows.
If
Y
has
an
all-
ones row
then
every
other
nonzero row has
at
most t
units
and,
thus, f
::;
t + 2 +
t(n
-
2)
= (t + 2)(t +
1)
+
t(n
- t - 4). Else,
at
most
t + 2 rows in Y have
t
+ 1
units
and,
thus, f
::;
(t
+ 2)(t +
1)
+
t(n
- t - 3). In
both
cases,
we
obtain:
(t
+ 2)(n - t - 1)
::;
(t + 2)(t + 1) +
t(n
- t - 3), which
contradicts
the
fact
that
n >
~(t2
+
3t
+ 4).
This
shows (c). Next,
we
claim:
(d) Every nonzero row in
M
has
at
least t - 1
units
in
the
heavy columns.
Indeed, suppose
that
a nonzero row
Uo
of M has
at
most t - 2
units
in
the
heavy
columns.
Then,
the
matrix
M
EB
Uo
(defined as mentioned above
by
replacing
each row
in
M by its
sum
modulo 2
with
uo)
is
an
h-realization
matrix
of
2tln
having t + 2 heavy columns,
thus
contradicting (c).
Hence, M
has
t -
1,
t, or t + 1 heavy columns. Suppose first
that
M
has
t - 1 heavy columns.
Then,
by (d), each nonzero row
of
M
has
units
in all
heavy columns. Therefore,
the
submatrix
of M restricted to
the
light
columns
(and
deleting
the
first zero row) is
the
incidence
matrix
of
a nontrivial
partial
projective
plane
of
order
t
with
n
-1
lines, in contradiction
with
our
assumption.
Suppose now
that
M
has
t heavy columns.
Then,
there is a row
Uo
of
M having
exactly
t - 1
units
in
the
heavy columns (else, M would correspond
to
the
star
340
Chapter
22.
Rigidity of
the
Equidistant
Metric
embedding of
2tln)'
But,
in
this case, the
matrix
M
E9
Uo
has t + 2 heavy
columns, contradicting (c). Finally, suppose
that
there are t + 1 heavy columns.
If
some row
Uo
of
M has t + 1
units
(resp. t - 1 units) in
the
heavy columns,
then
M
E9
Uo
has
t 1 (resp. t +
3)
heavy columns;
the
first case has
just
been
excluded above
and
the
second one is forbidden by (c). Hence, every nonzero row
of
"AJ
has t
units
in
the
heavy columns. Let x denote
the
binary vector indexed
by
the
columns
of
M
and
having ones precisely in
the
positions of
the
heavy
columns.
Then,
!v!
E9
x is the incidence
matrix
of a nontrivial
partial
projective
plane of order
t
with
n lines.
We
have again a contradiction
with
our assumption.
Therefore, relation
(22.0.9) holds.
We
now verify (22.0.10). Indeed,
if
n >
Ht
+ 2)2,
then
T
.s;
t + 1 by (a)
and
thus, using (22.0.9), n
.s;
t(t2
+
3t
4)
<
t(t
+ 2)2, a contradiction.
Therefore,
we
have obtained
that
n
t(t
+
2)2
and
t
2:
3.
By (22.0.9),
this
implies
that
T
2:
t +
2.
On
the other
hand,
T
.s;
t + 2 by (a). Hence, T = t +
2.
Thus,
T(n
- T) =
nt
which, by Lemma 22.0.8, implies
that
T
~
= 2t.
That
is,
t =
2,
while
we
had
assumed
that
t
2:
3.
This
concludes
the
proof. I
Consider, for instance,
the
case t
6.
By Theorem 22.0.4,
the
metric 121n is
h-rigid
if
n
2:
36 (as
PG(2,6)
does
not
exist).
It
is, in fact, h-rigid for all n
2:
33
as
stated
in
the
next result, proved by Hall, Jansen, Kolen
and
van Lint [1977].
Proposition
22.0.11.
The equidistant metric 121n is h-rigid for all n
2:
33. I
The
h-rigidity result from Theorem 22.0.6 was extended by Erdos
and
Frankl
[1978J
to
the
class of metrics
of
the form
t;15(
{i}) for
tl,."
,tn
E
the
case
tl
= ... = tn = t corresponding
to
the case of
the
equidistant metric
2tl
n
·
Theorem
22.0.12.
Let
t
l
, .
•.
,tn
be
positive integers.
If
n is large with respect
to
max(t1,
...
,t
n
),
then the metric
~l:Si:Sn
ti15(
{i}) is h-rigid. I
M.M. Deza, M. Laurent, Geometry of Cuts and Metrics, Algorithms and Combinatorics 15,
DOI 10.1007/978-3-642-04295-9_23, © Springer-Verlag Berlin Heidelberg 2010
Chapter
23.
Hypercube
Embeddings
of
the
Equidistant
Metric
We
study
in
this
chapter
how
to
construct
various
hypercube
embeddings for
the
equidistant
metric
2t1L
n
from designs. A Z+-realization of
2t1L
n
consists of a
family
B
of
(not
necessarily distinct) subsets of
Vn
such
that
l:
b(B)
=
2t1L
n
.
BEB
Given io E V
n
,
we
can
suppose
without
loss of generality
that
io
~
B for all
B E B (replacing if necessary B by
Vn
\
B).
Then,
B is a collection of
subsets
of
V
n
-
1
satisfying:
(i) each
point
of V
n
-
1
belongs
to
2t
members
of B,
and
(ii) any two
distinct
points
of V
n
-
1
belong
to
t
common
members
of B.
Such a
set
family B is known as a (2t, t, n - 1 )-design. Therefore,
the
hypercube
embeddings
of
2t1L
n
are
nothing
but
special classes of designs.
We
review
in
Section 23.1 some known results
on
designs
and
we
state
precisely
the
link
with
hypercube
embeddings of
the
equidistant
metric
in
Section 23.2. Results
on
the
minimum
h-size of
the
equidistant
metric
are
grouped
in
Section 23.3.
We
describe all
the
hypercube
embeddings
of
2t1L
n
for
small
n
or
t
in
Section 23.4.
Much
of
the
exposition
in
this
chapter
follows Deza
and
Laurent
[1993c].
23.1
Preliminaries
on
Designs
23.1.1
(r,
A,
n)-Designs
and
BIBD's
Let B
be
a collection of
(not
necessarily distinct) subsets of V
n
.
The
sets B E B
are called blocks. Let r, k, A
be
positive integers. Consider
the
following proper-
ties:
(i)
Each
point
of
Vn
belongs
to
r blocks.
(ii) Any two
distinct
points
of
Vn
belong
to
A
common
blocks.
(iii)
Each
block
has
cardinality
k.
Clearly,
if
(ii),(iii) hold,
then
(i) holds
with
(23.1.1)
n-1
r=A--
k-1
342
Chapter
23.
Hypercube Embeddings of
the
Equidistant
Metric
and
the
total
number
b of blocks in B (counting multiplicities)
is
given by
(23.1.2)
b =
rn
=
.A
n(n
-
1)
k
k(k-l)"
The
multiset
B
is
called a (r,.A,
n)-design
if (i),(ii) hold
with
0 <
.A
< r. B
is
said
to
be
trivial if B consists of
the
following blocks:
Vn
repeated
.A
times and,
for each
i E V
n
,
the
block {i}
repeated
r -
.A
times.
In
fact, if n
is
large
with
respect
to
r
and
.A,
then
every (r,.A, n)-design
is
trivial (this follows, e.g., from
the
rigidity results
of
Chapter
22).
The
multiset
B
is
called a (n, k, .A)-BIBD if (i),(ii),(iii) hold
with
.A
>
0,
1 < k < n -
1.
(BIBD
stands
for balanced incomplete block design.) A (n,
k,
.A)-
BIBD
is
said
to
be
symmetric
if r = k holds or, equivalently,
the
number
of
blocks b is equal
to
the
number
n
of
points.
Let
B
be
a (n, k, .A)-BIBD.
Then,
the
collection
B*
:=
{Vn
\
BIB
E
B}
is
a
(n,
k'
:=
n - k,.A'
:=
b - 2r + .A)-BIBD, called
the
dual of B. (Note
that
1 < k' < n - 1
and
(n
- 1)(b - 2r +.A) =
(b
-
r)(n
- k - 1), which
permits
to
check
that
.A'
> 0.)
If
B
is
symmetric,
then
B* too
is
symmetric. For instance,
the
dual
of
PG(2,
t)
is
a symmetric (t
2
+ t + 1, t
2
,
t
2
-
t)-BIBD.
The
following result
is
due
to Ryser [1963].
Theorem
23.1.3.
Let B
be
a (r,.A,
n)
-design with b blocks. Then, b
2:
n holds,
with equality
if
and only
if
B is a
symmetric
(n, r, .A)-BIBD.
Proof. Let A denote
the
incidence
matrix
of
B,
i.e., A is
the
n x b
matrix
with
entries
ai,B
= 1
if
i E
Band
ai,B
= 0
if
i
rt.
B,
for i E V
n
,
B E
B.
Suppose
that
b <
n.
Let M denote
the
n x n
matrix
obtained
by adding n - b zero columns
to
A.
Then,
MMT
=.AJ
+ (r -
.A)1,
where J is
the
all-ones
matrix
and
1
the
identity
matrix.
One
can
check
that
the
eigenvalues
of
M
MT
are r +
(n
-
1).A
and
r -
.A
(with multiplicity n - 1),
which shows
that
M
is
nonsingular. This contradicts
the
fact
that
M has a zero
column. Hence,
we
have shown
that
b
2:
n. Suppose now
that
b = n.
We
show
that
each block of B has cardinality r. From
the
above argument,
the
matrix
A
is
an
n x n
matrix
satisfying
(a)
AAT
=
.AJ
+
(r
-
.A)1,
and
AJ
=
rJ.
Hence,
implying
23.1 Preliminaries
on
Designs
343
Therefore,
JAJ
= (An + r -
A)r-lnJ.
But,
J
AJ
=
rnJ
from (a), which implies
(
c)
r - A =
r2
- An.
Substituting
(c)
in
(b),
we
obtain
JA
=
rJ.
This
shows
that
each block
of
B has
size
r. Hence, B
is
a
symmetric
(n,
r,
A)-BlED. I
Clearly, from (23.1.2), a necessary condition for the existence
of
a
(n,
k,
A)-
BlED
is
the
following divisibility condition:
(23.1.4)
k-l
is a divisor of
A(n-l)
and
k(k-l)
is a divisor
of
An(n-l).
This
condition is,
in
some cases, already sufficient for
the
existence
of
a (n,
k,
A)-
BlED.
A
few
such cases are described
in
Theorem 23.1.5 below; assertion (i) is
proved
in
Wilson [1975]' (ii)
in
Hanani [1975]'
and
(iii)
in
Mills [1990].
Theorem
23.1.5.
(i) Suppose that (23.1.4) holds and that n is large with respect to k
and
A.
Then, there exists a
(n,
k, A)-BlBD.
(ii)
For k
:S
5, a (n, k, A)-BlED exists whenever (23.1.4) holds with the single
exception: n
= 15, k =
5,
A =
2.
For k = 6, A
2:
2,
a (n,
6,
A)-BlED exists
whenever
(23.1.4) holds with the single exception: n =
21,
A =
2.
(iii) For k =
6,
A = 1, a (n,
6,
1)-BlBD exists whenever (23.1.4) holds with the
possible exception
of
95
undecided cases (including n = 46,51,61, 81, 141,
...
, 5391, 5901). I
Two
important
cases
of
parameters
for a
symmetric
BIBD are:
(i)
The
(e
+ t +
1,
t +
1,1
)-BlBD, which is nothing
but
the
projective plane
of
order t,
denoted
by
PG(2,
t).
(ii)
The
(4t-l,
2t, t)-BlBD, also known as
the
Hadamard design
of
order
4t-1.
Recall
that
Hadamard
designs are in one-to-one correspondence
with
Hadamard
matrices. Namely, a Hadamard
matrix
is
an
n x n
±1-matrix
A such
that
AAT
=
nI.
Its
order n
is
equal
to
1,
2
or
4t for some t
2:
1.
We
can
suppose
without
loss
of
generality
that
all entries
in
the
first row
and
in
the
first column
of
A are
equal
to
1. Replace each
-1
entry
of
A by °
and
delete its first row
and
column.
We
obtain
a (4t - 1) x (4t - 1)
binary
matrix
whose columns are
the
incidence
vectors
of
the
blocks
of
a
Hadamard
design
of
order
4t
-
1.
It
is conjectured
that
Hadamard
matrices
of
order 4t exist for all t
2:
1.
This
was proved for t
:S
106. (For more information
on
Hadamard
matrices see, e.g.,
Geramita
and
Seberry
[1979]
and
Wallis [1988].)