# Fundamentals of Linear Algebra and Optimization Homework 2

Problem B1 (10 pts). Given any m × n matrix A and any n × p matrix B, if we denote the columns of A by A1

, . . . , An and the rows of B by B1, . . . , Bn, prove that

AB = A

1B1 + · · · + A

nBn.

Problem B2 (10 pts). Let f : E → F be a linear map which is also a bijection (it is

injective and surjective). Prove that the inverse function f

−1

: F → E is linear.

Problem B3 (10 pts). Given two vectors spaces E and F, let (ui)i∈I be any basis of E and let (vi)i∈I be any family of vectors in F. Prove that the unique linear map f : E → F

such that f(ui) = vi

for all i ∈ I is surjective iff (vi)i∈I spans F.

Problem B4 (10 pts). Let f : E → F be a linear map with dim(E) = n and dim(F) = m.

Prove that f has rank 1 iff f is represented by an m × n matrix of the form

A = uv

with u a nonzero column vector of dimension m and v a nonzero column vector of dimension

n.

Problem B5 (120 pts). (Haar extravaganza) Consider the matrix

W3,3 =

1 0 0 0 1 0 0 0

1 0 0 0 −1 0 0 0

0 1 0 0 0 1 0 0

0 1 0 0 0 −1 0 0

0 0 1 0 0 0 1 0

0 0 1 0 0 0 −1 0

0 0 0 1 0 0 0 1

0 0 0 1 0 0 0 −1

(1) Show that given any vector c = (c1, c2, c3, c4, c5, c6, c7, c8), the result W3,3c of applying

W3,3 to c is

W3,3c = (c1 + c5, c1 − c5, c2 + c6, c2 − c6, c3 + c7, c3 − c7, c4 + c8, c4 − c8),

1

the last step in reconstructing a vector from its Haar coefficients.

(2) Prove that the inverse of W3,3 is (1/2)W

3,3

. Prove that the columns and the rows of

W3,3 are orthogonal.

(3) Let W3,2 and W3,1 be the following matrices:

W3,2 =

1 0 1 0 0 0 0 0

1 0 −1 0 0 0 0 0

0 1 0 1 0 0 0 0

0 1 0 −1 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 1

, W3,1 =

1 1 0 0 0 0 0 0

1 −1 0 0 0 0 0 0

0 0 1 0 0 0 0 0

0 0 0 1 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 1

.

Show that given any vector c = (c1, c2, c3, c4, c5, c6, c7, c8), the result W3,2c of applying W3,2

to c is

W3,2c = (c1 + c3, c1 − c3, c2 + c4, c2 − c4, c5, c6, c7, c8),

the second step in reconstructing a vector from its Haar coefficients, and the result W3,1c of

applying W3,1 to c is

W3,1c = (c1 + c2, c1 − c2, c3, c4, c5, c6, c7, c8),

the first step in reconstructing a vector from its Haar coefficients.

Conclude that

W3,3W3,2W3,1 = W3,

the Haar matrix

W3 =

1 1 1 0 1 0 0 0

1 1 1 0 −1 0 0 0

1 1 −1 0 0 1 0 0

1 1 −1 0 0 −1 0 0

1 −1 0 1 0 0 1 0

1 −1 0 1 0 0 −1 0

1 −1 0 −1 0 0 0 1

1 −1 0 −1 0 0 0 −1

.

Hint. First, check that

W3,2W3,1 =

W2 04,4

04,4 I4

,

where

W2 =

1 1 1 0

1 1 −1 0

1 −1 0 1

1 −1 0 −1

.

2

(4) Prove that the columns and the rows of W3,2 and W3,1 are orthogonal. Deduce from

this that the columns of W3 are orthogonal, and the rows of W−1

3

are orthogonal. Are the

rows of W3 orthogonal? Are the columns of W−1

3

orthogonal? Find the inverse of W3,2 and

the inverse of W3,1.

(5) For any n ≥ 2, the 2n × 2

n matrix Wn,n is obtained form the two rows

1, 0, . . . , 0

| {z }

2n−1

, 1, 0, . . . , 0

| {z }

2n−1

1, 0, . . . , 0

| {z }

2n−1

, −1, 0, . . . , 0

| {z }

2n−1

by shifting them 2n−1 − 1 times over to the right by inserting a zero on the left each time.

Given any vector c = (c1, c2, . . . , c2n ), show that Wn,nc is the result of the last step in the

process of reconstructing a vector from its Haar coefficients c. Prove that W−1

n,n = (1/2)W

n,n,

and that the columns and the rows of Wn,n are orthogonal.

Extra credit (30 pts.)

Given a m × n matrix A = (aij ) and a p × q matrix B = (bij ), the Kronecker product (or

tensor product) A ⊗ B of A and B is the mp × nq matrix

A ⊗ B =

a11B a12B · · · a1nB

a21B a22B · · · a2nB

.

.

.

.

.

.

.

.

.

.

.

.

am1B am2B · · · amnB

.

It can be shown (and you may use these facts without proof) that ⊗ is associative and that

(A ⊗ B)(C ⊗ D) = AC ⊗ BD

(A ⊗ B)

= A

⊗ B

,

whenever AC and BD are well defined.

Check that

Wn,n =

I2n−1 ⊗

1

1

I2n−1 ⊗

1

−1

,

and that

Wn =

Wn−1 ⊗

1

1

I2n−1 ⊗

1

−1

.

Use the above to reprove that

Wn,nW

n,n = 2I2n .

3

Let

B1 = 2

1 0

0 1

=

2 0

0 2

and for n ≥ 1,

Bn+1 = 2

Bn 0

0 I2n

.

Prove that

W

n Wn = Bn, for all n ≥ 1.

(6) The matrix Wn,i is obtained from the matrix Wi,i (1 ≤ i ≤ n − 1) as follows:

Wn,i =

Wi,i 02

i

,2n−2

i

02n−2

i

,2

i I2n−2

i

.

It consists of four blocks, where 02

i

,2n−2

i and 02n−2

i

,2

i are matrices of zeros and I2n−2

i is the

identity matrix of dimension 2n − 2

i

.

Explain what Wn,i does to c and prove that

Wn,nWn,n−1 · · · Wn,1 = Wn,

where Wn is the Haar matrix of dimension 2n

.

Hint. Use induction on k, with the induction hypothesis

Wn,kWn,k−1 · · · Wn,1 =

Wk 02

k,2n−2

k

02n−2

k,2

k I2n−2

k

.

Prove that the columns and rows of Wn,k are orthogonal, and use this to prove that the

columns of Wn and the rows of W−1

n

are orthogonal. Are the rows of Wn orthogonal? Are

the columns of W−1

n

orthogonal? Prove that

W−1

n,k =

1

2W

k,k 02

k,2n−2

k

02n−2

k,2

k I2n−2

k

.

Problem B6 (20 pts). Prove that for every vector space E, if f : E → E is an idempotent

linear map, i.e., f ◦ f = f, then we have a direct sum

E = Ker f ⊕ Im f,

so that f is the projection onto its image Im f.

Problem B7 (20 pts). Let U1, . . . , Up be any p ≥ 2 subspaces of some vector space E and

recall that the linear map

a: U1 × · · · × Up → E

4

is given by

a(u1, . . . , up) = u1 + · · · + up,

with ui ∈ Ui

for i = 1, . . . , p.

(1) If we let Zi ⊆ U1 × · · · × Up be given by

Zi =

u1, . . . , ui−1, −

X

p

j=1,j6=i

uj

, ui+1, . . . , up

X

p

j=1,j6=i

uj ∈ Ui ∩

X

p

j=1,j6=i

Uj

,

for i = 1, . . . , p, then prove that

Ker a = Z1 = · · · = Zp.

In general, for any given i, the condition Ui ∩

Pp

j=1,j6=i Uj

= (0) does not necessarily

imply that Zi = (0). Thus, let

Z =

u1, . . . , ui−1, ui

, ui+1, . . . , up

ui = −

X

p

j=1,j6=i

uj

, ui ∈ Ui ∩

X

p

j=1,j6=i

Uj

, 1 ≤ i ≤ p

.

Since Ker a = Z1 = · · · = Zp, we have Z = Ker a. Prove that if

Ui ∩

X

p

j=1,j6=i

Uj

= (0) 1 ≤ i ≤ p,

then Z = Ker a = (0).

(2) Prove that U1 + · · · + Up is a direct sum iff

Ui ∩

X

p

j=1,j6=i

Uj

= (0) 1 ≤ i ≤ p.

(3) Extra credit (40 pts). Assume that E is finite-dimensional, and let fi

: E → E be any

p ≥ 2 linear maps such that

f1 + · · · + fp = idE.

Prove that the following properties are equivalent:

(1) f

2

i = fi

, 1 ≤ i ≤ p.

(2) fj ◦ fi = 0, for all i 6= j, 1 ≤ i, j ≤ p.

TOTAL: 200 + 70 points.

5

, . . . , An and the rows of B by B1, . . . , Bn, prove that

AB = A

1B1 + · · · + A

nBn.

Problem B2 (10 pts). Let f : E → F be a linear map which is also a bijection (it is

injective and surjective). Prove that the inverse function f

−1

: F → E is linear.

Problem B3 (10 pts). Given two vectors spaces E and F, let (ui)i∈I be any basis of E and let (vi)i∈I be any family of vectors in F. Prove that the unique linear map f : E → F

such that f(ui) = vi

for all i ∈ I is surjective iff (vi)i∈I spans F.

Problem B4 (10 pts). Let f : E → F be a linear map with dim(E) = n and dim(F) = m.

Prove that f has rank 1 iff f is represented by an m × n matrix of the form

A = uv

with u a nonzero column vector of dimension m and v a nonzero column vector of dimension

n.

Problem B5 (120 pts). (Haar extravaganza) Consider the matrix

W3,3 =

1 0 0 0 1 0 0 0

1 0 0 0 −1 0 0 0

0 1 0 0 0 1 0 0

0 1 0 0 0 −1 0 0

0 0 1 0 0 0 1 0

0 0 1 0 0 0 −1 0

0 0 0 1 0 0 0 1

0 0 0 1 0 0 0 −1

(1) Show that given any vector c = (c1, c2, c3, c4, c5, c6, c7, c8), the result W3,3c of applying

W3,3 to c is

W3,3c = (c1 + c5, c1 − c5, c2 + c6, c2 − c6, c3 + c7, c3 − c7, c4 + c8, c4 − c8),

1

the last step in reconstructing a vector from its Haar coefficients.

(2) Prove that the inverse of W3,3 is (1/2)W

3,3

. Prove that the columns and the rows of

W3,3 are orthogonal.

(3) Let W3,2 and W3,1 be the following matrices:

W3,2 =

1 0 1 0 0 0 0 0

1 0 −1 0 0 0 0 0

0 1 0 1 0 0 0 0

0 1 0 −1 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 1

, W3,1 =

1 1 0 0 0 0 0 0

1 −1 0 0 0 0 0 0

0 0 1 0 0 0 0 0

0 0 0 1 0 0 0 0

0 0 0 0 1 0 0 0

0 0 0 0 0 1 0 0

0 0 0 0 0 0 1 0

0 0 0 0 0 0 0 1

.

Show that given any vector c = (c1, c2, c3, c4, c5, c6, c7, c8), the result W3,2c of applying W3,2

to c is

W3,2c = (c1 + c3, c1 − c3, c2 + c4, c2 − c4, c5, c6, c7, c8),

the second step in reconstructing a vector from its Haar coefficients, and the result W3,1c of

applying W3,1 to c is

W3,1c = (c1 + c2, c1 − c2, c3, c4, c5, c6, c7, c8),

the first step in reconstructing a vector from its Haar coefficients.

Conclude that

W3,3W3,2W3,1 = W3,

the Haar matrix

W3 =

1 1 1 0 1 0 0 0

1 1 1 0 −1 0 0 0

1 1 −1 0 0 1 0 0

1 1 −1 0 0 −1 0 0

1 −1 0 1 0 0 1 0

1 −1 0 1 0 0 −1 0

1 −1 0 −1 0 0 0 1

1 −1 0 −1 0 0 0 −1

.

Hint. First, check that

W3,2W3,1 =

W2 04,4

04,4 I4

,

where

W2 =

1 1 1 0

1 1 −1 0

1 −1 0 1

1 −1 0 −1

.

2

(4) Prove that the columns and the rows of W3,2 and W3,1 are orthogonal. Deduce from

this that the columns of W3 are orthogonal, and the rows of W−1

3

are orthogonal. Are the

rows of W3 orthogonal? Are the columns of W−1

3

orthogonal? Find the inverse of W3,2 and

the inverse of W3,1.

(5) For any n ≥ 2, the 2n × 2

n matrix Wn,n is obtained form the two rows

1, 0, . . . , 0

| {z }

2n−1

, 1, 0, . . . , 0

| {z }

2n−1

1, 0, . . . , 0

| {z }

2n−1

, −1, 0, . . . , 0

| {z }

2n−1

by shifting them 2n−1 − 1 times over to the right by inserting a zero on the left each time.

Given any vector c = (c1, c2, . . . , c2n ), show that Wn,nc is the result of the last step in the

process of reconstructing a vector from its Haar coefficients c. Prove that W−1

n,n = (1/2)W

n,n,

and that the columns and the rows of Wn,n are orthogonal.

Extra credit (30 pts.)

Given a m × n matrix A = (aij ) and a p × q matrix B = (bij ), the Kronecker product (or

tensor product) A ⊗ B of A and B is the mp × nq matrix

A ⊗ B =

a11B a12B · · · a1nB

a21B a22B · · · a2nB

.

.

.

.

.

.

.

.

.

.

.

.

am1B am2B · · · amnB

.

It can be shown (and you may use these facts without proof) that ⊗ is associative and that

(A ⊗ B)(C ⊗ D) = AC ⊗ BD

(A ⊗ B)

= A

⊗ B

,

whenever AC and BD are well defined.

Check that

Wn,n =

I2n−1 ⊗

1

1

I2n−1 ⊗

1

−1

,

and that

Wn =

Wn−1 ⊗

1

1

I2n−1 ⊗

1

−1

.

Use the above to reprove that

Wn,nW

n,n = 2I2n .

3

Let

B1 = 2

1 0

0 1

=

2 0

0 2

and for n ≥ 1,

Bn+1 = 2

Bn 0

0 I2n

.

Prove that

W

n Wn = Bn, for all n ≥ 1.

(6) The matrix Wn,i is obtained from the matrix Wi,i (1 ≤ i ≤ n − 1) as follows:

Wn,i =

Wi,i 02

i

,2n−2

i

02n−2

i

,2

i I2n−2

i

.

It consists of four blocks, where 02

i

,2n−2

i and 02n−2

i

,2

i are matrices of zeros and I2n−2

i is the

identity matrix of dimension 2n − 2

i

.

Explain what Wn,i does to c and prove that

Wn,nWn,n−1 · · · Wn,1 = Wn,

where Wn is the Haar matrix of dimension 2n

.

Hint. Use induction on k, with the induction hypothesis

Wn,kWn,k−1 · · · Wn,1 =

Wk 02

k,2n−2

k

02n−2

k,2

k I2n−2

k

.

Prove that the columns and rows of Wn,k are orthogonal, and use this to prove that the

columns of Wn and the rows of W−1

n

are orthogonal. Are the rows of Wn orthogonal? Are

the columns of W−1

n

orthogonal? Prove that

W−1

n,k =

1

2W

k,k 02

k,2n−2

k

02n−2

k,2

k I2n−2

k

.

Problem B6 (20 pts). Prove that for every vector space E, if f : E → E is an idempotent

linear map, i.e., f ◦ f = f, then we have a direct sum

E = Ker f ⊕ Im f,

so that f is the projection onto its image Im f.

Problem B7 (20 pts). Let U1, . . . , Up be any p ≥ 2 subspaces of some vector space E and

recall that the linear map

a: U1 × · · · × Up → E

4

is given by

a(u1, . . . , up) = u1 + · · · + up,

with ui ∈ Ui

for i = 1, . . . , p.

(1) If we let Zi ⊆ U1 × · · · × Up be given by

Zi =

u1, . . . , ui−1, −

X

p

j=1,j6=i

uj

, ui+1, . . . , up

X

p

j=1,j6=i

uj ∈ Ui ∩

X

p

j=1,j6=i

Uj

,

for i = 1, . . . , p, then prove that

Ker a = Z1 = · · · = Zp.

In general, for any given i, the condition Ui ∩

Pp

j=1,j6=i Uj

= (0) does not necessarily

imply that Zi = (0). Thus, let

Z =

u1, . . . , ui−1, ui

, ui+1, . . . , up

ui = −

X

p

j=1,j6=i

uj

, ui ∈ Ui ∩

X

p

j=1,j6=i

Uj

, 1 ≤ i ≤ p

.

Since Ker a = Z1 = · · · = Zp, we have Z = Ker a. Prove that if

Ui ∩

X

p

j=1,j6=i

Uj

= (0) 1 ≤ i ≤ p,

then Z = Ker a = (0).

(2) Prove that U1 + · · · + Up is a direct sum iff

Ui ∩

X

p

j=1,j6=i

Uj

= (0) 1 ≤ i ≤ p.

(3) Extra credit (40 pts). Assume that E is finite-dimensional, and let fi

: E → E be any

p ≥ 2 linear maps such that

f1 + · · · + fp = idE.

Prove that the following properties are equivalent:

(1) f

2

i = fi

, 1 ≤ i ≤ p.

(2) fj ◦ fi = 0, for all i 6= j, 1 ≤ i, j ≤ p.

TOTAL: 200 + 70 points.

5

You'll get 1 file (448.3KB)