Math Flashcards
Define span S
Definition 34:
Let S be a subset of V. The subspace generated by S, denoted by span S, is the smallest vector subspace of V containing S. It coincides with the intersection of all vector subspaces of V
Define a basis
Definition 40:
A set of vectors S of V is said to be a basis of V is S is a linearly independent set such that span S = V
Define dimension
Definition 46:
A vector space is said to have finite dimension if it has a basis with a finite number of elements
Definition 52:
The dimension of a finite dimensional vector space V is the number of elements of a basis of V
Define a linear functional
Definition 57:
A function L that maps from a vector space to real values is called a functional. It is linear if it satisfies the ‘decomposition’ property.
Define dual space of linear functionals
Definition 65:
The set of all linear functionals defined on a vector space V is called dual space of V and is denoted by V’
What is the relation between dimension of vector space V and its dual space V’
dim V = dim V’
Define a linear operator
Definition 82:
A function T that maps from V1 to V2 is called an operator. It is linear if it satisfies the ‘decomposition property’
Define the product of two linear operators T and S
(ST)(v) = S(T(v))
What is an isomorphism?
Definition 106:
Two vector spaces V1 and V2 are called isomorphic if there exists a linear bijective operator T. Such operator is called an isomorphism
What is the law of one price?
If two portfolios have the same future payoff across states, they must have the same value
Define when (L, p) satisfies the Law of One Price
If for all portfolios x, x’ in R^n,
R(x) = R(x’) => v(x) = v(x’)
Define a metric space
Definition 138: A space X is called a metric if there exists a positive function d: X x X --> [0, +inf), called distance (or metric), such that, for each x, y, z belonging to X, i) d(x,y) = 0 iff. x = y ii) d(x,y) = d(y,x) iii) d(x,y) <= d(x,z) + d(z,y)
Define the neighborhood to a point x in X of radius e
B_e(x) = {y in X: d(x,y)
Define an interior point and an isolated point
See page 78
Define a boundary point and an accumulation point
See page 78
Define, for a given set A, its closure
The closure of A is given by the union of A with its set of frontier points
Define a sequence
Definition 177:
A sequence of points {xn} of a metric space X converges to x if for each neighborhood of x, there exists n_epsilon>=1 such that xn is in this neighborhood for each n>=n_epsilon
Define a Cauchy Sequence
See page 92 (extension of definition 177)
What is the term for a metric space in which Cauchy sequences are convergent.
Complete
Is the space R^N with any of the metrics d1, d2, d_inf complete?
Yes by Theorem 196
Is the space of C([0,1]) complete?
Yes under the infinity metric by Theorem 197
But not under the d_1 metric!
Define compactness in calculus
Closed and bounded sets, e.g. interval [a,b]
Define an open cover
An open cover of A is any collection of open sets {Gi} such that A is a subset of the union of all Gi
Define a finite subcover
A finite subcover of A is a finite collection of sets, {G1,..,Gn}, taken from the open cover {Gi} that are still able to cover A so that A is a subset of the finite union of the open sets, Gi
Define a compact space
A metric space X is compact if X itself is a compact set
Are compact metric spaces complete?
Yes (by the Bolzano-Weierstrass property; a subset A of a metric space if compact iff. each sequence of A has at least a subsequence that converges to a point in A)
Define total boundedness
A metric space X is totally bounded, if for each epsilon>0, there exists a finite collection of points xi of X such that X = finite union of all neighborhoods of xi
Define the limit of a function
See page 101
Define continuity of a function
See page 103
Under the discrete metric, are singletons closed or open?
Singletons are then open sets
What is the Heine-Borel theorem on compact sets?
A subset of R^n is compact iff. it is closed and bounded under any metric (d1, d2, d_inf)
What is the Bolzano-Weierstrass theorem on compact sets?
A subset A of a metric space is compact if and only if it has the Bolzano-Weierstrass property, that is, each sequence of points of A has at least a subsequence that converges to some point of A.
What is the definition of the rank of a matrix?
The rank of a matrix is defined as (a) the maximum number of linearly independent column vectors in the matrix or (b) the maximum number of linearly independent row vectors in the matrix. Both definitions are equivalent.
If two finite dimensional vector spaces have the same dimension are they then isomorphic?
Yes! Theorem 111
How can we construct a basis for P
See solution to exercise set 2
How do we evaluate linear independence of an infinite set?
Definition 26:
An infinite set S of vectors of a vector space V is said to be linearly independent if each finite subset of vectors of S is linearly independent. Otherwise, S is said to be linearly dependent.
What is a monomial?
A polynomial with one term
Define a norm.
Definition 245:
Given a vector space V, a positive functional || ‘ ||: V -> [0,inf) is said to be a norm if it satisfies;
1) || v || = 0 iff. v = 0
2) || v + w || <= || v || + || w || for each v,w in V
3) || av || = |a| || v ||
It is a real-number. It can be viewed as the distance of a vector’s furthest point from the origin (in a metric sense). Or the length of the vector defined under some norm.
Define a normed vector space.
Definition 247:
A vector space V endowed with a norm is called a normed vector space
What are two remarkable properties of the distance induced by a norm wrt. the two vector operations of addition and scalar multiplication?
1) Translation invariant
d(v+x,w+x) = d(v,w)
2) Homogeneous
d(av,aw) = |a|*d(v,w)
Can the discrete metric be induced by any norm?
No. The discrete metric can be defined on any vector space but is not induced by any norm.
Can we use all the topological notions of metric space on normed vector spaces?
Yes since a normed vector space have a natural metric structure
Define a neighborhood in a normed vector space.
B_epsilon(v) = {w in V: || v - w || < epsilon}
Define a Banach Space.
Definition 252:
A normed vector space whose metric is complete is called a Banach Space (vector sequence that is Cauchy and converges)
Give 4 examples of Banach Spaces.
Page 112
For a linear operator between two normed vector spaces, what can we say if it is continuous at a point?
It is logically equivalent to being continuous on all of the domain vector space
Define boundedness in normed vector spaces.
Definition 260:
An operator T : V1 -> V2 between normed vector spaces is said to be bounded if there exists a scalar
K > 0 such that:
|| T(v) ||_2 <= K || v ||_1, for all v in V1
By lemma 261: A linear operator is bounded if and only if it is bounded in the traditional Calculus sense when restricted to the closed unit ball.
What is the relation between continuity and boundedness for a linear operator between normed vector spaces?
Theorem 263:
They are logically equivalent.
What is the topological dual space of V?
The set of all linear and continuous functionals defined on a normed vector space. It is denoted V*. The space V’ (for the dual space for linear functionals on any space) is often called the algebraic dual space of V. Hence, the topological dual space is a vector subspace of the algebraic dual space
If V_2 is a Banach space (complete nvs), what can we say about the normed vector space (B(V_1,V_2), || ‘ ||)?
Theorem 273:
It is also a Banach space
What are the inequalities we have to verify for a metric and norm respectively?
Triangular inequality = metric
Cauchy-Schwartz inequality = norm
Define a well-posed function.
If f is invertible and the inverse is continuous. Well posed equations thus feature unique “robust” results
Four problems to view from a function.
Direct
Causation
Identification
Induction
Where causation, identification and induction are all inverse problems
Which spaces are we dealing with when we are talking operator equations.
Vector spaces X and Y
What equations systems under what vector spaces can be solved by searching for fixed points?
Operator equations that are self-maps
Define the Banach contraction theorem
Definition 318:
A selfmap T: X –> X defined on a metric space X is a contraction if there exists a scalar 0<a></a>
What role does completeness play in the Banach Contraction theorem?
Theorem 320 (Banach): Completeness ensures the existence of fixed points of contractions
Is being a contraction on a complete metric space a sufficient or necessary condition for the existence of a unique and globally attracting fixed point?
It is a sufficient condition but not necessary.
E.g. f(x) = 2 + sqrt(x)
What conditions do we require for applying Weierstrass to determine if a max/min exists?
The set be compact.
The function f being continuous
How do we check for an alpha-contraction on a matrix?
See if there is a common scalar on A that is in the interval (0,1)
Define a maximum
Definition 362:
Page 183
Analogous considerations hold for the points of minimum
Define a a point of strict maximum
Definition 363:
Page 184
Analogous considerations hold for the points of minimum
What do we call solutions to problems of optimum?
Maximum or Minimum
Strong if extreme points are unique
What does the Weierstrass theorem ensure?
The existence of both points of maximum and minimum for continuous functions defined on compact sets. This all important result thus requires a metric structure on the space X
The hypothesis of continuity and compactness cannot be weakened
Define a correspondence
See chaper 12
Define convexity of a set C for a vector space.
See p. 213
What is the natural domain for concave functionals?
Convex sets of a vector space V. So when talking about concavity, we refer to a property of the functional and not the set, which is convex
Define the graph of a function
See page 225
Define the ipograph of a function
See page 225
State the Jensen inequality
See page 226
What is the remarkable property of concave functions when solving optimization problems?
If we find a local maximum, then it is a global maximum!
Theorem 461
Strict concavity is the simplest condition that guarantees the uniqueness of the point of maximum
Describe the general form of discrete time optimization.
See page 239
What is a uniquely controlled DP system?
If there is a unique d_t (decision) in our correspondence
So, it is as if, we are back-solving for the decision that satisfies for us to move from x to y and that this decision is unique
When the problem is not uniquely controlled, there is a correspondence G: X x X –> 2^D such that any d in G(x,y) is in the p(x) is a current available decision that moves the system from the current state x to the next period state y (see page 241)
What are the two primary interests for a reduced form of a discrete period optimization problem?
1) It may be easier to solve than the original DP
2) different problems DP may share a similar reduced form => common structure across problems
Define the convex hull of a set.
Formally, the convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. Convex hulls of open sets are open, and convex hulls of compact sets are compact. Every convex set is the convex hull of its extreme points. The convex hull operator is an example of a closure operator, and every antimatroid can be represented by applying this closure operator to finite sets of points.
What is a sufficient condition for a function, w : X –> R, must satisfy to be a solution to the Bellman equation?
It must be a bounded function, and then it is automatically the value function
Describe the essence of dynamic programming.
1) compute the value function by solving the Bellman equation (e.g. through the value function iteration)
2) find the solutions through sequential optimization
What is the optimal policy correspondence?
The optimal policy correspondence describes the evolution of the optimal path for problem RF
What does the space B(X) denote?
Space of bounded functions over a non empty set X
