Fundamentals of Linear Algebra and Optimization Homework 1

Problem B1 (10 pts). Prove that the axioms of vector spaces imply that
? ? 0 = 0
0 ? v = 0
? ? (􀀀v) = 􀀀(? ? v)
(􀀀?) ? v = 􀀀(? ? v);
for all v 2 E and all ? 2 K, where E is a vector space over K.
Problem B2 (40 pts). (1) Let (u1; : : : ; um) and (v1; : : : ; vm) be two families of vectors in some vector space E. Assume that each vi is a linear combination of the ujs, so that vi = ai 1u1 + ? ? ? + aimum; 1 ? i ? m;
and that the matrix A = (ai j) is an upper-triangular matrix, which means that ai j = 0 i?
1 ? j < i ? m. Prove that if (u1; : : : ; um) are linearly independent and if all the diagonal entries of A are nonzero, then (v1; : : : ; vm) are also linearly independent.
Hint. Use induction on m.
(2) Let A = (ai j) be an upper-triangular matrix. Prove that if all the diagonal entries of A are nonzero, then A is invertible and the inverse A􀀀1 of A is also upper-triangular.
Hint. Use induction on m.
Prove that if A is invertible, then all the diagonal entries of A are nonzero (do not use determinants or eigenvalues!).
(3) Prove that if the families (u1; : : : ; um) and (v1; : : : ; vm) are related as in (1), then
(u1; : : : ; um) are linearly independent i? (v1; : : : ; vm) are.

Problem B3 (40 pts). Consider the n ? n matrix
A =
0
BBBBBBBBB@
1 2 0 0 : : : 0 0
0 1 2 0 : : : 0 0
0 0 1 2 : : : 0 0
...
...
. . . . . . . . .
...
...
0 0 : : : 0 1 2 0
0 0 : : : 0 0 1 2
0 0 : : : 0 0 0 1
1
CCCCCCCCCA
:
(1) Find the solution x = (x1; : : : ; xn) of the linear system
Ax = b;
for
b =
0
BBB@
b1
b2
...
bn
1
CCCA
:
(2) Prove that the matrix A is invertible. Given that the number of atoms in the universe is estimated to be ? 1082, explain why it is practically impossible that the inverse of A will ever be computed if n ? 300.
(3) Assume b is perturbed by a small amount ?b (note that ?b is a vector). Find the new solution of the system
A(x + ?x) = b + ?b;
where ?x is also a vector. In the case where b = (0; : : : ; 0; 1), and ?b = (0; : : : ; 0; ?), show that
j(?x)1j = 2n􀀀1j?j:
(where j(?x)1j is the ?rst component of ?x).
(4) Prove that (A 􀀀 I)n = 0.
Problem B4 (80 pts). Consider the polynomials
B2
0(t) = (1 􀀀 t)2 B2
1(t) = 2(1 􀀀 t)t B2
2(t) = t2
B3
0(t) = (1 􀀀 t)3 B3
1(t) = 3(1 􀀀 t)2t B3
2(t) = 3(1 􀀀 t)t2 B3
3(t) = t3;
known as the Bernstein polynomials of degree 2 and 3.
(1) Show that the Bernstein polynomials B2
0(t);B2
1(t);B2
2(t) are expressed as linear com-
binations of the basis (1; t; t2) of the vector space of polynomials of degree at most 2 as follows: 0
@
B2
0(t)
B2
1(t)
B2
2(t)
1
A =
0
@
1 􀀀2 1
0 2 􀀀2
0 0 1
1
A
0
@
1
t
t2
1
A:
2
Prove that
B2
0(t) + B2
1(t) + B2
2(t) = 1:
(2) Show that the Bernstein polynomials B3
0(t);B3
1(t);B3
2(t);B3
3(t) are expressed as linear
combinations of the basis (1; t; t2; t3) of the vector space of polynomials of degree at most 3 as follows: 0
BB@
B3
0(t)
B3
1(t)
B3
2(t)
B3
3(t)
1
CCA
=
0
BB@
1 􀀀3 3 􀀀1
0 3 􀀀6 3
0 0 3 􀀀3
0 0 0 1
1
CCA
0
BB@
1
t
t2
t3
1
CCA
:
Prove that
B3
0(t) + B3
1(t) + B3
2(t) + B3
3(t) = 1:
(3) Prove that the Bernstein polynomials of degree 2 are linearly independent, and that the Bernstein polynomials of degree 3 are linearly independent.
(4) Recall that the binomial coe?cient
􀀀m
k
?
is given by
?
m
k
?
=
m!
k!(m 􀀀 k)!
;
with 0 ? k ? m.
For any m ? 1, we have the m + 1 Bernstein polynomials of degree m given by
Bm
k (t) =
?
m
k
?
(1 􀀀 t)m􀀀ktk; 0 ? k ? m:
Prove that
Bm
k (t) =
Xm
j=k
(􀀀1)j􀀀k
?
m
j
??
j
k
?
tj : (?)
Use the above to prove that Bm
0 (t); : : : ;Bm
m(t) are linearly independent.
(5) Prove that
Bm
0 (t) + ? ? ? + Bm
m(t) = 1;
Extra credit (20 pts). What can you say about the symmetries of the (m+ 1) ? (m+
matrix expressing Bm
0 ; : : : ;Bm
m in terms of the basis 1; t; : : : ; tm?
Prove your claim (beware that in equation (?) the coe?cient of tj in Bm
k is the entry on the (k+1)th row of the (j+1)th column, since 0 ? k; j ? m. Make appropriate modi?cations to the indices).
What can you say about the sum of the entries on each row of the above matrix? What about the sum of the entries on each column?

(6) The purpose of this question is to express the ti in terms of the Bernstein polynomials
Bm
0 (t); : : : ;Bm
m(t), with 0 ? i ? m.
First, prove that
ti =
Xm􀀀i
j=0
tiBm􀀀i
j (t); 0 ? i ? m:
Then prove that ?
m
i
??
m 􀀀 i
j
?
=
?
m
i + j
??
i + j
i
?
:
Use the above facts to prove that
ti =
Xm􀀀i
j=0
􀀀i+j
i
?
􀀀m
i
? Bm
i+j(t):
Conclude that the Bernstein polynomials Bm
0 (t); : : : ;Bm
m(t) form a basis of the vector
space of polynomials of degree ? m.
Compute the matrix expressing 1; t; t2 in terms of B2
0(t);B2
1(t);B2
2(t), and the matrix
expressing 1; t; t2; t3 in terms of B3
0(t);B3
1(t);B3
2(t);B3
3(t).
You should ?nd 0
@
1 1 1
0 1=2 1
0 0 1
1
A
and 0
BB@
1 1 1 1
0 1=3 2=3 1
0 0 1=3 1
0 0 0 1
1
CCA
:
(7) A polynomial curve C(t) of degree m in the plane is the set of points
C(t) =
?
x(t)
y(t)
?
given by two polynomials of degree ? m,
x(t) = ?0tm1 + ?1tm1􀀀1 + ? ? ? + ?m1
y(t) = ?0tm2 + ?1tm2􀀀1 + ? ? ? + ?m2 ;
with 1 ? m1;m2 ? m and ?0; ?0 6= 0.
Prove that there exist m + 1 points b0; : : : ; bm 2 R2 so that
C(t) =
?
x(t)
y(t)
?
= Bm
0 (t)b0 + Bm
1 (t)b1 + ? ? ? + Bm
m(t)bm
4
for all t 2 R, with C(0) = b0 and C(1) = bm. Are the points b1; : : : ; bm􀀀1 generally on the
curve?
We say that the curve C is a B?ezier curve and (b0; : : : ; bm) is the list of control points of
the curve (control points need not be distinct).
Remark: Because Bm
0 (t) + ? ? ? + Bm
m(t) = 1 and Bm
i (t) ? 0 when t 2 [0; 1], the curve segment C[0; 1] corresponding to t 2 [0; 1] belongs to the convex hull of the control points.
This is an important property of B?ezier curves which is used in geometric modeling to nd the intersection of curve segments. B?ezier curves play an important role in computer graphics and geometric modeling, but also in robotics because they can be used to model the trajectories of moving objects.
Problem B5 (40 pts). (a) Let A be an n?n matrix. If A is invertible, prove that for any
x 2 Rn, if Ax = 0, then x = 0.
The converse is true: If for all x 2 Rn, Ax = 0 implies that x = 0, then A is invertible.
We will prove this fact later, and you may use it without proof in part (b) of this problem.
(b) Let A be an m ? n matrix and let B be an n ? m matrix. Prove that Im 􀀀 AB is
invertible i? In 􀀀 BA is invertible.
TOTAL: 210 + 20 points.