Linear Algebra

for Engineers

𝐿 . . . 𝐿1𝑁   𝑀 1   𝑂1 
𝐿11 𝑀 1 + · · · + 𝐿 1𝑁 𝑀 𝑁 = 𝑂1  11
    
𝐿21 𝑀 1 + · · · + 𝐿 2𝑁 𝑀 𝑁 = 𝑂2  𝐿 21 . . . 𝐿2𝑁   𝑀 2   𝑂2 

.. →↑  . . . . ...   ...  =  ... 
 ..
.     
    
𝐿 𝑃𝑁 𝑀 1 + · · · + 𝐿 𝑃𝑁 𝑀 𝑁 = 𝑂𝑃  𝐿 𝑃𝑁 . . . 𝐿 𝑃𝑁   𝑀 𝑁  𝑂 𝑃 
   


Parin Chaipunya, Ph.D.

Department of Mathematics
KMUTT
Contents

Contents 2

List of Figures 4

1 What is Linear Algebra all about ? 5

1.1 The course overview . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Matrix algebra: a quick review . . . . . . . . . . . . . . . . . . . . . 6

2 Linear systems and matrix equations 12

2.1 Solutions of a linear system . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Matrix equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Echelon forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.4 Gauss elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5 Gauss-Jordan elimination . . . . . . . . . . . . . . . . . . . . . . . . 20
2.6 Rank and solutions of 𝑄𝑀 = 𝑂 . . . . . . . . . . . . . . . . . . . . . . 21
2.7 Finding solutions of 𝑄𝑀 = 𝑂. . . . . . . . . . . . . . . . . . . . . . . . 24

3 Vector spaces 26
3.1 Vector spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 The space R𝑁 and its subspaces . . . . . . . . . . . . . . . . . . . . . 28
3.3 Vector subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.4 Linear combination and linear span . . . . . . . . . . . . . . . . . . . 31
3.5 Linear independence . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.6 Basis and dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.7 Change of basis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.8 Rank-nullity theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.9 The geometry of the solution set of 𝑄 = 𝑂 . . . . . . . . . . . . . . . 39
Practice problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2
CONTENTS 3

4 Norms, dot products and orthogonality 43

4.1 Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.2 Dot products and orthogonality . . . . . . . . . . . . . . . . . . . . . 45
4.3 Orthogonal projection . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.4 Gram-Schmidt orthogonalization process . . . . . . . . . . . . . . . 49
Practice problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

5 Linear transformations 51
5.1 Matrix representation . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.2 Vector space of all linear transformations . . . . . . . . . . . . . . . 54
5.3 Composite linear transformation . . . . . . . . . . . . . . . . . . . . 54
5.4 Linear transformation in computer graphics . . . . . . . . . . . . . . 55
Practice problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

6 Determinant and invertibility 60

6.1 Sarrus rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.2 General definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.3 Block triangular matrices . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.4 Determinant, rank and invertibility. . . . . . . . . . . . . . . . . . . . 64
6.5 Inverse linear transformation . . . . . . . . . . . . . . . . . . . . . . 66
6.6 Geometry of determinant . . . . . . . . . . . . . . . . . . . . . . . . 67
Practice problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

7 Eigenvalues and eigenvectors 69

7.1 Eigenvalues and eigenvectors . . . . . . . . . . . . . . . . . . . . . . 69
7.2 Eigenbasis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
7.3 Diagonalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
7.4 Singular value decomposition . . . . . . . . . . . . . . . . . . . . . . 74
7.5 Quadratic forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
Practice problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

8 Applications 81
8.1 Minimizing convex quadratic functions . . . . . . . . . . . . . . . . 81
8.2 Least-squares solutions of linear systems . . . . . . . . . . . . . . . . 82
8.3 Linear regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.4 Principal component analysis . . . . . . . . . . . . . . . . . . . . . . 86
8.5 Image compression . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
List of Figures

2.1 The flow chart for determining the number of solutions of 𝑄𝑀 = 𝑂. . . . 22

2.2 A practical flow chart for determining the number of solutions of 𝑄𝑀 = 𝑂. 23
3.1 The linear span (pink plane) generated by the vectors 𝑅1 (red) and 𝑅2 (green).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
5.1 Green points flipped across the plane 𝑀 + 𝑆 = 0 into red points. . . . . 57
6.1 The mnemonic diagram for 3 ↓ 3 Sarrus rule. . . . . . . . . . . . . . . . 61
7.1 (Left) Convex quadratic form. (Middle) Concave quadratic form. (Right) Indefinite
quadratic form. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
8.1 A convex and concave quadratic function with their extreme points. . . 82
8.2 Linear regression . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.3 The orthogonal projection of 3-dimensional data onto the first two
principal components. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
8.4 The original image and its rank 𝑇 approximations for 𝑇 = 5, 20, 50, 100. 89

4
Chapter 1

What is Linear Algebra all about ?

1.1 The course overview

Linear Algebra is a spin-o! subject from the study of Linear Systems (or System
of Linear Equations) through generalizations and re-interpretations.

𝐿11 𝑀1 + · · · + 𝐿1𝑁 𝑀 𝑁 = 𝑂1 𝐿
 11 . . . 𝐿1𝑁   𝑀 1   𝑂 1 
𝐿21 𝑀1 + · · · + 𝐿2𝑁 𝑀 𝑁 = 𝑂2  . . . . ...   ...  =  ...  →↑ 𝑄𝑀 = 𝑂.
.. →↑  ..    
.     
 𝐿 𝑃𝑁 . . . 𝐿 𝑃𝑁  𝑀 𝑁  𝑂 𝑃 
   
𝐿 𝑃𝑁 𝑀1 + · · · + 𝐿 𝑃𝑁 𝑀 𝑁 = 𝑂𝑃 

In the above figure, we may observe a di!ernt view from a linear system into a
simple matrix equation. This gives a new interpretation; instead of finding 𝑀 that
solves an equation, we find a vector 𝑀 that is transformed (by a transformation 𝑄)
into a new vector 𝑂.
The study of solutions of 𝑄𝑀 = 𝑂 is then developed into the theory about vector
space. The theory helps understanding a hidden structure that helps paving the
way to computing.
Another aspect that is heavily studied revolves around matrices. Many modern
applications in the digital world are the byproduct of the matrix theory. In partic-
ular, matrix is a systematic way to put data into places and matrix computations
help dealing with those data — especially in the large scales.
This lecture note could be roughly divided into four parts.
Part 1. This is Chapter 2, which talks about linear systems, matrix equations and
how to solve them.

5
 1.2. MATRIX ALGEBRA: A QUICK REVIEW 6

Part 2. Consisting of Chapters 3–4, this part studies vector spaces, their algebraic
structure and geometric structure.

Part 3. This third part includes Chapters 5–7. It starts with an interpretation
of a matrix as a transformation, followed by di!erent constants that are
indications of the properties that a matrix carries. The factorizations into
canonical forms are also discussed here.

Part 4. This final part is Chapter 8 which talks about some selected applications
of linear algebra.
The classical lectures will also be accompanied with computer laboratory ses-
sions to accommodate more complex calculations and to demonstrate the appli-
cations.

1.2 Matrix algebra: a quick review

1.2.1 The anatomy of a matrix
Let us give a quick summary of elementary matrix algebra. Recall first that a
matrix is an array of numbers listed as a tableau as follows
colum (หล
 𝐿11 𝐿12 . . . 𝐿1𝑁 


·
 𝐿21 𝐿22 . . . 𝐿2𝑁  &อฟ ( แถว
 .
 .. .. . . . ...  .
 . 
 𝐿 𝑃1 𝐿 𝑃2 . . . 𝐿 𝑃𝑁 

แถว ห
This matrix is said to have dimension of 𝑃 ↓ 𝑁, i.e. having 𝑃 rows and 𝑁 columns.
The 𝑈 th row of this matrix is the array
' (
𝐿 𝑈1 𝐿 𝑈2 . . . 𝐿 𝑈𝑁 ,

while the 𝑉 th column is the array

 𝐿1𝑉 
 
 𝐿2𝑉 
 . .
 .. 
 
𝐿𝑃 𝑉 
 
ลี
 1.2. MATRIX ALGEBRA: A QUICK REVIEW 7

In this course, matrices are usually presented with capital roman alphabets,
i.e., 𝑄, 𝑊, 𝑋, . . . , etc.
The following illustration depicts the 𝑈 th row and 𝑉 th column of a matrix:

 · 
 .  · . . . 𝐿1𝑉 . . . ·
· ... ·
 .. .. ... ..   
 . .  · . . . 𝐿2𝑉 . . . ·
 . . . 𝐿 𝑈𝑁  . . 
 .
𝑈 row ↔ 𝐿 𝑈1 𝐿 𝑈2
.. . . ... . . . ...
th

 .. .. . . . ...   
 .  · · 𝐿 𝑃 𝑉 · · 
 · . . . ·   
 · ↗
𝑉 th column

1.2.2 Special classes of matrices

์ ม
Vectors เวก เตอร ี 1 Col
์

เ ย กเอ กเตอ
# หล ายR ow

Definition 1.1. A matrix that has a single column (i.e. of dimension 𝑁 ↓ 1) is called
a column vector. Likewise, a matrix that has a single row (i.e. of dimension 1 ↓ 𝑁)
is called a row vector.

In this course, we use the simple term vector to refer to a column vector. Vectors
in this course are usually presented with lower-case letters like 𝐿, 𝑂, 𝑌, . . . or more
often with 𝑀, 𝑆, 𝑍, 𝑅, . . . ,etc.
To save up spaces, a column vector 𝑀 (with 𝑁 entries) is usually written also
as 𝑀 = (𝑀1 , . . . , 𝑀 𝑁 ). Hence, writting

𝑀 = (𝑀1 , . . . , 𝑀 𝑁 ) F Kristes.... An

is the same as
 𝑀1 
.
𝑀 =  ..  .
𝑀 𝑁 
 
์

Square matrices (เมท กซ จต

Definition 1.2. A square matrix is the one having equal rows and columns.
รี
มี
ร์
ริ
 1.2. MATRIX ALGEBRA: A QUICK REVIEW 8
ทแยง

Let 𝑄 = [𝐿 𝑈𝑉 ]𝑁↓𝑁 be an 𝑁 ↓ 𝑁 square matrix. The diagonal of 𝑄 refers to the

elements 𝐿11 , 𝐿22 , . . . , 𝐿 𝑁𝑁 , as shown on the following figure:
-

 𝐿11 · . . . · 

 · 𝐿22 . . . · 
 .
 .. .. . . . ... 
 . *เ เ
 · . . . 𝐿 𝑁𝑁 
น ท

 ·
↘
diagonal of 𝑄

Definition 1.3. A diagonal matrix is a square matrix whose nonzero entries are only
on its diagonal.

If the elements along the diagonal are 𝑎1 , 𝑎2 , . . . , 𝑎𝑁 , then we write diag(𝑎1 , . . . , 𝑎𝑁 )

to denote such a diagonal matrix, that is อเ & วเ ยว ยน เล

 𝑎1 0 
·

:
 
diag( 1,355) =

diag(𝑎1 , . . . , 𝑎𝑁 ) =  .
𝑎2
... 
 
0 𝑎𝑁 
ิกเอก ก
ร

เมท

Definition 1.4. The identity matrix of dimension 𝑁 ↓ 𝑁 is the matrix 𝑏 given by
1 
 . 0
𝑏 = diag(1, . . . , 1) =  .. 

)⨌⨌*+⨌⨌, 0 
𝑁 times  1  𝑁↓𝑁 ่

(เมทร ิกสามเห ย

Definition 1.5. A matrix 𝑄 is said to be an upper triangular matrix if all the entries
below its diagonal are all 0. Likewise, it is said to be a lower triangular matrix if all
the entries above its diagonal are all 0.

The following figure illustrates, respectively, an upper triangular matrix and a

lower triangular matrix:
UPPEV ไ เ lower
*เ
 𝐿11 ≃   𝐿11 0 
น

 
 ...   ... 
   
0   ≃ 
 · 𝐿 𝑁𝑁   𝐿 𝑁𝑁 
เ น& หม ไเ
We simply say that 𝑄 is a triangular matrix if it is either an upper or a lower
น

triangular matrix.
มุ
มื
นี้
ว็
ม่
ตั
ป็
ชื่
ขี
ส้
ดี
ลั
ลี
ม่
ป็
 1.2. MATRIX ALGEBRA: A QUICK REVIEW 9

1.2.3 Matrix algebra

Transposition A= :133 cas
Suppose that 𝑄 is an 𝑃 ↓ 𝑁 matrix given by
=3x2
 𝐿11 𝐿12 . . . 𝐿1𝑁 

 𝐿21 𝐿22 . . . 𝐿2𝑁 
𝑄 =  .. .. . . . ...  = [𝐿 𝑈𝑉 ]𝑃↓𝑁 .
 . . 
 𝐿 𝑃1 𝐿 𝑃2 . . . 𝐿 𝑃𝑁 

·

The transpose of 𝑄, written as 𝑄𝑐 , is an 𝑁 ↓ 𝑃 matrix defined by

 𝐿11 𝐿21 . . . 𝐿 𝑃1 

 𝐿12 𝐿22 . . . 𝐿 𝑃2 
𝑄𝑐 =  .. .. . . . ...  = [𝐿 𝑉𝑈 ]𝑁↓𝑃 .
 . . 
 𝐿1𝑁 𝐿2𝑁 . . . 𝐿 𝑁𝑃 
 =ว
It is clear that (𝑄𝑐 )𝑐 = 𝑄. สมมาตร > A= 5 = A A= symatic
A matrix 𝑄 is said to be symmetric if 𝑄𝑐 = 𝑄. Of course, every symmetric
matrix is a square matrix.

Scalar multiplication
We can multiply a scalar (a constant) to a matrix in a componentwise fashion.
Let 𝑌 ⇐ R be a scalar and 𝑄 = [𝐿 𝑈𝑉 ]𝑃↓𝑁 a matrix. Then the multiplication of 𝑌
with 𝑄, written 𝑌𝑄, is defined by
 𝑌𝐿11 𝑌𝐿12 . . . 𝑌𝐿1𝑁 
A

 𝑌𝐿21 𝑌𝐿22 . . . 𝑌𝐿2𝑁 
=  ..
C = S

𝑌𝑄 = [𝑌𝐿 𝑈𝑉 ]𝑃↓𝑁 .. ... ..  .

 . .  = S
. CA=SA

𝑌𝐿 𝑃1 𝑌𝐿 𝑃2 . . . 𝑌𝐿 𝑃𝑁 

=

If 𝑌 = ⇒1, then we write ⇒𝑄 instead of (⇒1)𝑄.

Matrix addition and subtraction

Adding/subtracting two or more matrices, all of them need to have the same
dimension. Let 𝑄 = [𝐿 𝑈𝑉 ]𝑃↓𝑁 and 𝑊 = [𝑂 𝑈𝑉 ]𝑃↓𝑁 be any two matrices. Then 𝑄 ± 𝑊 is
A- B =

A = in BESG
=
 1.2. MATRIX ALGEBRA: A QUICK REVIEW 10

defined componentwise, that is

 𝐿11 ± 𝑂11 𝐿12 ± 𝑂12 . . . 𝐿1𝑁 + 𝑂 1𝑁 

 𝐿21 ± 𝑂21 𝐿22 ± 𝑂22 . . . 𝐿2𝑁 + 𝑂 2𝑁 
𝑄 ± 𝑊 = [𝐿 𝑈𝑉 ± 𝑂 𝑈𝑉 ]𝑃↓𝑁 =  .. .. ... .. .
 . . . 
 𝐿 𝑃1 ± 𝑂 𝑃1 𝐿 𝑃2 ± 𝑂22 . . . 𝐿 𝑃𝑁 + 𝑂 𝑃𝑁 

For matrices 𝑄, 𝑊, 𝑋 with the same dimension, it is clear that
⇑ 𝑄 ⇒ 𝑊 = 𝑄 + (⇒𝑊),

⇑ and 𝑄 ± 𝑊 = 𝑊 ± 𝑄,
* *

⇑ (𝑄 ± 𝑊)𝑐 = 𝑄𝑐 ± 𝑊𝑐 ,

⇑ (𝑄 ± 𝑊) ± 𝑋 = 𝑄 ± (𝑊 ± 𝑋) = 𝑄 ± 𝑊 ± 𝑋,

⇑ if 𝑌 is a scalar, then 𝑌(𝑄 ± 𝑊) = 𝑌𝑄 ± 𝑌𝑊.

Matrix multiplication
Now, we consider multiplying two matrices 𝑄 and 𝑊, denoted 𝑄𝑊. For this, we
require the number of columns of 𝑄 and the number of rows of 𝑊 to be the same.
Let 𝑄 = [𝐿 𝑈𝑉 ]𝑃↓𝑁& and 𝑊 = [𝑂 𝑈𝑉 ]&
𝑁↓𝑑 , then 𝑄𝑊 = [𝑌 𝑈𝑉 ] is the matrix of dimension 𝑃 ↓ 𝑑
where the entry 𝑌 𝑈𝑉 is defined by
ห กก วง = แถว
𝑌 𝑈𝑉 = 𝐿 𝑈1 𝑂1𝑉 + 𝐿 𝑈2 𝑂2𝑉 + · · · + 𝐿 𝑈𝑁 𝑂 𝑁𝑑 .

The following illustration helps understanding the calculation of 𝑌 𝑈𝑉 :

A B
 · 
 .  · . . . 𝑂1𝑉 . . . ·
· ... ·
 .. .. ... ..     
 . .  · . . . 𝑂2𝑉 . . . ·  · 
 𝐿 𝑈1 𝐿 𝑈2 . . . 𝐿 𝑈𝑁  . .   .
 . .. . . ... . . . ...  .
= · 𝑌 𝑈𝑉 . . .

 .. .. . . . ...     .. 
 .  · · 𝑂 𝑁 𝑉 · ·   
 · . . . ·   
 ·

While 𝑃 and 𝑑 are not necessarily equal, 𝑊𝑄 is not even well-defined. For this
-
reason alone, there is no reason that 𝑄𝑊 and 𝑊𝑄 are the same. In general, even for
square matrices 𝑄 and 𝑊, 𝑄𝑊 and 𝑊𝑄 are not equal.
ต้
ลั
วิ
 1.2. MATRIX ALGEBRA: A QUICK REVIEW 11

Theorem 1.6. Let 𝑄, 𝑊, 𝑋 be two matrices. Then, whenever the above products are
well-defined, we have
&
⇑ 𝑄(𝑊 ± 𝑋) = 𝑄𝑊 ± 𝑄𝑋,
* =
=

⇑ (𝑄 ± 𝑊)𝑋 = 𝑄𝑋 ± 𝑊𝑋,
<
=

⇑ (𝑄𝑊)𝑋 = 𝑄(𝑊𝑋) = 𝑄𝑊𝑋,

⇑ (𝑄𝑊)𝑐 = 𝑊𝑐 𝑄𝑐 ,

⇑ 𝑏𝑄 = 𝑄 = 𝑄𝑏, (The two 𝑏’s can be of different dimension!)

⇑ if 𝑌 is a scalar, then 𝑌(𝑄𝑊) = (𝑌𝑄)𝑊 = 𝑄(𝑌𝑊),

Let us practice a little bit to conclude this review session.

Exercise 1.7. Define

- .  0 ⇒1 ⇒2  1 1
   
𝑊 = ⇒1 0 0  , and 𝑋 =  0 2 .
  
1 0 ⇒1
𝑄= ,
0 ⇒1 0 ⇒2 0 1  ⇒1 0
2x3   3x3   3x2
Find
PrxBER13 ไม่นย
(a) 𝑄𝑊 (b) 𝑊𝑄 (c) 𝑊𝑋
(d) 𝑄𝑋 (e) 𝑄𝑊𝑋 (f) 𝑊𝑐 𝑄
!
2) AB = :- วน= conforttine, ristoticenet the
ส่
 Chapter 2

Linear systems and matrix equations

In this chapter, we focus on systems of linear equations (or linear systems) and
their reformulations into matrix equations through which all the analysis will be
carried out. We shall study the classifications of the matrix equation 𝑄𝑀 = 𝑂 based
on its solution set being empty, singleton, or otherwise. Along the way, we study,
among other things, the notions of echelon forms and rank. We shall also study
the Gauss and Gauss-Jordan elimination methods which reduce any matrix into
a row echelon and reduced row echelon forms, respectively. These methods are
also used in finding solutions of a linear system.
Recall that a single-variable equation is said to be linear if it is in the form

𝐿𝑀 = 𝑂. (ส ปสา ( วแปร) = าค

This can be easily solved if 𝐿 ω 0 achieving 𝑀 = 𝑂𝐿 .

Having two variables, say 𝑀 and 𝑆, we need two equations to fix the solution.
In this way, we cannot just choose any 𝑀 and 𝑆 independently because they are
linked by the given equations. This system of two equations are said to be a linear
system if it is in the form

𝐿11 𝑀 + 𝐿 12 𝑆 = 𝑂1
𝐿21 𝑀 + 𝐿 22 𝑆 = 𝑂2 .

To solve this system, we first eliminate a variable and fix the solution of the other
then substitute back into one of the original equations.
The same principle applies to the case of linear systems with three vari-

12
ตั
ค่
2.1. SOLUTIONS OF A LINEAR SYSTEM 13

ables, 𝑀, 𝑆 and 𝑒, as the following form

𝐿11 𝑀 + 𝐿 12 𝑆 + 𝐿 13 𝑒 = 𝑂1
𝐿21 𝑀 + 𝐿 22 𝑆 + 𝐿 23 𝑒 = 𝑂2
𝐿31 𝑀 + 𝐿 32 𝑆 + 𝐿 33 𝑒 = 𝑂3 .
To find a solution, we eleminate and substitute variables one by one.
We may now see the pattern: A linear system with 𝑁 variables and 𝑁 equations,
namely 𝑀1 , . . . , 𝑀 𝑁 , takes the form
𝐿11 𝑀1 + 𝐿 12 𝑀 2 + · · · + 𝐿 1𝑁 𝑀 𝑁 = 𝑂1
𝐿12 𝑀1 + 𝐿 22 𝑀 2 + · · · + 𝐿 2𝑁 𝑀 𝑁 = 𝑂2
.. ..
. .
𝐿 𝑁1 𝑀1 + 𝐿 𝑁2 𝑀 2 + · · · + 𝐿 𝑁𝑁 𝑀 𝑁 = 𝑂 𝑁 .
Again, the same elimination-and-substitution strategy still works here, but with a
lot more e!ort.

2.1 Solutions of a linear system

We start by asking ourselves a crucial question:

Is it necessary to have equal number of variables and equations?

The simple answer to the above question is “No”. We may have 𝑁 variables that
are linked by 𝑃 linear equations:
𝐿11 𝑀1 + 𝐿 12 𝑀2 + · · · + 𝐿1𝑁 𝑀 𝑁 = 𝑂1  
= 𝑂2 

𝐿12 𝑀1 + 𝐿 22 𝑀2 + · · · + 𝐿2𝑁 𝑀 𝑁 

.. ..

𝑃 equations
. .

= 𝑂𝑃 . 


𝐿 𝑃1 𝑀 1 + 𝐿 𝑃2 𝑀 2 + · · · + 𝐿 𝑃𝑁 𝑀 𝑁
)⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌*+⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌,
𝑁 variables

The array of values 𝑍1 , . . . , 𝑍𝑁 is called a solution of the above linear system if

subsituting 𝑀1 = 𝑍1 , . . . , 𝑀 𝑁 = 𝑍𝑁 into the LHS gives RHS.
Let us consider some exercises below to refresh the idea of linear systems and
how to solve them.
 2.1. SOLUTIONS OF A LINEAR SYSTEM 14

Exercise 2.1. Verify whether or not 𝑀 1 = 3, 𝑀2 = ⇒1 a solution of the following

linear system
23 - 139 G
2𝑀 1 ⇒ 3𝑀 2 = 9
𝑀1 + 𝑀 2 = 2. 2 วแ
2 สมกา

Exercise 2.2. Verify whether or not 𝑀 1 = 2, 𝑀 2 = 2 a solution of the following linear

system 2 วแพ
~
𝑀2 ⇒ 𝑀1 = 0 / 2- 2 =&
2 สมการ
2𝑀 1 ⇒ 3𝑀 2 = ⇒11. + 2221- 312) =- 2

On the other hand, how do we find a solution of this system?

Now let us turn to solving a linear system instead of just verifying values.

Exercise 2.3. Find a solution to the following linear system

𝑀1 + 𝑀2 ⇒ 𝑀3 = 1
2𝑀 1 ⇒ 𝑀 2 + 𝑀 3 = 2
𝑀1 ⇒ 𝑀 2 ⇒ 𝑀 3 = ⇒1.

Exercise 2.4. Find a solution to the following linear system

3𝑀 1 ⇒ 2𝑀 2 + 2𝑀 3 = 1
2𝑀 1 ⇒ 𝑀 2 + 𝑀 3 = 2
𝑀1 ⇒ 𝑀 2 = ⇒1.

We should have observed that the method used to solve (and to further analyze)
linear systems are di!erent from problem to problem. To develop a consistent
methodology, we first need to rewrite them as matrix equations.
ตั
ตั
2.2. MATRIX EQUATIONS 15

2.2 Matrix equations

2.2.1 Transforming a linear system into a matrix equation
A linear system could always be transformed into a matrix equation. Given a
linear system

𝐿11 𝑀 1 + 𝐿 12 𝑀2 + · · · + 𝐿1𝑁 𝑀 𝑁 = 𝑂1
𝐿12 𝑀 1 + 𝐿 22 𝑀2 + · · · + 𝐿2𝑁 𝑀 𝑁 = 𝑂2
.. ..
. .
𝐿 𝑃1 𝑀 1 + 𝐿 𝑃2 𝑀2 + · · · + 𝐿 𝑃𝑁 𝑀 𝑁 = 𝑂 𝑃 ,

we would define
 𝐿11 𝐿12 . . . 𝐿1𝑁   𝑂1   𝑀1 
    
 𝐿21 𝐿22 . . . 𝐿2𝑁   𝑂2   𝑀2 
𝑄 =  .. .. . . . ...  , 𝑂 =  ..  , 𝑀 =  ..  .
 . .   .  .
 𝐿 𝑃1 𝐿 𝑃2 . . . 𝐿 𝑃𝑁  𝑂 𝑃  𝑀 𝑁 
    
We call 𝑄 the coe!cient matrix, 𝑂 the target vector, and 𝑀 an unknown vector. Then
we have
 𝐿11 𝑀1 + 𝐿12 𝑀2 + · · · + 𝐿1𝑁 𝑀 𝑁 
 
 𝐿12 𝑀1 + 𝐿22 𝑀2 + · · · + 𝐿2𝑁 𝑀 𝑁 
𝑄𝑀 =  .. 

 . 
 𝐿 𝑃1 𝑀1 + 𝐿 𝑃2 𝑀2 + · · · + 𝐿 𝑃𝑁 𝑀 𝑁 
 
·

and so the matrix equation

𝑄𝑀 = 𝑂

is equivalent to the linear system in question. When one analyze this equation,
we usually construct the following augmented matrix

  
 𝐿 11 . . . 𝐿1𝑁  𝑂1 
[𝑄 | 𝑂] =  .. . . . ..
. . 

..
. .

  
 𝐿 𝑃1 . . . 𝐿 𝑃𝑁 𝑂𝑃 
Note that the vertical bar separating 𝑄 and 𝑂 is purely notational. It is actually
an 𝑃 ↓ (𝑁 + 1) matrix where the first 𝑁 columns are from 𝑄 and the last is 𝑂.
 2.2. MATRIX EQUATIONS 16

2.2.2 Analyzing 𝑄𝑀 = 𝑂
We are not only interested in solving 𝑄𝑀 = 𝑂, but also to understand it.
The first and foremost behavior we would like to observe about the equa-
tion 𝑄𝑀 = 𝑂 is the number of solutions it has. We may very roughly speak of
consistent systems (those having a solution) and inconsistent systems (those without
a solution), but we want a more detailed description in this course. This leads us
to consider the three cases:
⇑ (well-posed) 𝑄𝑀 = 𝑂 has a unique solution, ค ต ตอบเด

⇑ (under-determined) 𝑄𝑀 = 𝑂 has multiple solutions, ยค ต

ม

หลา
-

⇑ (over-determined) 𝑄𝑀 = 𝑂 has no solution. ไ ค

To convince that all the three cases could happen, let us do the following
exercise.
Exercise 2.5. Let us observe that:
1 0 1  2
   
(a) Let 𝑄 = 1 0 ⇒1 and 𝑂 = 0 .
0 1 0  1
   
Then 𝑄𝑀 = 𝑂 has a unique solution, which is 𝑀 ≃ = (1, 1, 1). **= = E
- . - .
1 0 ⇒1 0 x1- x1=0
(b) Let 𝑄 = and 𝑂 = .
⇒1 1 0 1
Then 𝑄𝑀 = 𝑂 has multiple solutions. For example, 𝑀 ≃ = (0, 1, 0) and 𝑀 ≃≃ =
(1, 2, 1) are both solutions for this system. verify
*** = 1 = 9
 1 1 2
   
(c) Let 𝑄 =  0 2 and 𝑂 = 1 . At =
b)+free=
⇒1 4 0
   
Then 𝑄𝑀 = 𝑂 has no solution.

It is noticeably that the number of solutions depends on the relationship be-

tween the number of rows (equations) and the number of columns (variables). It
is casually understood that
⇑ a well-posed system has equal number of variables and equations,
⇑ an under-determined system has less equations than variables,
มี
มี
มี
ม่
ำ
ำ
ำ
2.3. ECHELON FORMS 17

⇑ an over-determined system has more equations than variables.

However, to really use this verdict, we need to be sure that the systems is reduced
into its simplest form, i.e. the row echelon form.
Let us do one more exercise to persuade ourselves that we need to reduce a
system before judging it. by ( =) /
Petective =

At =
1 1 2 4
<
Act 3 =

+1+
·

    2x2 + 31 : S

Exercise 2.6. Let 𝑄 = 0 1 1 and 𝑂 = 1 .

 
1 2 3 5
   
Then we have 3 variables and 3 equations, but multiple solutions. For in-
stance, 𝑀 ≃ = (2, 0, 1) and 𝑀 ≃≃ = (3, 1, 0) are both solutions of this system. We
will come back to explain this exercise again.

2.3 Echelon forms

2.3.1 Elementary row operations
Recall the operations that we did when solving linear systems in the previous
exercises:
⇑ multiplying a constant to an equation,
⇑ adding or subtracting two equations,
⇑ swapping order of equations.
These operations are transfered to the framework of matrix equations as elemetary
row operations (or simply row operations), which include
⇑ multiplying a constant to a row, #contou ># &
⇑ adding or subtracting two rows, +, -1 &
⇑ swapping rows. &; & or &

2.3.2 Row echelon forms

Consider a matrix 𝑓 = [𝑃 𝑈𝑉 ]𝑃↓𝑁 . A row of 𝑓 is called a zero row if it only
consists of 0. A row that is not a zero row is called non-zero row. In a non-zero
row, the first non-zero column in that row is called the leading entry.
 2.3. ECHELON FORMS 18

Looking at the following matrix leading enfry

0 𝜑 . . .
·
 0 0 → zero Now

0 . . . 0  zerO NOW
hon

𝑔 = 
0 ...
. . . . . .
,
0 𝜑 ...
→
0 0 ... . . . 0 

we conclude that the rows #2 and #4 are zero rows of this matrix, while he circled
entries (𝜑’s are any nonzero numbers) are the leading entries of their rows.

Definition 2.7. This matrix 𝑓 is in a row echelon form if the following two conditions
are satisfied:
(1) All zero rows are stacked at the bottom.

(2) In each non-zero row, its leading entry is on the left of all the leading entries
below it.

One may simply observe this visually by stacking zero rows at the bottom and
see that the leading entries are arranged in a staircase manner (see an example
ˆ
below with 𝑔).
Notice that the above matrix 𝑔 is not in an echelon form (why?). However, we
may use row operations (swapping rows) to acheive an equivalent matrix in the
following echelon form
 𝜑 . . . . . . . . . 
น

 0 → ตาม

 𝜑 . . . 
𝑔 = 
0 0 0 →
0 . . . . . . 0 
ˆ .
 0
 0 0 . . . . . . 0  zzero

row

prep

Definition 2.8. A matrix 𝑓 is in a reduced row echelon form if it is in a row echelon

form and the following additional conditions are satisfied:
(3) all leading entries are 1, leading - 1

(4) all entries above a leading entry are 0. * บน Monzero อง ง เ น &ห

Now let us practice checking if a given matrix is in a row echelon form or the
reduced row echelon form.
ต้
ป็
 2 .

CNS
A: ? 1
(0)
B=
0
②4 -

Relater
4. กแทนท
RE

:Credit

Room
29, :
&3- REA
ที
ถู
วี
 2.4. GAUSS ELIMINATION 19

Exercise 2.9. Determine whether or not the matrices given in the following are in
row echelon and reduced row echelon form.
1 2 0 →1 Hof 0 1 2 0 0 9 nof

&   &
REF REA

(a) 𝐿 = &
3 2 0 0 
 (b) 𝑀 = 0 & 2 →2 5 HOP
0 →1
&PRREF
RREF

&  0 1 1 0 0
2 4 0 1   0 &
0 1 0 →1 0 REF
& 0 REf  0 &
1 1 1 0 0 0 1 0 0 RREF
0 5 HDPRREF  0 0 &
(c) 𝑁 =  (d) 𝑂 = 0 1
0 →1
& 2 →2
0
0 0 0 0 &
0 0 0 &1 0 0 0 0 0 0 0
0 0 0 0 0 0 Zero row 
 0 0 0 0 0 0
 
Let us state some facts that could be useful in future considerations.
Theorem 2.10. The following facts hold true:
↑ Every matrix can be turned into a row echelon form using elementary row operations. เมทร ิกมอๆ ล ด ปเ
ได

↑ A single matrix may be turned into several row echelon forms. ได้เม ทรร ิก าง น เ

↑ every matrix can be reduced into a unique reduced row echelon form. ลด
หน้า ตา จะเห อ
ง RREF

Exercise 2.11. Use elementary row operations to find row echelon forms of the
matrices from Exercise 2.9.
นต อ นการแ ache
Gauss elimination

2.4 Gauss elimination ม ี5 น M an REF

The aim of the Gauss elimination is to give a systematic procedure to simplify

any matrix into a row echelon form. To do this, we eliminate as many nonzero
entries as possible by the following the steps below:
1. Start with the first nonzero column. Pick a nonzero entry, swap that row to the
top. Set 𝑃 = 1. ส บ &ใน /U
Monzer CO

2. Eliminate nonzero entries below the chosen entry from the previous step. ท ท ไ าง HonZ

ให เ น ZE

3. Find the next column with nonzero entry after the row 𝑃. Pick that nonzero
entry and swap to the row 𝑃 + 1. เ อนไป ท col อไ ป
อ ก ท um m จะล มแด วและห Oper e

4. Eliminate all the nonzero entries below the chosen entry from the previous
step.
ดึ
ก้
ห้
ลั
ป็
ั่
รู
ต้
ลื่
ต่
ขั้
ำ
ขั้
ลั
ป็
ำ
กั
ที่
ล่
ที่
มื
ต่
ำ
 2.5. GAUSS-JORDAN ELIMINATION 20

5. Set 𝑃 ↓ 𝑃 + 1 and repeat Steps 3–5 to complete all columns/rows.

Exercise 2.12. Use Gauss elimination to turn the following matrices into a row
echelon form.
1 0 →1
1 2 0 →1  1
  1 1 0 
(a) 𝐿 = 3 2 0 0  / (b) 𝑀 = 
2
2 4 0 1  2 4 1 1 
  3 6 2 1 

0 0 →1 2 2
 1  0 0 1
1 1 0  1 0
(c) 𝑁 =  (d) 𝑂 = 
0 0 1 1
0 →2 0 1  0 0 0 0 0
0 0 0 1  1 0 1 1 0
 
*ใ
สดว

2.5 Gauss-Jordan elimination ท PRE

The process of Gauss elimination reduces any given matrix into a row echelon
form. However, if we would like to go further in obtaining a reduced row echelon
form, we need a small extra computation in the Gauss elimination steps. This
modified algorithm is known as the Gauss-Jordan elimination whose steps are listed
as follows:
1. Start with the first nonzero column. Pick a nonzero entry, make it into 1 and
swap that row to the top. Set 𝑃 = 1.

2. Eliminate all nonzero entries in that column except the 1 from the previous step.

3. Find the next column with nonzero entry after the row 𝑃. Pick that nonzero
entry, make it into 1 and swap to the row 𝑃 + 1.

4. Eliminate all the nonzero entries in that column except the 1 from the previous
step.

5. Set 𝑃 ↓ 𝑃 + 1 and repeat Steps 3–5 to complete all columns/rows.

Exercise 2.13. Use Gauss-Jordan elimination to obtain the reduced row echelon
form of the following matrices.
ำ
 Ex 2.12
a =!
ไ
-

(b) B= ①

More ด
&4
2 I
&6
~

. ever, Co dia ↓
R -

*
&st2Re :
Ry * 1
&- 1
& 0- 1

0 1 -

!Re:
~ &4 * Retro

#3 A Razer lodin titl

3

Ex 2.
16

·for
Ref &res
Lo"Clinic B)= 3 at ::
อ

mas
0:
&-
-

1) &2
& &&

=ว inch nice. o so
VanK( DC = 2

ห ว R
3

!อ

·carReRe:
add-on
:อ-อ
& ศว:อ

Ref Pit3a" Condo หมวด

~

REF

NARKCB) = &
ติ
ลั
วิ
 2.6. RANK AND SOLUTIONS OF 𝐿𝑀 = 𝑁 21

→2 0
0 0 0 0 0  1 3
  2 0

(a) 𝐿 =   (b) 𝑂 = 
1 3
0 1 2 3 0 0
1 0 →1 2 3 1 →1 0
  1 1 1 3


2.6 Rank and solutions of 𝐿𝑀 = 𝑁

We regard each row of a matrix as an information. A matrix is then a collection
of information. Some of these information may be obtained from others and hence
does not genuinely a new information. A row echelon form (or reduced row echelon
form) of a matrix is viewed as a collection of genuine information in the sense that
each row cannot be deduced from the remaining rows, hence no rows can be
removed. It is natural that each matrix contains a certain amount of information,
and this amount is fixed.

2.6.1 Rank 2 จ นว น Non zero /NOW

Before we define the rank of a matrix, let us point out the following fact.

Theorem 2.14. Let 𝐿 be a given matrix. Then

↑ all row echelon forms of 𝐿 has the same number of nonzero rows,

↑ the reduced row echelon form of 𝐿 is unique.

With the consistence of nonzero rows in the above observation, one may define
a rank of a matrix to be the number of nonzero rows in a row echelon form. That
is, the rank is the number of genuine information that a matrix carries.

Definition 2.15. The rank of a matrix 𝐿 is defined to be the number of nonzero

rows of any row echelon form of 𝐿. The rank of 𝐿 is denoted by rank(𝐿).

Exercise 2.16. Find the rank of the matrices from the previous exercises.

2.6.2 Number of solutions

Recall that a row echelon form of a matrix reveals the minimal true information
that it carries. Therefore, the number of solutions of a matrix equation 𝐿𝑀 = 𝑁 can
ำ
2.6. RANK AND SOLUTIONS OF 𝐿𝑀 = 𝑁 22

be observed from the row echelon form of the augmented matrix [𝐿 | 𝑁]. More pre-
cisely, the number of solutions of 𝐿𝑀 = 𝑁 can be concluded from the rank([𝐿 | 𝑁])
as presented in the theorem below.

Theorem 2.17. Consider the equation 𝐿𝑀 = 𝑁 that corresponds to a system of 𝑃 variables

and 𝑄 equations. Then the following conclusion is drawn:
↑ rank(𝐿) < rank([𝐿 | 𝑁]) ↓↔ 𝐿𝑀 = 𝑁 has no solution.

↑ rank(𝐿) = rank([𝐿 | 𝑁]) = 𝑃 ↓↔ 𝐿𝑀 = 𝑁 has a unique solution.

↑ rank(𝐿) = rank([𝐿 | 𝑁]) < 𝑃 ↓↔ 𝐿𝑀 = 𝑁 has multiple solutions.

The following flow chart helps the explaining the use of rank to determine the
number of solutions of 𝐿𝑀 = 𝑁.

Start: Compute rank(𝐿) and rank([𝐿 | 𝑁])

No
rank(𝐿) = rank([𝐿 | 𝑁]) Stop: No solution.

Yes

No
rank(𝐿) = 𝑃 Stop: Multiple solutions.

Yes

Stop: Unique solution.

Figure 2.1: The flow chart for determining the number of solutions of 𝐿𝑀 = 𝑁.

A practical aspect
Consider again the system represented by 𝐿𝑀 = 𝑁 with 𝑃 variables and 𝑄
equations. In practice, to see if rank(𝐿) < rank([𝐿 | 𝑁]) happens, we do not need
2.6. RANK AND SOLUTIONS OF 𝐿𝑀 = 𝑁 23

to compute rank(𝐿) and rank([𝐿 | 𝑁]) separately.

Consider directly the matrix [𝐿 | 𝑁]. When reducing [𝐿 | 𝑁] to one of its row
echelon form [𝐿ˆ | 𝑁],ˆ the 𝐿ˆ is always a row echelon form of 𝐿. Therefore, we also
obtain a row echelon form of 𝐿 in the process of obtaining a row echelon form
of [𝐿 | 𝑁]. Then the following hold: If a row echelon form of [𝐿 | 𝑁] consists of a row
of the form [0 . . . 0 | 𝜑] (where 𝜑 ω 0), then rank(𝐿) < rank([𝐿 | 𝑁]) and so 𝐿𝑀 = 𝑁
has no solution.
Let us rewrite the above flow chart in a more practical perspective.

Start: Find a row echelon form of [𝐿|𝑁].

Yes
Contains [0 . . . 0|↗]
# Stop: No solution.

No

Yes
#nonzero rows = #var. Stop: Unique solution.

No
Stop: Multiple solutions.

Figure 2.2: A practical flow chart for determining the number of solutions of 𝐿𝑀 =
𝑁.

Exercise 2.18. Determine the number of solutions of the following system:

3𝑀 1 + 𝑀 2 → 𝑀 3 = 3
𝑀1 → 𝑀2 + 𝑀3 = 1
A= = 2𝑀 2 → 2𝑀 3 = 0

-
AIB =
3
&for = enAR- 3R Totten arest Red
2.7. FINDING SOLUTIONS OF 𝐿𝑀 = 𝑁. 24

Exercise 2.19. Determine the number of solutions of the following system:

2𝑀 1 + 𝑀 2 → 𝑀 3 = 2
𝑀1 + 𝑀2 = 2
𝑀2 + 𝑀3 = 0

Exercise 2.20. Determine the number of solutions of the following system:

𝑀1 + 𝑀2 + 𝑀3 + 𝑀4 =4

&
2𝑀 1 + 3𝑀 2 → 𝑀 3 → 𝑀 4 =3
𝑀2 + 𝑀3 =2
2𝑀 1 → 𝑀 2 + 𝑀 3 → 𝑀 4 =1
𝑀1 + 𝑀 2 → 𝑀 3 → 2𝑀 4 =0

Exercise 2.21. Determine the number of solutions of the following system:

𝑀1 + 𝑀2 + 𝑀3 + 𝑀4 =4
2𝑀 1 + 3𝑀 2 → 𝑀 3 → 𝑀 4 =3
𝑀2 + 𝑀3 =2
2𝑀 1 → 𝑀 2 + 𝑀 3 → 𝑀 4 =1
𝑀1 + 𝑀2 → 𝑀3 → 𝑀4 =0

2.7 Finding solutions of 𝐿𝑀 = 𝑁.

Now, after being able to determine the number of solutions of 𝐿𝑀 = 𝑁, it is time
to actually find its solutions (if one exists). The strategy is to simplify the aug-
mented matrix [𝐿|𝑁] using either Gauss elimination or Gauss-Jordan elimination,
and start analyzing from there.

Exercise 2.22. Solve the following linear system

𝑀1 + 𝑀2 → 𝑀3 = 6
𝑀1 → 𝑀 2 + 𝑀 3 = →2
2𝑀 1 → 2𝑀 2 + 3𝑀 3 = →5
 -&
-
-

่ 1 หา ค ตอบ ตรง ๆ ก จ

172: 2x, =&

11 = 2

แทน +1 = 2 ลงใน -X 2+ X
=- P-&

งไน @ - 2X243 +3 = - C

&- : - X3 = 1

แทน X 3 = - 1 ใน El x 2 = 3
... ระบบ สมการ ้ค
น

ี ตอมเ ย ว อ4=(

2 ลด ป เ น REF / RR
่

=in be

/B = I I called
&

Re Re
Love is /
·
RCE

&stro- can

Reserver Lotus 11 REF /

↓
-14 Xettz:
-2X2+2X3 = -%

<3 = - 1

· ·์ ac-es
o
aRe
วิธีที
ลุ
ดี
ำ
วิธี
ป็
ที
มี
รู
ำ
ำ
คื
 7
1

A =

AIS ) =
· -

Peace : to test is for RoNe for tos :

· Nanktib

# ฬ&MER
by Trunks
functio-
กี
ตั้
2.7. FINDING SOLUTIONS OF 𝐿𝑀 = 𝑁. 25

Exercise 2.23. Solve the following linear system

𝑀1 + 𝑀2 → 𝑀3 → 𝑀4 =0
𝑀1 → 𝑀2 + 𝑀3 + 𝑀4 =2
𝑀2 → 2𝑀 3 = →1
𝑀1 + 𝑀 2 + 3𝑀 3 + 2𝑀 4 =7

Exercise 2.24. Solve the following linear system

2𝑀 1 + 𝑀 2 → 3𝑀 3 = 1
𝑀1 → 𝑀2 + 𝑀3 = 1
3𝑀 1 → 2𝑀 3 = 2

Exercise 2.25. Solve the following linear system

𝑀1 + 2𝑀 2 → 𝑀 3 + 𝑀 4 = 3
2𝑀 1 → 2𝑀 2 + 2𝑀 3 → 𝑀 5 = 2
2𝑀 1 → 3𝑀 3 = →1
Chapter 3

Vector spaces =- sept structure

Let us motivate the study of a vector space, again, from the equation 𝐿𝑀 = 𝑁
that corresponds to a system of 𝑂 variables and 𝑃 equations. Let us begin with
the special case where 𝑁 = 0.
It turns out that when 𝐿𝑀 = 0 has more than one solution, it has infinitely
many of them. Let us demonstrate this fact. Let 𝑀 ↑ and 𝑀 ↑↑ both be solutions
of 𝐿𝑀 = 0. Take any numbers 𝜑 and 𝜒. Then we get

𝐿(𝜑𝑀 ↑ + 𝜒𝑀 ↑↑ ) = 𝜑𝐿𝑀 ↑ + 𝜒𝐿𝑀 ↑↑ = 0.

This means from two di!erent solutions, we can generate infinitely many more by
choosing di!erent values of 𝜑 and 𝜒.
Let S be the set that contains all the solutions of 𝐿𝑀 = 0. It turns out that the
shape S belongs to a particular class, e.g. a single dot, a straight line, a 2D flat
plane, a 3D space, etc. We actually observe that all of them are linear in nature. In
fact, we shall see subsequently that a solution set of the equation 𝐿𝑀 = 0, if not
empty, is a vector space (or a linear space).
Not limited to this, the concept of a linear space is also a backbone of modern
mathematics which applies to power series expansion, Fourier series and trans-
forms, Laplace transforms, di!erential equations, etc.
In this chapter, we introduce a general definition of a vector space but we will
emphasize on the Euclidean space R𝑂 and its subspaces. We shall also discuss
notions related to a vector space including, among others, basis and dimension.

26
3.1. VECTOR SPACES 27

3.1 Vector spaces

Let us begine with the definition of a general vector space.

Definition 3.1 (General vector space). Let 𝑄 be a nonempty set (whose elements
we call vectors) and 𝑅 be a scalar field (whose elements we call scalars and 𝑅 is
usually either R or C). Let + and · be the vector addition (adding two vectors in 𝑄
yields a vector in 𝑄) and scalar multiplication (multiplying a scalar in 𝑅 and a vector
in 𝑄 yields a vector in 𝑄). Then the set 𝑄 together with the operations + and ·
(precisely written as the tuple (𝑄 , +, ·)) is said to be a vector space over the scalar
field 𝑅 if the following conditions are satisfied for all 𝑆, 𝑇, 𝑈 ↓ 𝑄 and all 𝜑, 𝜒 ↓ 𝑅:
(V1) 𝑆 + 𝑇 = 𝑇 + 𝑆;

(V2) (𝑆 + 𝑇) + 𝑈 = 𝑆 + (𝑇 + 𝑈);

(V3) there is a zero vector, denoted by 0, such that 𝑆 + 0 = 0 + 𝑆 = 𝑆;

(V4) for each 𝑆 ↓ 𝑄, there is a vector in 𝑄, denoted by →𝑆 and called the negative
of 𝑆, such that 𝑆 + (→𝑆) = (→𝑆) + 𝑆 = 0;

(V5) 𝜑(𝑆 + 𝑇) = 𝜑𝑆 + 𝜑𝑇;

(V6) (𝜑 + 𝜒)𝑆 = 𝜑𝑆 + 𝜒𝑆;

(V7) (𝜑𝜒)𝑆 = 𝜑(𝜒𝑆);

(V8) 1𝑆 = 𝑆.

To clarify some frequent questions, the following remarks are in order.

↔ The zero vector and the number zero are both denoted by 0. Thus the reader
must be aware of the context where 0 is used.

↔ The negative of each 𝑆 ↓ R𝑂 is unique, and it is given exactly by the formula →𝑆 =

(→1)𝑆.

↔ We avoid to use ‘·’ to denote multiplication because this could be confused with
the dot product that we shall study later.
 ดเ กน
3.2. THE SPACE R𝑂 AND ITS SUBSPACES 28
RMAM =
Smoothie
Of
แถม

3.2 The space R𝑂 and its subspaces

We denote R𝑂 as the set of all 𝑂-dimensional real vectors 𝑀 = (𝑀 1 , . . . , 𝑀 𝑂 )
where 𝑀 𝑉 ↓ R for each 𝑉 = 1, . . . , 𝑂. Equipped with the vector addition ‘+’ and
scalar multiplication ‘ · ’ (where we always omit the symbol ‘ · ’), the following
properties hold for every 𝑆, 𝑇, 𝑈 ↓ R𝑂 and every 𝜑, 𝜒 ↓ R:
(E1) 𝑆 + 𝑇 = 𝑇 + 𝑆;

(E2) (𝑆 + 𝑇) + 𝑈 = 𝑆 + (𝑇 + 𝑈);

(E3) there is a zero vector, denoted by 0, such that 𝑆 + 0 = 0 + 𝑆 = 𝑆;

(E4) for each 𝑆 ↓ R𝑂 , there is a vector in R𝑂 , denoted by →𝑆 and called the negative
of 𝑆, such that 𝑆 + (→𝑆) = (→𝑆) + 𝑆 = 0;

(E5) 𝜑(𝑆 + 𝑇) = 𝜑𝑆 + 𝜑𝑇;

(E6) (𝜑 + 𝜒)𝑆 = 𝜑𝑆 + 𝜒𝑆;

(E7) (𝜑𝜒)𝑆 = 𝜑(𝜒𝑆);

(E8) 1𝑆 = 𝑆.
Therefore, R𝑂 (with its usual vector addition and scalar multiplication) is a vector
space. In what follows, the space R𝑂 (called the Euclidean space) is always equipped
with these classical operations unless explicitly stated otherwise.
One may observe the following development as 𝑂 starts o! from 𝑂 = 1. We
have:
↔ The space R1 = R which looks is a straight line (a 1D object).

↔ The space R2 which looks is a flat plane (a 2D object).

↔ The space R3 which is the 3D space we live in.

↔ The spaces R𝑂 with 𝑂 ↗ 3 are understood intuitively (adding one more axis
to R3 and so on). They are beyond our ability to draw.
Vector spaces เ นตร งโ โก้ง fin er SPN

Vector
* * sub
Space
S

spaces อนใน Vector Space

9 . * #
IR
พู
ซ้
ม่
ล็
ส้
 3.3. VECTOR SUBSPACES 29

3.3 Vector subspaces

Now let’s see how a space R𝑂 carries within itself. The space R2 actually
contains many straight lines. These lines behave just like the real line R, if it
contains 0. Roughly speaking, the 2D space R2 carries smaller 1D vector spaces.
Similarly, this 3D space R3 contains many straight lines as well as flat planes. In
the same fashion, this R3 carries smaller 1D and 2D vector spaces. This goes on
to R4 , R5 , etc. This phenomenon serves as the basic intuition of a vector subspace,
that is, a subset which is again a vector space in itself.
Definition 3.2 (Vector subspace). Suppose that 𝑄 is a vector space. Then a sub-
set 𝑊 ↘ 𝑄 is called a vector subspace of 𝑄 (or simply a subspace of 𝑄) if 𝑊 is a vector
space with the vector addition and scalar multiplication inherited from 𝑄.

In practice, to check whether or not a subset 𝑊 is a vector subspace, we use

either the single-step criterion or the double-step criterion presented as follows.
& Theorem 3.3 (Single-step subspace criterion). Let 𝑄 be a vector space and 𝑊 ↘ 𝑄. If
the following condition holds IR

(S1) 𝜑𝑆 + 𝜒𝑇 ↓ 𝑊 for any 𝑆, 𝑇 ↓ 𝑊 and any 𝜑, 𝜒 ↓ 𝑅,

then 𝑊 is a vector subspace of 𝑄.
Theorem 3.4 (Double-step subspace criterion). Let 𝑄 be a vector space and 𝑊 ↘ 𝑄.
If the following two conditions hold
(D1) 𝑆 + 𝑇 ↓ 𝑊 for all 𝑆, 𝑇 ↓ 𝑊,
(D2) 𝜑𝑆 ↓ 𝑊 for all 𝑆 ↓ 𝑊 and 𝜑 ↓ 𝑅,
then 𝑊 is a vector subspace of 𝑄.

On the contrary, to show that 𝑊 ↘ 𝑄 is not a vector subspace, we need to find

those elements 𝑆, 𝑇 ↓ 𝑊 and 𝜑, 𝜒 ↓ 𝑊 that violate one of the criteria (S1), (D1) or
(D2). Alternatively, we could also find the vectors (and possibly scalars) in which
one of (V1)–(V8) is false.
Now that we know R𝑂 is a vector space, let us explore some ot its subspaces.
Exercise 3.5. Show that 𝑊 = {(𝑀, 𝑋) ↓ R2 | 𝑀 = 2𝑋} is a subspace of R2 .
Exercise 3.6. Show that the set 𝑊 = {(𝑀1 , 𝑀2 ) ↓ R2 | 𝑀1 = 𝑀22 } is not a subspace of R2 .
 EXC. S ECRY เ น (910) GE

C2117 C

E = <CMY1 EIR"I
E

ey3 C--S, 2.31 C

#

x =

(110) #

ใ ้Therom 3.3 ในกา ารแสดง า เป็น subspac es ขอ

ก ห นดให
้
F และะ &,B G
ue,r E
& HtBREET
U=C UniUL) ) Re:2 H2
·:: U, PEE =>

V = (V11 /2) / ViteVz

ได
จะ ้ Cu +BY = a +
=CUN, Pr =
CPU , #BES
& %

จะะเ นว่า x = & UytBVe = GC242 + B (2V

2
%
CMULTOVI) =
=2 & ULPCBV2 = 24

ป า & U+BF
·: :. ส G

*เ น รห ง Space S ของI

ไ เ D Spac
ท

การแสดง น SU · หา & BERR UVEE

&UtBVG
#

· หา U, VEE ่U+P E

· KINEIR, UEE QU · แสดง ให้ไ ว่า O

Ex 3.6 E = { #MILC) = IR" I x 1 = <2 "

เ อก &=
-2 ↑
x =
u = (
11GE
↑1

จะะเ นไ ว่า &u 2 (1,11

= Strip#-to A
=

, f
และ &U = ( 2,2) &
#

:"' to ไ เ น SubSPace S
2

Ex 3.7

(b) D #o X = #12 / / 2 =
&xytb
(a) * - Sirirail xztax, จารณา Vector

0-x2 = dx,+b = · * ไ เ
r o = 28,8
ก หน ดให
้ H = Cuy,U2) Ex => Ustd จะะเ น า

=Via Val EX => View ↑ :" & # x และ

ส ป า -* ไ เ น Subo spor ces ของ

จะ ะได้ า &4 +PV = d (U1,42) + BCFII

= (KU1, &(2) + ( BU,, &
-

=(4) + PVI, QUCHPV)

~ ~
*
1 +2

จะะเ นว ่า x2 =GUctOV2 = SCOU1 +8Ca V

= (CU1+BK1) = &XI
~
*
+
·. . QU+&V E * และะได้ า เป็น S ubspace
ด้
ที
ที
ด้
พิ
ป็
ช่
ลื
ว่
ม่
ำ
ว่
ห็
ม่
ช้
ห็
ำ
จ่
ห็
ว่
รุ
ห็
ป็
ป็
ป็
ม่
ว่
รุ
ว่
ม่
ป็
 A spac E เพร าะวง
ไม่เ ว Su
3.3. VECTOR SUBSPACES 30

&2 of

Exercise 3.7. Consider a set of the form สมการเ นตร

%
~
𝐿 = {(𝑀1 , 𝑀2 ) | 𝑀 1 = 𝑁𝑀2 + 𝑂}, · x%

where 𝑁, 𝑂 → R are constants. Show the following:

(a) When 𝑂 = 0, then 𝐿 is a subspace of R2 for any choice of 𝑁.
(b) When 𝑂 ω 0, then 𝐿 is not a subspace of R2 for any choice of 𝑁.
In particular, we may conclude from the above facts that all straight lines passing
through the origin are subspaces of R2 and the ones not passing are not.
Exercise 3.8. Verify which of the following sets are subspaces of R2 .
(a) 𝑃 = {(𝑀, ↑𝑀) | 𝑀 → R}.
(b) 𝐿 = {(𝑀, ↑2𝑀) | 𝑀 ↓ 0}.
(c) 𝑄 = {(𝑀, 𝑅) | 𝑅 ↔ 𝑀}.

We may furthernotice that a set involves nonlinear operations volving one

or more of the variables (e.g. multiplications, powers, square roots, exponents,
logarithms, etc.) is usually not a linear space.
Exercise 3.9. Show that the following sets are not vector subspaces of R2 .
<- วแปร คูณ น
(a) 𝑆 = {(𝑀 1 , 𝑀2 ) → R2 | 𝑀1 𝑀 2 = 0}.
↗ =- ม
ลัง/ด อด N
(b) 𝑇 = {(𝑀 1 , 𝑀2 ) → R2 | 𝑀1 + 2𝑀 2 = 1}. กา รยกก

(c) 𝐿 = {(𝑀, 𝑅) → R2 | 𝑀1 (1 ↑ 𝑀 2 ) = ↑1}.

<- วแป รค ณ
-

(d) 𝑄 = {(𝑀, 𝑀 2 ) |
&>
𝑀 → R}.
ยกก
Exercise 3.10. Which of the following are vector spaces.
(a) 𝐿 = {(𝑀, ↑2𝑀 + 2𝑈, 𝑈) | 𝑀, 𝑈 → R}. * 1 ·
เ

* NY = x2 ไ เฉพาะ x +
·

(b) 𝑄 = {(𝑀, 𝑅, 𝑈) → R3 | 𝑀𝑅 = 𝑀𝑈}. #

(c) 𝑉 = {(𝑀 1 , . . . , 𝑀 𝑊 ) | 𝑀 1 = 0 and 𝑀 𝑊 = 0} /

We next consider in the upcoming exercises the two important vector spaces
that are generated by a given matrix.
คุ
ชิ
ตั
กั
ตั
ำ
มี
ส้
ด้
ำ
 EX
(a)
3.

W = &CAgIX) ( x
ERR
as
V #

(1) X= ECricXIX203 %
(2) Y = <2 x, y)
/Y =*

3 หา a=-1
&
4 = =(1, -2) EX { =1 1 Y =2 Y= # X & code
Ch = ( 112) ↑* < <= = = = = = 2 Year <Is &
:x ไ เ น Subsprce ขอ ง IRY

(C) เ อก &= -

H = (CI, 2) EY <X = 1, Y===== / 1 x )

&U = SC 112) &Y ( x = -
11 4 = 2, 4 * * *
~

::: "ไ เ น SU A Spac

CN) M = dAneX2) 1x nd อ าว อย 1 ต
EX 3.9

เ อก u = =(110) (EFire- o
=adm
V =
10,1) ( EP Fitc = o

จะเ นว า u+5 = (1, 8 ) + 0, 17 =21,1 ) &M ( XIX2 =S

::: ส ปไ วา Mไ เ น น Sub spo

่า

3,1 A elpmen
KINCAL = EXPIRYDATE&3 is a subspice of "

ก หน U &Ker CAL -a All = &

o E Ker CA) -> Art &

&, BE /K

จะไ 7 ACQUtOr = ALGultNCor1 = d Au + B Av

ว

subspaces ของ IRY

3.12 At /RMAN

Im CAT = { Ax / +ERRY3 = &YEIRM EXERRM; Y = Ax

3

ก หน ดให E imCAl => 7WEIRY; 4 =

้
4

1 Gim CA) => EZEIRY: V = Az

&, BE IR

ได้ ่า CUTBR = GAWTB

จะ

=- ACOW) + ASBET

#BES
=A

. . IPEIR": &U + BP = A4

·อ
ด้
ด้
ห็
ป็
ลื
ว่
ลื
ำ
ม่
ำ
รุ
ป็
ม่
ม่
ป็
ม็
ม่
น้
 3.4. LINEAR COMBINATION AND LINEAR SPAN 31

Exercise 3.11. Let 𝐿 be any 𝑀 → 𝑁 matrix. Then the solution set of 𝐿𝑂 = 0 is a

vector subspace of R𝑁 . This set is actually called the kernel of 𝐿, or ker(𝐿). In some
text books, the kernel is also called the null space.

Exercise 3.12. Let 𝐿 be any 𝑀 → 𝑁 matrix. Then the set of all products 𝐿𝑂 is a
vector subspace of R𝑀 . This set is actually called the image of 𝐿, or im(𝐿).

3.4 Linear combination and linear span

To ultimately study basis and dimension of a vector space, we start with the
notions of linear combination and linear span.

Definition 3.13 (Linear combination). Let (𝑃 , +, ·) be a vector space over the

field 𝑄 ↑ { R, C} and 𝑅 1 , 𝑅2 , . . . , 𝑅 𝑆 are vectors in 𝑃. A linear combination of these
vectors is any vector 𝑅 ↑ 𝑃 of the form
เร
𝑅 = 𝜑1 𝑅1 + 𝜑2 𝑅2 + · · · + 𝜑 𝑆 𝑅 𝑆 =- inser สน ส

where 𝜑 1 , . . . , 𝜑 𝑆 are scalars.

Example 3.14. Consider the vectors 𝑅 = (4, 0, 3), 𝑅1 = (1, 0, 0), 𝑅2 = (0, 1, 0) and 𝑅 3 =
(0, 0, 1) from R3 . Then 𝑅 is a linear combination of 𝑅1 and 𝑅 3 , but not of 𝑅1 and 𝑅 2 .

Exercise 3.15. Let 𝑅 = (5, 5, ↓5, 3), 𝑅 1 = (1, 2, 0, 0), 𝑅2 = (↓1, 1, 1, 1) and 𝑅3 =
(↓2, 0, 3, ↓1). Is 𝑅 a linear combination of the other vectors 𝑅1 , 𝑅2 , 𝑅3 ?

Exercise 3.16. Let 𝑅 = (2, 3, ↓1, 1), 𝑅 1 = (1, 1, 3, 2), 𝑅2 = (↓1, 2, 1, 0) and 𝑅3 =
(2, 0, 0, ↓1). Is 𝑅 a linear combination of the other vectors 𝑅1 , 𝑅2 , 𝑅3 ?

A nice way to generate a vector subspace from a few vectors is to use the linear
space, which is nothing else but all the possible linear combinations of such given
vectors.

Definition 3.17 (Linear span). Let 𝑃 be a vector space over the field 𝑄 ↑ { R, C}
and 𝑇 = {𝑅1 , 𝑅2 , . . . , 𝑅 𝑆 } ↔ 𝑃. Then the linear span (or simply the span) of 𝑇 is
! #
"
𝑆
span(𝑇) = span(𝑅1 , . . . , 𝑅 𝑆 ) = 𝜑 𝑈 𝑅 𝑈 | 𝜑1 , . . . , 𝜑 𝑆 ↑ 𝑄 ,
𝑈=1
all linear combi
3 ก
of VINV21 .... Ve
ทุ
 Ex 3.10 V=(

ข
ๆ = 31,0,0)
4,03) # การ เ ค า V เป็น Linear Com by ของ าง ว 1. *
ข2 = 28,790) kwa Add .... sx = Cde co-/
ิ Io ... .. * ไม่
V3 = 8,0,1) * row ม ค

<in
ส เ น
linearr comboii ของ และบ
② จารณากา รร ค ตอบข
อง At = 3 + คา Mor ostowLinear 0..... 3103 ค ตอ
อ งสามาร รถหา &1 A2 IR-
&3 G
*
เ นจริง
V =&
1
V
1 + &3 3
·
↓

: = #
Afriv d =3 = : ·-

Ax=1 อง: ค

CAID =3 #-
=

A==
+= e d = + = 3

า Alb = ด / re
Retro TriYes,
จารณ

starry on REF /
:ไ
:1
มี NOW ใน ปแ บน CO. . . Old
เ องจา ก Ax=
S

! ค งใ ว
:· Ax
:
-

6
#Nobester o isselected !

ตอ บ
A1 &3
1
P = &evet& gVg

:· F เ น Linear combination ขอ
งขา &V &* /PostPrePost
cii) Vไ เ น Linea-Camb i ขอ ง ขา แล RMF Retrod -
ะ

Ax=b ไ ่ ค ไม ิดเต
่ม

A: =
<= 11 1= :

จะ ะพบ า า CAID = IPURE

เ องจาก rews ใน ป แบบ O, ... 0
ูปไ
สร วา Ax :D ไ ม " ไ เ น linea r com eb ขอ ง ชาแล ะ
ข้
ที่
ต้
มี
พิ
มี
ด้
จึ
ชิ
มี
ด้
มี
นื่
ป็
นื่
มี
ป็
ช็
ม่
ป็
มี
ม่
มี
ว่
ม่
ำ
รู
รู
ำ
ม่
ำ
ำ
พิ
ชั่
ป็
ว่
ป็
ำ
ต้
ชุ
ม่
ด่
มิ
ชิ
ำ
3.4. LINEAR COMBINATION AND LINEAR SPAN 32

i.e. the set of all linear combinations of vectors in 𝐿. We also say that the
set 𝑀 = span(𝐿) is generated by 𝑁 1 , . . . , 𝑁 𝑂 , or that 𝑁1 , . . . , 𝑁 𝑂 are generating vectors
for 𝑀.

Figure 3.1: The linear span (pink plane) generated by the vectors 𝑁 1 (red)
and 𝑁2 (green).

Exercise 3.18. Let 𝑃 be a vector space and 𝐿 = {𝑁1 , . . . , 𝑁 𝑂 } be a subset of 𝑃. Show

that span(𝐿) is a vector subspace of 𝑃.

Exercise 3.19. Find span(𝐿) where 𝐿 is given by

(a) 𝐿 = {(1, 0), (0, 1)}

(b) 𝐿 = {(1, 0), (1, 1)}

(c) 𝐿 = {(0, 1, 0), (2, 0, 2)}

Also notice that the same set may be generated by a di!erent set of vectors.

At this point, one may also observe that a single vector 𝑁 may be written
as a linear combination of vectors 𝑁 1 , . . . , 𝑁 𝑂 in more than one way. Hence the
representation of 𝑁 as

𝑁 = 𝜑1 𝑁1 + · · · + 𝜑 𝑂 𝑁 𝑂

may not be unique due to the available choices of the coe"cients 𝜑 𝑄 ’s. Let us
investigate this non-unique characteristic in the following example.
 EX 3.10 = EVIIV 11 ... ข
spomCFY = 2air 19 ; EIRB

ก หน ดให้ U E GPr
m CEY ==> &1,... , &k u=GIY t , .... ,
F E SPom (FY => 1 ....... , * P= &V + .... ,
&, PEIR
้ า Gu
จะะได
+Br = G CG + .... . +, kedve) + BCIt,.... + &g
= &
&MV +. . . . . & &VR + Ba +. . . . + B &

=- Cay + . . ... + ( &KTBCIVR . . . ~

กา ↑k

::: กๆ 1.... . . 7/G/R:

QU+BP = ·1, + . . . . . . XRP (

End
·3 QU+BP เ น linear ข
Comb 80 * V

1. CUTBP
ESPOMCFY

- 3. Spam (F) เ น SubSPace S

3. +

a) W= 541,87, <OM
V. Ne
SPAM( U) = SPOM ( ( 7,07,0,17

= ,Vy + &aVe &1,42E IRY

= 2, (1,0) + &2 <011) 19 1 ga2EIRY

= (&1,0) + 10, 42) 191 , &DEIRY
= CM1, &2) 1 & 1,22 G #

= IR

1) F = &( 1,0), <1,113

Sparmers = Spor 1,01, 29,1

= , (110) + &221, 11 14 1,
&2EIR3

= (GR2, 92 &1,92
ที่
ป็
ป็
ว่
ำ
มึ
มี
มี
ที่
ที่
3.4. LINEAR COMBINATION AND LINEAR SPAN 33

Example 3.20. Consider 𝐿1 = (1, 1), 𝐿2 = (1, 0) and 𝐿3 = (0, 1). Then the vector 𝐿 =
(2, 2) can be obtained as a linear combination of 𝐿1 , 𝐿2 , 𝐿3 by either
𝐿 = 0𝐿1 + 2𝐿 2 + 2𝐿 3
or
𝐿 = 1𝐿1 + 1𝐿 2 + 1𝐿 3
or
𝐿 = 4𝐿1 → 2𝐿 2 → 2𝐿 3
et cetera.
In this example, if we delete one of the vectors 𝐿1 , 𝐿 2 or 𝐿 3 , then 𝐿 can still be
written as a linear combination of the remaining vectors, and, in a unique way.
Let us do this as the next exercise.
Exercise 3.21. From the previous example...
(a) Find span({𝐿1 , 𝐿2 , 𝐿3 }).
(b) Show that 𝐿 ↑ span({𝐿 1 , 𝐿2 , 𝐿3 }).
(c) Show that if one of the vectors 𝐿 1 , 𝐿2 , 𝐿3 is dropped, then the new linear span
equals the original one. Moreover, 𝐿 can be written as a linear combination
of the remaining vectors in a unique way.
(d) If we drop one more vector, then the generated span is a di!erent one.

In this previous exercise, we see several worthy remarks. Let us list the impor-
tant ones:
↓ R2 itself is a linear span.
↓ A subspace can be written as a linear span in several di!erent ways.
↓ Some of the generating vectors are superfluous, and hence can be dropped.
This means we may write the same linear span with less generating vectors.
↓ We cannot drop too many generating vectors while maintaining the same linear
span. The minimal vectors left are the most important ones. In fact, these are
basis vectors that we will later discuss.
 3.5. LINEAR INDEPENDENCE 34

3.5 Linear independence การ เ น สระเ ง

We still need one more notion, the linear independence, to get ourselves ready
for the discussion of basis vectors.
Definition 3.22 (Linear independence). Let 𝑀 be a vector space. The nonzero vec-
tors 𝐿 1 , . . . , 𝐿 𝑁 ↑ 𝑀 are said to be linearly independent if the only coe"cients 𝜑1 , . . . , 𝜑 𝑁
that makes * V1 , . . . . Via linerly indep <=> Ax & ค ตอบเก

𝜑1 𝐿1 + · · · + 𝜑 𝑁 𝐿 𝑁 = 0
X =
=

are given by 𝜑 1 = 𝜑2 = · · · = 𝜑 𝑁 = 0.
If 𝐿 1 , . . . , 𝐿 𝑁 are not linearly independent, we say that they are linearly dependent.
Exercise 3.23. Show that the vectors 𝐿 1 = (1, 0) and 𝐿2 = (0, 1) are linearly inde-
pendent.
Exercise 3.24. Show that the vectors 𝐿1 = (1, 1, 1), 𝐿 2 = (1, 1, 0) and 𝐿3 = (1, 0, 0)
are linearly independent.
Exercise 3.25. Show that the vectors 𝐿1 = (1, 1), 𝐿2 = (1, 0) and 𝐿3 = (0, 1) are
linearly dependent (i.e. not linearly independent).
Exercise 3.26. Show that if 𝐿1 , . . . , 𝐿 𝑁 are linearly dependent, then at least one of
these vectors can be written as a linear combination of the remaining ones with
some nonzero coe"cients.

3.6 Basis and dimension

The motivation to the notion of a basis of a vector space came from the idea
that a minimal choice of vectors can be selected and form the same vector space.
Notice that if the generative vectors of a vector space are linearly independent,
then we have no chance dropping any vectors. In the other words, these vectors
are already minimal.

3.6.1 Basis (ฐาน)

Definition 3.27 (Basis). Let 𝑀 be a vector space. The vectors 𝐿 1 , . . . , 𝐿 𝑁 ↑ 𝑀 are
called basis vectors of 𝑀 if the following two conditions are satisfied
ป็
ชิ
อิ
มี
ำ
 และ Ve = ( 9,17 linerly Inded.
Ex 3.13
Vi = 1 1,0) E B. 26

#VAN = ไ เป็น line rly

า in
=

V19 .... ,
V /17

&

A = = = = = 19 CREF แ ีV
วจะม ; ียนใน
เข ป Liner Combin &ti& a ของเเวกเตอ

NonRCA) = 2 # Vide
า Vic... , V a ไ เ
Pro สม น line rly i

:. Vy, Va เ น ส ระเ ง เ น

ข :วา
สมกา ค
Ax = 0 ละะม ตอ
มx=
EX 3.2 P
Vy = ( 1,117) V2 = ( 1,198) <11 &
3:
จะะม ี Xiอ าง
·

ร & อย หน ง ว

. . & Vet .... &jUp + . . . . . . KVA = &

&1V1 + CIV2+ & 33
A = views = &
&, V1 = - & iV1 - XeV....... - &i- -Vi- 1 -
Citivity ... - & kVk
agry + &2VLTGIVI = &

A: Vs V า = ? RE

/
V I

NonKGAD = 3

ง
V3,52,7 เ น liner.l y i n dep

3.25
v , = 1,1) V2 = (110) V3 = ( 01

A:
Criver = 1

RERIT In 9 REG
⑨
·
VAR
rank CA) = 2 =

:- V11V21V3 ไ เ น liner/
y ind
ด้
ที่
ติว่
ป็
ว่
จึ
ส้
ป็
ป็
ตั
นึ่
ม่
ม่
ำ
ล้
ย่
ชิ
รู
ป็
ม่
อิ
น้
3.6. BASIS AND DIMENSION 35

→ span({𝐿1 , . . . , 𝐿 𝑀 }) = 𝑁,
→ 𝐿1 , . . . , 𝐿 𝑀 are linearly independent.
The set {𝐿 1 , . . . , 𝐿 𝑀 } is called a basis of 𝑁.

The following facts are noteworthy.

Theorem 3.28. The following assertions hold true.
→ Every vector space has a basis.
→ All di!erent bases of a vector space have the same number of elements.
Exercise 3.29. Consider the vector space R𝑂 and vectors 𝑃1 , . . . , 𝑃 𝑂 ↑ R𝑂 given by
𝑃1 = (1, 0, 0, . . . , 0)
↑" = EAnner, . . . Fall !⨌⨌⨌⨌⨌"#⨌⨌⨌⨌⨌$
<11 . . . . , In E /R 𝑂 ↓ 1 times
𝑃2 = (0, 1, 0, . . . , 0 )
!⨌⨌"#⨌⨌$
𝑂 ↓ 2 times
..
.
𝑃 𝑂 = (0, 0, . . . , 0, 1).
!⨌⨌⨌⨌⨌"#⨌⨌⨌⨌⨌$
𝑂 ↓ 1 times

Show that these vectors 𝑃1 , . . . , 𝑃 𝑂 constitute a basis for R𝑂 .

This basis is known as the standard basis for R𝑂 .
Exercise 3.30. Find some other bases for R𝑂 .
Exercise 3.31. Find a basis for the vector space
𝑁 = {(𝑄1 , 𝑄2 , 𝑄3 ) ↑ R3 | 2𝑄1 ↓ 𝑄 3 = 0, 𝑄 1 + 3𝑄 2 = 0}.
Exercise 3.32. Find a basis for the vector space
𝑅 = {(𝑄1 + 𝑄 2 ↓ 𝑄 3 , 𝑄3 ↓ 𝑄 2 , 𝑄1 ) ↑ R3 | 𝑄1 , 𝑄2 , 𝑄3 ↑ R}.

The next exercise gives an important insight, saying that a vector space of
dimension 𝑂 does not contain a proper subspace of equal dimension.
Exercise 3.33. Let 𝑁 be a vector space with dimension dim(𝑁) = 𝑂. If 𝑅 ↔ 𝑁 is a
subspace of 𝑁 with dim(𝑅) = 𝑂, then 𝑅 = 𝑁.
 - 1 & ↑

Ea 3.50 ใ โดะ2 = (100 , ....,

My

fe: Enter = 21,119, . . . , 0)

Fi = &, +ext . . . . . Oj = ( 11 1

En = ext . . . . . In = ( 11 . .... 1

Claim ify, fa...., ด เ น basi s NO

spenlife, ... sta) = R

o

if
Fic ..., on finetly indep

trial
spomifa, .... fal = &fifact ... &1 . . . . . . &ERY
+

a)
an

=Santation
/ /Cr. ....
&2 t....
:
+&n
&nGR {
=1
ป็
ห้
ริ
 3.31 V= &21 2) EIRY/ 21 - =30, X1 +322 = 0
งเก ต า V เเ ค
น เซต ของ ตอของ ระบบส

2Xq-X3 = 0 - 3 หลายค ตอบ (ลองเช

1,42x3 = &-

9 X3 = 2X 1

& x2 = x 1 ⑤

::: ค ตอนขอ งระบ ผสมการร ้อ

x = = = = =<1 3 INTER

= 3, CEIR

. . V = <(1,512) /ER3 = Spam (( 1,53,27)

~
liner combination new =
=1,3,2
Claim: (1,127 เ น basis ของ
-

&
-(a) Spon ( 195312) =
-(P) ( 11512)เ น -linerlyy inde
Ve<โดย
เพราะะม เ

::: ส ุป า (1,5127 3 เป็น bas is

สั
ยู
ดี
ป็
นี
ป็
งิ
ำ
ล่
ว่
ำ
รุ
มี
ำ
 3.6. BASIS AND DIMENSION 36

3.6.2 Basis representation

&
Let 𝐿 be a vector space and consider a basis B = {𝑀 1 , . . . , 𝑀 𝑁 }. Then any
vector 𝑂 → 𝐿 could be written uniquely as a linear combination of basis elements
as

𝑂 = 𝜑1 𝑀1 + 𝜑2 𝑀2 + · · · + 𝜑 𝑁 𝑀 𝑁 .

However, to make such an expression consistent, we need to fix the order of

elements in B = {𝑀1 , 𝑀2 , . . . , 𝑀 𝑁 } as such. The shorthand notation for this is given
by
 𝜑1 
 
 𝜑2 
𝑂 =  ..  = (𝜑1 , . . . , 𝜑 𝑁 )B .
 . 
𝜑 𝑁 
 B

When 𝐿 = R𝑁 is equipped with the standard basis E = {𝑃1 , . . . , 𝑃 𝑁 }, we know

that the basis representation 𝑂 = (𝑂1 , . . . , 𝑂 𝑁 )E is just the same as the classical
expression 𝑂 = (𝑂1 , . . . , 𝑂 𝑁 ). Therefore, it is agreed to write 𝑂 = (𝑂1 , . . . , 𝑂 𝑁 )
without indicating the basis when the standard basis is used.

Exercise 3.34. Let us equip R2 with the basis B = {(1, 0), (1, 1)}. Then write down
the vectors 𝑂 = (3, 2) and 𝑄 = (↑2, 5) in the representation of the basis B.

Exercise 3.35. Suppose that R3 is equipped with the basis

B = {(1, 0, 0), (1, 1, 0), (1, 1, 1)}.

Write the vector 𝑂 = (3, 2, 1) in the representation of the basis B.

3.6.3 Dimension ( /ขนาด

Definition 3.36. Once again that we would like to emphasize that every basis of a
vector space 𝐿 contains the same number of basis vectors. This consistent number
is referred to as the dimension of 𝐿, or briefly as dim(𝐿).
↑

Example 3.37. Recall from the above exercises that dim(R𝑁 ) = 𝑁, dim(𝐿) = 1
and dim(𝑅) = 2.
มิ
มิ
ติ
3.7. CHANGE OF BASIS 37

3.7 Change of basis

In some circumstance, one may want to switch from one basis to another to
gain some advantages. In this section, we first see how to find a matrix that maps a
representation from one basis into another basis. This change-of-basis matrix will
serve as a fundamental tool for the further studies. Let us carry out a derivation
of this matrix.
Let 𝐿 be an 𝑀-dimensional vector space, B = {𝑁1 , · · · , 𝑁 𝑀 } and B→ = {𝑁1→ , · · · , 𝑁 𝑀→ }
be two bases of 𝐿.
Suppose that a vector 𝑂 ↑ 𝐿 is represented in the basis B as

𝑂 = 𝜑1 𝑁1 + 𝜑2 𝑁2 + · · · + 𝜑 𝑀 𝑁 𝑀 .

In other words, we have 𝑂 = (𝜑1 , · · · , 𝜑 𝑀 )B . To write this vector 𝑂 in a new basis

B→, 𝑂 = (𝜑→1 , · · · , 𝜑→𝑀 )B→ , we write the equation

𝑂 = 𝜑→1 𝑁 1→ + 𝜑 →2 𝑁2→ + · · · + 𝜑→𝑀 𝑁 𝑀→

and solve for the unknown coe!cients 𝜑→1 , · · · , 𝜑→𝑀 . Putting the two equations
above together and let

   
   
𝑃 = 𝑁 1 𝑁 2 · · · 𝑁 𝑀  𝑃→ = 𝑁1→ 𝑁 2→ · · · 𝑁 𝑀→ 
   
   
 𝜑1   𝜑→ 
   1
𝑄 =  ...  𝑅 =  ...  ,
𝜑 𝑀  𝜑→ 
   𝑀
we arrive at the casual linear system

𝑃→𝑅 = 𝑃𝑄. (3.1)

Since the vectors 𝑁1→ , · · · , 𝑁 𝑀→ form a basis, they are linearly independent and so
rank(𝑃→) = 𝑀 which means (𝑃→)↓1 exists. Finally, we may obtain the unknown
coe!cients from

𝑅 = (𝑃→)↓1 𝑃𝑄.
3.8. RANK-NULLITY THEOREM 38

We conclude the change-of-basis formula as

𝑂B→ = [B→ ↔ B]𝑂B ,

where

[B→ ↔ B] = (𝑃→)↓1 𝑃

is called the change-of-basis matrix from B into B→.

To change back from B→ to B, the equation (3.1) can be used again but this time
𝑅 is known and 𝑄 is unknown. Similar analysis yields 𝑄 = 𝑃↓1 𝑃→𝑅. We may notice
here that we may derive the change-of-basis matrix from B→ to B as

[B ↔ B→] = 𝑃↓1 𝑃→.

It is interesting to observe that

[B→ ↔ B] = (𝑃→)↓1 𝑃 = [𝑃↓1 𝑃→]↓1 = [B ↔ B→]↓1 .

Exercise 3.38. Let 𝐿 be a vector space and B, B→, B→→ are three bases of 𝐿. Show
that [B→→ ↔ B] = [B→→ ↔ B→][B→ ↔ B].

Exercise 3.39. Suppose that S is the standard basis of R𝑀 and B be any basis of R𝑀 .
Find the change-of-basis matrices between the two bases S and B.

Exercise 3.40. Consider R2 . Let B be the standard basis on R2 and B→ = {(1, 1), (↓1, 1)}
be another basis on R2 .
(a) Find the change-of-basis matrices [B→ ↔ B] and [B ↔ B→].

(b) Write the vector 𝑅 = (4, ↓1) in the basis B→.

(c) Write the vector 𝑄 = (0, 2)B→ in the standard basis.

3.8 Rank-nullity theorem

The rank-nullity theorem is one of the connerstone in linear algebra and it
provides useful information in several circumstances.
The rank of any matrix 𝑆 could actually be expressed alternatively by the
following result.
 3.9. THE GEOMETRY OF THE SOLUTION SET OF 𝑆 = 𝑁 39

Theorem 3.41 (The rank theorem). If 𝑆 is a matrix, then rank(𝑆) = dim(im(𝑆)).

~
↓
We may define the nullity of a matrix following this line. &AxIKEIRY3
Definition 3.42. If 𝑆 is a matrix, then its nullity of 𝑆, denoted by 𝑀𝑇𝑈𝑈(𝑆), is defined
by 𝑀𝑇𝑈𝑈(𝑆) = dim(ker(𝑆)).
* KerCAT = GREIRPIANO
Finally, we may link the relationship between the rank and nullity in the
following well-known theorem. ิท วแ
· Ax = 0 ว
Theorem 3.43 (Rank-nullity theorem). If 𝑆 has 𝑀 columns, then
ronKCAl
rank(𝑆) + 𝑀𝑇𝑈𝑈(𝑆) = 𝑀. => HUN CAT = -

Exercise 3.44. Re-assess exercises 3.31 and 3.32 in terms of dimensions using the
rank-nullity theorem.

Exercise 3.45. Consider the following linear system:

3𝑅 1 + 2𝑅 2 ↓ 3𝑅 4 = 0

{ 2𝑅 2 + 𝑅 4 = 0
2𝑅 2 ↓ 2𝑅 3 ↓ 𝑅 4 = 0

Use the rank-nullity theorem to conclude the dimension of the solution set of the
above system.

3.9 The geometry of the solution set of 𝑆 = 𝑁

We have investigated already that the solution set of 𝑆𝑅 = 𝑁 is a linear space if
and only if 𝑁 = 0. Moreover, the solution set of 𝑆𝑅 = 0 receives a special treatment
as ker(𝑆). However, one could observe that if 𝑆 𝑅¯ = 𝑁 has a solution 𝑅0 , then the
solution set of 𝑆𝑅 = 𝑁 is given by

𝑅0 + ker(𝑆) = {𝑅0 + 𝑄 | 𝑄 ↑ ker(𝑆)}.

The
from sin die
This means the solution set of 𝑆𝑅 = 𝑁 is a translation of ker(𝑆), so that they have
the same dimension and shape.

*
KevCAl
*
{xIAx=P
· ~
# sub S ไ เ D Spe
*

# น SU
ตั
ม่
ป็
 Ex 3.93

องการ านใ น di m a KerCA) Y FHU/C

hall Casa
-
rankacAl

A:
Los

RER- Re 28REA
Nank ( A = 3, MER

HUI) CAT = - UNARSCAT &- 3 = %

·: เซต ค าตอ ~ขอระผผสมการร กษณะ เ นต
ต้
มิ
ลั
ด้
ส้
 3.9. THE GEOMETRY OF THE SOLUTION SET OF 𝐿 = 𝑀 40

Exercise 3.46. Consider the following linear system:

3𝑁 1 + 2𝑁 2 → 3𝑁 4 = 2
2𝑁 2 + 𝑁 4 = →1 ** Ax = $
2𝑁 2 → 2𝑁 3 → 𝑁 4 = 0

Use the rank-nullity theorem to draw conclusion about the geometry of the solu-
tion set of the above system.
* เซตร าตอ บ ก ณะอ า งใช dimons

เซต
ต าตอ กขอ ระบ บสมการน เ ด การ เ ่อนขน านของ

จ าก อ -PS I dim Ker CAT - MUNICAL =

ึ
ง นะเ นเ
:. เซ ต ค ตอนขอ งระบ ผสมการ
ค จ กษ

dimension: 1
มี
ต้
ย่
ษั
ี้
กิ
ลื่
วิ
ด้
ำ
ลั
ลั
ข้
ป็
3.9. THE GEOMETRY OF THE SOLUTION SET OF 𝐿 = 𝑀 41

Practice problems
1. Show that the vectors in each of the following items are linearly dependent.

↑ 𝑂1 = (1, 2, 0), 𝑂2 = (0, 1, 1).

↑ 𝑂1 = (0, 1, 0), 𝑂2 = (0, 0, 1), 𝑂3 = (1, 1, 0).
↑ 𝑂1 = (1, 0, 0, 1), 𝑂 2 = (1, 0, 1, 0), 𝑂 3 = (1, 0, 0, 0), 𝑂 4 = (0, 2, 1, 0).

2. Show that the vectors in each of the following items are not linearly independent.

↑ 𝑂1 = (0, 1, 1), 𝑂2 = (→1, →1, →1), 𝑂3 = (1, 0, 0).

↑ 𝑂1 = (2, 2, 0, 0), 𝑂 2 = (0, 1, 0, 1), 𝑂 3 = (2, 1, 0, 3), 𝑂 4 = (→2, 1, 0, 2).

3. Find a basis for the following vector spaces and determine their dimensions.

↑ 𝑃 = {𝑁 ↓ R3 | 𝑁1 = →𝑁3 , 𝑁 2 = →𝑁1 }.
!" #$
1 0 1
↑ 𝑃 = 𝑄𝑅𝑆 .
0 1 1
↑ 𝑃 = {(𝑁 1 + 𝑁 3 , →2𝑁2 ) | 𝑁 1 , 𝑁2 , 𝑁3 ↓ R}.
↑ 𝑃 = {(3𝑁 1 , 𝑁1 + 𝑁 2 → 𝑁 3 , 𝑁3 ) | 𝑁 1 , 𝑁2 , 𝑁3 ↓ R}.
↑ 𝑃 = {𝑁 ↓ R3 | 2𝑁1 → 3𝑁 2 = 0, 𝑁 1 + 2𝑁 3 = 0}.

4. Find dim(ker(𝐿)) and dim(im(𝐿)) of the following instances of a matrix 𝐿.

(Hint: Make use of the rank-nullity theorem.)
" #
0 1 2
↑ 𝐿=
1 1 2
1 2 1
 
↑ 𝐿 = 2 3 1 .
2 0 0
 
" #
0 0 1 1
↑ 𝐿= .
1 1 0 0
0 2
 
↑ 𝐿 = 1 1 .
2 0
 
3.9. THE GEOMETRY OF THE SOLUTION SET OF 𝐿 = 𝑀 42

5. Determine the dimension of the solution set of the following linear system:

2𝑁 1 + 𝑁3 = 2
𝑁2 + 𝑁3 → 𝑁4 = 2
𝑁1 → 𝑁 4 = 0.

6. Suppose that 𝐿 is a matrix such that dim(ker(𝐿)) = 1 + dim(im(𝐿)). Show

that 𝐿 has odd number of rows. (Hint: Use the rank-nullity theorem.)
Chapter 4

Norms, dot products and orthogonality

In this chapter we concern with some geometry on vector spaces. Geometry

in this context refers to measurements, where we mainly consider length and angle.

4.1 Norms
A norm is a function defined on a vector space with certain properties. A norm
us usually interpreted as the size or length of an element in the underlying vector
space.

Definition 4.1 (Norm). Let 𝑃 be a real vector space. A norm is any function ↔ · ↔ :
𝑃 ↗ R such that the following properties hold true for any vectors 𝑁, 𝑇 ↓ 𝑃 and
scalar 𝜑 ↓ R:
(1) ↔ 𝑁↔ ↘ 0 and ↔ 𝑁↔ = 0 ≃⇐ 𝑁 = 0,

(2) ↔ 𝜑𝑁↔ = | 𝜑|↔ 𝑁↔,

(3) ↔ 𝑁 + 𝑇↔ ⇒ ↔ 𝑁↔ + ↔ 𝑇↔ .

There could be several norms on a single vector space. Depending on the

circumstance, a particular norm could be more appropriate than the other ones.
In this note, we only focus on the norms for vectors in R𝑈 and for matrices in R𝑉⇑𝑈 .

4.1.1 Norms on R𝑈
Let us take a look at some common choices of norms on the vector space R𝑈 .

43
4.1. NORMS 44

Definition 4.2 (𝑊-Norms). For 1 ⇒ 𝑊 < ⇓, the 𝑊-norm of a vector 𝑁 ↓ R𝑈 is defined

by
+
𝑊 𝑊 𝑊
↔ 𝑁↔ 𝑊 = | 𝑁| 1 + · · · + | 𝑁| 𝑈 .
For 𝑊 = ⇓, the ⇓-norm (or the max norm) of 𝑁 is defined by
↔ 𝑁↔ ⇓ = max{| 𝑁1 | , . . . , | 𝑁 𝑈 |}.

Among these 𝑊-norms, the case 𝑊 = 2 is the most important and ↔ 𝑁↔ 2 is also
known as the Euclidean norm on R𝑈 .
Remark. Since the Euclidean norm is the most common one used in the literature,
we shall write just ↔ 𝑁↔ instead of ↔ 𝑁↔ 2 for simplicity.
Exercise 4.3. Show in R2 and R3 that the value ↔ 𝑁↔ 2 of the Euclidean norm is exactly
the length of the vector 𝑁.
Exercise 4.4. Let 𝑋 = (3, 0, 1) and 𝑂 = (→2, 1, 2) be two vectors in R3 .
(a) Find the lengths of the two vectors 𝑋 and 𝑂.
(b) Find ↔ 𝑋↔ 1 and ↔ 𝑂↔ ⇓ .

4.1.2 Norms on R𝑉⇑𝑈

In the same way that R𝑈 could be equipped with di!erent norms, there are
various choices of norms to be used in the vector space R𝑉⇑𝑈 .
The first and simplest norm is the 𝑊-norms which resembles the 𝑊-norms in R𝑈 .
Definition 4.5 (𝑊-Norms for matrices). Let 1 ⇒ 𝑊 < ⇓. The 𝑊-norm of a matrix 𝐿 ↓
R𝑉⇑𝑈 is defined by
,
-
./𝑉 /
𝑈
↔ 𝐿↔ 𝑊 = 𝑊
| 𝑎 𝑌𝑍 | 𝑊 .
𝑌=1 𝑍=1

In case 𝑊 = ⇓, the ⇓-norm (also called the max-norm) of 𝐿 is defined by

↔ 𝐿↔ ⇓ = max | 𝑎 𝑌𝑍 |.
𝑌=1,...,𝑉
𝑍=1,...,𝑈

The 2-norm is also known as the Frobenius norm and sometimes written as ↔ 𝐿↔ 𝑏 .
4.2. DOT PRODUCTS AND ORTHOGONALITY 45

" #
1 2 →1 1
Exercise 4.6. Compute the Frobenius norm of a matrix 𝐿 = .
→2 →2 0 →1

Definition 4.7 (Unit vectors). A vector 𝑋 ↓ R𝑈 is said to be unit if ↔ 𝑋↔ = 1.

The following process of scaling a nonzero vector into a unit vector of the same
direction is called normalization.

Exercise 4.8 (Normalization). Show that for any nonzero vector 𝑋 ↓ R𝑈 , the vec-
tor 𝑋 ↑ = ↔ 𝑋↔
𝑋
is unit. Here, we say that the vector 𝑋 is normalized into 𝑋 ↑ .

4.2 Dot products and orthogonality

Dor products provide a higher level of understanding of the vector space at
hand. One shall see that it is also closely related to the norms. Moreover, the
dot product is the key element that allows one to define and study orthogonality.
Note that the orthogonality has been an important concept in modern applications
concerning data and information theory.

4.2.1 Dot product

Let us start formally with the definition of the (Euclidean) dot product.

Definition 4.9. The dot product between two vectors 𝑋, 𝑂 ↓ R𝑈 is defined by

/
𝑈
𝑋 · 𝑂 = 𝑋1 𝑂 1 + · · · + 𝑋𝑈 𝑂 𝑈 = 𝑋𝑌 𝑂 𝑌 = 𝑋 ⇔ 𝑂.
𝑌=1

The following theorem summarizes the useful properties when one computes
the dot products. We also highlight the connections between the dot product and
the Euclidean norm in the following theorem.

Theorem 4.10. The following holds for any vectors 𝑋, 𝑂, 𝑐 ↓ R𝑈 and scalars 𝜑 ↓ R:
↑ 𝑋 · 𝑂 = 𝑂 · 𝑋,

↑ (𝜑𝑋) · 𝑂 = 𝑋 · (𝜑𝑂) = 𝜑(𝑋 · 𝑂),

↑ 𝑋 · (𝑂 + 𝑐) = 𝑋 · 𝑂 + 𝑋 · 𝑐,
4.2. DOT PRODUCTS AND ORTHOGONALITY 46

↑ 𝑋 · 𝑋 = 0 ≃⇐ 𝑋 = 0,
𝑈 2
↑ 𝑋·𝑋 = 𝑌=1 𝑋𝑌 = ↔ 𝑋↔ 2 ↘ 0.

Let us practice some calculations.

Exercise 4.11. Let 𝑋 = (1, →1, 2, 4) and 𝑂 = (2, 4, →1, 𝑎), where 𝑎 is a constant. What
constant 𝑎 makes 𝑋 · 𝑂 = 0 ?

Another important relationship between the dot product and the Euclidean
norm is the following theorem, which provides an easy formula to compute the
angle between two nonzero vectors.

Theorem 4.12. Let 𝑋, 𝑂 ↓ R𝑈 be two nonzero vectors. Then

𝑋 · 𝑂 = ↔ 𝑋↔↔ 𝑂↔ cos 𝜒,

where 𝜒 is the angle between 𝑋 and 𝑂.

In particular, we may obtain the following formula for 𝜒:
! $
𝑋·𝑂
𝜒 = arccos .
↔ 𝑋↔↔ 𝑂↔

Exercise 4.13. Find the angle between the two vectors 𝑋 = (1, 1, 1) and 𝑂 = (0, 1, 0).

4.2.2 Orthogonality
In many situations, we are only interested to know whether the two vectors
are orthogonal (or perpendicular). In such a case, we simply observe whether the
dot product vanishes. More generally, the sign of the dot product provides some
rough information about the angle between two nonzero vectors.

Theorem 4.14. If 𝑋, 𝑂 ↓ R𝑈 are two nonzero vectors and 𝜒 the angle between them, then
↑ 𝑋 · 𝑂 = 0 if and only if 𝜒 = 0,

↑ 𝑋 · 𝑂 > 0 if and only if 𝜒 ↓ [0, 𝜓/2),

↑ 𝑋 · 𝑂 < 0 if and only if 𝜒 ↓ (→𝜓/2, 0].

4.3. ORTHOGONAL PROJECTION 47

Exercise 4.15. Let 𝑋 = (1, 1), 𝑂 = (2, →1), 𝑁 = (→2, 1) and 𝑇 = (3, 6). Find out all the
orthogonal pairs among these vectors.

Let us now speak of a set of pairwise orthogonal vectors.

Definition 4.16 (Orthogonal family). Let U = {𝑂 1 , . . . , 𝑂 𝑉 } be a subset of R𝑈 . We

say that U is an orthogonal family if

𝑂 𝑌 · 𝑂 𝑍 = 0, (𝑌 ω 𝑍)

for all 𝑌, 𝑍 = 1, . . . , 𝑉.

Example 4.17. Show that U = {(1, →2, 0), (4, 2, 1), (2, 1, →10)} is an orthogonal fam-
ily.

A more practical way to verify that U is an orthogonal family follows from the
following theorem.

Theorem 4.18. Let U = {𝑂1 , . . . , 𝑂 𝑉 } be a family of vectors in R𝑈 and let 𝑑 be a matrix

whose columns are vectors in U. Then U is an orthogonal family if and only if 𝑑 𝑒 𝑑 is a
diagonal matrix.

Proof. Suppose that 𝑑 𝑒 𝑑 = [𝑐 𝑌𝑍 ]𝑉⇑𝑉 . Then we have 𝑐 𝑌𝑍 = 𝑂 ⇔ 𝑂 = 𝑂 𝑌 · 𝑂 𝑍 . At

𝑌 𝑍
any 𝑌 ω 𝑍, we have 𝑐 𝑌𝑍 = 0 if and only if 𝑂 𝑌 and 𝑂 𝑍 are orthogonal.

It is important to point out that orthogonality implies independence.

Exercise 4.19. Suppose that U is an orthogonal family of nonzero vectors. Show

that its elements are linearly independent.

4.3 Orthogonal projection

If we look at two vectors, one may have a feeling that the first vector have a
hint of the information that the second one provides. For example, a vector (1, 1)
is going slightly right, which means it has a flavor of another vector (1, 0). In the
same way, it also has a flavor of (0, 1). On the other hand, the two vectors (1, 0)
and (0, 1) has no flavors of one another. This is because they are orthogonal. The
flavor we are observing right now is formally called the orthogonal projection.
4.3. ORTHOGONAL PROJECTION 48

4.3.1 Orthogonal projection onto a vector

We begin with the orthogonal projection of a vector onto another vector.

Definition 4.20. Let 𝑂 ↓ R𝑈 be a nonzero vector. The orthogonal projection of a

vector 𝑋 ↓ R𝑈 onto 𝑂 is defined by
𝑂
proj𝑂 (𝑋) = (𝑋 · 𝑂) .
↔ 𝑂↔ 2

Exercise 4.21. Let 𝑋 = (1, 0) and 𝑂 = (1, 1). Find proj𝑂 (𝑋).

Exercise 4.22. Let 𝑋 = (→1, 1, 0) and 𝑂 = (1, →1, 2). Verify that both proj𝑂 (𝑋)
and proj𝑋 (𝑂) are both the zero vector.

The following fact provides the instrumental idea for the development of the
Gram-Schmidt orthogonalization process in the next section.

Exercise 4.23. If 𝑋, 𝑂 ↓ R𝑈 are nonzero vectors, show that 𝑋 →proj𝑂 (𝑋) is orthogonal
to 𝑂.

4.3.2 Orthogonal projection onto a subspace

Sometimes we need to make a projection onto a subspace rather than just a
single vector (like in principal component analysis). This is achieved by taking
the sum of orthogonal projections onto each basis elements of the subspace in
question.

Theorem 4.24. If 𝑃 is a subspace of a vector space R𝑈 , then the orthogonal projection

of 𝑋 ↓ R𝑈 onto 𝑃 is obtained by the formula
/
𝑉
proj𝑃 (𝑋) = proj𝑂 𝑍 (𝑋),
𝑍=1

where V = {𝑂1 , . . . , 𝑂 𝑉 } is a basis of 𝑃.

Exercise 4.25. Let 𝑃 = span((1, 0, →1), (0, 1, 0)). Find the orthogonal projection of
the vector 𝑋 = (1, 1, 1) onto 𝑃.
4.4. GRAM-SCHMIDT ORTHOGONALIZATION PROCESS 49

4.4 Gram-Schmidt orthogonalization process

Motivated by the observation made in the previous section, we present now a
process called Gram-Schmidt orthogonalization process which creates an orthogonal
basis out of any basis by removing the flavor of all the previous basis elements.
Recall first that a basis for a vector space is said to be an orthogonal basis if it is
also an orthogonal family.

Theorem 4.26 (Gram-Schmidt orthogonalization process). Let 𝑃 be a vector space

with dot product and let U = {𝑂1 , · · · , 𝑂 𝑈 } be a basis of 𝑃. We define

𝑂 1↖ = 𝑂1
𝑂 2↖ = 𝑂2 → proj𝑂 ↖ (𝑂 2 )
1

𝑂 3↖ = 𝑂3 → proj𝑂 ↖ (𝑂 3 ) → proj𝑂 ↖ (𝑂 3 )
2 1
..
.
𝑂 ↖𝑌 = 𝑂 𝑌 → proj𝑂 ↖ (𝑂 𝑌 ) → · · · → proj𝑂 ↖ (𝑂 𝑌 )
𝑌→1 1
..
.
𝑂 𝑈↖ = 𝑂 𝑈 → proj𝑂 ↖ (𝑂 𝑈 ) → · · · → proj𝑂 ↖ (𝑂 𝑈 ).
𝑈→1 1

Then the family U↖ = {𝑂1↖ , · · · , 𝑂 𝑈↖ } is an orthogonal basis for 𝑃.

Remark. The Gram-Schmidt orthogonalization process is order-sensitive. If we

re-index the basis elements, then the resulting orthogonal basis could be a di!erent
one.

Exercise 4.27. Consider R2 with the basis U = {(1, →3), (→1, 0)}. Use the Gram-
Schmidt process to create an orthogonal basis from U.

Exercise 4.28. Consider R3 with the basis B = {(1, 0, 0), (1, 0, 1), (0, →2, 0)}. Or-
thogonalize B using the Gram-Schmidt process.
4.4. GRAM-SCHMIDT ORTHOGONALIZATION PROCESS 50

Practice problems
1. Find the lengthiest and shortest vectors among the following:

↑ 𝑂1 = (3, 2, →1),
↑ 𝑂2 = (1, →3, 4),
↑ 𝑂3 = (→2, 3, 1),
↑ 𝑂4 = (1, 0, 4).

2. Let 𝑋 = (1, →2, 0) and 𝑂 = (0, 1, 1). Find the angle between the two vectors 𝑋
and 𝑂.

3. Consider the following bases of R3 :

↑ B1 = {(1, 0, 0), (0, 0, 1), (0, →1, 1)}

↑ B2 = {(0, →1, 1), (1, 1, 0), (0, →1, 0)}
↑ B3 = {(1, 0, 1), (0, 1, 2), (1, 1, 0)}

Which of these are orthogonal ?

4. Use the Gram-Schmidt process to orthogonalize the non-orthogonal bases from

the previous question.
Chapter 5

Linear transformations

There is a special class of functions that maps between two vector spaces, called
linear transformation. We will discover later that this class is special because it can
be fully described with matrices in the Euclidean setting. This characterization
also brings about a new interpretation to the equation 𝐿𝑁 = 𝑀.
Definition 5.1. Let 𝑃 and 𝑓 be two vector spaces over the field 𝑔 ↓ { R, C}. A
function 𝑒 : 𝑃 ↗ 𝑓 is said to be a linear transformation if the condition
𝑒(𝜑𝑁 + 𝜔𝑇) = 𝜑𝑒(𝑁) + 𝜔𝑒(𝑇)
holds true for all 𝑁, 𝑇 ↓ 𝑃 and 𝜑, 𝜔 ↓ 𝑔.

In this definition, it should be remarked that the additions and multiplications

appeared on both sides of the equation, i.e. 𝜑𝑁+𝜔𝑇 and 𝜑𝑒(𝑁)+𝜔𝑒(𝑇), are additions
and multiplications on di!erent spaces 𝑃 and 𝑓, respectively.
Exercise 5.2. Show that the following functions are linear transformations.
(a) 𝑒 : R2 ↗ R defined by 𝑒(𝑁) = 𝑒(𝑁1 , 𝑁2 ) = 2𝑁1 → 𝑁 2 .
(b) 𝑒 : R ↗ R2 defined by 𝑒(𝑁) = (2𝑁, 𝑁).
(c) 𝑒 : R3 ↗ R2 defined by 𝑒(𝑁) = 𝑒(𝑁1 , 𝑁2 , 𝑁3 ) = (2𝑁1 → 𝑁 2 , 𝑁2 → 2𝑁 3 ).
(d) 𝑒 : R2 ↗ R2 defined by 𝑒(𝑁) = (𝑁2 , 𝑁1 ).
Exercise 5.3 (Matrices as linear transformations.). Let 𝐿 be an 𝑉 ⇑ 𝑈 matrix. Show
that the function 𝑒 : R𝑈 ↗ R𝑉 given by
𝑒(𝑁) = 𝐿𝑁

51
5.1. MATRIX REPRESENTATION 52

is a linear transformation. With this fact, we can now view the matrix 𝐿 as a
function that transforms 𝑁 ↓ R𝑈 into 𝐿𝑁 ↓ R𝑉 .

Exercise 5.4. Let 𝑃 and 𝑓 be two vector spaces and 𝑒 : 𝑃 ↗ 𝑓 be a linear

transformation. Show that 𝑒(0) = 0. Again, one should be cautious that 0 on
the LHS and RHS of the equation belongs to di!erent vector spaces 𝑃 and 𝑓,
respectively.

We may use the converse of the above fact to disprove linearity of a function:
If 𝑒(0) ω 0, then 𝑒 is not a linear transformation.

Exercise 5.5. Show that the following functions are not linear transformations.
(a) 𝑒 : R ↗ R defined by 𝑒(𝑁) = 3𝑁 + 1.

(b) 𝑒 : R ↗ R2 defined by 𝑒(𝑁) = (𝑁, 𝑁 2 ).

(c) 𝑒 : R2 ↗ R2 defined by 𝑒(𝑁) = (𝑁1 + 𝑁 2 , 𝑁1 𝑁2 ).

(d) 𝑒 : R2 ↗ R defined by 𝑒(𝑁) = sin(𝑁1 ) + cos(𝑁 2 ).

Exercise 5.6. Determine whether or not the following functions are linear trans-
formations.
(a) 𝑒(𝑁1 , 𝑁2 ) = sin2 (𝑁 1 ) + cos2 (𝑁2 ).

(b) 𝑒(𝑁) = sin2 (𝑁) + cos2 (𝑁).

(c) 𝑒(𝑁1 , 𝑁2 ) = sin2 (𝑁 1 ) + cos2 (𝑁 1 ) → (1 + 𝑁2 ).

5.1 Matrix representation

We have already seen that an 𝑉 ⇑ 𝑈 matrix defines a linear transformation
from R𝑈 into R𝑉 . In this section, we show that the converse is also true. That is,
any linear transformation from R𝑈 into R𝑉 defines an 𝑉 ⇑ 𝑈 matrix. This matrix
representation plays a very important role in the analysis of a linear transformation
itself.
5.1. MATRIX REPRESENTATION 53

5.1.1 The formula for the matrix representation

We have seen that every matrix can be seen as a linear transformation. Now,
we show that every linear transformation can also be seen as a matrix. Suppose
that 𝑒 : R𝑈 ↗ R𝑉 is a linear transformation. Then there is an 𝑉 ⇑ 𝑈 matrix 𝐿𝑒 in
which

𝑒(𝑁) = 𝐿𝑒 𝑁 (↙𝑁 ↓ R𝑈 ).

This matrix 𝐿𝑒 is called the matrix representation of 𝑒 (or shortly the matrix of 𝑒)
and can be formulated by
 
 
𝐿𝑒 = 𝑒(𝑅1 ) 𝑒(𝑅2 ) . . . 𝑒(𝑅 𝑈 )

 
 
where 𝑅1 , . . . , 𝑁 𝑈 are vectors in the standard basis of R𝑈 .
Exercise 5.7. Find the matrix representations of all the linear transformations from
Exercise 5.2.

5.1.2 Kernel and range

Definition 5.8. Given a linear transformation 𝑒 : 𝑃 ↗ 𝑓. The kernel (or null space)
of 𝑒 is given by

ker(𝑒) = {𝑁 ↓ 𝑃 | 𝑒(𝑁) = 0}.

Likewise, the range of 𝑒 is

ran(𝑒) = {𝑇 ↓ 𝑓 | ∝𝑁 ↓ 𝑃 : 𝑇 = 𝑒(𝑁)} = {𝑒(𝑁) | 𝑁 ↓ 𝑃}.

It can be noticed that ker(𝑒) = ker(𝐿𝑒 ) and ran(𝑒) = im(𝐿𝑒 ), hence they both
are linear subspaces. Moreover, we may
↑ compute the kernel ker(𝑒) by solving the linear system 𝐿𝑒 𝑁 = 0,

↑ compute the range ran(𝑒) as the linear span of the columns of 𝐿𝑒 .

This relationship allows the application of the rank-nullity theorem in the context
of linear transformations.
5.2. VECTOR SPACE OF ALL LINEAR TRANSFORMATIONS 54

Exercise 5.9. Consider the linear transformation 𝑒 : R3 ↗ R2 defined by

𝑒(𝑁1 , 𝑁2 , 𝑁3 ) = (2𝑁1 → 𝑁 2 , 𝑁1 + 𝑁 2 ).

Find ker(𝑒) and ran(𝑒).

5.2 Vector space of all linear transformations

Following the following result, we deduce that the set of all linear trasforma-
tions between two vector spaces is actually a vector space.

Theorem 5.10. Let 𝑃 and 𝑓 be two vector spaces over the field 𝑔 ↓ { R, C}. We define

L (𝑃 , 𝑓) = {All linear transformations 𝑒 : 𝑃 ↗ 𝑓}.

For any 𝑕, 𝑒 ↓ L and scalar 𝜑 ↓ 𝑔, we define addition 𝑕 +𝑒 and scalar multiplication 𝜑𝑒

by

(𝑕 + 𝑒)(𝑁) = 𝑕(𝑁) + 𝑒(𝑁) and (𝜑𝑒)(𝑁) = 𝜑𝑒(𝑁).

Then L (𝑃 , 𝑓) is a vector space over the field 𝑔 under the above albegra.

If 𝑃 = R𝑈 and 𝑓 = R𝑉 , then each linear transformation 𝑒 : 𝑃 ↗ 𝑓 is

equivalent to a matrix 𝐿𝑒 . Hence the vector space L (𝑃 , 𝑓) is then reduced to

R𝑉⇑𝑈 = {All matrices of dimension 𝑉 ⇑ 𝑈}.

Hence we write L (𝑃 , 𝑓) ′ R𝑉⇑𝑈 to denote this equivalence.

Exercise 5.11. Consider the space R𝑉⇑𝑈 . For 𝑌 = 1, . . . , 𝑉 and 𝑍 = 1, . . . , 𝑈, de-

fine 𝑖 𝑌𝑍 to be the matrix whose element at the position (𝑌, 𝑍) is 1 and all 0 elsewhere.
Show that these matrices form a basis for R𝑉⇑𝑈 .

5.3 Composite linear transformation

Now, let us consider compositions of linear transformations.
5.4. LINEAR TRANSFORMATION IN COMPUTER GRAPHICS 55

Exercise 5.12. Suppose that 𝑑 , 𝑃 , 𝑓 are three vector spaces and let 𝑒 : 𝑑 ↗ 𝑃
and 𝑕 : 𝑃 ↗ 𝑓 be two linear transformation. Show that the composition 𝑕 ↑ 𝑒 :
𝑑 ↗ 𝑓, defined by

𝑕 ↑ 𝑒(𝑁) = 𝑕(𝑒(𝑁)),

is also a linear transformation.

Exercise 5.13. Following the previous exercise:
(a) Show that ker(𝑒) ∞ ker(𝑕 ↑ 𝑒).

(b) Give an example where we have ker(𝑒) ω ker(𝑕 ↑ 𝑒).

(c) Give an example where we have ker(𝑒) = ker(𝑕 ↑ 𝑒).

Exercise 5.14. Follwing the above:
(a) Show that ran(𝑕 ↑ 𝑒) ∞ ran(𝑕).

(b) Give an example where we have ran(𝑕 ↑ 𝑒) ω ran(𝑕).

(c) Give an example where we have ran(𝑕 ↑ 𝑒) = ran(𝑕).

5.4 Linear transformation in computer graphics

Many of the transformation in computer graphics are actually linear transfor-
mation. The most important and fundamental ones are the flips and rotations.

5.4.1 2D Flippings
Flipping refers to the situation where a point is mirrored across a given linear
plane. The most basic ones are the flippings across the 𝑁- and 𝑇-axis, respectively.

Flipping across 𝑁-axis

When a point (𝑁, 𝑇) ↓ R2 is flipped across the 𝑁-axis, it is moved to (𝑁, →𝑇).
Hence we define the flipping across the 𝑁-axis (the plane 𝑇 = 0) by a func-
tion F(𝑇=0) : R2 ↗ R2 , with

F𝑁 (𝑁, 𝑇) = (𝑁, →𝑇).

5.4. LINEAR TRANSFORMATION IN COMPUTER GRAPHICS 56

This is clearly a linear transformation. The matrix representation of F(𝑇=0) will be

denoted by 𝑏(𝑇=0) and is given by
" #
1 0
𝑏(𝑇=0) = .
0 →1

Flipping across 𝑇-axis

Similarly, a point (𝑁, 𝑇) ↓ R2 is flipped across the 𝑇-axis (the plane 𝑁 = 0) means
it is moved to (→𝑁, 𝑇). Then we define this flip by a linear transformation F(𝑁=0) :
R2 ↗ R2 with

F(𝑁=0) (𝑁, 𝑇) = (→𝑁, 𝑇).

Its matrix representation is then derived as

" #
→1 0
𝑏(𝑁=0) = .
0 1

Flipping across any plane 𝑎𝑁 + 𝑀𝑇 = 0

One could also construct a linear transformation of flipping a point across an
arbitrary plane given by an equation 𝑎𝑁 + 𝑀𝑇 = 0. The process involves the use of
plane geometry, and the resulting flipping matrix is
" #
1 𝑀 2 → 𝑎 2 →2𝑎𝑀
𝑏(𝑎𝑁+𝑀 𝑇=0) = 2 .
𝑎 + 𝑀2 →2𝑎𝑀 𝑎 2 → 𝑀 2

The following figure illustrates the flipping of points in R2 across the plane 𝑁 + 𝑇 =
0.
5.4. LINEAR TRANSFORMATION IN COMPUTER GRAPHICS 57

Figure 5.1: Green points flipped across the plane 𝑁 + 𝑇 = 0 into red points.

5.4.2 2D rotations
Here, we consider an operator that rotates a point (𝑁, 𝑇) ↓ R2 about the origin
by a certain angle 𝜒 in the counter-clowise direction. Let us write R𝜒 : R2 ↗ R2 to
denote the 2D rotation. To derive the formula of R𝜒 , we write (𝑁, 𝑇) in the polar
coordinate so that

𝑁 = 𝑆 cos(𝜒0 ) and 𝑇 = 𝑆 sin(𝜒0 )

for some 𝑆 ↘ 0 and 𝜒0 ↓ [0, 2𝜓). Then we have

R𝜒 (𝑁, 𝑇) = (𝑆 cos(𝜒0 + 𝜒), 𝑆 sin(𝜒0 + 𝜒)).

Next, we derive that

𝑆 cos(𝜒0 + 𝜒) = 𝑆[cos(𝜒0 ) cos(𝜒) → sin(𝜒0 ) sin(𝜒)]

= [𝑆 cos(𝜒0 )] cos(𝜒) → [𝑆 sin(𝜒0 )] sin(𝜒)
= 𝑁 cos(𝜒) → 𝑇 sin(𝜒)

and also

𝑆 sin(𝜒0 + 𝜒) = 𝑆[sin(𝜒0 ) cos(𝜒) + cos(𝜒0 ) sin(𝜒)]

= [𝑆 sin(𝜒0 )] cos(𝜒) + [𝑆 cos(𝜒0 )] sin(𝜒)
= 𝑁 sin(𝜒) + 𝑇 cos(𝜒).
5.4. LINEAR TRANSFORMATION IN COMPUTER GRAPHICS 58

Hence we have

R𝜒 (𝑁, 𝑇) = (𝑁 cos(𝜒) → 𝑇 sin(𝜒), 𝑁 sin(𝜒) + 𝑇 cos(𝜒))

" #" #
cos(𝜒) → sin(𝜒) 𝑁
= .
sin(𝜒) cos(𝜒) 𝑇

This shows that R𝜒 is a linear transformation and its matrix representation is given
by
" #
cos(𝜒) → sin(𝜒)
𝑗𝜒 = .
sin(𝜒) cos(𝜒)
5.4. LINEAR TRANSFORMATION IN COMPUTER GRAPHICS 59

Practice problems
1. Determine whether the following functions are linear transformations.

↑ 𝑒(𝑁1 , 𝑁2 ) = (2𝑁1 , 3𝑁1 → 𝑁 2 ).

↑ 𝑒(𝑁1 , 𝑁2 , 𝑁3 ) = (0, 1, 𝑁1 + 𝑁 2 + 𝑁 3 ).
↑ 𝑒(𝑁1 , 𝑁2 ) = (𝑁1 → 𝑁 22 + 𝑁 1 𝑁 2 , 2 + 𝑁 2 ).
 3𝜓 
↑ 𝑒(𝑁1 , 𝑁2 , 𝑁3 ) = cos (𝑁 1 + 𝑁 2 + 𝑁 3 ).
" #
2
  𝑁2
↑ 𝑒(𝑁1 , 𝑁2 ) = 2 3 .
𝑁1

2. Suppose that 𝐿 is an 𝑉 ⇑ 𝑈 matrix and 𝑒 : R𝑈 ↗ R𝑉 is defined by

𝑒(𝑁) = 𝐿𝑁.

Show that the matrix representation of 𝑒 is 𝐿𝑒 = 𝐿.

3. Find a matrix representation of the following linear transformations.

↑ 𝑒(𝑁1 , 𝑁2 ) = (𝑁1 , 𝑁2 , 𝑁1 , 𝑁2 ).
↑ 𝑒(𝑁1 , 𝑁2 , 𝑁3 ) = 𝑁1 + 𝑁 2 + 𝑁 3 .
↑ 𝑒(𝑁1 , 𝑁3 , 𝑁3 , 𝑁4 ) = (𝑁1 + 𝑁 3 , →𝑁2 → 3𝑁 4 ).

4. Find dim(𝑄𝑅𝑆 𝑒) and dim(𝑆𝑎𝑈 𝑒) of 𝑒 from Exercise 3 by using the rank-nullity

theorem.

5. Find 𝑄𝑅𝑆 𝑒 and 𝑆𝑎𝑈 𝑒 of 𝑒 from Exercise 3.

Chapter 6

Determinant and invertibility

The determinant is a scalar value assigned to a square matrix. Many properties

of a matrix is encoded withing its determinant. The most important one would be
the invertibility of a matrix (or of the corresponding linear transformation). The
determinant can also be used to explain how a transformation actually transforms
the space. The determinant of a matrix 𝐿 is denoted by 𝑘𝑅𝑙(𝐿) or |𝐿|.

6.1 Sarrus rules

The determinant can be defined for any 𝑈 ⇑ 𝑈 matrices, but let us first focus on
the 2 ⇑ 2 and 3 ⇑ 3 cases as they can be easily computed using the Sarrus rule.

6.1.1 2 ⇑ 2 matrices
Let 𝐿 be a 2 ⇑ 2 matrix. Then its determinant can be computed by

𝑘𝑅𝑙(𝐿) = 𝑎11 𝑎22 → 𝑎 12 𝑎21 .

This formula is known as the 2 ⇑ 2 Sarrus rule.

" # " # " #
1 3 1 3 3 6
Exercise 6.1. Find the determinant of 𝐿 = ,𝑚 = and 𝑛 = .
→2 1 1 1 1 2
Note that det(𝐿) can be positive, negative and 0, and this is independent of the
sign of elements in a matrix.

60
6.2. GENERAL DEFINITION 61

6.1.2 3 ⇑ 3 matrices
Let 𝐿 be a 3 ⇑ 3 matrix. Then its determinant can be computed by

𝑘𝑅𝑙(𝐿) = (𝑎11 𝑎22 𝑎33 + 𝑎 12 𝑎23 𝑎31 + 𝑎 13 𝑎21 𝑎32 )

→ (𝑎 31 𝑎22 𝑎13 → 𝑎 32 𝑎23 𝑎11 → 𝑎 33 𝑎21 𝑎12 ).

This formula is known as the 3 ⇑ 3 Sarrus rule. The following mnemonic device
is useful for this rule:
→ → →
𝑎11 𝑎12 𝑎13 𝑎11 𝑎12

𝑎21 𝑎22 𝑎23 𝑎21 𝑎22

𝑎31 𝑎32 𝑎33 𝑎31 𝑎32

+ + +
Figure 6.1: The mnemonic diagram for 3 ⇑ 3 Sarrus rule.

Exercise 6.2. Find 𝑘𝑅𝑙(𝐿) where 𝐿 is given by

1 1 1
 
𝐿 = 2 2 3 .
0 1 0
 

6.2 General definition

The situation is quite di!erent when it comes to determinant of matrices or
larger than 3 ⇑ 3. There is no mnemonic device for this and it requires the
immediate notions of minor and cofactor matrices.
Definition 6.3 (Minor matrix). Let 𝐿 be an 𝑈 ⇑ 𝑈 matrix. We write 𝐿→𝑌𝑍 to denote
the (𝑈 → 1) ⇑ (𝑈 → 1) matrix obtained by removing Row#𝑌 and Col#𝑍 from 𝐿. The
minor matrix of 𝐿, denoted by 𝑜(𝐿), is an 𝑈 ⇑ 𝑈 matrix

𝑜(𝐿) = [𝑜 𝑌𝑍 ]𝑈⇑𝑈

whose element 𝑜 𝑌𝑍 is computed by

𝑜 𝑌𝑍 = 𝑘𝑅𝑙(𝐿→𝑌𝑍 ).
6.2. GENERAL DEFINITION 62

Definition 6.4 (Cofactor matrix). The cofactor matrix of 𝐿, denoted by 𝑛(𝐿), is an

𝑈 ⇑ 𝑈 matrix

𝑛(𝐿) = [𝑛 𝑌𝑍 ]𝑈⇑𝑈

whose element 𝑛 𝑌𝑍 is computed by

𝑛 𝑌𝑍 = (→1)𝑌+𝑍 𝑜 𝑌𝑍 = (→1)𝑌+𝑍 𝑘𝑅𝑙(𝐿→𝑌𝑍 ).

We are now ready for the formal definition of the determinant of any 𝑈 ⇑ 𝑈
matrix.
Definition 6.5 (Determinant). The determinant of 𝐿 can be computed by fixing any
row 𝑌 and calculate
/
𝑈
𝑘𝑅𝑙(𝐿) = 𝑎 𝑌𝑍 𝑛 𝑌𝑍 = 𝑎 𝑌1 𝑛 𝑌1 + 𝑎 𝑌2 𝑛 𝑌2 + · · · + 𝑎 𝑌𝑈 𝑛 𝑌𝑈 ,
𝑍=1

or equivalently by fixing any column 𝑍 and calculate

/
𝑈
𝑘𝑅𝑙(𝐿) = 𝑎 𝑌𝑍 𝑛 𝑌𝑍 = 𝑎1𝑍 𝑛1𝑍 + 𝑎 2𝑍 𝑛2𝑍 + · · · + 𝑎 𝑈 𝑍 𝑛 𝑈 𝑍 .
𝑌=1

One should notice now the inductive nature of minors and cofactors of 𝐿. For
instance, to compute the minor (and the cofactor) of a 4 ⇑ 4 matrix, we need to
compute determinants of 3 ⇑ 3 matrices. Similarly, computing the minor (and the
cofactor) of a 5 ⇑ 5 matrix requires the determinants of 4 ⇑ 4 matrices, etc.
Let us warm up with a 3 ⇑ 3 matrix wihtout using the Sarrus rule.
Exercise 6.6. Let
 2 →1 0
 
→1 0 3 .
 
 0 2 3
 
Find 𝑘𝑅𝑙(𝐿) using di!erent rows/columns.

Let us move on to larger matrices.

Exercise 6.7. Find the determinant of the following matrices.
6.2. GENERAL DEFINITION 63

2 0 3 →2
1 0 0 4   0
 1 0 →3 1 
0 1 0 →3  1
(a) 𝐿 =  (b) 𝑚 =  3 0 3 1 
→1 →2 3 
0
3 →1 0 0 2 
1 1 2 0   →1
 1 0 2 0 4 

Let us now state some useful properties of the determinant.

Theorem 6.8. Suppose that 𝐿 and 𝑚 are square 𝑈 ⇑ 𝑈 matrices, then..

↑ If 𝐿 contains a zero row or a zero column, then 𝑘𝑅𝑙(𝐿) = 0.

↑ If 𝐿 contains two identical rows or columns, then 𝑘𝑅𝑙(𝐿) = 0.

↑ If 𝐿 is a triangular matrix, then 𝑘𝑅𝑙(𝐿) = 𝑎 11 𝑎22 . . . 𝑎 𝑈𝑈 .

↑ 𝑘𝑅𝑙(𝐿𝑚) = 𝑘𝑅𝑙(𝐿)𝑘𝑅𝑙(𝑚)

↑ 𝑘𝑅𝑙(𝐿𝑒 ) = 𝑘𝑅𝑙(𝐿)

↑ 𝑘𝑅𝑙(𝑝𝐿) = 𝑝 𝑈 𝑘𝑅𝑙(𝐿) for any scalar 𝑝 ↓ R.

From the last property, it implies that 𝑘𝑅𝑙(→𝐿) = (→1)𝑈 𝑘𝑅𝑙(𝐿) so that we have
𝑘𝑅𝑙(→𝐿) = →𝑘𝑅𝑙(𝐿) when 𝑈 is odd and 𝑘𝑅𝑙(→𝐿) = 𝑘𝑅𝑙(𝐿) when 𝑈 is even.
Also note that the determinant is not distributed under summation, that
is, 𝑘𝑅𝑙(𝐿 + 𝑚) and 𝑘𝑅𝑙(𝐿) + 𝑘𝑅𝑙(𝑚) are independent.
1 3 1   →3 0
 0  0 0
0 3 →4   2 0
Exercise 6.9. Let 𝐿 =  
11 28 0
11 385 →98 0
and 𝑚 = . Find 𝑘𝑅𝑙(2𝐿𝑚).
0 0  42 11
0 0 0 →1   13 0 →56 2
 
Exercise 6.10. Find two matrices 𝐿 and 𝑚 such that 𝑘𝑅𝑙(𝐿 + 𝑚) ω 𝑘𝑅𝑙(𝐿) + 𝑘𝑅𝑙(𝑚).

Exercise 6.11. Find two matrices 𝐿 and 𝑚 such that 𝑘𝑅𝑙(𝐿 + 𝑚) = 𝑘𝑅𝑙(𝐿) + 𝑘𝑅𝑙(𝑚).
6.3. BLOCK TRIANGULAR MATRICES 64

6.3 Block triangular matrices

We may extend the technique known for triangular matrices to a more general
cae of block triangular matrices.
Any matrix 𝐿 can be subdivided into 𝑊 ⇑ 𝑞 blocks in such a way that
 𝐿11 𝐿12 . . . 𝐿1𝑞 

 𝐿21 𝐿22 . . . 𝐿2𝑞 
𝐿 =  .. .. . . . ...  ,
 . . 
𝐿 𝑊1 𝐿 𝑊2 . . . 𝐿 𝑊𝑞 

with appropriate dimensions for each submatrices 𝐿 𝑄𝑟 ’s.
We say that 𝐿 is in an upper block triangular form if 𝐿 can be subdivided into
𝑊 ⇑ 𝑊 blocks with each block 𝐿 𝑄𝑟 being a square matrix and
𝐿11 ∈ 

 0 𝐿22 
𝐿 =  .. . ,

 . 
. .
 0 . . . 0 𝐿 𝑊𝑊 
 
where ∈ means any values are acceptable. Likewise, we can define a lower block
triangular matrix in the same way. We simply say that 𝐿 is a block trinangular matrix
if it is either upper or lower block traingular.
The following theorem simplifies the calculation the determinant of a block
triangular.
Theorem 6.12. If 𝐿 is a block triangular matrix with all diagonals 𝐿11 , . . . , 𝐿 𝑊𝑊 being
square matrices, then 𝑘𝑅𝑙(𝐿) = 𝑘𝑅𝑙(𝐿11 )𝑘𝑅𝑙(𝐿22 ) . . . 𝑘𝑅𝑙(𝐿𝑈𝑈 ).
 4 7 8 
 2 3
 3 2 1 
 →1 5
Exercise 6.13. Find 𝑘𝑅𝑙(𝐿) where 𝐿 =  0 0 2 1 5  .
 0 0 3 →1 4 

 0 0 5 2 6 


6.4 Determinant, rank and invertibility.

It is interesting to see how the determinant is related more to the equation
𝐿𝑁 = 𝑀 or even to the matrix 𝐿 itself.
6.4. DETERMINANT, RANK AND INVERTIBILITY. 65

Definition 6.14 (Invertibility). Given a square 𝑈 ⇑ 𝑈 matrix 𝐿. We say that

↑ 𝐿 has a full rank if rank(𝐿) = 𝑈;

↑ 𝐿 is invertible if there exists an 𝑈 ⇑ 𝑈 matrix, denoted with 𝐿→1 , satisfying

𝐿𝐿→1 = 𝐿→1 𝐿 = 𝑠. In this case, 𝐿→1 is called the inverse matrix of 𝐿.

One may suspect an existence of a matrix 𝑚 in which 𝐿𝑚 = 𝑠 but 𝑚𝐿 ω 𝑠 (or

vice verse). It turns out for a square matrix that such exceptional situation would
not happen.
The following result shows a useful equivalence between concepts we have
seen.

Theorem 6.15. The following conditions are equivalent:

↑ 𝐿 has a full rank.

↑ 𝐿 is invertible.

↑ 𝑘𝑅𝑙(𝐿) ω 0.
In the case where 𝐿 is invertible (which is actually where 𝑘𝑅𝑙(𝐿) ω 0), the inverse matrix
of 𝐿 can be calculated by
1
𝐿→1 = 𝑎𝑘𝑍(𝐿),
𝑘𝑅𝑙(𝐿)
where 𝑎𝑘𝑍(𝐿) = 𝑛(𝐿)𝑒 is called the adjoint of 𝐿.

Exercise 6.16. Let 𝐿 be a 2 ⇑ 2 invertible matrix. Find a general formula for 𝐿→1 .

Exercise 6.17. Find the inverse of the following matrices.

" # 1 0 1 2 0 0 
   
(b) 𝑚 = 0 0 1 (c) 𝑛 = 1 0 →2
1 2
(a) 𝐿 =
1 3 1 0 0 0 1 0 
   
We have the following properties concerning inverse matrices.

Theorem 6.18. Let 𝐿 and 𝑚 be two 𝑈 ⇑ 𝑈 matrices.

↑ If 𝐿 is invertible, then the equation 𝐿𝑁 = 𝑀 has a unique solution for all 𝑀 ↓ R𝑈 .
Moreover, the solution is given by 𝑁 = 𝐿→1 𝑀.
6.5. INVERSE LINEAR TRANSFORMATION 66

↑ If both 𝐿 and 𝑚 are invertible, then the product 𝐿𝑚 is also invertible and

(𝐿𝑚)→1 = 𝑚→1 𝐿→1 .

↑ If one of 𝐿 or 𝑚 is not invertible, then the product 𝐿𝑚 is not invertible.

Exercise 6.19. Find a solution of the following linear system by using the inverse
of the coe"cient matrix.

2𝑁 1 = 4
𝑁1 → 2𝑁 3 = →3
𝑁 2 = 1.
" # " #
1 0 →2 1
Exercise 6.20. Let 𝐿 = and 𝑚 = . Find (𝐿𝑚)→1 .
1 4 2 0

6.5 Inverse linear transformation

As we now know that linear transformations (on R𝑈 ) and matrices are equivalent
concepts. Their invertibility can be concluded from the matrix representations

Definition 6.21 (Invertible transformation). A linear transformation 𝑒 : R𝑈 ↗ R𝑈

is invertible if there is a function 𝑒 →1 : R𝑈 ↗ R𝑈 in which 𝑒 ↑𝑒 →1 (𝑁) = 𝑒 →1 ↑𝑒(𝑁) = 𝑁
for all 𝑁 ↓ R𝑈 . The function 𝑒 →1 here is called the inverse transformation (or briefly
the inverse) of 𝑒.

The most important property that we need to address is that the inverse 𝑒 →1 is
also a linear transformation. This fact follows from the following result.

Theorem 6.22. If 𝑒 : R𝑈 ↗ R𝑈 is an invertible linear transformation whose matrix

representation is 𝐿𝑒 , then the inverse 𝑒 →1 of 𝑒 is given by the inverse matrix 𝐿𝑒→1 . From
this, we know that 𝑒 →1 is also a linear transformation.

Exercise 6.23. Let 𝑒(𝑁) = 𝑒(𝑁1 , 𝑁2 , 𝑁3 ) = (𝑁1 , 𝑁1 + 𝑁 2 , 𝑁1 + 𝑁 3 ) be a linear transfor-

mation. Find the inverse transformation of 𝑒.

Beyond invertibility, we see in the following exercise that the determinant

could also provide other information about a linear transformation.
6.6. GEOMETRY OF DETERMINANT 67

Exercise 6.24. Let 𝑒 be a linear transformation whose matrix representation is 𝐿𝑒 .

Then
• 𝑘𝑅𝑙(𝐿𝑒 ) ω 0 if and only if ker(𝑒) = {0}.

• 𝑒 is one-to-one if and only if ker(𝑒) = {0}.

• 𝑘𝑅𝑙(𝐿𝑒 ) ω 0 if and only if 𝑒 is one-to-one and onto.

6.6 Geometry of determinant

Let 𝐿 be a matrix that induces a linear transformation 𝑒𝐿 : R𝑈 ↗ R𝑈 is a linear
transformation. Then 𝑘𝑅𝑙(𝐿) encodes how the space R𝑈 is deformed under the
application of 𝑒𝐿 . We can also note from the rank-nullity theorem that 𝑒𝐿 cannot
explode the space in the sense that it is impossible to gain additional dimensions
by the transformation 𝑒𝐿 .
More precisely, the determinant 𝑘𝑅𝑙(𝐿) informs us the following information:
• The absolute value | 𝑘𝑅𝑙(𝐿)| is the area/volume of the parallelotope generated
by columns of 𝐿. Since columns of 𝐿 are 𝑒𝐿 (𝑅 𝑌 )’s, we obtain the information of
how the parallellotope generated by 𝑅1 , . . . , 𝑅 𝑈 are enlarged/shrinked through
the transformation 𝑒𝐿 .

• The sign of 𝑘𝑅𝑙(𝐿) tells about the change of orientation of the transformation.
If 𝑘𝑅𝑙(𝐿) is negative, then the transformation does not preserve the orientation
of the axes.
6.6. GEOMETRY OF DETERMINANT 68

Practice problems
1. Compute the determinants of the following matrices.
2 7 2

↑ 𝐿 = 0 0 1 .
1 0 0

2 7 0 6 3 

0 1 0 2 3 

↑ 𝑚 = 0 0 1 1 4  .
0 0 →1 →2 3 

0 0 0 0 →1

 1 0
 12 0 0
 0 0
 3 0 0
↑ 𝑛 =  →1 5 0 1 2 .
→11 2 1 1 0

 1 1 1 1
 →4

2. Which of the above matrices are invertible?

3. Consider if the linear transformation

𝑒(𝑁1 , 𝑁2 , 𝑁3 ) = (𝑁1 → 𝑁 2 , 𝑁2 + 2𝑁 3 , 2𝑁1 → 𝑁 3 )

is invertible. If 𝑒 is invertible, find 𝑒 →1 .

4. Show that the linear transformation

𝑒(𝑁 1 , 𝑁2 ) = (2𝑁1 → 𝑁 2 , 𝑁2 → 2𝑁 1 )

is not invertible.

5. Find 𝑒 →1 of the following linear transformation

𝑒(𝑁1 , 𝑁2 , 𝑁3 , 𝑁4 ) = (𝑁4 , 𝑁2 , 𝑁3 , 𝑁1 ).
Chapter 7

Eigenvalues and eigenvectors

Eigenvalues and eigenvectors are important concepts that has long list of ap-
plications. For example, it can be used to transform a di!erential equation into a
polynomial. In data analytics, eigenvectors represents important information that
is extracted from a square matrix. This technique is known as principal compo-
nent analysis, which is one of the main tool to extract information from a large
pool of data. In this course, we will see only an immediate use of eigenvectors
in the construction of basis that can be used for storing large matrix with limited
memory.

7.1 Eigenvalues and eigenvectors

Definition 7.1 (Eigenvalues and eigenvectors). Consider a square 𝑈 ⇑ 𝑈 matrix.
A scalar 𝜕 is called an eigenvalue of 𝐿 if there exists a nonzero vector 𝑂 (again,
possibly complex) for which
𝐿𝑂 = 𝜕𝑂.
For an eigenvalue 𝜕 of 𝐿, all nonzero vectors 𝑂 in which 𝐿𝑂 = 𝜕𝑂 are called
eigenvectors of 𝐿 associated with 𝜕. A pair (𝜕, 𝑂) is called an eigenpair if 𝜕 is an
eigenvalue of 𝐿 and 𝑂 is an eigenvector associated to 𝜕.

Geometrically, if we regard 𝐿 as a transformation, then (𝜕, 𝑂) is a pair of

eigenvalue-eigenvector of 𝐿 if and only if the transformed vector 𝐿𝑂 lies on the
same line as the original vector 𝑂.
In many situtations, the eigenvalues 𝜕’s are allowed to be complex numbers
even though the matrix is real. However, this complex eigenvalues fall outside the

69
7.1. EIGENVALUES AND EIGENVECTORS 70

scope of this lecture note. In this course, we shall only focus on real eigenpairs.
Before we proceed to finding eigenvalues and the associated eigenvectors of a
matrix, let us show that eigenvectors associated to each eigenvalue, together with
the zero vector, form a vector space.
Exercise 7.2. Let 𝐿 be an 𝑈 ⇑ 𝑈 matrix and 𝜕 ↓ R be an eigenvalue of 𝐿. Then the
set
𝑖𝜕 = {0} ∋ {All eigenvectors of 𝜕.} = {𝑂 ↓ R𝑈 | 𝐿𝑂 = 𝜕𝑂}
is a vector space, which is called the eigenspace associated to 𝜕.
" #
1 1
Exercise 7.3. Let 𝐿 = . Then 𝜕 = 1 is an eigenvalue of 𝐿 and the associated
0 1
eigenvectors are any vectors along the 𝑁-axis. Also describe this geometrically.

Now, let us turn to a practical aspect of finding eigenvalues and their associated
eigenvectors. When one tries to solve the eigenvalue-eigenvector equation
𝐿𝑂 = 𝜕𝑂,
a di"culty arises from the fact that both scalar 𝜕 and nonzero vector 𝑂 are un-
knowns. Hence the right-hand-side product 𝜕𝑂 implies that the above equation
itself is nonlinear. However, we can rearrange the said equation into the following
form
(𝐿 → 𝜕𝑠)𝑂 = 0. (7.1)
In order to obtain 𝑂 ω 0, it is necessary to have
𝑘𝑅𝑙(𝐿 → 𝜕𝑠) = 0. (7.2)
Notice that the above equation is free of the unknown vector 𝑂. Writing down
the determinant further shows that (7.2) is in fact a polynomial, known as the
characteristic polynomial of 𝐿. The fundamental theorem of algebra then gurantees that
(7.2) always has repeatable 𝑈 complex solutions (provided that 𝐿 is of dimension
𝑈 ⇑ 𝑈).
Once eigenvalues 𝜕 are sorted out from the characteristic polynomial (7.2), we
return to (7.1) with the known 𝜕’s. This makes (7.1) simply a linear system for
each eigenvalues 𝜕.
Finally, let us write down a summary of steps to find all eigenvalues and
eigenvectors of a matrix 𝐿:
7.1. EIGENVALUES AND EIGENVECTORS 71

Step 1. Find all eigenvalues 𝜕’s by solving det(𝜕𝑠 → 𝐿) = 0.

Step 2. Finding eigenvectors 𝑂’s associated to each 𝜕 by solving the linear systems
(𝐿 → 𝜕𝑠)𝑂 = 0.
Let us practice finding the eigenvalues and eigenvectors using the above pro-
cedures.
" #
0 1
Exercise 7.4. Let 𝐿 = . Then 𝐿 has no real eigenvalues.
→1 0
" #
→1 0
Exercise 7.5. Find all eigenvalues and eigenvectors of a matrix 𝐿 = .
2 0

The characteristic equation of an 𝑈 ⇑ 𝑈 matrix always has the degree of 𝑈. It

is often that the (real) root of the equation is repeated, at which case we have
repeated eigenvalues. The following are two examples where we have repeated
eigenvalues.

Exercise 7.6. Find all eigenvalues and eigenvectors of the following matrices.
 5 →10 →5  5 →6 →6
   

(a) 𝐿 =    
2 14 2  (b) 𝑚 =  →1 4 2 
→4 →8 6   3 →6 →4
   
We end the section with a list of fundamental properties of the eigenvalues
and eigenvectors that could be useful for future use.

Theorem 7.7. Consider a square matrix 𝐿.

• If (𝜕1 , 𝑂1 ) and (𝜕2 , 𝑂2 ) are eigenpairs of 𝐿 with 𝜕1 ω 𝜕2 , then 𝑂1 and 𝑂 2 are linearly
independent.

• If det(𝐿) = 0, then 𝜕 = 0 is one of the eigenvalues of 𝐿.

• If 𝜕 is an eigenvalue of 𝐿, then 𝑄𝜕 is an eigenvalue of 𝑄𝐿.

• If 𝜕 is an eigenvalue of 𝐿 and 𝑈 ↓ N, then 𝜕𝑈 is an eigenvalue of 𝐿𝑈 .

• 𝐿 and 𝐿𝑒 have the same eigenvalues.

• If 𝐿 is invertible and 𝜕 is an eigenvalue of 𝐿, then 𝜕→1 is an eigenvalue of 𝐿→1 .

7.2. EIGENBASIS 72

• If 𝐿 is a triangular matrix, then eigenvalues of 𝐿 are the elements in the diagonal of 𝐿.

• If 𝐿 is symmetric, then all eigenvalues of 𝐿 are real.
• Let 𝜕1 , · · · , 𝜕𝑈 be all the eigenvalues of 𝐿 (repeatable), then
/
𝑈 /
𝑈 
𝑈
𝜕 𝑌 = 𝑙𝑆(𝐿) = 𝑎 𝑌𝑌 and 𝜕 𝑌 = 𝑘𝑅𝑙(𝐿).
𝑌=1 𝑌=1 𝑌=1

7.2 Eigenbasis
One of the most important features from the eigenpairs is the possiblity to con-
struct a new meaningful basis, called the eigenbasis, that simplifies the computation
related to a given matrix.
Definition 7.8 (Eigenbasis). Let 𝐿 be a square matrix of dimension 𝑈 ⇑ 𝑈. If 𝐿 has
linearly independent real eigenvectors 𝑂1 , . . . , 𝑂 𝑈 , then these eigenvectors form a
basis S = {𝑂 1 , . . . , 𝑂 𝑈 }. This special basis is called the eigenbasis generated by 𝐿.
Remark. According to the previous section, if 𝐿 has 𝑈 distinct real eigenvalues,
then the eigenvectors associated to each eigenvalues will automatically be linearly
independent.
Exercise 7.9. Find the eigenbases associated to each of the following matrices.
" #  1 0 →1   5 →10 →5 
   
(b) 𝑚 =  0 2 0  (c) 𝑛 =  2 14 2 
1 →3
(a) 𝐿 =
3 0  →1 0 →1   →4 →8 6 
   
A stronger result could be drawn when 𝐿 is symmetric, and this is known as
the spectral theorem.
Theorem 7.10 (Spectral theorem). If 𝐿 is an 𝑈 ⇑ 𝑈 symmetric matrix, then 𝐿 has
eigenvectors 𝑂1 , . . . , 𝑂 𝑈 that form an orthonormal basis on R𝑈 . In simpler words, the
matrix 𝐿 has an orthonormal eigenbasis.

Let us confirm the spectral theorem with one of the matrices above.
 1 0 →1 
 
Exercise 7.11. Construct an orthonormal eigenbasis for 𝑚 =  0 2 0  .
 →1 0 →1 
 
7.3. DIAGONALIZATION 73

7.3 Diagonalization
Diagonalization is the process that changes the basis under which a square
matrix becomes a diagonal matrix. While it is not always possible to diagonalize
every matrix, there could be more than one way to diagonalize a matrix. However,
it turns out that a matrix is always diagonalized under its own eigenbasis. Let us
formally state these ideas below using a more tractable approach.

Definition 7.12. A 𝑈 ⇑ 𝑈 matrix 𝐿 is diagonalizable if there is an 𝑈 ⇑ 𝑈 invertible

matrix 𝑑 and an 𝑈 ⇑ 𝑈 diagonal matrix 𝑡 such that

𝐿 = 𝑑𝑡𝑑 →1 .

Here, since 𝑑 is invertible, the columns of 𝑑 forms a basis U on R𝑈 . Moreover,

the two matrices 𝑑 and 𝑑 →1 could be interpreted, respectively, as the change-of-
basis matrices [S △ U] and [U △ S]. With this view, the diagonal matrix 𝑡 is the
representation of 𝐿 in the basis U, that is

𝑡 = [U △ S]𝐿[S △ U] = 𝐿U
U.

Theorem 7.13. If an 𝑈 ⇑ 𝑈 matrix 𝐿 has 𝑈 independent real eigenvectors 𝑂 1 , . . . , 𝑂 𝑈

which are associated respectively to eigenvalues 𝜕1 , . . . , 𝜕𝑈 , then 𝐿 is diagonalizable and
we have

𝐿 = 𝑃ε𝑃 →1 ,

where 𝑃 is the matrix whose 𝑌 th column is 𝑂 𝑌 , and ε = diag(𝜕1 , . . . , 𝜕𝑈 ).

Exercise 7.14. Diagonalize the following matrices.

" # " # 2 0 0
 
(c) 𝑛 = 0 1 1
1 3 →3 0
(a) 𝐿 = (b) 𝑚 =
3 1 1 2 0 1 1
 
Diagonalization has some uses in matrix computation. The first use case is
when one wants to compute a matrix power 𝐿 𝑄 when 𝑄 is large. Instead of
7.4. SINGULAR VALUE DECOMPOSITION 74

computing the matrix power 𝐿 𝑄 , if 𝐿 is diagonalized into 𝐿 = 𝑃ε𝑃 1 , then

𝐿 𝑄 = (𝑃ε𝑃 →1 )(𝑃ε𝑃 →1 ) · · · (𝑃ε𝑃 →1 )

⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌
𝑄 times
= 𝑃ε [(𝑃 𝑃)ε][(𝑃 →1𝑃)ε] · · · [(𝑃 →1𝑃)ε] 𝑃 →1
→1
⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌
𝑄 → 1 times
𝑄 →1
= 𝑃ε 𝑃 ,

and recall that ε 𝑄 = diag(𝜕1𝑄 , . . . , 𝜕𝑈𝑄 ). Note that matrix power is widely used to
approximate the matrix exponential that appears frequently in system of ordinary
di!erential equations.
2 0 1
 

Exercise 7.15. Let 𝐿 =   . Find 𝐿10 .
0 1 0 
 0 0 →1 
 

7.4 Singular value decomposition

We could in fact decompose any 𝑉 ⇑ 𝑈 matrix 𝐿 in a similar method as diago-
nalization, called singular value decomposition.
Definition 7.16. Let 𝐿 be an 𝑉 ⇑ 𝑈 matrix. A singular value decomposition (or SVD)
of 𝐿 is the factorization of the form

𝐿 = 𝑑ϑ𝑃 ⇔ ,

where
▽
↑ ϑ = diag(𝜖1 , . . . , 𝜖𝑈 )𝑉⇑𝑈 , with 𝜖𝑌 = 𝜕 𝑌 and 𝜕1 ↘ 𝜕2 ↘ · · · ↘ 𝜕𝑈 ↘ 0 are the
eigenvalues of 𝐿⇔ 𝐿,
↑ 𝑃 is an 𝑈 ⇑ 𝑈 matrix whose 𝑌 th column, 𝑂 𝑌 , is the normalized eigenvector of 𝐿⇔ 𝐿
associated to 𝜕 𝑌 ,
1
↑ 𝑑 is an 𝑉 ⇑ 𝑉 matrix whose 𝑌 th column, 𝑋𝑌 , is given by 𝑋𝑌 = 𝜖𝑌 𝑂 𝑌 at 𝑌 in which 𝜖𝑌 >
0, and 𝑋𝑌 = 0 at 𝑌 in which 𝜖𝑌 = 0.
Remark. Some remarks are in order.
↑ The number of nonzero eigenvalues of 𝐿⇔ 𝐿 equals the rank of 𝐿.
7.5. QUADRATIC FORMS 75

↑ In some source, the matrix 𝑑 is required that 𝑑 ⇔𝑑 = 𝑠. Here we may replace

the 𝑋𝑌 at 𝑌 in which 𝜖𝑌 = 0 with anything that fullfil 𝑑 ⇔𝑑 = 𝑠. In fact, the values
at which 𝜖𝑌 = 0 does not participate in the factorization.

The following fact highlights the reason why SVD is considered an important
factorization technique.
Theorem 7.17. Any matrix can be factorized using SVD.

If 𝐿 is regarded as a transformation, then the SVD says that every transforma-

tion is achieved by making a rotation with 𝑃 ⇔ , followed by rescale along the axes
with ϑ, and finally followed by another rotation 𝑑.
1 2
 0 0 0
0 0
Exercise 7.18. Compute a SVD of the matrix 𝐿 = 
0 3 0
0 0 0 0 0
0 2 0 0 0


7.5 Quadratic forms

A quadratic form is a generalization of the square term in a polynomial of one
variable. In the multi-variable setting, a quadratic form refers to those terms
involving the product of any two variables. To give a better picture, we list the
quadratic forms of up to 3 variables below.

↑ 1 variable. 𝑞(𝑁) = 𝑎𝑁 2 , where 𝑎 ↓ R is a constant.

↑ 2 variables. 𝑞(𝑁, 𝑇) = 𝑎𝑁 2 + 𝑀𝑇 2 + 𝑝𝑁 𝑇, where 𝑎, 𝑀, 𝑝 ↓ R.
↑ 3 variables. 𝑞(𝑁, 𝑇, 𝑢) = 𝑎𝑁 2 + 𝑀𝑇 2 + 𝑝𝑇 2 + 𝑘𝑁𝑇 + 𝑅𝑁𝑢 + 𝑣 𝑇𝑢.

Following this line, we now state the formal definition of a quadratic form of 𝑈
variables.
Definition 7.19 (Quadratic forms). A function 𝑞 : R𝑈 ↗ R is called a quadratic form
on R𝑈 if
/
𝑈 /
𝑈
𝑞(𝑁) = 𝑞(𝑁1 , . . . , 𝑁 𝑈 ) = 𝑝 𝑌𝑍 𝑁 𝑌 𝑁 𝑍 ,
𝑌=1 𝑍=𝑌
7.5. QUADRATIC FORMS 76

where 𝑝 𝑌𝑍 ’s are real coe"cients.

7.5.1 Matrix-vector form

The most important result regarding quadratic forms is about their matrix-
vector representation.
 
Theorem 7.20. Let 𝑞(𝑁 1 , . . . , 𝑁 𝑈 ) = 𝑈𝑌=1 𝑈𝑍=𝑌 𝑝 𝑌𝑍 𝑁 𝑌 𝑁 𝑍 be a quadratic form on R𝑈 . Then
there exists a symmetric 𝑈 ⇑ 𝑈 matrix 𝐿 such that

𝑞(𝑁) = 𝑁 ⇔ 𝐿𝑁.

In particular, this matrix is given by

2𝑝11 . . . 𝑝1𝑈 
 𝑝12 𝑝13
 𝑝12 2𝑝 22 𝑝23 . . . 𝑝2𝑈 
1 
𝐿 =  𝑝 13 𝑝23 2𝑝 33 . . . 𝑝3𝑈  .
.. 
(7.3)
2  .. .. .. ...
 . . . . 
 𝑝1𝑈 . . . 2𝑝 𝑈𝑈 
 𝑝2𝑈 𝑝3𝑈

Exercise 7.21. Consider the quadratic form

𝑞(𝑁, 𝑇) = 2𝑁 2 + 3𝑁𝑇 + 𝑇 2 .

Find a matrix 𝐿 in which 𝑞(𝑋) = 𝑋 ⇔ 𝐿𝑋, where 𝑇 = (𝑁, 𝑇).

Exercise 7.22. Write down the quadratic form

𝑞(𝑁1 , 𝑁2 , 𝑁3 ) = 2𝑁12 → 𝑁 2 𝑁3 + 𝑁 1 𝑁3 + 𝑁 32

in the vector-matrix form.

7.5.2 Classification of quadratic forms

It is useful in applications to identify the convexity of a quadratic function. The
following Figure 7.1 illustrates respectively a convex, a concave, and an indefinite
quadratic forms.
7.5. QUADRATIC FORMS 77

Figure 7.1: (Left) Convex quadratic form.

(Middle) Concave quadratic form.
(Right) Indefinite quadratic form.

Looking at Figure 7.1, one may make infer that a convex quadratic form is
suitable for minimization, a concave quadratic form is suitable for maximization,
and an indefinite one does not work well with both.
When a quadratic form 𝑞(𝑁) is converted into its matrix-vector form 𝑞(𝑁) =
𝑁 ⇔ 𝐿𝑁using the formula (7.3), such convexity could be observed through eigen-
values of 𝐿. Before we go to the main result, we first define the signs of a symmetric
matrix using the signs of its eigenvalues.

Definition 7.23 (Matrix classification). A symmetric matrix 𝐿 is said to be

↑ positive semidefinite if all eigenvalues of 𝐿 are ↘ 0,

↑ positive definite if all eigenvalues of 𝐿 are > 0,

↑ negative semidefinite if all eigenvalues of 𝐿 are ⇒ 0,

↑ negative definite if all eigenvalues of 𝐿 are < 0,

↑ indefinite if 𝐿 has both positive and negative eigenvalues.

Remark. From the definition, one may observe that positive definiteness implies
positive semidefiniteness and similar to the negative counterpart.

The following result characterizes the convexity of a quadratic form using the
sign of its underlying matrix.

Theorem 7.24. A quadratic form 𝑞(𝑁) = 𝑁 ⇔ 𝐿𝑁 is

7.5. QUADRATIC FORMS 78

↑ convex ≃⇐ 𝐿 is positive semidefinite,

↑ concave ≃⇐ 𝐿 is negative semidefinite,

↑ indefinite ≃⇐ 𝐿 is indefinite.

Exercise 7.25. Classify the quadratic form 𝑞(𝑁) = 𝑁 ⇔ 𝐿𝑁, where 𝐿 is given as
follows.
" # 1 2 1
 
(b) 𝐿 = 2 →1 0
3 →2
(a) 𝐿 =
→2 3 1 0 0
 

7.5.3 Quadratic forms reformulation without cross terms

One may notice that a complication of a quadratic form is rooted in its cross
terms. Opposing to the pure terms that is the true squares 𝑝 𝑌𝑌 𝑁 2𝑌 ’s, the cross terms
are the those 𝑝 𝑌𝑍 𝑁 𝑌 𝑁 𝑍 involving two di!erent variables. In general, we may write a
quadratic form as
/
𝑈 /
𝑈 /
𝑈 /
𝑈 /
𝑈
𝑞(𝑁) = 𝑝 𝑌𝑍 𝑁 𝑌 𝑁 𝑍 = 𝑝 𝑌𝑌 𝑁 2𝑌 + 𝑝 𝑌𝑍 𝑁 𝑌 𝑁 𝑍 .
⨌⨌⨌⨌⨌⨌ ⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌⨌
𝑌=1 𝑍=𝑌 𝑌=1 𝑌=1 𝑍=𝑌+1

pure terms cross terms

When writing 𝑞(𝑁) as a matrix-vector form 𝑞(𝑁) = 𝑁 ⇔ 𝐿𝑁, the diagonal entries
are responsible for the pure terms’ coe"cients and the o!-diagonal entries are
corresponding to the cross terms.
At this stage, one may apply the diagonalization technique studied in the
Section 7.3 to the matrix 𝐿. Recall that 𝐿 is symmetric, so the spectral theorem
ensures that it has an orthonormal eigenbasis {𝑂 1 , . . . , 𝑂 𝑈 }, where 𝑂 𝑌 is an eigen-
vector of 𝐿 associated to an eigenvalue 𝜕 𝑌 . Let 𝑃 and ε be defined accordingly to
the diagonalization 𝐿 = 𝑃ε𝑃 →1 . From the orthonormality, we have

𝑃𝑃 ⇔ = 𝑠 = 𝑃 ⇔𝑃

which means 𝑃 →1 = 𝑃 ⇔ . Therefore, the diagonalization becomes

𝐿 = 𝑃ε𝑃 ⇔
7.5. QUADRATIC FORMS 79

and finally we obtain

𝑞(𝑁) = 𝑁 ⇔𝑃ε𝑃 ⇔ 𝑁 = (𝑃 ⇔ 𝑁)⇔ ε(𝑃 ⇔ 𝑁) = 𝑇 ⇔ ε𝑇.

If we put 𝑞ˆ (𝑇) = 𝑇 ⇔ ε𝑇, then 𝑞ˆ is a quadratic form that has no cross terms.
We have just showed that the diagonalization technique could always be ap-
plied to find a new basis (in this case the orthonormal eigenbasis) under which
the cross terms are eliminated.

Exercise 7.26. Use the diagonalization technique to eliminate the cross terms of
the quadratic form 𝑞(𝑁) = 𝑁 ⇔ 𝐿𝑁, where 𝐿 is given below.
" # 1 2 1
 
(b) 𝐿 = 2 →1 0
3 →2
(a) 𝐿 =
→2 3 1 0 0
 
7.5. QUADRATIC FORMS 80

Practice problems
1. Find all eigenvalues and eigenvectors of the following matrices:
3 0 →2 1 0 3 
 
↑ 𝐿 = 0 1 0  ↑ 𝑚 = 0 2 0 
1 →1 0  3 0 →1
 
1 0 0 →2 0 0
 
↑ 𝑛 = 0 3 4 ↑ 𝑡 =  0 3 0
0 0 1 1 3 2
 
2. Find the eigenbasis, whenever possible, from the matrices 𝐿, 𝑚, 𝑛, 𝑡 above.
Chapter 8

Applications

In this chapter, we discuss several applications of linear algebra using the

concepts and tools of earlier chapters.

8.1 Minimizing convex quadratic functions

Let us start with the definition.

Definition 8.1 (Quadratic functions). A quadratic function is a function 𝑣 : R𝑈 ↗

R of the form

𝑣 (𝑁) = 𝑁 ⇔ 𝐿𝑁 + 𝑀 ⇔ 𝑁 + 𝑝,

where 𝐿 ↓ R𝑈⇑𝑈 is a symmetric matrix, 𝑀 ↓ R𝑈 is a vector, and 𝑝 ↓ R is a scalar.

Remark. A quadratic function is not the same as a quadratic form. Rather, it is a

quadratic form 𝑁 ⇔ 𝐿𝑁 added to an a"ne function 𝑀 ⇔ 𝑁 + 𝑝.

Theorem 8.2. A quadratic function 𝑣 (𝑁) = 𝑁 ⇔ 𝐿𝑁 + 𝑀 ⇔ 𝑁 + 𝑝 is convex (concave) if

and only if 𝐿 is positive semidefinite (negative semidefinite). Moreover, its minimizers
(maximizers) can be found by solving the linear system

𝑀
𝐿𝑁 = → .
2

81
8.2. LEAST-SQUARES SOLUTIONS OF LINEAR SYSTEMS 82

Figure 8.1: A convex and concave quadratic function with their extreme points.

Exercise 8.3. Find all minimizers of the convex quadratic function 𝑣 (𝑁) = 𝑁 ⇔ 𝐿𝑁 +
𝑀 ⇔ + 𝑝 with
" # " #
1 0 →2
𝐿= , 𝑀= , 𝑝 = →1.
0 0 0

Exercise 8.4. Consider a quadratic function 𝑣 (𝑁) = 𝑁 ⇔ 𝐿𝑁 + 𝑀 ⇔ 𝑁 + 𝑝 where

2 1 0 1
   
𝐿 = 1 2 0 ,
 𝑀 =  0  , 𝑝 = 2.
0 0 1 →2
   
Show that 𝑣 (𝑁) is convex and find all minimizers of 𝑣 (𝑁).

8.2 Least-squares solutions of linear systems

In this section, we apply the minimization of a convex quadratic function
to achieve a practical aspect of inconsistent linear systems. Recall that a linear
system 𝐿𝑁 = 𝑀 is called inconsistent if it has no solution. This happens if and only
if 𝑆𝑎𝑈 𝑄(𝐿) < 𝑆𝑎𝑈𝑄([𝐿 𝑀]). When a linear system is inconsistent, we usually seek a
relaxed solution 𝑁¯ in the sense that 𝐿 𝑁¯ is the closest to 𝑀.
Definition 8.5. A vector 𝑁¯ is called a least-squares solution of a linear system 𝐿𝑁 = 𝑀
if 𝑁¯ minimizes the residual function 𝑗(𝑁) = ↔ 𝐿𝑁 → 𝑀↔ 2 .

The first important fact is that we can always find a least-squares solution even
if the linear system has no solution in the classical sense.
8.2. LEAST-SQUARES SOLUTIONS OF LINEAR SYSTEMS 83

Theorem 8.6. A linear system always has a least-squares solution.

The next result is also very important in the practical aspect.

Theorem 8.7. The residual function is a convex quadratic function.

Proof. From the definition of a residual function, we have

𝑗(𝑁) = ↔ 𝐿𝑁 → 𝑀↔ 2
= (𝐿𝑁 → 𝑀)⇔ (𝐿𝑁 → 𝑀)
= (𝑁 ⇔ 𝐿⇔ → 𝑀 ⇔ )(𝐿𝑁 → 𝑀)
= 𝑁 ⇔ 𝐿⇔ 𝐿𝑁 → 𝑀 ⇔ 𝐿𝑁 → 𝑁 ⇔ 𝐿⇔ 𝑀 + 𝑀 ⇔ 𝑀
= 𝑁 ⇔ (𝐿⇔ 𝐿)𝑁 → 2(𝐿⇔ 𝑀)⇔ 𝑁 + 𝑀 ⇔ 𝑀.

This shows that 𝑗 is a quadratic function. Since the matrix 𝑤 = 𝐿⇔ 𝐿 is positive

semidefinite, it follows that 𝑗(𝑁) is convex.

Now that we know 𝑗(𝑁) is a convex quadratic function, the least-squares

solutions of 𝐿𝑁 = 𝑀 are obtained by solving the new linear system

𝐿⇔ 𝐿𝑁 = 𝐿⇔ 𝑀.

Let us first show that the least-squares solutions coincide with the classical
solutions for consistent systems.
Theorem 8.8. If a linear system 𝐿𝑁 = 𝑀 is consistent, then the least-squares solutions are
exactly the classical solutions.

Proof. First notice that 𝑗(𝑁) = ↔ 𝐿𝑁 → 𝑀↔ 2 ↘ 0 for any 𝑁. Moreover we know

that 𝑗(𝑁) = 0 if and only if 𝐿𝑁 = 𝑀. This means the classical solutions of 𝐿𝑁 = 𝑀
are the least-squares solutions, and vice versa.

We now look at some examples.

Exercise 8.9. Consider the linear system

2𝑁 1 + 3𝑁 2 = 2
𝑁1 → 𝑁2 = 1
𝑁1 + 4𝑁 2 = 0
8.3. LINEAR REGRESSION 84

(a) Show that this system has no solution.

(b) Find the least-squares solution.

Exercise 8.10. Show that the following system has no classical solution and find
the least-squares solution

𝑁1 + 𝑁2 =0
2𝑁 1 + 𝑁 3 =2
𝑁2 → 𝑁3 = →1
𝑁1 + 𝑁3 = 1.

8.3 Linear regression

Regression is a statistical tool that is used to find the function of a particular
class that fits best to the observed data. In this course, we only focus on the linear
regression which means that we would like to fit a straight line to the observed
data. To keep things simple, we only consider the 1-dimensional case.

Figure 8.2: Linear regression

Suppose that we take 𝑉 samples at controlled variable 𝑁1 , · · · , 𝑁 𝑉 where we

observed the value 𝑇1 , · · · , 𝑇𝑉 , respectively. This could be presented as a table
8.3. LINEAR REGRESSION 85

Controlled variable (𝑁) Observed data (𝑇)

𝑁1 𝑇1
𝑁2 𝑇2
.. ..
. .
𝑁𝑉 𝑇𝑉

In this 1-dimensional linear regression paradigm, we make an assumption that

the observed data 𝑇 𝑌 depends linearly on a single controlled variable 𝑁 𝑌 . That is, we
believe that, with a good choice of parameters 𝑎, 𝑀 ↓ R, we will get
𝑇𝑌 ′ 𝑎𝑁 + 𝑀
 ⨌⨌⨌⨌
𝑌

observed value predicted value

for all samples 𝑌 = 1, . . . , 𝑉.

For any 𝑋 = (𝑎, 𝑀), we measure how good the approximation 𝑇 𝑌 ′ 𝑎𝑁 𝑌 + 𝑀 is
using the squares error1 . The squares error between the observed value 𝑇 𝑌 and the
predicted value 𝑎𝑁 𝑌 + 𝑀 can be computed by the formula
Err(𝑋) = (𝑇1 → (𝑎𝑁 1 + 𝑀))2 + (𝑇2 → (𝑎𝑁 2 + 𝑀))2 + · · · + (𝑇𝑉 → (𝑎𝑁 𝑉 + 𝑀))2 .
Putting 𝑇 = (𝑇1 , . . . , 𝑇𝑉 ), 𝑁 = (𝑁 1 , . . . , 𝑁 𝑉 ), 1 = (1, . . . , 1), 𝐿 = [𝑁; 1] and 𝑋 = (𝑎, 𝑀),
⨌⨌⨌⨌
𝑉 times
we can further simplify the Err formula above into
Err(𝑋) = ↔ 𝑇 → (𝑎𝑁 + 𝑀1)↔ 2
= ↔ 𝑇 → [𝑁 1]𝑋↔ 2
= ↔ 𝐿𝑋 → 𝑇↔ 2 .
This implies the function Err reduces to a squared norm with a linear system
inside. Therefore, selecting 𝑋 = (𝑎, 𝑀) that minimizes the squares error Err(𝑋)
is finding a least-square solution to the system 𝐿𝑋 = 𝑇. Finally, the parameter
𝑋 = (𝑎, 𝑀) can be determined by solving the linear system
𝐿⇔ 𝐿𝑋 = 𝐿⇔ 𝑇.

Let us now do a practice exercise for linear regression.

1A
more classical approach is to use the root mean-squares error (RMSE) or the mean-squares error (MSE).
However, these approach end up with the same solutions as the squares error approach that we used.
8.4. PRINCIPAL COMPONENT ANALYSIS 86

Exercise 8.11. A scientist is experimenting a new drug that slows down the growth
of certain species of bacteria under a controlled environment. The procedures are
as follows: The initial colony of 1 CFU (colony-forming unit) is deployed in an
agar plate. For 60 minutes, the scientist will observe the number of bacterial cells
every 5 minutes. The following is the observed data

Observed time (min.) Number of bacterial cells (CFU)

0 1
5 1.45
10 2.02
15 2.5
20 2.97
25 3.49
30 3.92
35 4.55
40 5.11
45 5.60
50 6.13
55 6.64
60 7.23

Write the linear system for the linear regression that estimate the data in the
above table.

8.4 Principal component analysis

Principal component analysis (briefly PCA) is another statistical tool that is used
to reduce data dimension while maintaining the most information possible. The
data dimension corresponds to the number of features of each sample.
Given a dataset of 𝑉 points in R𝑈 :

X̂ = { 𝑁ˆ 1 , . . . , 𝑁ˆ 𝑉 } ∞ R𝑈 .

One of the naïve methods to reduce the data dimension is to delete some of the
features from the dataset. However, this does not retain the most information
possible. Instead, we seek an orthogonal projection onto a lower-dimensional
8.4. PRINCIPAL COMPONENT ANALYSIS 87

subspace of designated dimension 𝑄 ⇒ 𝑈 such that the information, measured using

the variance, is maximized. The basis of this optimal subspace is called the principal
components, and it happens to be the (normalized) eigenvectors corresponded to
the 𝑄 largest eigenvalues of the covariance matrix of the centered dataset.
To make an optimal dimension reduction using the PCA, we first need to center
the data:

X = {𝑁1 , . . . , 𝑁 𝑉 },
1 /
𝑉
𝑁 𝑌 = 𝑁ˆ 𝑌 → 𝑁,
¯ 𝑁¯ = 𝑁ˆ 𝑌 .
𝑉
𝑌=1

The covariance matrix of the centered dataset X is defined by

1 /
𝑉
1
𝑕= 𝑁𝑌 𝑁⇔
𝑌 = 𝑥𝑥 ⇔ ,
𝑉 𝑉
𝑌=1

where 𝑥 is the matrix whose 𝑌 th column is 𝑁 𝑌 .

The 𝑄 principal components are the orthonormal basis V = {𝑂1 , . . . , 𝑂 𝑄 } ∞ R𝑈

such that the information measured with the variance, 𝑄𝑍=1 𝑂 ⇔
𝑍
𝑕𝑂 𝑍 , is maximized.

Theorem 8.12. The 𝑄 principal components of the centered dataset X = {𝑁 1 , . . . , 𝑁 𝑉 } ∞

R𝑈 , with 𝑄 ⇒ 𝑈, is obtained by the normalized eigenvectors corresponded to the 𝑄 largest
eigenvalues of 𝑕 = 𝑉1 𝑥𝑥 ⇔ . That is, if

𝜕1 ↘ 𝜕2 ↘ · · · ↘ 𝜕 𝑈 ↘ 0

are then eigenvalues of 𝑕, then the 𝑄 principal components V = {𝑂 1 , . . . , 𝑂 𝑄 } satisfy

(𝑕 → 𝜕 𝑍 𝑠)𝑂 𝑍 = 0 and ↔ 𝑂𝑍↔ = 1

for all 𝑍 = 1, . . . , 𝑄.

Once the 𝑄 principal components V = {𝑂1 , . . . , 𝑂 𝑄 } is obtained, the centered

dataset X is projected onto 𝑃 = span(V) to obtain the projected dataset

X∈ = {𝑁1∈ , . . . , 𝑁 𝑉
∈
} ∞ 𝑃,
𝑁 ∈𝑌 = proj𝑃 (𝑁 𝑌 ), 𝑌 = 1, . . . , 𝑉.
8.5. IMAGE COMPRESSION 88

Recall that dim(𝑃) = 𝑄 ⇒ 𝑈, so that X∈ is a dataset in a lower-dimensional space.

Figure 8.3: The orthogonal projection of 3-dimensional data onto the first two
principal components.

8.5 Image compression

In this subsection, we demonstrate how a digital image file could be com-
pressed into a smaller file size without losing significant details using singular
value decomposition (SVD). One should be clear that compression and resizing
are two di!erent things. Any compression method should not reduce the pixel
size of an image but rather the memory used to store it.
A grayscale digital image is nothing but an 𝑉 ⇑𝑈 matrix 𝐿 whose pixel entry 𝑎 𝑌𝑍
is a gray value between 0 (representing black) and 1 (representing white). In a
similar way, an rgb color digital image is representing with three layers of the
respective color’s intensity matrix.
We shall only demonstrate a grayscale case for simplicity. Suppose that 𝐿 is
an 𝑉 ⇑ 𝑈 matrix representing a grayscal digital image. Suppose that 𝐿 is factorized
with SVD into

𝐿 = 𝑑ϑ𝑃 ⇔ ,

where we recall that 𝑑 ↓ R𝑉⇑𝑉 , ϑ ↓ R𝑉⇑𝑈 and 𝑃 ↓ R𝑈⇑𝑈 . Also, remember that
the information is stored in 𝑑 and 𝑃 at columns 𝑌’s such that 𝜖𝑌 > 0. Moreover,
8.5. IMAGE COMPRESSION 89

since 𝜖1 ↘ 𝜖2 ↘ · · · ↘ 𝜖𝑈 ↘ 0, the information values are sorted in a decreasing

order. That means the information values in the early columns of 𝑑 and 𝑃 are
higher than the later columns. Such an observation motivates us to discard the
later columns and only keep the first 𝑄 columns that matter the most in our image
matrix:

𝐿 ′ 𝐿 𝑄 = 𝑑 𝑄 ϑ 𝑄 𝑃𝑄⇔ ,

where 𝑄 ⇒ min{𝑉, 𝑈} and

↑ 𝑑 𝑄 = [𝑋1 𝑋2 . . . 𝑋 𝑄 ]𝑉⇑𝑄 ,

↑ ϑ 𝑄 = diag(𝜖1 , . . . , 𝜖 𝑄 ) 𝑄⇑𝑄 ,

↑ 𝑃𝑄 = [𝑂1 𝑂2 . . . 𝑂 𝑄 ]𝑈⇑𝑄 .
This method is sometimes called the low-rank approximation or rank 𝑄 approximation,
due to the fact that the full image is approximated up to the rank 𝑄 matrix 𝐿 𝑄 .
Note that 𝐿 𝑄 maintains the dimension 𝑉 ⇑ 𝑈 of the original data.

Figure 8.4: The original image and its rank 𝑄 approximations for 𝑄 = 5, 20, 50, 100.
 You’re now on your own, kid!

Outroduction.
I truly hope you did learned some boring mathematics but, in the back of your
head, aware how creative stu!s are made out of it.
Linear algebra, like many other branches of mathematics, are milestones in
bleeding-edge technologies around us.
Good engineers know how things work.
Great engineers know how to make them better!

All the best.

Parin Chaipunya