AN INTRODUCTION TO
OPTIMIZATION
SOLUTIONS MANUAL
Fourth Edition
Edwin K. P. Chong and Stanislaw H. Żak
A JOHN WILEY & SONS, INC., PUBLICATION
,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 6= 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 6= 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, a⊤
i ] ∈ R
n+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
X
α i ai = 0.
i=1
Pk
The first component of the above vector equation is i=1 αi = 0, while the last n components have the form
Pk
i=1 αi ai = 0, completing the proof.
2.4
a. We first postmultiply M by the matrix
" #
Ik O
−M m−k,k I m−k
to obtain " #" # " #
M m−k,k I m−k Ik O O I m−k
= .
M k,k O −M m−k,k I m−k M k,k O
Note that the determinant of the postmultiplying matrix is 1. Next we postmultiply the resulting product
by " #
O Ik
I m−k O
to obtain " #" # " #
O I m−k O Ik Ik O
= .
M k,k O I m−k O O M k,k
Notice that " #! " #!
Ik O O Ik
det M = det det ,
O M k,k I m−k O
where " #!
O Ik
det = ±1.
I m−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,
" #!
Ik O
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 I m−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 1 0
...
" #
O I m−k 0 0 1 = 2 6= det (−M k,k ) .
det = det
M k,k O · · ·
··· ··· · · ·
...
2 0 0
Therefore, in general,
det M 6= 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 I k −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
OPTIMIZATION
SOLUTIONS MANUAL
Fourth Edition
Edwin K. P. Chong and Stanislaw H. Żak
A JOHN WILEY & SONS, INC., PUBLICATION
,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 6= 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 6= 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, a⊤
i ] ∈ R
n+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
X
α i ai = 0.
i=1
Pk
The first component of the above vector equation is i=1 αi = 0, while the last n components have the form
Pk
i=1 αi ai = 0, completing the proof.
2.4
a. We first postmultiply M by the matrix
" #
Ik O
−M m−k,k I m−k
to obtain " #" # " #
M m−k,k I m−k Ik O O I m−k
= .
M k,k O −M m−k,k I m−k M k,k O
Note that the determinant of the postmultiplying matrix is 1. Next we postmultiply the resulting product
by " #
O Ik
I m−k O
to obtain " #" # " #
O I m−k O Ik Ik O
= .
M k,k O I m−k O O M k,k
Notice that " #! " #!
Ik O O Ik
det M = det det ,
O M k,k I m−k O
where " #!
O Ik
det = ±1.
I m−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,
" #!
Ik O
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 I m−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 1 0
...
" #
O I m−k 0 0 1 = 2 6= det (−M k,k ) .
det = det
M k,k O · · ·
··· ··· · · ·
...
2 0 0
Therefore, in general,
det M 6= 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 I k −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
