Graphics Reference
In-Depth Information
corresponds to interchanging the ith and jth columns in N
q-1
and the ith and jth rows
in N
q
(c) Replacing
{
}
{
}
q
q
q
q
q
q
q
c
,...,
c
,...,
c
by
c
,...,
c
+
kc
,...,
c
1
i
1
i
j
n
n
q
q
for some integers k and i π j corresponds to replacing the ith column of N
q-1
by
the ith column plus k times the jth column and replacing the jth row of N
q
by the jth
row minus k times the ith row.
The proof of parts (a) and (b) of Claim 1 is easy and left to the reader. Part (c) is
readily deduced from the identities
(
)
=
()
+
()
q
q
q
q
∂
c c
+
∂
c kc
∂
q
q
q
i
j
i
j
and
n
n
q
q
(
)
=
(
)
+-
(
)
q
+
1
Â
t
q
t
q
q
q
q
q
q
q
Â
t
q
t
q
∂
c
h
c
=
h
c
+
kc
h
k
h
c
+
h
c
.
q
+
1
is
i
j
js
is
j
t
=
1
tti j
=
1,
π
,
Claim 1 is proved.
Now consider the 0th incidence matrix E
0
= (e
ij
) of K. Note how each column has
only two nonzero entries, namely, one +1 and one -1.
Claim 2.
Any integer matrix P = (p
ij
) having the property that each nonzero
column has precisely two nonzero entries, one of which is +1 and the other is -1, can
be transformed into a normalized matrix as defined by Theorem 7.2.5.3 via a sequence
of matrix operations of the type described in Claim 1 above.
Claim 2 is proved by induction on the number of rows (or columns) in P.
First, by interchanging rows, we may assume that p
11
=+1. The next step is to
zero out the first row past the first entry by a sequence of column operations.
Specifically, if p
1j
=±1 for some j > 1, then replace the jth column of P by ( jth column
- p
1j
(1st column)). The new matrix P¢=(p
ij
) will have p¢
1j
= 0 and either the
jth column is zero or there are again just two nonzero entries, one +1 and the other
-1. By a sequence of such operations we arrive at a matrix P≤=(p
ij
) such that
p
11
= 1, p
1j
= 0, for j > 1, and P≤ also satisfies the same hypotheses as the original
matrix P. Now p≤
i1
will equal -1 for some i > 1. Subtracting the 1st row from the
ith row of P≤, will give us a matrix Q = (q
ij
), such that q
i1
= q
1j
= 0 for i, j > 1. The
inductive hypothesis would then apply to the matrix (q
ij
)
2£i,2£j
and finish the proof
of Claim 2.
In order to prove our theorem we shall prove the following assertions for
k > 0:
