A COMPLETE SOLUTION MANUAL
FOR AN INTRODUCTION TO
OPTIMIZATION
FOURTH EDITION BY EDWIN K. P. CHONG AND STANISLAW H. ŻAK
,1. Methods of Proof and Some Notation
1.1
A B not A not B A⇒B (not B)⇒(not A)
F F T T T T
F T T F T T
T F F T F F
T T F F T T
1.2
A B not A not B A⇒B not (A and (not B))
F F T T T T
F T T F T T
T F F T F F
T T F F T T
1.3
A B not (A and B) not A not B (not A) or (not B))
F F T T T T
F T T T F T
T F T F T T
T T F F F F
1.4
A B A and B A and (not B) (A and B) or (A and (not B))
F F F F F
F T F F F
T F F T T
T T T F T
1.5
The cards that you should turn over are 3 and A. The remaining cards are irrelevant to ascertaining the
truth or falsity of the rule. The card with S is irrelevant because S is not a vowel. The card with 8 is not
relevant because the rule does not say that if a card has an even number on one side, then it has a vowel on
the other side.
Turning over the A card directly verifies the rule, while turning over the 3 card verifies the contraposition.
2. Vector Spaces and Matrices
2.1
We show this by contradiction. Suppose n < m. Then, the number of columns of A is n. Since rank A is
the maximum number of linearly independent columns of A, then rank A cannot be greater than n < m,
which contradicts the assumption that rank A = m.
2.2
.
⇒: Since there exists a solution, then by Theorem 2.1, rank A = rank[A.b]. So, it remains to prove that
rank A = n. For this, suppose that rank A < n (note that it is impossible for rank A > n since A has
only n columns). Hence, there exists y ∈ Rn, y /= 0, such that Ay = 0 (this is because the columns of
1
,A are linearly dependent, and Ay is a linear combination of the columns of A). Let x be a solution to
Ax = b. Then clearly x + y = x is also a solution. This contradicts the uniqueness of the solution. Hence,
rank A = n.
→: By Theorem 2.1, a solution exists. It remains to prove that it is unique. For this, let x and y be
solutions, i.e., Ax = b and Ay = b. Subtracting, we get A(x — y) = 0. Since rank A = n and A has n
columns, then x — y = 0 and hence x = y, which shows that the solution is unique.
2.3
Consider the vectors ā i = [1,i aT]T∈Rn+1, i = 1, . . . , k. Since k ≥n + 2, then the vectors ā 1 , . . . , ā k must
be linearly independent in Rn+1. Hence, there exist α1, . . . αk, not all zero, such that
Σ
k
αiai = 0.
i=1
Σk
The first component of the above vector equation is αi = 0, while the last n components have the form
Σk
i=1
i=1 αia i = 0, completing the proof.
2.4
a. We first postmultiply M by the matrix
" #
Ik O
—M m—k,k Im—k
to obtain
" #" # " #
M m—k,k Im—k Ik O O Im—k
= .
M k,k O —M m—k,k Im—k M k,k O
Note that the determinant of the postmultiplying matrix is 1. Next we postmultiply the resulting product
by
" #
O Ik
Im—k O
to obtain " #" # " #
O Im—k O Ik Ik O
= .
M k,k O Im—k O O M k,k
Notice that
"
Ik O #! " #!
det M = det O Ik
O M k,k det Im—k O ,
where
" O Ik #!
det = 1.
Im—k O ±
The above easily follows from the fact that the determinant changes its sign if we interchange columns, as
discussed in Section 2.2. Moreover,
#!
"I O
k
det = det(I k) det(M k,k ) = det(M k,k).
O M k,k
Hence,
det M = ± det M k,k.
b. We can see this on the following examples. We assume, without loss of generality that M m—k,k = O and
let M k,k = 2. Thus k = 1. First consider the case when m = 2. Then we have
" # " #
O Im—k 0 1
M = = .
M k,k O 2 0
2
, Thus,
det M = —2 = det (—M k,k) .
Next consider the case when m = 3. Then
" # 0 .
O Im—k 0 . 1 0
det = det = 2 = det ( )
. 0 1 / —M k,k .
M k,k O ··· ··· ··· ···
2 . 0 0
Therefore, in general,
det M /= det (—M k,k)
However, when k = m/2, that is, when all sub-matrices are square and of the same dimension, then it is
true that
det M = det (—M k,k) .
See [121].
2.5
Let " #
A B
M=
C D
and suppose that each block is k ×k. John R. Silvester [121] showed that if at least one of the blocks is
equal to O (zero matrix), then the desired formula holds. Indeed, if a row or column block is zero, then the
determinant is equal to zero as follows from the determinant’s properties discussed Section 2.2. That is, if
A = B = O, or A = C = O, and so on, then obviously det M = 0. This includes the case when any three
or all four block matrices are zero matrices.
If B = O or C = O then " #
A B
det M = det = det (AD) .
C D
The only case left to analyze is when A = O or D = O. We will show that in either case,
det M = det (—BC) .
Without loss of generality suppose that D = O. Following arguments of John R. Silvester [121], we premul-
tiply M by the product of three matrices whose determinants are unity:
" #" #" #" # " #
I k —I k I k O Ik —I k A B —C O
= .
O Ik Ik Ik O Ik C O A B
Hence,
" # " #
A B —C O
det =
C O A B
= det (—C) det B
= det (—I k ) det C det B.
Thus we have
" #
A B
det = det (—BC) = det (—CB) .
C O
3
FOR AN INTRODUCTION TO
OPTIMIZATION
FOURTH EDITION BY EDWIN K. P. CHONG AND STANISLAW H. ŻAK
,1. Methods of Proof and Some Notation
1.1
A B not A not B A⇒B (not B)⇒(not A)
F F T T T T
F T T F T T
T F F T F F
T T F F T T
1.2
A B not A not B A⇒B not (A and (not B))
F F T T T T
F T T F T T
T F F T F F
T T F F T T
1.3
A B not (A and B) not A not B (not A) or (not B))
F F T T T T
F T T T F T
T F T F T T
T T F F F F
1.4
A B A and B A and (not B) (A and B) or (A and (not B))
F F F F F
F T F F F
T F F T T
T T T F T
1.5
The cards that you should turn over are 3 and A. The remaining cards are irrelevant to ascertaining the
truth or falsity of the rule. The card with S is irrelevant because S is not a vowel. The card with 8 is not
relevant because the rule does not say that if a card has an even number on one side, then it has a vowel on
the other side.
Turning over the A card directly verifies the rule, while turning over the 3 card verifies the contraposition.
2. Vector Spaces and Matrices
2.1
We show this by contradiction. Suppose n < m. Then, the number of columns of A is n. Since rank A is
the maximum number of linearly independent columns of A, then rank A cannot be greater than n < m,
which contradicts the assumption that rank A = m.
2.2
.
⇒: Since there exists a solution, then by Theorem 2.1, rank A = rank[A.b]. So, it remains to prove that
rank A = n. For this, suppose that rank A < n (note that it is impossible for rank A > n since A has
only n columns). Hence, there exists y ∈ Rn, y /= 0, such that Ay = 0 (this is because the columns of
1
,A are linearly dependent, and Ay is a linear combination of the columns of A). Let x be a solution to
Ax = b. Then clearly x + y = x is also a solution. This contradicts the uniqueness of the solution. Hence,
rank A = n.
→: By Theorem 2.1, a solution exists. It remains to prove that it is unique. For this, let x and y be
solutions, i.e., Ax = b and Ay = b. Subtracting, we get A(x — y) = 0. Since rank A = n and A has n
columns, then x — y = 0 and hence x = y, which shows that the solution is unique.
2.3
Consider the vectors ā i = [1,i aT]T∈Rn+1, i = 1, . . . , k. Since k ≥n + 2, then the vectors ā 1 , . . . , ā k must
be linearly independent in Rn+1. Hence, there exist α1, . . . αk, not all zero, such that
Σ
k
αiai = 0.
i=1
Σk
The first component of the above vector equation is αi = 0, while the last n components have the form
Σk
i=1
i=1 αia i = 0, completing the proof.
2.4
a. We first postmultiply M by the matrix
" #
Ik O
—M m—k,k Im—k
to obtain
" #" # " #
M m—k,k Im—k Ik O O Im—k
= .
M k,k O —M m—k,k Im—k M k,k O
Note that the determinant of the postmultiplying matrix is 1. Next we postmultiply the resulting product
by
" #
O Ik
Im—k O
to obtain " #" # " #
O Im—k O Ik Ik O
= .
M k,k O Im—k O O M k,k
Notice that
"
Ik O #! " #!
det M = det O Ik
O M k,k det Im—k O ,
where
" O Ik #!
det = 1.
Im—k O ±
The above easily follows from the fact that the determinant changes its sign if we interchange columns, as
discussed in Section 2.2. Moreover,
#!
"I O
k
det = det(I k) det(M k,k ) = det(M k,k).
O M k,k
Hence,
det M = ± det M k,k.
b. We can see this on the following examples. We assume, without loss of generality that M m—k,k = O and
let M k,k = 2. Thus k = 1. First consider the case when m = 2. Then we have
" # " #
O Im—k 0 1
M = = .
M k,k O 2 0
2
, Thus,
det M = —2 = det (—M k,k) .
Next consider the case when m = 3. Then
" # 0 .
O Im—k 0 . 1 0
det = det = 2 = det ( )
. 0 1 / —M k,k .
M k,k O ··· ··· ··· ···
2 . 0 0
Therefore, in general,
det M /= det (—M k,k)
However, when k = m/2, that is, when all sub-matrices are square and of the same dimension, then it is
true that
det M = det (—M k,k) .
See [121].
2.5
Let " #
A B
M=
C D
and suppose that each block is k ×k. John R. Silvester [121] showed that if at least one of the blocks is
equal to O (zero matrix), then the desired formula holds. Indeed, if a row or column block is zero, then the
determinant is equal to zero as follows from the determinant’s properties discussed Section 2.2. That is, if
A = B = O, or A = C = O, and so on, then obviously det M = 0. This includes the case when any three
or all four block matrices are zero matrices.
If B = O or C = O then " #
A B
det M = det = det (AD) .
C D
The only case left to analyze is when A = O or D = O. We will show that in either case,
det M = det (—BC) .
Without loss of generality suppose that D = O. Following arguments of John R. Silvester [121], we premul-
tiply M by the product of three matrices whose determinants are unity:
" #" #" #" # " #
I k —I k I k O Ik —I k A B —C O
= .
O Ik Ik Ik O Ik C O A B
Hence,
" # " #
A B —C O
det =
C O A B
= det (—C) det B
= det (—I k ) det C det B.
Thus we have
" #
A B
det = det (—BC) = det (—CB) .
C O
3
