Principles of Mathematics in Operations Research

Solutions 225

Let Cnn — Yz- Thus,

det A = an- a 22 • fe • • • (nn = au

-Q12Q21 +022011

an

012023031 + 013Q32Q21 ~ Q11023032 ~ Q13Q31022 ~ 012021033 + Q11022033

-012021 +022011

" Z '

zz

Since the denominator of one term cancels the numerator of the previous term,

det A = Z = y, aipia (^2) P2
peP
npt det [epi, eP2,..., ePn J, ()
where P has all n\ permutations (pi,... ,pn) of the numbers {1, 2,..., n}, ePi
is the pf^1 canonical unit vector and det Pp = det[epi, eP2,..., ePn] = ±1 such
that the sign depends on whether the number of exchanges in the permutation
matrix Pp is even or odd.
Consider the terms in the above formula for det A involving an. They
occur when the choice of the first column is p\ — 1 yielding some permutation
P = (P2J • • • >Pn) °f the remaining numbers {2, 3,..., n}. We collect all these
terms as An where the cofactor for an is
E'
pep
-An = y , a (^2) P2"-a' npn O-ei ip.
Hence, det A should depend linearly on the row (an, 012,. •
det A = an An + 012^12 H h alnA\n.
)Oi„):
Let us prove Property 11 using the induction approach. The base condition
was already be shown to be true by the example in the main text. We may
use (*) as the induction hypothesis for n = k.
Claim: J2PeP a2p 2 " ' anpn det Pp = (—1)1+1 detMn. We will use induction
for proving the claim.
Base(n = 3): An = 022033 - a 2 3a 32 = (-l)^2 *^22 °^23.
032 033
Induction(n = k + 1): Y.^pa2,P2 • • • ak+i,Pk+1 det Pp- = (-1)1+1 detMn-
Using the induction hypothesis for n — k in () we have:
det Mn = a 2 2A 22 H h a2n^2n,
in which we may use the induction hypothesis of the claim for the cofactor
A 2 j- The rest is almost trivial.