Linear algebra
COMPSCI 753
Kaiqi Zhao
The University of Auckland
Basic Operands
Scalar Vectors
• A scalar is a single number
• Integers, real numbers, etc.
• Denoted by a single letter like 𝑐 𝑜𝑟 𝑁
• A vector is a 1-D array of numbers: 𝑣” • Can be real, binary, integer, etc. 𝒗 = 𝑣#
• Denote by bold font like 𝒗 ∈ R! Matrices Tensors
• A matrix is a 2-D array of numbers:
• Denoted by bold capital 𝑨 ∈ R$×!
Row 𝐴”,” 𝐴”,# Column 𝐴#,” 𝐴#,#
𝑣⋮ !
• A tensor is an array of numbers, that may have:
• zero dimensions, and be a scalar
• one dimension, and be a vector
• two dimensions, and be a matrix
• or more dimensions.
1
Vector Operation – Norms
• Functions that measure how “large” a vector is
• Imagine a distance metric between the origin and the point represented by the
vector.
• A norm satisfies the following properties:
• 𝑓 𝑥 =0 ⇒𝑥=0(positivedefinite)
• 𝑓 𝑥+𝑦 ≤𝑓 𝑥 +𝑓 𝑦 (triangleinequality)
• ∀𝑎 ∈ R, 𝑓 𝑎𝑥 = |𝑎|𝑓(𝑥) (absolutely scalable)
2
𝐿! Norm
𝒙(= #𝑥)
)
• 𝐿”norm,p=1: 𝒙”=7|𝑥’| ‘
• 𝐿#norm,p=2: 𝒙#= 7𝑥’# ‘
*
( (
• Max norm, infinite p:
𝒙 ( = max|𝑥’| ‘
3
Vector Operation – Dot Product
• Dot product of two vectors
𝒂⏉𝒃 = #𝑎)𝑏) )
• It can also be written in terms of their 𝐿# norms and the angle 𝜃 between them
𝒂⏉𝒃= 𝒂, 𝒃,cos(𝜃)
Image taken from math is fun
4
Vector projection
• Giventwovectors𝒂and𝒃,let𝒃>= 𝒃 be the unit vector in the direction of 𝒃. 𝒃
• Then 𝒂𝒃> gives a projection of 𝒂 onto the line of 𝒃, i.e.,
𝒂𝒃/=𝒂0 𝒃 = 𝒂 cos(𝜃) 𝒃
Image taken from wikipedia
5
Cosine Similarity
• Cosine of the angle between two vectors measures similarity:
𝒂0𝒃 𝒂𝒃
• Orthogonal vectors 𝒂 ⊥ 𝒃: Two vectors 𝒂 and 𝒃 are orthogonal to each other if 𝒂 @ 𝒃 = 0
cos 𝜃 =
6
Matrix Operation – Transpose
𝑨⏉
𝐴”,” 𝐴”,#
𝑨= 𝐴#,” 𝐴#,# ⇒𝑨⏉=
𝐴*,” 𝐴*,#
),.
= 𝐴.,)
𝐴”,” 𝐴#,” 𝐴*,” 𝐴”,# 𝐴#,# 𝐴*,#
• The transpose of the matrix can be thought of as a mirror image across the main diagonal.
𝑨𝑩 ⏉ = 𝑩⏉𝑨⏉
7
Matrix Operation – Dot-Product
𝑪=𝑨⋅𝑩
𝐴 𝐴 𝐴 𝐵*,*
*,* *,, *,0 𝐵,,* 𝐴,,* 𝐴,,, 𝐴,,0 𝐵0,*
𝐶),. = #𝐴),/𝐵/,. /
𝐵*,, 𝐵,,, 𝐵0,,
𝐵*,0 𝐵,,0 𝐵0,0
=
𝐶 𝐶 𝐶 *,* *,, *,0
𝐶,,* 𝐶,,, 𝐶,,0
• The #columns of A has to be the same as #rows in B. • Let𝑨∈R$×! and𝑩∈R!×, then𝑪∈R$×,
8
Systems of Equation
expands to
𝐴”,”𝑥” + 𝐴”,#𝑥# + ⋯ + 𝐴”,!𝑥! = 𝑏” 𝐴#,”𝑥” + 𝐴#,#𝑥# + ⋯ + 𝐴#,!𝑥! = 𝑏#
…
𝐴$,”𝑥” + 𝐴$,#𝑥# + ⋯ + 𝐴$,!𝑥! = 𝑏$
𝑨𝒙 = 𝒃
• 𝑨is𝑚×𝑛and𝒙is𝑛×1
• A linear system of equations can have:
• No solution
• Many solutions
• Exactly one solution – only when 𝑚 = 𝑛
9
Matrix Operation – Inversion
1* 1 𝑨𝑨=𝑰𝑰=⋱
• Matrix inverse:
• Solving a system using an inverse:
1
𝑨𝒙 = 𝒃 ⇒ 𝑨1*𝑨𝒙 = 𝑨1*𝒃 ⇒ 𝒙 = 𝑨1*𝒃
• Matrix can only be inverted if it is a square matrix and all the rows/columns are linearly independent
• Orthogonal matrix:
𝑨⏉𝑨=𝑨𝑨⏉ =𝑰 𝑨-” = 𝑨⏉
10
Matrix Operation – Determinant
• Determinant of a square matrix maps the matrix to a scalar, denoted by det𝐴 or|𝐴|
Image taken from wikipedia
• Measures how much multiplication by the matrix expands or contracts the space.
• Useful Properties:
det(𝑨𝑩) = det 𝑨 det(𝑩) det𝑨⏉ =det𝑨
11
Eigenvalues and Eigenvectors
• An eigenvector of a square matrix 𝐴 is a nonzero vector 𝒗 such that left multiply by 𝑨 only changes the scale of 𝒗.
𝑨𝒗 = 𝜆𝒗
• The scalar λ is known as the eigenvalue.
• If we rescale the eigenvector 𝒗 by a constant c, c𝒗 remains the eigenvector of 𝑨 of the same eigen
value λ. As such, we often use eigenvector to be
of unit length:
𝒗=1
12
Characteristic Polynomial
• Eigenvalue equation of matrix 𝑨:
𝑨𝒗 = 𝜆𝒗 ⇒ 𝑨𝒗 − 𝜆𝒗 = 0 ⇒ 𝑨 − 𝜆𝑰 𝒗 = 0
• If nonzero eigenvector 𝒗 exists:
det𝑨−𝜆𝑰 =0
• By expanding the determinant as a function of 𝜆, we often get: det(𝑨−𝜆𝑰)= 𝜆”−𝜆 𝜆#−𝜆 … 𝜆!−𝜆 =0
• The 𝜆”, 𝜆#, … , 𝜆! are roots of the characteristic polynomial, and are eigenvalues of 𝑨
13
Example
• Consider the matrix:
• The characteristic polynomial is:
𝑨=
21 12
det 𝑨 − 𝜆𝑰 = 𝑑𝑒𝑡 2 − 𝜆
• Ithasroots𝜆=1and𝜆=3whicharethetwoeigenvaluesof𝑨.
1
1 2−𝜆
= 3 − 4𝜆 + 𝜆# = 0
• We can then solve for eigenvectors using 𝑨𝒗 = 𝜆𝒗:
𝒗./”= 1,−1⏉
and 𝒗./* = 1,1 ⏉
14