Vector spaces & Linearity

Paul Schrimpf

04 November, 2019

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License

Vector Spaces

Vector Space

  • Set \(V\), operations \(+:V \times V \to V\) and \(\cdot: \mathbb{R} \times V \to V\) such that
    • \((V,+)\) is commutative group: \(\forall x,y,z \in V\)
      1. (Algebraically) closed: \(x + y \in V\)
      2. Associative: \((x + y) + z = x + (y+z)\)
      3. Identity: \(\exists 0 \in V\) such that \(x + 0 = x\)
      4. Invertible: \(\exists -x \in V\) such that \(x + (-x) = 0\)
      5. Commutative: \(x + y = y + x\)
    • Scalar multiplication has properties on next slide

Vector Space

  • Set \(V\), operations \(+:V \times V \to V\) and \(\cdot: \mathbb{R} \times V \to V\) such that
    • \((V,+)\) is commutative group
    • Scalar multiplication is: \(\forall \alpha, \beta \in \mathbb{R}\)
      1. Closed: \(\alpha x \in V\)
      2. Distributive: \(\alpha(x + y) = \alpha x + \alpha y\) and \((\alpha + \beta) x = \alpha x + \beta x\)
      3. Consistent with multiplication in \(\mathbb{R}\): \(1x = x\) and \((\alpha \beta) x = \alpha (\beta x)\)


  • \(\mathbb{R}^n\)
  • Spaces of sequences
  • Spaces of functions


  • \(S \subseteq V\) is a linear subspace if \(\forall x,y \in S\) and \(\alpha \in \mathbb{R}\) \[ \alpha x + y \in S \]
  • Examples

Linear Combinations

  • \(\mathbf{x}_1,..., \mathbf{x}_k \in V\), linear combination is \[c_1 \mathbf{x}_1 + ... + c_k \mathbf{x}_k \] where \(c_1, ..., c_k \in \mathbb{R}\)

  • span of \(W \subseteq V\) is set of all linear combinations of elements of \(W\)

    • is a linear subspace

Linear independence

  • \(W \subseteq V\) is linearly independent if \[ \sum_{j=1}^k c_j \mathbf{x}_j = 0 \] implies \(c_1 = c_2 = ... = c_k = 0\) for any \(k\) and \(\mathbf{x}_1, ..., \mathbf{x}_k \in W\)
  • Dimension of a vector space is the cardinality of the largest set of linearly independent elements
  • Basis \(B \subseteq V\) is a set of linearly independent elements that span \(V\)
  • Should show dimension is well-defined and basis exists

Any basis has the same cardinality

  • Lemma: If \(A\) and \(B\) are bases for \(V\), then \(|A| = |B|\)

    • \(A\) basis means for each \(\mathbf{b} \in B\), \(\exists\) finite \(A_b \subset A\) and \(x_{a,b} \in \mathbb{R}\) such that \(\mathbf{b} = \sum_{\mathbf{a}\in A_b} x_{a,b} \mathbf{a}\)
    • \(B \cup (A \setminus \cup_{b \in B} A_b)\) is linearly independent, so \(A = \cup_{b \in B} A_b\)
    • \(|A| \leq |B|\)

Basis exists

  • Lemma: Let \(V\) be a vector space, then \(\exists\) a basis

    • \(\exists L \subseteq V\) s.t \(L\) linearly independent
    • Define \(\mathcal{P} = \{S \subseteq V: L \subseteq S \text{ and } S \text{ linearly independent}\}\)
    • \(\mathcal{P}, \subseteq\) is partially ordered
    • \(\overline{C} = \cup_{S \in \mathcal{C}} S\) is upper bound for chain \(\mathcal{C}\)
    • By Zorn’s lemma, \(\exists\) maximal \(B \in \mathcal{P}\)
    • Span\((B) = V\)

Linear independence

  • Lemma: Let \(B\) be a basis for a vector space \(V\). Then \(\forall \mathbf{x} \in V\) there exists a unique \(x_1, ..., x_k \in \mathbb{R}\) and \(b_1, ..., b_k \in B\) such that \(\mathbf{x} = \sum_{i=1}^k x_i b_i\)
  • \(\mathbb{R}^n\) is the only finite dimensional vector space

Normed Vector Spaces

Normed Vector Space

  • \(\Vert \cdot \Vert:V \to \mathbb{R}\) s.t.
    • \(\Vert v \Vert \geq 0\), \(=0\) iff \(v=0\)
    • \(\Vert \alpha v \Vert = |\alpha| \Vert v \Vert\)
    • \(\Vert v_1 + v_2 \Vert \leq \Vert v_1 \Vert + \Vert v_2 \Vert\)
  • Gives a metric \(d(v_1,v_2) = \Vert v_1 - v_2 \Vert\)

Normed Vector Spaces

  • \(\mathbb{R}^n\) with \(\Vert \mathbf{x} \Vert = \sqrt{\sum_{i=1}^n x_i^2}\)
  • \(\ell_p =\) infinite sequences s.t. \[ \Vert x\Vert_p = \left( \sum_{i=1}^\infty |x_i|^p \right)^{1/p} < \infty \]
  • \(\mathcal{L}_p([0,1]) = \{f:[0,1] \to \mathbb{R}\}\) s.t. \[ \Vert f \Vert_p = \left(\int_0^1 |f(x)|^p dx\right)^{1/p} < \infty \]

Linear Transformations

Linear Transformations

  • \(A:V \to W\) s.t. \(\forall v_1,v_2\in V\,,\,\alpha \in \mathbb{R}\)
    • \(A(v_1 + v_2) = Av_1 + Av_2\)
    • \(A(\alpha v_1 ) = \alpha A v_1\)
  • Represented as matrices when \(V\) and \(W\) finite dimensional

Linear Transformations

  • Examples:
    • Integration: \(V = \{f:[0,1] \to \mathbb{R} s.t. \int_0^1 |f(x)|dx < \infty \}\), \(A:V \to \mathbb{R}\) \[ Af = \int_0^1 a(x) f(x) dx \] with \(\sup_{x \in [0,1]} |a(x)| < \infty\)

Linear Transformations

  • Examples:
    • Differentiation: \(C^k([0,1]) =\) \(\{f:[0,1] \to \mathbb{R} \;,\; f \text{ k times cont differentiable}\}\)

    • \(D:C^1([0,1]) \to C^0([0,1])\), \[ (Df)(x) = \frac{df}{dx}(x) \]

Linear Transformations

  • Examples:
    • Conditional expectation

Vector space of linear transformations

  • \(L(V,W) =\) { linear transformations from \(V\) to \(W\) }
  • Addition: \((A + B)(v) = Av + Bv\)
  • Scalar multiplication: \(A(\alpha v) = \alpha Av\)

Matrix multiplication=composition of linear transformations

  • \(A : V \to W\), \(B: X \to V\)
  • \(V\) is \(n\) dimension with basis \(f_j\)
  • \(W\) is \(m\) dimension with basis \(e_i\)
  • \(X\) is \(p\) dimension with basis \(g_k\)

Matrix multiplication=composition

\[ \begin{aligned} A(B g_k) = & A (\sum_{j=1}^n b_{jk} f_j) = \sum_{j=1}^n b_{jk} A f_j \\ = & \sum_{j=1}^n b_{jk} \left(\sum_{i=1}^m a_{ij} e_i\right) = \sum_{i=1}^m \left(\sum_{j=1}^n a_{ij} b_{jk} \right) e_i \\ = & \begin{pmatrix} \sum_{j=1}^n a_{1j} b_{j1} & \cdots & \sum_{j=1}^n a_{1j} b_{jp} \\ \vdots & \ddots & \vdots \\ \sum_{j=1}^n a_{mj} b_{j1} & \cdots & \sum_{j=1}^n a_{mj} b_{jp} \end{pmatrix} g_k \\ = & (AB)g_k . \end{aligned} \]

Null space and range

  • \(A \in L(V,w)\), null space of \(A\) \[ null(A) = \{x \in V: Ax = 0\} \subseteq V \]
  • range of \(A\) \[ range(A) = \{Ax: x \in V\} \subseteq W \]

Dual Spaces

Dual Spaces

  • Dual space of \(V\), \(V^\ast = \{ v^\ast: V \to \mathbb{R} s.t. v^\ast \text{ continuous} \}\)
  • Example: \({\mathbb{R}^n}^\ast \simeq \mathbb{R}^n\)
  • Prices are elements of a dual space
  • Example: \({\mathcal{L}^p}^\ast \simeq \mathcal{L}^q\) where \(1/p + 1/q = 1\)


  • \(A: V \to W\), the transpose is \(A^T:W^\ast \to V^\ast\) defined by \[ (A^T w^\ast)v = w^\ast (Av) \]

Separating hyperplane theorem


  • Hyperplane \(H_{\xi,c} = \{x \in V: \xi x = c\}\) where \(c \in \mathbb{R}\) and \(\xi \in V^\ast\)

    • is affine i.e. \(\forall x, y \in H_{\xi,c}\) and \(\lambda \in \mathbb{R}\), \(\lambda x + (1-\lambda)y \in H_{\xi,c}\)


  • \(S \subseteq V\) is convex if \(\forall x, y \in S\) and \(\lambda \in (0,1)\), we have \(x \lambda + y(1-\lambda) \in S\)

Separating hyperplane theorem

  • If \(S_1\) and \(S_2 \subseteq V\) are convex and \(S_1 \cap S_2 = \emptyset\) and either \(V\) is finite dimensional or the interior of \(S_1\) or \(S_2\) is not empty. Then there exists a hyperplane, \(H_{\xi c} = \{ x: \xi x = c \}\) such that \[ \xi s_1 \leq c \leq \xi s_2 \] for all \(s_1 \in S_1\) and \(s_2 \in S_2\). We say that \(H_{\xi,c}\) separates \(S_1\) and \(S_2\).

Lagrange multipliers exist

  • Let \(V\) and \(W\) be normed vector spaces, \(A \in B(V,\mathbb{R})\) and \(C \in B(V,W)\). Assume that \(range(C)\) is closed. Then \(null(A) \supseteq null(C)\) if and only if \(A = \mu C\) for some \(\mu \in W^*\)

Farkas’ Lemma

Let \(A\) be an \(m\) by \(n\) matrix and \(b \in \mathbb{R}^m\) either:

  1. \(\exists x = (x_1, ..., x_n) \in \mathbb{R}^n\) such that \(x_1 \geq 0, ..., x_n \geq 0\) and \(Ax = b\) or
  2. \(\exists y \in \mathbb{R}^m\) such that \(y^T A e_i \geq 0\) for each standard basis vector \(e_i \in \mathbb{R}^n\) and \(y^T b < 0\)

but not both.

Welfare theorems


  • Set of commmodities \(S\), a normed vector space
  • \(I\) consumers with preference relations \(\succeq_i\)
  • \(J\) firms with production possibility sets \(Y_j\)
  • Allocation \((x,y) \in S^{I + J}\)
    • Feasible if \(y_j \in Y_j\) and \(\sum_i x_i = \sum_j y_j\)

Pareto efficient

  • \((x^0,y^0)\) Pareto efficient if feasible and no other feasible allocation such that \(x_i \succeq_i x_i^0\) for all \(i\) and \(x_i \succ_i x_i^0\) for at least one \(i\)

Competetive equilibrium

Allocation \((x^e,y^e)\) and price, \(p \in S^*\) such that

  1. \((x^e,y^e)\) feasible
  2. Consumers maximize \(px \leq p x_i^e\) implies \(x_i^e \succeq_i x\)
  3. Firms maximize, \(y \in Y_j\) implies \(py \leq p y_j^e\)

Preference properties

  • Local non-satiation : for each \(x\) and \(\epsilon>0\) \(\exists x'\) such that \(\Vert x-x' \Vert \leq \epsilon\) and \(x' \succ_i x\)
  • Convex : if \(x \succeq_i z\) and \(y \succeq_i z\), \(\lambda \in [0,1]\) then \(\lambda x + (1-\lambda) y \succeq_i z\)
  • Continuous : for any \(x \succ_i z\) \(\exists \delta > 0\) such that for all \(x' \in N_\delta(x)\), \(x' \succ_i z\)

First Welfare theorem

If \((x^e,y^e)\) and \(p\) is a competitive equilibrium and preferences a locally non-satiated, then \((x^e,y^e)\) is Paretor efficient.

Second Welfare theorem

If preferences are locally non-satiated, convex, and continuous, and \((x^e, y^e)\) is Pareto efficient, then \(\exists p \in S^*\) such that \((x^e,y^e)\) and \(p\) is a competitive equilibrium.