# 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 A1 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

[email protected]

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

[email protected]

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 = 2n1jj:

(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

[email protected]

B3

0(t)

B3

1(t)

B3

2(t)

B3

3(t)

1

CCA

=

0

[email protected]

1 3 3 1

0 3 6 3

0 0 3 3

0 0 0 1

1

CCA

0

[email protected]

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 coecient

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)mktk; 0 k m:

Prove that

Bm

k (t) =

Xm

j=k

(1)jk

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 coecient 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 modications 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 =

Xmi

j=0

tiBmi

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 =

Xmi

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

[email protected]

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 + 1tm11 + + m1

y(t) = 0tm2 + 1tm21 + + 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; : : : ; bm1 generally on the

curve?

We say that the curve C is a Bezier 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 Bezier curves which is used in geometric modeling to nd the intersection of curve segments. Bezier 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 nn 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.

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 A1 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

[email protected]

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

[email protected]

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 = 2n1jj:

(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

[email protected]

B3

0(t)

B3

1(t)

B3

2(t)

B3

3(t)

1

CCA

=

0

[email protected]

1 3 3 1

0 3 6 3

0 0 3 3

0 0 0 1

1

CCA

0

[email protected]

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 coecient

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)mktk; 0 k m:

Prove that

Bm

k (t) =

Xm

j=k

(1)jk

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 coecient 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 modications 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 =

Xmi

j=0

tiBmi

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 =

Xmi

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

[email protected]

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 + 1tm11 + + m1

y(t) = 0tm2 + 1tm21 + + 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; : : : ; bm1 generally on the

curve?

We say that the curve C is a Bezier 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 Bezier curves which is used in geometric modeling to nd the intersection of curve segments. Bezier 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 nn 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.

You'll get 1 file (125.9KB)