Number Theory: An Introduction to Mathematics

3 The Art of Weighing 235

where+and−stand for 1 and−1 respectively, thenAtA= 4 I 3. With this experi-
mental design the individual weights may all be determined with twice the accuracy
of the weighing procedure.
The next result shows, in particular, that if we wish to maximize det(AtA)among
then×mmatricesAwith all entries 0,1or−1, then we may restrict attention to those
with all entries 1 or−1.

Proposition 8Letα,βbe real numbers withα<βand letSbe the set of all n×m
matrices A=(αjk)such thatα≤αjk≤βfor all j,k. Then there exists an n×m
matrix M=(μjk)such thatμjk∈{α,β}for all j,k and

det(MtM)=max

A∈S

det(AtA).

Proof For anyn×mreal matrixA, either the symmetric matrixAtAis positive
definite and det(AtA)>0, orAtAis positive semidefinite and det(AtA)=0. Since
the result is obvious if det(AtA)=0foreveryA∈S, we assume that det(AtA)> 0
for someA∈S. This impliesm≤n. Partition such anAin the form

A=(vB),

wherevis the first column ofAandBis the remainder. Then

AtA=

[

vtvvtB

Btv BtB

]

andBtBis also a positive definite symmetric matrix. By multiplyingAtAon the left by
[
I −vtB(BtB)−^1
OI

]

and taking determinants, we see that

det(AtA)=f(v)det(BtB),

where

f(v)=vtv−vtB(BtB)−^1 Btv.

We can writef(v)=vtQv,where

Q=I−P, P=B(BtB)−^1 Bt.

FromPt =P = P^2 we obtainQt = Q= Q^2. HenceQ= QtQis a positive
semidefinite symmetric matrix.
Ifv=θv 1 +( 1 −θ)v 2 ,wherev 1 andv 2 are fixed vectors andθ∈R,thenf(v)is
a quadratic polynomialq(θ)inθwhose leading coefficient

vt 1 Qv 1 −v 2 tQv 1 −v 1 tQv 2 +v 2 tQv 2

is nonnegative, sinceQis positive semidefinite. It follows thatq(θ)attains its maxi-
mum value in the interval 0≤θ≤1 at an endpoint.