Isomorphism Rank and Nullity Inner Product and Norm Approximation

SC 639 (Autumn 2020) - Mathematical Structures for

Control

1
Ravi N. Banavar
Harsh Oza 1

1
Systems and Control Engineering,
IIT Bombay, India

June 28, 2021

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Outline

1 Isomorphism

2 Rank and Nullity

3 Inner Product and Norm

4 Approximation

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Outline

1 Isomorphism

2 Rank and Nullity

3 Inner Product and Norm

4 Approximation

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Isomorphism

Isomorphism
A bijective linear transformation between two finite dimensional subspaces
is called an isomorphism.

• Let A : V → W be a linear mapping between two subspaces.

• Subspaces V and W are called isomorphic to each other if the A is
surjective and injective.
• If A is an isomorphism, then dim(V ) = dim(W ).

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Outline

1 Isomorphism

2 Rank and Nullity

3 Inner Product and Norm

4 Approximation

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Range space and Null space

Range Space
Let A : V → W be a linear transformation. The range space (R(A)) is
given by following.

R(A) = {w ∈ W |w = Av, ∀v ∈ V } (1)

Null space
Let A : V → W be a linear transformation. The null space (N(A)) is
given by following.

N (A) = {v ∈ V |Av = 0, ∀v ∈ V } (2)

• R(A) is a subspace of W.
• N(A) is a subspace of V.
• A is one-one if N (A) = {0}

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Rank and Nullity

• The dimension of Range space of A is called Rank of A (ρ(A)).

• The dimension of Null space of A is called Nullity of A (ν(A)).

Rank-Nullity Theorem
Let A : V → W be linear with dim(V ) = k. Then,

ρ(A) + ν(A) = k (3)

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Proof

• Let ν(A) = m and basis for null space of A be {u1 , u2 , . . . , um }.

• Extend the set as {u1 , u2 , . . . , un , w1 , w2 , . . . , wn } to be a basis of the
vector space V . Thus dim(V ) = m + n
• We need to prove that R(A) is finite and dim(R(A)) = n
• Let v ∈ V

v = a1 u1 + a2 u2 + . . . + an un + b1 w1 + b2 w2 + . . . + bn wn

applying transformation A on both sides,

Av = b1 Aw1 + b2 Aw2 + . . . + bn Awn

Here, Aui disappears because ui ∈ N (A)

• This implies {Aw1 , Aw2 , . . . , Awn } spans the entire range of A.

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Proof

• Now, we show {Aw1 , Aw2 , . . . , Awn } is linearly independent.

c1 Aw1 + c2 Aw2 + . . . + cn Awn = 0

Then,
A(c1 w1 + c2 w2 + . . . + cn wn ) = 0
hence, (c1 w1 + c2 w2 + . . . + cn wn ) ∈ N (A)

(c1 w1 + c2 w2 + . . . + cn wn ) = (d1 u1 + d2 u2 + . . . + dn un )
• This implies all c and d are zero because
{u1 , u2 , . . . , un , w1 , w2 , . . . , wn } is linearly independent.
• Thus,{Aw1 , Aw2 , . . . , Awn } is linearly independent and spans the
range of A.

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Outline

1 Isomorphism

2 Rank and Nullity

3 Inner Product and Norm

4 Approximation

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Norm

Norm
Given a vector space V over a field F, a norm on V is a non-negative
valued function || · || : V → with following properties.

Let, v, w ∈ V and if a is a scalar then,

1 ||av|| = |a| · ||v||,
2 ||v|| ≥ 0, with equality if and only if v = 0V ,
3 ||v + w|| ≤ ||v|| + ||w||,

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Examples of Norm

1 Let v ∈ Rn . The p-norm is given by,

v
u n
u
p
X
||v||p = t |vi |p
i=1

p
2 Let A ∈ Rm×n . The Frobenius norm is given by, ||A|| = T r(AT A)
3 Let V be the vector space consisting of all continuous functions on [a, b]
Rb
and f ∈ V . Then,||f ||1 = a |f (x)|dx
 1/2
R∞ 2
4 The 2-norm of a signal f (t) is ||f ||2 = −∞
f (t) dt

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Inner Product

Inner Product
An inner product in a vector space is a numerically valued function of
ordered pair of vectors v and w, such that
1 hα1 v1 + α2 v2 , wi = α1 hv1 , wi + α2 hv2 , wi
2 hv, wi = hw, vi;
3 hv, vi ≥ 0; hv, vi = 0 if and only if v = 0

Examples:
1 Let u, v ∈ V = Rn . Then, hu, vi = uT v is an inner product.
2 Let V be the vector spaceR 1consisting of all continuous functions and
f, g ∈ V . Then, hf, gi = 0 f (t)g(t) dt is an inner product.
3 Let u, v ∈2 . Then hu, vi = u1 v1 + 10u2 v2 is an inner product.

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Norm induced by inner product

Norm (induced by inner product)

Let V be an inner pproduct space. The norm of a vector v ∈ V is defined to
be a scalar ||v|| = hv, vi.

Let V be an inner product space. If v, w ∈ V and if a is a scalar then, it

satisfies following additional properties.
1 ||v + w||2 + ||v − w||2 = 2(||v||2 + ||w||2 )
2 ||v − w|| ≥ |||v|| − ||w|||

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Bessel’s Inequality

Theorem
Let V be an inner product space and u = {u1 , u2 , . . . , un } be an
orthonormal set in V . Let x ∈ V be arbitary. Define u ∈ V by
u= n
P
k=1 hx, uk iuk . Then,
n
X
||u||2 = |hx, uk i|2 6 ||x||2 (4)
k=1

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Proof.
Pn
Let g = k=1 hx, uk iuk

n
X n
X
||g||2 = hg, gi = hx, uk i2 ||uk ||2 = hx, uk i2 (5)
k=1 k=1

For each x ∈ V we have that,

0 ≤ ||x − g||2 = hx − g, x − gi
= ||x||2 − 2hx, gi = ||g||2
n
X
= ||x||2 − 2hx, hx, uk iuk i + ||g||2
k=1 (6)
n
X
= ||x||2 − 2 |hx, uk i|2 + ||g||2
k=1

= ||x||2 − ||g|| 2

Therefore, ||g||2 ≤ ||x||2 , which implies that, ||g|| ≤ ||x||.

n
X
|hx, uk i|2 6 ||x||2 (7)
k=1
SC 633 Spring 2020
 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Cauchy-Schwarz Inequality

Recall: We may write a vector u as a scalar multiple of a nonzero vector v,

plus a vector orthogonal to the vector v.
 
hu, vi hu, vi
u= v+ u− v (8)
||v||2 ||v||2

Theorem
Let V be an inner product space and u, v ∈ V . Then,

|hu, vi| 6 ||u|| ||v|| (9)

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Proof.
Let u, v ∈ V . If v = 0, then both sides of (9) equal 0 and the desired
inequality holds. Thus we assume that v 6= 0 . Consider orthogonal
decomposition,
hu, vi
u= v+w
||v||2
By Pythagorean theorem,
hu, vi 2
||u||2 = || v|| + ||w||2
||v||2
|hu, vi|2
= + ||w||2
||v||2
|hu, vi|2
≥
||v||2

Multiplying both sides of this inequality by ||v||2 and taking square root
gives the Cauchy-Schwarz inequality.

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Adjoint Transformation
• Let V be any vector space and V 0 be its dual space. A is a linear
transformation V .
• For each fixed y ∈ V 0 , the function y 0 defined by y 0 (x) = [Ax, y] is a
linear functional on V .
• The adjoint A0 : V 0 → V is defined by the following property.
[Ax, y] = [x, A0 y] (10)

Adjoint Transformation (based on inner product)

Let V and W be inner product spaces and A : V → W be a linear
transformation. A linear transformation A0 : W → V satisfying the
condition hA(v), wi = hv, A0 (w)i for all V ∈ V and W ∈ W is called an
adjoint transformation of A.
Let V, W and Y be inner product spaces. Let A : v → W , B : v → W and
C : W → Y be linear transformations having adjoints and k be a scalar.
Then,
0 0 0
1 (A + B) = A + B
0 0
2 (kA) = k̄A
0 0 0
3 (CA) = A C
0 0
4 (A ) = A
SC 633 Spring 2020
 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Riesz Representation Theorem

Riesz Representation Theorem

Let V be an inner product space. If δ ∈ V 0 then there exists a unique
vector y ∈ V satisfying δ(v) = hv, yi for all v ∈ V .

Example: Let n > 1 be an integer and let V be the subspace of Pn

consisting of all polynomial functionsRof degree at most n, on which we have
1
an inner product defined by hf, gi = −1 f (t)g(t) dt. Let δ ∈ V 0 be a linear
functional defined by δ : f 7→ f (0). Then
R 1 there exists a polynomial function
p ∈ V satisfying the condition f (0) = −1 f (t)p(t) dt for all f ∈ V .

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Projection
Projection
If V is the direct sum of M and N , so that every z ∈ V maybe written,
uniquely, in form of z = x + y, with x ∈ M and y ∈ N , the projection on
M along N is the transformation E defined by, Ez = x.

• A linear transformation E is a projection on some subspace if and only

if it is idempotent, that is, E 2 = E.
Proof: If E is the projection on M along N , and if z = x + y, then

E 2 z = EEz = Ex = x = Ez (11)

Conversely, suppose E 2 = E. Let N be a set of all vectors z ∈ V such that

Ez = 0. Let M be a set of all vectors z ∈ V such that Ez = z.
For an arbitary z we have,

z = Ez + (1 − E)z

If we write Ez = x and (1 − E)z = y, then Ex = E 2 z = Ez = x and

2
Ey = E(1L− E)z = Ez − E z = 0, so that x ∈ M and y ∈ N . This proves
V = M N and that the projection on M along N is E.
SC 633 Spring 2020
 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Properties of Projections

• If E is a projection on M along N , then M and N are, respectively,

the sets of all solutions of equations Ez = z and Ez = 0.
• A linear transformation E is a projection if and only if 1 − E is a
projection. If E is a projection on M along N then 1 − E is the
projection on N along M.
• E1 + E2 is a projection ⇐⇒ E1 E2 = E2 E1 = 0; then E = E1 + E2 is
L
a projection on M along N , where M = M1 M2 and N = N1 ∩ N2
• E1 − E2 is a projection ⇐⇒ E1 E2 = E2 E1 = E2 ; then E = E1 − E2 is
L
a projection on M along N , where M = M1 ∩ N2 and N = N1 M2
• If E1 E2 = E2 E1 = E, then E is a projection on M along N , where
M = M1 ∩ M2 and N = N1 + N2
• If M is a subspace invariant under linear transformation A, then
EAE = AE for every projection E on M. Conversely, if EAE = AE
for some projection E on M, then M is invariant under linear
transformation A.

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Outline

1 Isomorphism

2 Rank and Nullity

3 Inner Product and Norm

4 Approximation

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Least Squares Method

• Let a linear system be given by Ax = b, where A ∈m×n , x ∈m and b ∈n

then, the aim is to find best approximation of b which is in the range
space of A.
• The problem is converted to minimizing the error e = ||Ax − b||2 .
• The solution x̂ is which minimizes e is the same as locating the point
p = Ax̂ that is closer to b than any other point in the column space of
A.
• The error vector e must be perpendicular to the column space.
• All vectors perpendicular to the column space lie in the left nullspace.
Thus the error vector e must be in the nullspace of AT :

AT (b − Ax̂) = 0
x̂ = (AT A)−1 AT b (12)
 
p = Ax̂ = A (AT A)−1 AT b

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Example

Let a linear system be Ax = b where,

   
1 0 6
A = 1 1 b = 0
1 2 0

Here, b does not lie in the column space of A. So we have to find a best
approximation which lies in column span of A.
By (12) we get,  
5
p= 2 
−1
Geometrically, p is an orthogonal projection of b on column space of A.

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Geometric representation of least squares approximation

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Example

Problem: Sheldon wants to buy an apartment. But he wants to make sure

that he pays the right market value for the apartment. So he decides to do
a survey and tabulates them as under.
Area (in hundred Sq. ft) 12 10 15 6
No. of Bedrooms 2 3 4 1
Price(in Lacs) 70 75 85 50
Now, Sheldon has finalized a 750 Sq. ft. and 3 bedroom apartment. What
do you think he should pay? (For 0 Sq. ft. and 0 bedroom apartment the
price should be zero.)

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Example

12x + 2y = 70
10x + 3y = 75
15x + 4y = 85
60x + 1y = 50

We write it as
AX = b
where,    
12 2   70
10 3 x 75
A=
15
 X= b= 
4 y 85
6 1 50

X = (AT A)−1 AT b
 
5.800
=
1.967

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Example

Now we have to find the value of a 750 sq. ft. and 3 bedroom apartment.

P rice = 7.5x + 3y
= 49.4

Hence, Sheldon should pay 49.4 Lacs for the apartment.

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

References

1 Halmos, Paul R. Finite-dimensional vector spaces. Courier Dover

Publications, 2017.
2 Golan, Jonathan S. The Linear Algebra. Springer, 2007.
3 Strang, Gilbert. Linear Algebra and its applications. Cengage
Learning, 2005.

SC 633 Spring 2020

 Isomorphism Rank and Nullity Inner Product and Norm Approximation

Thank You

SC 633 Spring 2020