background info

Question 1

O(g(n)):

Answer 1

f(n) in O(g(n)) as n->∞ if there exists constant C>0 and an integer n0 such that |f(n)|<=C|g(n)| for n>n0

Question 2

O(g(x)):

Answer 2

f(x) in O(g(n)) as x->0 if there exists a constant C>0 and a real number ε>0 such that |f(x)|<=C|g(x)| for |x|<ε

Question 3

Ω(g(n))/Ω(g(x)):

Answer 3

just g(n/x) in O(f(n/x)), everything else the same

Question 4

o(g(n/x)):

Answer 4

is good for All C

Question 5

coordinate of a vector:

Answer 5

xi in x basically, digits

Question 6

e vector:

Answer 6

vector with all coordinates = 1

Question 7

inner product:

Answer 7

|x,y|=(n)Σ(i=1)xiyi

Question 8

bilinear:

Answer 8

|x, ay1+by2|=a|x,y1|+b|x,y2|

Question 9

orthogonal:

Answer 9

|x,y|=0

Question 10

linear subspace:

Answer 10

subset V in R^n such that for any x,y in V and a,b in R, ax+by in V (so all linear combos in V)

Question 11

linear combo:

Answer 11

of vectors x1,…,xn in R^n, of the form y=(k)Σ(i=1)λixi, λi in R

Question 12

span:

Answer 12

set of linear combos, forms a linear subspace in R^n

Question 13

linearly independent:

Answer 13

(k)Σ(i=1)λixi = 0

Question 14

basis:

Answer 14

minimal set of vectors that spans a linear subspace, elements are always linearly independent, basically from unique linear combos of these the entire subspace can be described

Question 15

dimension:

Answer 15

no. of elements in a basis

Question 16

orthogonal basis:

Answer 16

|bi,bj|=0 (i!=j)

Question 17

orthonormal basis:

Answer 17

orthogonal and |bi,bi|=1

Question 18

standard basis:

Answer 18

orthonormal basis {e1,…,en} where ei has 1 in ith column and 0 otherwise

Question 19

direct sum:

Answer 19

of vector spaces that don’t intersect, V⊕W={v+w: v in V, w in W}

Question 20

orthogonal complement:

Answer 20

of a subspace V, just all vectors that are orthogonal to smth in V, written V^⊥, V⊕V^⊥=R^n

Question 21

direct product:

Answer 21

VxW={(v,w) in R^(n+m): v in V, w in W} (V in R^n, W in R^m) where (v,w) is just. w tacked on the end of v

Question 22

linear map:

Answer 22

a mxn matrix makes a linear map from R^n to R^m with y=Ax, yi=(n)Σ(j=1)aijxj

Question 23

symmetric:

Answer 23

a matrix is symmetric when A=A^T

Question 24

matrix multiplication:

Answer 24

C=AB where cij=(p)Σ(k=1)aikbkj

Question 25

⟨x,y⟩:

Answer 25

x^(T)y

Question 26

rank of a matrix:

Answer 26

rk(A), max number of linearly independent rows/columns

Question 27

kernel:

Answer 27

kerA:={x in R^n: Ax=0}, dim(kerA)=n-rk(A)

Question 28

image:

Answer 28

ImA={Ax: x in R^n}, dim(ImA)=rk(A), (kerA)^⊥=ImA^T

Question 29

system of linear equations:

Answer 29

aijxj=bi but several systems of sums -> Ax=b where x and b are vectors, if the columns of A are lin independent, there’s at most 1 solution, there’s infinite otherwise

Question 30

conditions of a matrix that are equivalent:

Answer 30

A is invertible
rk(A)=n
kerA={0}
ImA=R^n
the rows are linearly independent
the columns are linearly independent
det(A)!=0

Question 31

det(A):

Answer 31

Σsgn(σ)a(↓1σ(1))…a(↓nσ(n)) where Sn is the group of permutations of [n]={1,…,n} with sgn(σ) the sign, the parity of the no. of inversions
example - for A=
(a11 a12
a21 a22)
det(A)=a11a22-a12a21
also all the eigenvalues multiplied together

Question 32

orthogonal matrix:

Answer 32

⟨qi,qj⟩=δij, δij=1 if i=j and 0 otherwise, alternatively Q^(T)Q=QQ^T=1
⟨Qx,Qy⟩=⟨x,y⟩, det(Q)=1

Question 33

eigenvector:

Answer 33

u in Au=λu, u!=0, λ is the eigenvalue

Question 34

characteristic polynomial:

Answer 34

det(λI-A)=0, eigenvalues are the roots

Question 35

trace:

Answer 35

sum of the diagonal elements, also sum of the eigenvalues

Question 36

norm:

Answer 36

a function that satisfies:
||x||>=0 and ||x||=0 iff x=0
||λx||=|λ| ||x|| for all λ
||x+y||<=||x||+||y||

Question 37

||x||1:

Answer 37

1 norm, (n)Σ(i=1)|xi|

Question 38

||x||2:

Answer 38

2 norm, ((n)Σ(i=1)(xi)^2)^(1/2)

Question 39

||x||∞:

Answer 39

max(|xi|), 1<=i<=n

Question 40

(||x||2)^2:

Answer 40

euclidean norm, x^(T)x=⟨x,x⟩ (inner product)

Question 41

unit sphere (with respect to a norm):

Answer 41

{x in R^n: ||x||=1}

Question 42

unit ball:

Answer 42

{x in R^n: ||x||<=1}, closed

Question 43

norms relations:

Answer 43

||x||∞<=||x||2<=root(n)||x||∞
||x||∞<=||x||1<=n||x||∞

Question 44

cauchy-swartz inequality:

Answer 44

⟨x,y⟩<=||x||2||y||2, with equality iff x and y are linearly dependent
also -1<=⟨x,y⟩/||x||2||y||2<=1

Question 45

angle:

Answer 45

angle between vectors x and y is θ such that cos(θ)=|x,y|/||x||2||y||2
if x and y are orthogonal, cosθ=0

Question 46

matrix norm:

Answer 46

fits all the vector norm conditions and also ||AB||<=||A||||B||

Question 47

matrix and vector norm relation:

Answer 47

given ||x||, ||A||=max(||Ax||/||x||)=max(||Ax||), x:||x||<=1

Question 48

||A||1:

Answer 48

maxj((n)Σ(i=1)|aij|)

Question 49

||A||∞:

Answer 49

maxi((n)Σ(j=1)|aij|)

Question 50

||A||2:

Answer 50

root(λ(max)(A^(T)A)), where λ(max) is the largest eigenvalue of A^(T)A
so when A is symmetric, ||A||2=λ(max)(A)

Question 51

dual norm:

Answer 51

||x||*=max⟨x,y⟩, y:||y||<=1

Question 52

frobenius norm:

Answer 52

||A||F=root((n)Σ(i,j=1)(aij)^2)

Question 53

orthogonal invariant:

Answer 53

2 norm and frobenius norm are, so for any Q in O(n), ||QA||2=||AQ||2=||A||2, same with F instead of 2

Question 54

positive semidefinite:

Answer 54

A is symmetric, x^(T)Ax>=0, written A⪰0, is positive definite if that’s >0, also all eigenvalues are nonnegative (and positive for definite)

Question 55

⟨x,y⟩A:

Answer 55

⟨x,Ay⟩=x^(T)Ay

Question 56

||x||A:

Answer 56

root(⟨x,x⟩A)

Question 57

QR decomposition:

Answer 57

A is mxn, A=QR where Q is orthogonal and mxm and R is upper triangular and mxn

Question 58

LU decomposition:

Answer 58

A is nxn, A=LU where L is lower triangular nxn and U is upper triangular nxn

Question 59

symmetric eigenvalue decomposition:

Answer 59

A is symmetric, A=QΛQ^T where Q is orthogonal with eigenvectors as rows, and Λ is diagonal with eigenvalues on the diagonal

Question 60

cholesky decomposition:

Answer 60

A is positive definite symmetric, A=LL^T, L is nxn lower triangular with strictly positive diagonal entries

Question 61

singular value decomposition:

Answer 61

A is mxn, A=UΣV^T, where U is mxm orthogonal, V is nxn orthogonal, and Σ is a diagonal matrix with singular values σ1>=…>=σ↓min{m,n}, these are the square roots of the eigenvalues of A^(T)A

Question 62

singular values and norms:

Answer 62

||A||2=σ1(A)
||A||F=root((n)Σ(i=1)(σi(A)^2))
if A is symmetric, the singular values are the absolute values of the eigenvalues

Question 63

C^(k)([a,b]):

Answer 63

the set of functions continuous on [a,b] and whose first k derivatives exist and are continuous on (a,b)

Question 64

infimum:

Answer 64

inf(f(x))=max{y in R: for all x in [a,b], f(x)>=y} (largest y such that any f(x) is larger, a lower bound essentially)

Question 65

supremum:

Answer 65

sup(f(x))=min{y in R: for all x in [a,b], f(x)<=y} (smallest y such that any f(x) is smaller, an upper bound essentially)

Question 66

intermediate value theorem:

Answer 66

f in C([a,b]) and y satisfies inf(f(x))<=y<=sup(f(x)), then there exists ξ in [a,b] such that f(ξ)=y
basically because f is continuous and y is between the lowest and highest value f(x) can take, f must pass through y

Question 67

mean value theorem:

Answer 67

f in C^1([a,b]), x,x0 in (a,b) with x!=x0, then there exists ξ in (x0,x) (or (x,x0) whatever works) such that f(x)=f(x0)+f’(ξ)(x-x0)
rearranges to f’(ξ)=(f(x)-f(x0))/(x-x0)

Question 68

taylor expansion:

Answer 68

f in C^n([a,b]), x,x0 in (a,b) with x!=x0, then there exists ξ in (x,x0) or (x0,x) such that f(x)=(n)Σ(i=0)((f^(i)(x0)/i!)(x-x0)^i) + (f^(n+1)(ξ)/(n+1)!)(x-x0)^(n+1)
f^(n) meaning nth derivative

Question 69

rolle’s theorem:

Answer 69

special case of the mvt, f in C^1([a,b]) with f(a)=f(b), then there exists ξ in (a,b) such that f’(ξ)=0
if you start and end at the same elevation, there must be a flat part at the top or bottom of a hill (or the whole walk ig)

Question 70

integral mean value theorem

Answer 70

f,g in C([a,b]), f does not change sign on [a,b], then there exists ξ in (a,b) such that:
(b)∫(a)f(x)g(x)dx=g(ξ) (b)∫(a)f(x)dx

Question 71

open ball:

Answer 71

radius ε around point p in R^n, B^n(p,ε)={x: ||x-p||2<ε}

Question 72

open subset:

Answer 72

for every p in subset U, there exists ε>0 such that B(p,ε) entirely within U (can’t have overlapping boundaries)
a set C is closed if R^n\C is open

Question 73

closure:

Answer 73

clS of a set S within R^n, the intersection of all closed sets containing S

Question 74

interior:

Answer 74

intS of a set S within R^n, the union of all open sets contained in S

Question 75

boundary:

Answer 75

bdS=clS\intS

Question 76

unit sphere:

Answer 76

{x in R^n: ||x||2=1}, also the boundary of the unit ball

Question 77

neighbourhood:

Answer 77

a neighbourhood of a point x is a set N such that there exists an open set U with x in U within N

Question 78

span(S):

Answer 78

{(k)Σ(i=1)λixi, λ1,…,λk real and x1,…,xk in S}

Question 79

relatively open/closed:

Answer 79

S is relatively open/closed if it is open/closed in the induced topology on span
there also exists relative interior/closure

Question 80

compact:

Answer 80

a set is compact if it’s closed and bounded

Question 81

lipschitz continuous:

Answer 81

f:S->R, for all x,y in S, ||f(x)-f(y)||2<=L||x-y||2, L>0

Question 82

limit point:

Answer 82

a point x that is the limit of a subsequence

Question 83

cauchy sequence:

Answer 83

for every ε>0 there exists k0>0 such that for all k,l>k0, ||xk-xl||2<ε

Question 84

banach space:

Answer 84

a vector space where every cauchy sequence contains a convergent subsequence

Question 85

sets and limit points:

Answer 85

a set C is closed iff every sequence has all its limit points in C
the closure of C is the set of all limit points in C
a set C is compact iff every sequence of points has A limit point in C (so only at least 1, not all)

Question 86

differentiation (first principles):

Answer 86

lim(h->0)(||f(x0+h)-f(x0)-Jf(x0)h||2/||h||2)=0

Question 87

jacobian matrix:

Answer 87

Jf(x0)=(∂f1/∂x1……..∂fm/∂xn) (is a matrix you get it), the partial derivatives are evaluated at x0

Question 88

gradient:

Answer 88

∇f(x0)={∂f/∂x1,…,∂f/∂fxn}^T

Question 89

level set:

Answer 89

{x in R^2: f(x)=c}, the curve on which the function value does not change (the contour lines on a map)

Question 90

hessian matrix:

Answer 90

∇^(2)f(x0)={∂^(2)f/∂x1∂x1……∂^(2)f/∂xn∂xn) but matrix you get it, symmetric therefore square

Question 91

directional derivative:

Answer 91

Dx0f(x0) of f:R^n->R^m in direction v in R^n at x0 is Dvf(x0)=lim(h->0)(f(x0+hv)-f(x0)/h)

Question 92

directional derivative special cases:

Answer 92

v=ei, Deif(x0)=(∂f/∂xi)(x0), the partial derivative of xi at x0
if f:R^n->R with continuous derivative near x0, Dvf(x0)=∇f(x0)^(T)v=⟨∇f(x0),v⟩

Question 93

chain rule:

Answer 93

h=g(f(x)), Jh(x0)=Jg(f(x0))Jf(x0)

Question 94

chain rule and directional derivative:

Answer 94

if f’(x0)=v, then the derivative of g(f(x)) is the directional derivative of g in the direction of v, ⟨∇g(f(x0)),v⟩

Question 95

multivariate mean value theorem:

Answer 95

f in C^(1)(U), x0,x in U, x!=x0, then there exists t in (0,1) such that f(x)-f(x0)=⟨∇f(tx+(1-t)x0),x-x0⟩

Question 96

higher order partial derivative:

Answer 96

D^(a)f(x)=∂^(|a|)f(x)/∂^(a1)x1…∂^(an)xn, |a|=(n)Σ(i=1)ai
x^a=(x1)^(a1)…(xn)^(an)

Question 97

taylor expansion:

Answer 97

f(x)=(|a|<=k)ΣD^(a)f(x0)(x-x0)^a + (|a|=k)Σra(x)(x-x0)^a, ra(x)->0 as x->x0

Question 98

lagrange multipliers:

Answer 98

let x* be a maximum of f(x) under the constraint g(x)=c (so a max among all points x such that g(x)=c), then there exists a λ in R such that ∇f(x)=∇λg(x)

Question 99

lagrangian:

Answer 99

the lagrangian of a function f(x) with the constraint g(x)=c is the function Λ:R^(n)xR->R defined by Λ(x,λ)=f(x)-λ(g(x)-c)

Question 100

jacobian with respect to coordinates:

Answer 100

Jx(x0,y0)=the jacobian regular but all with (x0,y0) on the right to show with respect to
basically means we are considering f as a function only at (x0,y0) and taking all other coordinates (only the y’s are important?) as parameters

Question 101

implicit function theorem:

Answer 101

f:R^mxR^n->R^n and k times continually differentiable, assume f(x0,y0) is 0 and that the jacobian at (x0,y0) is nonsingular, then there exists an open neighbourhood y0 in Uy and function h in C^(k)(Uy,R^(n), such that h(y0)=x0, f(h(y),y)=0 for y in Uy
Jh(y)=-Jfy(h(y),y)(Jxf(h(y),y))^(-1) for all y in Uy

Question 102

absolute error:

Answer 102

Eabs(x^)=|x-x^| (x^ is an approximation and also an x with a hat)

Question 103

relative error:

Answer 103

Erel(x^)=|x-x^|/|x|

Question 104

floating point arithmetic:

Answer 104

x=+-f*2^e, f is a fraction in [0,1] and e is the exponent (not the 2.72 thing), f gets 52 bits e 11 and 1 for the sign for total 64 bits

Question 105

significant figures:

Answer 105

ikyk what these are but we are working with 4, also Important Note the final 0 counts as one if it’s to the right of the decimal point, so 1.2040 is Five significant figures, 1.204 is assumed to have stuff after that has been rounded to the 4