TEST BANK FOR An Introduction to Optimization 4th edition By Edwin K. P. Chong, Stanislaw H. Zak

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 rankA is
the maximum number of linearly independent columns of A, then rankA cannot be greater than n < m,
which contradicts the assumption that rankA = m.
2.2
): Since there exists a solution, then by Theorem 2.1, rankA = rank[A
.. .
b]. So, it remains to prove that
rankA = n. For this, suppose that rankA < n (note that it is impossible for rankA > n since A has
only n columns). Hence, there exists y 2 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,
rankA = 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 rankA = 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 ¯ai = [1, a>
i ]> 2 Rn+1, i = 1, . . . , k. Since k n + 2, then the vectors ¯a1, . . . , ¯ak must
be linearly independent in Rn+1. Hence, there exist 1, . . . k, not all zero, such that
Xk
i=1
iai = 0.
The first component of the above vector equation is
Pk
i=1 i = 0, while the last n components have the form Pk
i=1 iai = 0, completing the proof.
2.4
a. We first postmultiply M by the matrix
"
Ik O
−Mm−k,k Im−k
#
to obtain "
Mm−k,k Im−k
Mk,k O
# "
Ik O
−Mm−k,k Im−k
#
=
"
O Im−k
Mk,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
Mk,k O
# "
O Ik
Im−k O
#
=
"
Ik O
O Mk,k
#
.
Notice that
detM = det
 "
Ik O
O Mk,k
#!
det
 "
O Ik
Im−k O
#!
,
where
det
 "
O Ik
Im−k O
#!
= ±1.
The above easily follows from the fact that the determinant changes its sign if we interchange columns, as
discussed in Section 2.2. Moreover,
det
 "
Ik O
O Mk,k
#!
= det(Ik) det(Mk,k) = det(Mk,k).
Hence,
detM = ±detMk,k.
b. We can see this on the following examples. We assume, without loss of generality that Mm−k,k = O and
let Mk,k = 2. Thus k = 1. First consider the case when m = 2. Then we have
M =
"
O Im−k
Mk,k O
#
=
"
0 1
2 0
#
.
2
Thus,
detM = −2 = det (−Mk,k) .
Next consider the case when m = 3. Then
det
"
O Im−k
Mk,k O
#
= det
2
6666664
0
...
1 0
0
...
0 1
· · · · · · · · · · · ·
2
...
0 0
3
7777775
= 2 6= det (−Mk,k) .
Therefore, in general,
detM 6= det (−Mk,k)
However, when k = m/2, that is, when all sub-matrices are square and of the same dimension, then it is
true that
detM = det (−Mk,k) .
See [121].
2.5
Let
M =
"
A B
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 detM = 0. This includes the case when any three
or all four block matrices are zero matrices.
If B = O or C = O then
detM = det
"
A B
C D
#
= det (AD) .
The only case left to analyze is when A = O or D = O. We will show that in either case,
detM = det (−BC) .
Without loss of generality suppose that D = O. Following arguments of John R. Silvester [121], we premultiply
M by the product of three matrices whose determinants are unity:
"
Ik −Ik
O Ik
# "
Ik O
Ik Ik
# "
Ik −Ik
O Ik
# "
A B
C O
#
=
"
−C O
A B
#
.
Hence,
det
"
A B
C O
#
=
"
−C O
A B
#
= det (−C) detB
= det (−Ik) detC detB.
Thus we have
det
"
A B
C O
#
= det (−BC) = det (−CB) .
3
2.6
We represent the given system of equations in the form Ax = b, where
A =
"
1 1 2 1
1 −2 0 −1
#
, x =
2
6664