Elementary Linear Algebra (2024-25 @IITH)

Amit Tripathi

Indian Institute of Technology, Hyderabad

(IIT) Elementary Linear Algebra (2024-25 @IITH) 1 / 28

Orthogonal vectors
Definition
Let (V , <, >) be an inner product space and let α, β ∈ V . We say that α
is orthogonal to β if < α, β >= 0. A set S of vectors is called an
orthogonal set if all pairs of distinct vectors in S are orthogonal.

Remark
The 0 vector is orthogonal to every vector.

Example
With respect to the dot product on R3 , the set {i, j, k} is an orthogonal
set.

Example
The vector (x, y ) in R2 is orthogonal to the vector (−y , x) (again with dot
product).
(IIT) Elementary Linear Algebra (2024-25 @IITH) 2 / 28
Orthogonal vectors
Theorem
Any orthogonal set of non-zero vectors is linearly independent.

Proof.
Let S = {α1 , · · · , αn } be an orthogonal set. Suppose for some scalars
c1 , · · · , cn ∈ R,
c1 α1 + · · · + cn αn = 0.
Applying <, α1 > we get

c1 < α1 , α1 > + · · · + cn < αn , α1 >= 0.

By orthogonality, all the inner product, except the first one, vanish. Since
α1 ̸= 0, we get c1 = 0. Similarly, we conclude

c1 = · · · = cn = 0.

(IIT) Elementary Linear Algebra (2024-25 @IITH) 3 / 28

Orthogonal vectors

Corollary
If dim(V ) = n, then any orthogonal set of non-zero vectors will have at
most n vectors.

Example
The standard ordered basis B = {(1, 0, 0), (0, 1, 0), (0, 0, 1)} is an
orthogonal basis of R3 .

Question: Suppose β = xi + yj + zk. Suppose β · i = a, β · j = b and

β · k = c. Find the values of x, y and z ?

(IIT) Elementary Linear Algebra (2024-25 @IITH) 4 / 28

Orthogonal vectors
Lemma
Let S = {α1 , · · · , αn } be an orthogonal set of non-zero vectors. If α ∈ V
be any vector which can be expressed as

β = c1 α1 + · · · + cn αn , for some scalars c1 , · · · , cn ∈ R.

Then for each i,

< β, αi >
ci = .
||αi ||2

Proof.
Taking inner product with <, αi > on both sides, we get

< β, αi >= ci ||αi ||2 .

(IIT) Elementary Linear Algebra (2024-25 @IITH) 5 / 28

Orthonormal vectors
Definition
A unit vector is a vector whose norm is 1. An orthonormal set is an
orthogonal set S such that every α ∈ S is a unit vector.

Example
With respect to the dot product on R3 , the set {i, j, k} is an orthonormal
set.

Example
If S = {α1 , · · · , αn } is an orthogonal set of non-zero vectors, then the set
 
′ α1 αn
S = ,··· ,
||α1 || ||αn ||

is an orthonormal set.

(IIT) Elementary Linear Algebra (2024-25 @IITH) 6 / 28

Gram-Schmidt Orthogonalization Procedure
There is an algorithm which always gives an orthonormal basis for any
finite dimensional vector space.
Example
Let V be a 3-dimensional space and let B = {α1 , α2 , α3 } be a basis.
(a) Is {α1 } orthogonal and linearly independent? Set β1 = α1 .
(b) Is {α1 , α2 } orthogonal (hence linearly independent) ? How about
the modified set {α1 , α2 + cα1 } for some c ̸= 0. Taking
< α1 , α2 >
c =− works. Set
||α1 ||2
< α1 , α2 >
β2 = α2 − α1 .
||α1 ||2

(c) Then {β1 , β2 } is orthogonal, linearly independent and spans the same
space as {α1 , α2 }.

(IIT) Elementary Linear Algebra (2024-25 @IITH) 7 / 28

Gram-Schmidt Orthogonalization Procedure

Example
(a) Is {β1 , β2 , α3 } orthogonal and linearly independent? Consider the set
{β1 , β2 , α3 + aβ1 + bβ2 } for some a, b ̸= 0. Taking
< β1 , α3 > < β2 , α3 >
a=− 2
and b = − works. Set
||β1 || ||β2 ||2

< β1 , α3 > < β2 , α3 >

β 3 = α3 − 2
β1 − β2 .
||β1 || ||β2 ||2

Then {β1 , β2 , β3 } is an orthogonal set.

(b) Can it happen that β3 = 0 ? In particular, it is a linearly
independent.
v
(c) Apply the map v 7→ to get an orthonormal basis of V .
||v ||

(IIT) Elementary Linear Algebra (2024-25 @IITH) 8 / 28

Gram-Schmidt Orthogonalization Procedure

Theorem
Let (V , <, >) be an inner product space. Let S = {α1 , · · · , αn } be a
linearly independent set.
Then one can construct an orthogonal set S ′ = {β1 , · · · , βn } of non-zero
vectors such that S ′ is an orthonormal basis for the space spanned by S.

(IIT) Elementary Linear Algebra (2024-25 @IITH) 9 / 28

Gram-Schmidt Orthogonalization Procedure
Proof.
(a) Start by setting β1 = α1 .
(b) Inductively, for some k ≤ n suppose an orthonormal set {β1 , · · · , βk }
is already constructed. Set
k
X < αk+1 , βi >
βk+1 = αk+1 − βi .
||βi ||2
i=1

(c) Then for any j ≤ k,

k
X < αk+1 , βi >
< βk+1 , βj > =< αk+1 , βj > − < βi , βj >
||βi ||2
i=1
=< αk+1 , βj > − < αk+1 , βj >= 0.

Thus, βk+1 is orthogonal to all the vectors in the set {β1 , · · · , βk }.

(IIT) Elementary Linear Algebra (2024-25 @IITH) 10 / 28

Gram-Schmidt Orthogonalization Procedure

Proof.
(a) Can βk+1 = 0 ? Thus, {β1 , · · · , βk+1 } are linearly independent.
(b) How to get an orthonormal basis?

Corollary
If B = {β1 , · · · , βn } is an orthonormal basis, then for any

α = x1 β1 + · · · + xn βn
α′ = y1 β1 + · · · + yn βn ,

the value of < α, α′ > is x1 y1 + · · · + xn yn .

(IIT) Elementary Linear Algebra (2024-25 @IITH) 11 / 28

One remark

Remark
Suppose our starting (non-orthonormal) basis set is {α1 , · · · , αn }.
Suppose we have applied the above procedure till m steps to get a
orthonormal set {β1 , · · · , βm }. Then

< α1 , · · · , αm >=< β1 , · · · , βm > .

(IIT) Elementary Linear Algebra (2024-25 @IITH) 12 / 28

Geometry behind Gram-Schmidt Procedure

Example
Suppose we are given vectors {v1 , v2 } ∈ R2 . We set u1 = v1 . Next we
write v2 in terms of u1 and a vector u2 which is perpendicular to v2 .

(IIT) Elementary Linear Algebra (2024-25 @IITH) 13 / 28

Geometry behind Gram-Schmidt Procedure
Example

We project v2 on the vector u1 to get the component of v2 in the direction

of u1 as
u1
||v2 || cos(α) · .
||u1 ||
u1 · v2
Here cos(α) = .
||u1 || · ||v2 ||

(IIT) Elementary Linear Algebra (2024-25 @IITH) 14 / 28

Geometry behind Gram-Schmidt Procedure
Example

Putting them together, we get the component of v2 in the direction of u1

to be
u1 · v2 u1 u1 · v2
||v2 || · = u1 .
||u1 || · ||v2 || ||u1 || ||u1 ||2
Thus, the component in the perpendicular direction
u1 · v2
u2 = v 2 − u1 .
||u1 ||2
(IIT) Elementary Linear Algebra (2024-25 @IITH) 15 / 28
Gram-Schmidt Orthogonalization Procedure

Example
Let      
1 1 2
v1 =  1  , v2 = 0 , v3 = −2 .
−1 2 3
This is a basis of R3 . Start by setting w1 = v1 . Next set
 
4/3
< v2 , w1 > 1
w2 = v2 − w1 = v2 + w1 = 1/3 .
||w1 ||2 3
5/3

(IIT) Elementary Linear Algebra (2024-25 @IITH) 16 / 28

Gram-Schmidt Orthogonalization Procedure
Example
Let
       
1 1 2 4/3
v1 =  1  , v2 = 0 , v3 = −2 , w1 = v1 , w2 = 1/3 .
−1 2 3 5/3

We now set
< v3 , w1 > < v3 , w2 >
w3 = v3 − 2
w1 − w2
||w1 || ||w2 ||2
 
1
3
= v3 + w1 − w2 = −3/2 .
2
−1/2

To obtain an orthonormal basis from this orthogonal basis, we replace each

wi
vector wi by .
||wi ||
(IIT) Elementary Linear Algebra (2024-25 @IITH) 17 / 28
Orthogonal vectors

Example
(a) Let V = R2 and let W be the subspace consisting of y = 0.
(b) Let W ′ = {x = 0} and W ′′ = {y = x}.
(c) It is clear that V ∼
= W ⊕ W ′ and V ∼
= W ⊕ W ′′ .
(d) So there are many complementary subspaces to W .

(IIT) Elementary Linear Algebra (2024-25 @IITH) 18 / 28

Orthogonal complement

Lemma
Let (V , <, >) be an inner product space and let W be a subspace of V .
Let W ⊥ be the set of all vectors α ∈ V such that

< α, w >= 0, for all w ∈ W .

Then W ⊥ is a subspace and V = W ⊕ W ′ .

Proof.
It is immediate that W ⊥ is a subspace. To get W ⊥ , we start with a basis
BW = {α1 , · · · , αm } of W . Extend it to a basis

BV = {α1 , · · · , αm , αm+1 , · · · , αn }

of V .

(IIT) Elementary Linear Algebra (2024-25 @IITH) 19 / 28

Orthogonal complement

Proof.
Apply Gram-Schmidt process on BV to get a orthonormal basis
{β1 , · · · , βm , βm+1 , · · · , βn }. As remarked earlier, by construction of this
basis, we have

W =< α1 , · · · , αm >=< β1 , · · · , βm > .

Let
W ⊥ =< βm+1 , · · · , βn > .
It is clear that any vector v ∈ V , can be written as a unique sum

v = w + w ′,

where w ∈ W and w ′ ∈ W ⊥ .

(IIT) Elementary Linear Algebra (2024-25 @IITH) 20 / 28

Orthogonal complement

Definition
The subspace W ⊥ thus obtained is called the orthogonal complement of
W with respect to the given inner product.

(IIT) Elementary Linear Algebra (2024-25 @IITH) 21 / 28

Applications of orthogonality

The approximation problem: Let (V , <, >) be an inner product

space. Let β ∈ V be any vector. Suppose we have a vector subspace
W ⊆ V . We want to approximate β by vectors in W .
Question: How to quantify ”best approximation” ?
Definition
We say that α ∈ W is a best approximation of β by vectors in W if for
every γ ∈ W , we have

||β − α|| ≤ ||β − γ||.

(IIT) Elementary Linear Algebra (2024-25 @IITH) 22 / 28

Applications of orthogonality

Figure: The best approximation of vector u is w

(IIT) Elementary Linear Algebra (2024-25 @IITH) 23 / 28

Approximating a vector
Lemma
The vector α ∈ W is a best approximation of β by vectors in W
if and only if β − α is orthogonal to every vector in W . Further, if α is a
best approximation of β, then it is unique.

Proof.
First assume that the vector α ∈ W is such that β − α is orthogonal to
every vector in W . For any arbitrary γ ∈ W , we have

||β − γ||2 = ||(β − α) + (α − γ)||2

= ||β − α||2 + ||α − γ||2 + 2 < β − α, α − γ >

Since α − γ ∈ W , by assumption, the second term vanishes. Thus, we get

||β − γ||2 ≥ ||β − α||2 .

Since γ ∈ W was arbitrary, we get that α is a best approximation.

(IIT) Elementary Linear Algebra (2024-25 @IITH) 24 / 28
Approximating a vector

Proof.
Conversely, suppose α ∈ W is a best approximation of β. Suppose
β = w + w ′ be the unique representation of β as a sum of vectors w ∈ W
and w ′ ∈ W ⊥ . Sufficient to show that w = α. If not, then

||β − α||2 = ||β − w ||2 + ||w − α||2 + 2 < β − w , w − α > .

Here the third vanishes as β − w = w ′ ∈ W ⊥ and α − w ∈ W . Thus, we

get a contradiction unless α = w as we wanted to show.
Uniqueness is clear.

(IIT) Elementary Linear Algebra (2024-25 @IITH) 25 / 28

Row rank = Column rank

Lemma
Let A be any m × n matrix. Then

N(At A) = N(A).

Proof.
If X ∈ N(A) then At A(X ) = At (AX ) = 0. Thus N(A) ⊆ N(At A).
Conversely, suppose X ∈ N(At A), i.e. At AX = 0. Multiplying on the left
by X t , we get (AX )t (AX ) = 0, which (with usual norm) gives

||AX || = 0.

This means that AX = 0, thus X ∈ N(A).

(IIT) Elementary Linear Algebra (2024-25 @IITH) 26 / 28

Row rank = Column rank

Lemma
For any matrices A and B such that AB can be defined, we have

rank(AB) ≤ rank(A).

Definition
Let A be an m × n matrix. The row rank of A is the subspace of Rn
spanned by the rows of A. The row-rank of A is the dimension of this
subspce.

(IIT) Elementary Linear Algebra (2024-25 @IITH) 27 / 28

Row rank = Column rank

Lemma
For any m × n matrix A

row − rank(A) = column − rank(A).

Proof.
We know that
rank(At ) = rank(At A) ≤ rank(A).
Interchanging A and At , we get

rank(At ) = rank(A).

(IIT) Elementary Linear Algebra (2024-25 @IITH) 28 / 28