MS-C1342 Linear algebra, V/2023 Noferini / Puska

Linear algebra
Exercise sheet 4 / Model solutions

1. Let a ∈ Rn and A = aaT .

 T
(a) Give a geometrical interpretation to the mapping x 7→ Ax. Fix n = 2, a = 1 1
and draw the set
{Ax | x ∈ R2 , kxk2 = 1}.
(b) Show that kAk2 = kak22 .
 T
(c) Fix n = 2, a = 1 1 . Calculate kAk2 , kAkF and kAkmax .

Solution.
a x T
(a) By direct calculation: Ax = aaT x = kak22 kak 2 a. Hence, the mapping x 7→ Ax is the
2
projection of x to the direction of a scaled by kak22 . For the second part, denote
   
1 1 ⊥ 1 1
a0 = √ and a0 = √ .
2 1 2 −1
Any x ∈ R2 can be written as x = ta0 + sa⊥ 0 for some t, s ∈ R. By direct calculation,
it holds that kxk22 = t2 + s2 . The condition kxk2 = 1 implies that t ∈ [−1, 1]. Thus,

{Ax | x ∈ R2 , kxk2 = 1} = {akak2 t | t ∈ [−1, 1]}.

(b) By definition:
kAxk2 kaaT xk2
kAk2 = maxn = maxn .
x∈R kxk2 x∈R kxk2
Noticing that aT x is a scalar and using the Cauchy–Schwarz inequality gives

|aT x|kak2
kAk2 = maxn ≤ kak22 .
x∈R kxk2
a
Choosing x = kak2
gives

|aT a|kak2
kAk2 ≥ = kak22 .
kak2

Hence, kAk2 = kak22 .

P 1/2
(c) Using item (b) gives kAk2 = (12 + 12 ) = 2. By defintion, kAkF = 2
ij aij =2
and kAkmax = maxij |aij | = 1.

1/7
MS-C1342 Linear algebra, V/2023 Noferini / Puska

2. Let A, B, X ∈ Rn×n , a, b ∈ Rn and k · k some vector norm (same notation is used for the
corresponding operator norm). Show that:

(a) ka + bk ≥ kak − kbk , (so-called “reverse triangle inequality”)

(b) kA + Bk ≥ kAk − kBk ,
(c) The matrix I − X is invertible, if kXk < 1.

Hint: In (c) assume that there exists 0 6= x ∈ N (I − X) and argue by contradiction.

Solution.

(a) Applying the triangle inequality to the vectors s = a + b and m = −b, we have

kak = ks + mk ≤ ksk + kmk = ka + bk + kbk.

This shows that ka + bk ≥ kak − kbk. A similar trick, applied to s and d = −a, yields
ka + bk ≥ kbk − kak. Hence,

|kak − kbk| = max kak − kbk, kbk − kak ≤ ka + bk.

(b) By the triangle inequality,

kAk = kA + B − Bk ≤ kA + Bk + kBk

and
kBk = kB + A − A| ≤ kA + Bk + kAk
(remember that for any matrix X we have k − Xk = kXk). The statement follows by
an argument similar to item (a).
(c) For any induced norm k · k and using items (a–b),

k(I − X)xk kXxk

≥1− ≥ 1 − kXk > 0;
kxk kxk

in the penultimate step we have used the fact that

kXxk
kXk ≥
kxk

which is true because kXk is the maximum possible value of that ratio. This implies
that, for any nonzero x, (I − X)x cannot be 0, since it has positive norm. This in turn
implies that I − X is invertible under the given assumptions.

2/7
MS-C1342 Linear algebra, V/2023 Noferini / Puska

3. Let x ∈ Rn , A, B ∈ Rn×n and k · k be some vector norm (same notation is used for the
corresponding operator norm). Show that

kAxk ≤ kAkkxk , kABk ≤ kAkkBk and kIk = 1. (1)

Show by counterexample that k · kmax and k · kF are not operator norms.

Hint: Find matrices A, B ∈ R2×2 such that some of the properties in (1) do not hold. Note
that kIkmax = 1. In addition, the Frobenius norm satisfies the second inequality in (1): let
AT = [a1 , . . . , an ] and B = [b1 , . . . , bn ], so that
n n n n
X
2 X X X
kABk2F = aTi bj ≤ kai k22 kbj k22 = kai k22 kbj k22
i,j=1 i,j=1 i=1 j=1
X n n
X
= |aki |2 |blj |2 = kAk2F kBk2F
i,k=1 j,l=1

where the Cauchy–Schwarz inequality was used.

Solution. For an operator norm it holds that

kAk = sup kAxk.

kxk=1

x
From this follows that, for all x, we have kA kxk k ≤ kAk, and by one of the defining
properties of norms we get
kAxk ≤ kAkkxk.
By using the previous inequality we get

kABk = sup kABxk

kxk=1

≤ sup kAkkBxk
kxk=1

= kAk sup kBxk

= kAkkBk
≤ kAkkBk

The Frobenius norm is defined by

!1/2
X
kAkF = |aij |2 .
i,j

√
Let’s assume now that A = In ; from this follows that kAkF = n, and clearly

sup kIxk = 1,
kxk=1

3/7
MS-C1342 Linear algebra, V/2023 Noferini / Puska

from which follows that the Frobenius norm is an operator norm only when n = 1.
The maximum norm is kAkmax = max |aij |. Define A = (aij ) so that aij = 1 for all i, j.
Now
kAAkmax = n ≥ kAkmax kAkmax = 1,
which goes against the property of operator norms shown above.

4. Let A ∈ Rm×n .

(a) Show that

N (AT A) = N (A).
That is, the null space of A can be determined by computing eigenvectors correspond-
ing to the zero eigenvalue for ATA.
(b) Let  
1 1
A =   0 ,
0 
where  ∈ R. Compute eigenvalues for the matrix AT A by hand. For which values of
 the null-space of A is trivial?
(c) Determine N (A) using matlab, when  = 1, 10−6 and 10−9 . Compute eigenvalues
and corresponding eigenvectors for ATA numerically. Does Matlab agree with you on
the dimension of N (A) for each value of ? Include the script that you used and the
computed eigenvalues and vectors to your solution.

Hints: (a) The inclusion N (A) ⊂ N (AT A) can be easily proven. To prove that N (AT A) ⊂
N (A), multiply AT A from both sides with x and interpret the result as kAxk22 . (c) Try out
the commands help eig and format long in Matlab.
Solution.

(a) Method 1: The elements x in the null space of the matrix AT A satisfy

AT Ax = 0 multiply on the left by xT

xT AT Ax = 0
⇔ (Ax)T (Ax) = 0
⇔ kAxk2 = 0
⇔ Ax = 0

meaning that those elements x belong also to the null space of A. On the other hand,
if we take x ∈ N (A), then Ax = 0, which implies that AT Ax = AT 0 = 0, meaning
that surely also all elements of N (A) belong to the null space of AT A.

4/7
MS-C1342 Linear algebra, V/2023 Noferini / Puska

Method 2: We have
x ∈ N (AT A)
⇔ AT Ax = AT (Ax) = 0
⇔ Ax ∈ N (AT ) notice that Ax ∈ R(A), too.
On the other hand, recall that with respect to the Euclidean inner product we always
have R(A) ⊥ N (AT ), as we saw in a previous homework assignment. For this reason,
we get R(A) ∩ N (AT ) = {0}, and here’s why: if x ∈ R(A) ∩ N (AT ), then xT x =
kxk22 = 0, which is equivalent to x = 0 by definition of norm, and conversely we have
of course 0 ∈ R(A) ∩ N (AT ). We can then continue the chain of equivalences above
by
Ax ∈ R(A) ∩ N (AT ) ⇔ Ax = 0 ⇔ x ∈ N (A).
(b) Let us compute the eigenvalues λ:
AT A − λI = 0
 
  1 1
1  0 
 0 − λI = 0
1 0 
0 
 2

1+ 1
− λI = 0
1 1 + 2
1 + 2 − λ 1
=0
1 1 + 2 − λ
(1 + 2 − λ)2 − 1 = 0
1 + 2 − λ = ±1
(
2
λ= 2
 +2
The matrix has non-trivial null space if and only if some of its eigenvalues is 0, and let
us see when this happens:
λ1 = 2 = 0 ⇔  = 0
√
λ2 = 2 + 2 = 0 ⇔  = ± −2
Because of the assumption  ∈ R, the only possibility in which the matrix has non-
trivial null space is when  = 0.
(c) The Matlab code
format long % shows more decimals
for eps = [1, 10^(-6), 10^(-9)]
M=[1+eps^2, 1;1, 1+eps^2]; % matrix A^T * A
[V,D] = eig(M) % V = 2x2 matrix, with column eigenvectors,
% D = diagonal matrix, with eigenvalues on diagonal
end

5/7
MS-C1342 Linear algebra, V/2023 Noferini / Puska

prints the eigenvectors and eigenvalues for each value of .

When  = 1 the eigenvalues are 1 and 3, and the eigenvectors are [−0.7071 0.7071]T
and [0.7071 0.7071]T . (A bit more clearly, for λ = 1 we get the eigenvectors [v1 v2 ]
such that v1 = −v2 , and for λ = 3 we have v1 = v2 .) Since both eigenvectors differ
from zero, N (A) = {0}.
The output of the code is
V =

-0.707106781186547 0.707106781186547
0.707106781186547 0.707106781186547

D =

1 0
0 3

V =

-0.707106781186547 0.707106781186547
0.707106781186547 0.707106781186547

D =

0.000000000001000 0
0 2.000000000001000

V =

-0.707106781186547 0.707106781186547
0.707106781186547 0.707106781186547

D =

0 0
0 2
When  = 1 the eigenvalues are 1 and 3, and the eigenvectors are [−0.7071 0.7071]T
and [0.7071 0.7071]T . (A bit more clearly, for λ = 1 we get the eigenvectors [v1 v2 ]

6/7
MS-C1342 Linear algebra, V/2023 Noferini / Puska

such that v1 = −v2 , and for λ = 3 we have v1 = v2 .) Since both eigenvectors differ
from zero, N (A) = {0}.
For  = 10−9 the eigenvalues are, up to numerical precision, 0 and 2. Thus the numer-
ical rank of the matrix is different from what was obtained by analytical computations.
For  = 10−6 the smaller of the eigenvalues is 10−12 . This is still recognized as nonzero,
but very small eigenvalues such as this can cause problems in numerical computations.

7/7