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