REVIEW
Linear Algebra
1
Matrices
Notation:
•
•
•
•
Matrices are denoted by bold uppercase letters
Aij denotes the entry in i th row and j th column
If A is n × m, it has n rows an m columns
If A is n × m, then A
6.3 1.0 2.2
3.6 4.7 8.9
A11
3.3 5.3 4.5
1.0 4.5 3 .4 . A32
Rn m
A =
4 × 3
A matrix is a 2-dimensional array
Î ´
2
Vectors
Notation:
•
•
•
Vectors are denoted by bold lowercase letters
ai denotes the ith entry
If a is m dimensional, then a
3.3
1.0
6.3
3.6
.
a2
a =A vector is a matrix with
many rows and one column
RmÎ
3
Transpose
Swap the rows and columns of a matrix
3 × 2 2 × 3
3
4
1
1 3
6 1
3 5
3 × 1 1 × 3
(A⊤)21
Properties of matrix transposes:
• Aij = (A⊤)ji
• If A is n × m, then A⊤ is m × n
A12
4
Addition and subtraction
These are element-wise operations
3 5
6 1
+
4 5
8 12
=
3 +4
6 +8Addition:
Subtraction:
5
1
—
4
3
=
5 —4
1 —3
5
Matrix scalar multiplication
We multiply each matrix element by the scalar value
3 3 5 4
6 1 2
=
9 15 12
3 618
—0.5 3
8
=
—1.5
—4
6
Matrix-vector multiplication
Involves repeated scalar products
1 4 3
6 1 2
4
2
—7
=
1 x 4 +4 x 2 +3 x (—7)=—9
6 x 4 +1 x 2 +2 x (—7)= 12
7
Matrix-vector multiplication
=
A w y
n × m m × 1 n × 1
ith row
yi equals scalar
product between ith
row of A and w
To perform inner products, # columns
in A must equal # rows of w
We repeat for each
row of A, so if A has
n rows, so does y
8
Matrix-matrix multiplication
Also involves several scalar products
18
9
Matrix-matrix multiplication
A B C
m × pn × m n × p
=
To perform inner products,
# columns in A must equal
# rows of B
ijC is scalar product
of ith row of A and
jth column of B
We repeat for each
row of A, so if A has
n rows, so does C
ith row
jth col
We repeat for each
column of B, so if B has p
columns, so does C
10
Matrix-matrix multiplication
m × pn × m n × p
Associative, i.e., (AB)C = A(BC)
Not commutative, i.e., AB ≠ BA
CBA
11
Identity matrix
One is the scalar multiplication identity, i.e., c × 1 = c
In is the n × n identity matrix, i.e., InA = A and AIm = A forany
n × m matrix A
Identity matrices are square, with ones on the diagonal entries
9 3 5
4 1 2
1 0 0
0 1 0
0 0 1
=
9 3 5
4 1 2
12
Inverse matrix
1/c is the scalar inverse, i.e., c × 1/c = 1
Multiplying a matrix by its inverse results in the identity matrix
•
•
For an n × n matrix A, A-1 denotes its inverse (when it exists)
AA-1 = A-1A = In
Only a square matrix (when n = m) can have an inverse
13
Euclidean norm for vectors
14
REVIEW
Big O Notation
15
Big O Notation
Describes how algorithms respond to changes in input size
•
•
Both in terms of processing time and space requirements We
refer to complexity and Big O notation synonymously
Required space proportional to units of storage
• Typically 8 bytes to store a floating point number
Required time proportional to number of ‘basic operations’
• Arithmetic operations (+, −, ×, /), logical tests (<, >, ==)
16
Big O Notation
Notation:
•
•
For large enough x, these terms won’t matter
E.g., x2+3x ≤ Cx2
f(x) =O(g(x))
• Can describe an algorithm’s time or space complexity
Informal definition: f does not grow faster than g
Formal definition: |f(x)| ≤ C|g(x)|
Ignores constants and lower-order terms
Nx >”
Nx >”
17
O(1) complexity
Constant time algorithms perform the same number of operations every
time they’re called
• E.g., performing a fixed number of arithmetic operations
Similarly, constant space algorithms require a fixed amount of storage every
time they’re called
• E.g., storing the results of a fixed number of arithmetic operations
EXAMPLE 1 :
18
O(n) complexity
Linear time algorithms perform a number of operations proportional to the number
of inputs
• E.g., adding two n-dimensional vectors requires O(n) arithmetic operations
Similarly, linear space algorithms require storage proportional to the size of the
inputs
• E.g., adding two n-dimensional vectors results in a new n-dimensional vector
which requires O(n) storage
EXAMPLE 2 :
19
O(n2) complexity
Quadratic time algorithms perform a number of operations proportional to the
square of the number of inputs
• E.g., outer product of two n-dimensional vectors requires O(n2) multiplication
operations (one per each entry of the resulting matrix)
Similarly, quadratic space algorithms require storage proportional to the square of
the size of the inputs
• E.g., outer product of two n-dimensional vectors requires O(n2) storage (one
per each entry of the resulting matrix)
EXAMPLE 3 :
20
Time and space complexity can differ
Inner product of two n-dimensional vectors
•
•
O(n) time complexity to multiply n pairs of numbers O(1)
space complexity to store result (which is a scalar)
Matrix inversion of an n × n matrix
•
•
O(n3) time complexity to perform inversion O(n2)
space complexity to store result
21
Matrix-vector multiply
Goal: multiply an n × m matrix with an m × 1 vector
Computing result takes O(nm) time
•
•
There are n entries in the resulting vector
Each entry computed via dot product between two m-dimensional vectors
(a row of input matrix and input vector)
Storing result takes O(n) space
• The result is an n-dimensional vector
EXAMPLE 1 :
22
Matrix-matrix multiply
Goal: multiply an n × m matrix with an m × p matrix
Computing result takes O(npm) time
•
•
There are np entries in the resulting matrix
Each entry computed via dot product between two m-dimensional vectors
Storing result takes O(np) space
• The result is an n × p matrix
EXAMPLE 2 :
23