Fundamentals of Linear Algebra and Optimization Homework 3 Solution

Problem B1 (20 pts). Let U1, . . . , Up be any p ≥ 2 subspaces of some vector space E.
Prove that U1 + · · · + Up is a direct sum iff
Ui ∩
?X
i−1
j=1
Uj
?
= (0), i = 2, . . . , p.
Problem B2 (50 pts). Given any vector space E, a linear map f : E → E is an involution
if f ◦ f = id.
(1) Prove that an involution f is invertible. What is its inverse?
(2) Let E1 and E−1 be the subspaces of E defined as follows:
E1 = {u ∈ E | f(u) = u}
E−1 = {u ∈ E | f(u) = −u}.
Prove that we have a direct sum
E = E1 ⊕ E−1.
Hint. For every u ∈ E, write
u =
u + f(u)
2
+
u − f(u)
2
.
(3) If E is finite-dimensional and f is an involution, prove that there is some basis of E
over which the matrix of f is of the form
Ik,n−k =
?
Ik 0
0 −In−k
?
,
where Ik is the k × k identity matrix (similarly for In−k) and k = dim(E1). Can you give a
geometric interpretation of the action of f (especially when k = n − 1)?
1
Problem B3 (50 pts). A rotation Rθ in the plane R
2
is given by the matrix
Rθ =
?
cos θ − sin θ
sin θ cos θ
?
.
(1) Use Matlab to show the action of a rotation Rθ on a simple figure such as a triangle
or a rectangle, for various values of θ, including θ = π/6, π/4, π/3, π/2.
(2) Prove that Rθ is invertible and that its inverse is R−θ.
(3) For any two rotations Rα and Rβ, prove that
Rβ ◦ Rα = Rα ◦ Rβ = Rα+β.
Use (2)-(3) to prove that the rotations in the plane form a commutative group denoted
SO(2).
Problem B4 (110 pts). Consider the affine map Rθ,(a1,a2)
in R
2 given by
?
y1
y2
?
=
?
cos θ − sin θ
sin θ cos θ
? ?x1
x2
?
+
?
a1
a2
?
.
(1) Prove that if θ 6= k2π, with k ∈ Z, then Rθ,(a1,a2) has a unique fixed point (c1, c2),
that is, there is a unique point (c1, c2) such that
?
c1
c2
?
= Rθ,(a1,a2)
?
c1
c2
?
,
and this fixed point is given by
?
c1
c2
?
=
1
2 sin(θ/2) ?
cos(π/2 − θ/2) − sin(π/2 − θ/2)
sin(π/2 − θ/2) cos(π/2 − θ/2) ? ?a1
a2
?
.
(2) In this question, we still assume that θ 6= k2π, with k ∈ Z. By translating the
coordinate system with origin (0, 0) to the new coordinate system with origin (c1, c2), which
means that if (x1, x2) are the coordinates with respect to the standard origin (0, 0) and if
(x
0
1
, x0
2
) are the coordinates with respect to the new origin (c1, c2), we have
x1 = x
0
1 + c1
x2 = x
0
2 + c2
and similarly for (y1, y2) and (y
0
1
, y0
2
), then show that
?
y1
y2
?
= Rθ,(a1,a2)
?
x1
x2
?
2
becomes
?
y
0
1
y
0
2
?
= Rθ
?
x
0
1
x
0
2
?
.
Conclude that with respect to the new origin (c1, c2), the affine map Rθ,(a1,a2) becomes
the rotation Rθ. We say that Rθ,(a1,a2)
is a rotation of center (c1, c2).
(3) Use Matlab to show the action of the affine map Rθ,(a1,a2) on a simple figure such as a
triangle or a rectangle, for θ = π/3 and various values of (a1, a2). Display the center (c1, c2)
of the rotation.
What kind of transformations correspond to θ = k2π, with k ∈ Z?
(4) Prove that the inverse of Rθ,(a1,a2)
is of the form R−θ,(b1,b2)
, and find (b1, b2) in terms
of θ and (a1, a2).
(5) Given two affine maps Rα,(a1,a2) and Rβ,(b1,b2)
, prove that
Rβ,(b1,b2) ◦ Rα,(a1,a2) = Rα+β,(t1,t2)
for some (t1, t2), and find (t1, t2) in terms of β, (a1, a2) and (b1, b2).
Even in the case where (a1, a2) = (0, 0), prove that in general
Rβ,(b1,b2) ◦ Rα 6= Rα ◦ Rβ,(b1,b2)
.
Use (4)-(5) to show that the affine maps of the plane defined in this problem form a
nonabelian group denoted SE(2).
Prove that Rβ,(b1,b2) ◦Rα,(a1,a2)
is not a translation (possibly the identity) iff α+β 6= k2π,
for all k ∈ Z. Find its center of rotation when (a1, a2) = (0, 0).
If α+β = k2π, then Rβ,(b1,b2) ◦Rα,(a1,a2)
is a pure translation. Find the translation vector
of Rβ,(b1,b2) ◦ Rα,(a1,a2)
.
Problem B5 (80 pts). A subset A of R
n
is called an affine subspace if either A = ∅, or
there is some vector a ∈ R
n and some subspace U of R
n
such that
A = a + U = {a + u | u ∈ U}.
We define the dimension dim(A) of A as the dimension dim(U) of U.
(1) If A = a + U, why is a ∈ A?
What are affine subspaces of dimension 0? What are affine subspaces of dimension 1
(begin with R
2
)? What are affine subspaces of dimension 2 (begin with R
3
)?
Prove that any nonempty affine subspace is closed under affine combinations.
(2) Prove that if A = a + U is any nonempty affine subspace, then A = b + U for any
b ∈ A.
3
(3) Let A be any nonempty subset of R
n
closed under affine combinations. For any
a ∈ A, prove that
Ua = {x − a ∈ R
n
| x ∈ A}
is a (linear) subspace of R
n
such that
A = a + Ua.
Prove that Ua does not depend on the choice of a ∈ A; that is, Ua = Ub for all a, b ∈ A. In
fact, prove that
Ua = U = {y − x ∈ R
n
| x, y ∈ A}, for all a ∈ A,
and so
A = a + U, for any a ∈ A.
Remark: The subspace U is called the direction of A.
(4) Two nonempty affine subspaces A and B are said to be parallel iff they have the same
direction. Prove that that if A 6= B and A and B are parallel, then A ∩ B = ∅.
Remark: The above shows that affine subspaces behave quite differently from linear subspaces.
Problem B6 (120 pts). (Affine frames and affine maps) For any vector v = (v1, . . . , vn) ∈
R
n
, let vb ∈ R
n+1 be the vector vb = (v1, . . . , vn, 1). Equivalently, vb = (vb1, . . . , vbn+1) ∈ R
n+1 is
the vector defined by
vbi =
(
vi
if 1 ≤ i ≤ n,
1 if i = n + 1.
(1) For any m + 1 vectors (u0, u1, . . . , um) with ui ∈ R
n and m ≤ n, prove that if the m
vectors (u1 − u0, . . . , um − u0) are linearly independent, then the m + 1 vectors (ub0, . . . , ubm)
are linearly independent.
(2) Prove that if the m + 1 vectors (ub0, . . . , ubm) are linearly independent, then for any
choice of i, with 0 ≤ i ≤ m, the m vectors uj − ui
for j ∈ {0, . . . , m} with j − i 6= 0 are
linearly independent.
Any m + 1 vectors (u0, u1, . . . , um) such that the m + 1 vectors (ub0, . . . , ubm) are linearly
independent are said to be affinely independent.
From (1) and (2), the vector (u0, u1, . . . , um) are affinely independent iff for any any choice
of i, with 0 ≤ i ≤ m, the m vectors uj − ui
for j ∈ {0, . . . , m} with j − i 6= 0 are linearly
independent. If m = n, we say that n + 1 affinely independent vectors (u0, u1, . . . , un) form
an affine frame of R
n
.
4
(3) if (u0, u1, . . . , un) is an affine frame of R
n
, then prove that for every vector v ∈ R
n
,
there is a unique (n+ 1)-tuple (λ0, λ1, . . . , λn) ∈ R
n+1, with λ0 +λ1 +· · ·+λn = 1, such that
v = λ0u0 + λ1u1 + · · · + λnun.
The scalars (λ0, λ1, . . . , λn) are called the barycentric (or affine) coordinates of v w.r.t. the
affine frame (u0, u1, . . . , un).
If we write ei = ui − u0, for i = 1, . . . , n, then prove that we have
v = u0 + λ1e1 + · · · + λnen,
and since (e1, . . . , en) is a basis of R
n
(by (1) & (2)), the n-tuple (λ1, . . . , λn) consists of the
standard coordinates of v − u0 over the basis (e1, . . . , en).
Conversely, for any vector u0 ∈ R
n and for any basis (e1, . . . , en) of R
n
, let ui = u0 + ei
for i = 1, . . . , n. Prove that (u0, u1, . . . , un) is an affine frame of R
n
, and for any v ∈ R
n
, if
v = u0 + x1e1 + · · · + xnen,
with (x1, . . . , xn) ∈ R
n
(unique), then
v = (1 − (x1 + · · · + xx))u0 + x1u1 + · · · + xnun,
so that (1−(x1 +· · ·+xx)), x1, · · · , xn), are the barycentric coordinates of v w.r.t. the affine
frame (u0, u1, . . . , un).
The above shows that there is a one-to-one correspondence between affine frames (u0, . . .,
un) and pairs (u0,(e1, . . . , en)), with (e1, . . . , en) a basis. Given an affine frame (u0, . . . , un),
we obtain the basis (e1, . . . , en) with ei = ui −u0, for i = 1, . . . , n; given the pair (u0,(e1, . . .,
en)) where (e1, . . . , en) is a basis, we obtain the affine frame (u0, . . . , un), with ui = u0 + ei
,
for i = 1, . . . , n. There is also a one-to-one correspondence between barycentric coordinates
w.r.t. the affine frame (u0, . . . , un) and standard coordinates w.r.t. the basis (e1, . . . , en).
The barycentric cordinates (λ0, λ1, . . . , λn) of v (with λ0 + λ1 + · · · + λn = 1) yield the
standard coordinates (λ1, . . . , λn) of v − u0; the standard coordinates (x1, . . . , xn) of v − u0
yield the barycentric coordinates (1 − (x1 + · · · + xn), x1, . . . , xn) of v.
(4) Let (u0, . . . , un) be any affine frame in R
n and let (v0, . . . , vn) be any vectors in R
m.
Prove that there is a unique affine map f : R
n → R
m such that
f(ui) = vi
, i = 0, . . . , n.
(5) Let (a0, . . . , an) be any affine frame in R
n and let (b0, . . . , bn) be any n + 1 points in
R
n
. Prove that the (n + 1) × (n + 1) matrix A corresponding to the unique affine map f
such that
f(ai) = bi
, i = 0, . . . , n,
5
is given by
A =
?
bb0
bb1 · · · bbn
?
ba0 ba1 · · · ban
?−1
.
In the special case where (a0, . . . , an) is the canonical affine frame with ai = ei+1 for
i = 0, . . . , n − 1 and an = (0, . . . , 0) (where ei
is the ith canonical basis vector), show that

ba0 ba1 · · · ban
?
=


1 0 · · · 0 0
0 1 · · · 0 0
.
.
.
.
.
.
.
.
. 0 0
0 0 · · · 1 0
1 1 · · · 1 1


and

ba0 ba1 · · · ban
?−1
=


1 0 · · · 0 0
0 1 · · · 0 0
.
.
.
.
.
.
.
.
. 0 0
0 0 · · · 1 0
−1 −1 · · · −1 1


.
For example, when n = 2, if we write bi = (xi
, yi), then we have
A =


x1 x2 x3
y1 y2 y3
1 1 1




1 0 0
0 1 0
−1 −1 1

 =


x1 − x3 x2 − x3 x3
y1 − y3 y2 − y3 y3
0 0 1

 .
(6) Recall that a nonempty affine subspace A of R
n
is any nonempty subset of R
n
closed
under affine combinations. For any affine map f : R
n → R
m, for any affine subspace A of
R
n
, and any affine subspace B of R
m, prove that f(A) is an affine subspace of R
m, and that
f
−1
(B) is an affine subspace of R
n
.
Problem B7 (30 pts). Let A be any n × k matrix
(1) Prove that the k × k matrix AA and the matrix A have the same nullspace. Use
this to prove that rank(AA) = rank(A). Similarly, prove that the n × n matrix AA and
the matrix A have the same nullspace, and conclude that rank(AA) = rank(A).
We will prove later that rank(A) = rank(A).
(2) Let a1, . . . , ak be k linearly independent vectors in R
n
(1 ≤ k ≤ n), and let A be the
n × k matrix whose ith column is ai
. Prove that AA has rank k, and that it is invertible.
Let P = A(AA)
−1A (an n × n matrix). Prove that
P
2 = P
P
= P.
What is the matrix P when k = 1?
6
(3) Prove that the image of P is the subspace V spanned by a1, . . . , ak, or equivalently
the set of all vectors in R
n of the form Ax, with x ∈ R
k
. Prove that the nullspace U of P is
the set of vectors u ∈ R
n
such that Au = 0. Can you give a geometric interpretation of U?
Conclude that P is a projection of R
n onto the subspace V spanned by a1, . . . , ak, and
that
R
n = U ⊕ V.
Hint. You may use results from HW2.
TOTAL: 460 points.
7