CO250 INTRODUCTION TO OPTIMIZATION
INTRODUCTION TO OPTIMIZATION
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
CO250 INTRODUCTION TO OPTIMIZATION
ASSIGNMENT 1∗
EDT Please submit a pdf file to CROWDMARK. Recall, no other
form of submission is acceptable; late assignments will not be accepted. It is the responsibility of the students
to make sure that the pdf file they submit is clearly readable.
Important information: You are expected to do the assignments on your own. The only sources
Usage of any other source in doing the homework assignments is against the academic integrity rules for
co250 in the Spring 2021 term.
For example, copying or paraphrasing a solution from some fellow student or from old solutions from
previous offerings of related courses or various sources on the web, qualifies as cheating and the TA’s have
been instructed to actively look for evidence of academic offences when evaluating assignment papers. By
uWaterloo policy, academic integrity violations by a student in assignments will lead to a mark of zero in that
assignment and a 5% deduction from the Final Course Grade. In addition, all academic offences are reported
to the Associate Dean for Undergraduate Studies.
If you have any questions about the marking and feedback on assignments, then you should first check
your solutions against the posted solutions. After that if you still have questions please contact the TAs in
charge of feedback for the assignment. For Assignment 1 the following TAs are in charge:
Question TA email address
1 Joan Etude Arrow [email protected]
2 Salomon Bendayan [email protected]
3 Jimit Majmudar [email protected]
4 Jonathan Chang [email protected]
[This Assignment is for Linear Algebra Review most relevant to co250. If you have trouble completing
any part of this assignment it is a strong indication that you need to review your linear algebra. You will not
be successful in this course if you do not have the required background in linear algebra.]
∗COPYRIGHT: Reproduction, sharing or online posting of this document is strictly forbidden c©University of Waterloo, Walaa
Moursi and Martin Pei.
1
2Exercise 1 (25 marks=7+(3+3+3+3)+(2+2+1+1)).
Let n be a positive integer. Note that in this course, all vectors in Rn are column vectors so that if x ∈ Rn,
then the transpose of x, denoted by x>, is a row vector.
(a) Let c, x ∈ Rn. Denote their entries by c1, c2, . . . , cn and x1, x2, . . . , xn. Express c>x and cx> in terms
of the entries of c and x.
Let m be a positive integer and let A ∈ Rm×n, B ∈ Rm×n, c, x ∈ Rn and b, y ∈ Rm. For each of the
expressions below (which are strings of matrix multiplications), if the expression makes sense, describe
the dimensions of the result and show your work. If the expression does not make sense, explain why.
(b) A>y
Ay
yB
y>B
(c) ABxy
Axy>B
y>AB>x
A2x
3Exercise 2 (25 marks=15+5+5).
(a) For each of the following set of vectors determine whether theset of vectors is linearly independent or
linearly dependent. If the set is linearly dependent, express one vector in the set as a linear combination
of the others.
(i)
A1 =
−1−5
1
, A2 =
12
1
, A3 =
14
3
(ii)
A1 =
−10
0
, A2 =
20
4
, A3 =
2−2
1
A4 =
2−5
−1
(b) Let m and k be a pair of positive integers. Prove that every linearly independent subset of vectors in Rm
is part of a basis. So, given a linearly independent subset of vectors (say k of them) in Rm, we can always
find m− k vectors to extend the inital subset to a basis for Rm.
(c) Let S = {A1, A2, . . . , Am} ⊂ Rm be a linearly independent subset of vectors. Prove that the set S forms
a basis of Rm.
4Exercise 3 (30 marks).
For each of the following statements either prove that the statement is correct, or provide a counterexample
or a suitable proof that shows that the statement is incorrect.
(a) Let n ≥ 2 be an integer, and let a, b be vectors in Rn. If a ≥ b does not hold, then either a = b or a < b.
(b) Let m,n ≥ 2 be integers, let A be an m-by-n matrix, and let x be an n-dimensional vector. Then,
Ax = 0 implies that either x = 0 or that A = 0.
(c) Let m and n be positive integers, let A be an m-by-n matrix, and let y be a non-zero, m-dimensional
vector such that y>A = 0>.
Then the rows of A are linearly dependent.
(d) Let m and n be positive integers, let A be an m-by-n matrix, and let y be a non-zero, m-dimensional
vector such that y>A = 0>.
Then the columns of A are linearly dependent.
(e) In the matrix A below it is possible to find 5 linearly independent columns:
A =
12 3 4 0 −6 −1 0 37
2 19 −6 32 0 0 3 0
0 −1 3 −6 7 4 11 2
10 −21 33 0 0 51 1 71
.
(f) Let n be a positive integer and A be an n-by-n matrix. If Ax = 0 has only the trivial solution, namely
x = 0, then Ax = b has a unique solution for every b ∈ Rn.
(g) Let n ≥ 2 be an integer and let A be an n-by-n nonzero matrix. Then A is invertible, i.e., A−1 exists.
(h) Let m and n be positive integers, let A be an m-by-n matrix, and let b be an m-dimensional vector.
Suppose that the system Ax = b has a unique solution. Then m = n.
(i) Let m and n be positive integers, let A be an m-by-n matrix, and let x be an n-dimensional vector and
let b be an m-dimensional vector. If Ax = b has a solution, then b is a linear combination of the columns
of A.
(j) Let m and n be positive integers, and let A be an m-by-n matrix. If m > n, then there exists a nonzero
m-dimensional vector b such that the system Ax = b has no solution.
5Exercise 4 (20 marks=5+15).
(a) Consider the system of equations Ax = b, where A is an m× n matrix and b ∈ Rm is a vector. Suppose
there exists a vector y (of the appropriate dimension) such that y>A = 0 and y>b 6= 0.
Prove that Ax = b has no solution.
(b) Consider the system of linear equations:
x1 − 3x2 + x3 = 2,
3x1 − 4x2 + x3 = 0,
2x1 − x2 = 1.
i. Write the system in the form Ax = b.
ii. Use Gaussian elimination to show that the system has no solution.
iii. Find a vector y ∈ R3 that satisfies y>A = 0 and y>b 6= 0.