Math 202A: Lecture 3

Here is a brief recap of Week 1. We defined combinatorics to be the branch of mathematics which studies the category \mathbf{FSet} whose objects are finite sets and whose morphisms are functions. We noted that a function f \in \mathrm{Hom}(X,Y) can be encoded as a matrix over \{0,1\}. This is done by choosing a labeling x_1,\dots,x_n of X, a labeling y_1,\dots,y_m of Y, and building the m \times n matrix [f] with entries

[f]_{ij} = \begin{cases} 1,\text{ if } f(x_j)=y_i \\ 0,\text{ otherwise}\end{cases}.

In data science, the matrix [f] is referred to as a one-hot encoding of the function f. The one-hot encoding of a function depends on a labeling of the points of its domain and codomain: a relabeling of X will cause [f] to be right-multiplied by an n \times n permutation matrix, while a relabeling of Y requires us to left-multiply [f] by an m \times m permutation matrix. Also note that if gf \in \mathrm{Hom}(X,Y) and g \in \mathrm{Hom}(Y,Z) then [g \circ f]=[g] \circ [f]. So we see that combinatorics can be encoded in terms of structured matrices defined over \mathbb{Z}_2.

We next defined linear algebra to be the study of the category \mathbf{FVec} whose objects are finite-dimensional complex vector spaces equipped with a scalar product, which we refer to these as Hilbert spaces, and whose morphisms are linear transformations between Hilbert spaces. We defined the quantization functor

\mathcal{F} \colon \mathbf{FSet} \longrightarrow \mathbf{FVec},

which sends each finite set X to the Hilbert space \mathcal{F}(X) of functions a \colon X \to \mathbb{C} equipped with the pointwise operations and scalar product

\langle a,b \rangle = \sum\limits_{x \in X} \overline{a(x)}b(x).

The Hilbert space \mathcal{F}(X) has an orthonormal basis consisting of the elementary functions

e_x(y) = \begin{cases} 1, \text{ if }x=y \\ 0, \text{ if } x\neq y \end{cases}.

Any function a \in \mathcal{F}(X) can be written as a linear combination of elementary functions,

a = \sum\limits_{x \in X} \alpha_x e_x,

where

\alpha_x = a(x)=\langle e_x,a\rangle.

Here we noted an alternative notation favored by algebraists: we simply write x instead of e_x, so that \mathcal{F}(X) becomes the space of formal \mathbb{C}-linear combinations of elements of X,

a= \sum\limits_{x \in X} \alpha_x x.

This saves us one layer of indexing, and it is a good notation for many purposes. When thought of in this way, \mathcal{F}(X) is referred to as the free vector space on the set X, and X sits inside \mathcal{F}(X) as an orthonormal basis. We will mostly use this formal notation going forward, although in other contexts (mostly analysis) the original functional notation is a better fit.

It remains to stipulate how \mathcal{F} transports morphisms in \mathbf{FSet} to morphisms in \mathbf{FVec}, i.e. how \mathcal{F} transforms functions between finite sets into linear transformations between Hilbert spaces. The recipe is so simple that it looks tautological: \mathcal{F} sends a given function f \in \mathrm{Hom}(X,Y) to the transformation \mathcal{F}(f) \in \mathrm{Hom}(\mathcal{F}(X),\mathcal{F}(Y)) defined by

[\mathcal{F}(f)]x = f(x), \quad x \in X.

Thus, if we choose an ordering x_1,\dots,x_n of X and an ordering y_1,\dots,y_m of Y so that X and Y become ordered orthonormal bases of \mathcal{F}(X) and \mathcal{F}(Y), the matrix of the linear transformation \mathcal{F}(f) relative to these bases is simply the one-hot encoding of the original function f,

[\mathcal{F}(f)] =[f].

The reason that this apparently tautological translation of a set function f into a linear transformation \mathcal{F}(f) is useful is that it gives us many, many more matrix representations. Indeed, the only operations we could perform on the one-hot encoding [f] are permuting its rows and columns. However, for the linear transformation \mathcal{F}(f) we can multiply on the left and/or right by arbitrary invertible matrices to get new representations of the same function which are more advantageous and reveal properties of the function f which are not apparent from the one-hot encoding. The fact that this can be done in a systematic way is the Singular Value Decomposition, which is in some sense the main theorem of Math 202A: it tells us we can always find orthonormal bases L \subset \mathcal{F}(X) and R \subset \mathcal{F}(Y) such that the matrix of \mathcal{F}(f) is real diagonal. The bases L and R are called the left singular vectors and the right singular vectors of \mathcal{F}(f), respectively, and the nontrivial entries of the corresponding diagonal form of \mathcal{F}(f) are called its singular values. In fact, this powerful result holds not just for transformations between Hilbert spaces which are functorial images of finite set functions, but for arbitrary linear transformations.

Next week, after a basic review of Hilbert spaces, we will move towards formulating and proving the SVD. In fact, for such a powerful result the proof is quite simple and straightforward, and in the case of linear transformations which come from set functions as above it has a nice interpretation in terms of bipartite graphs which is a good aid to intuition. We finish this week by introducing one more functor which transports us from the combinatorial category \mathbf{FSet} into a different part of mathematics.

Let X be any set, not necessarily finite. Recall that a binary relation on X is a subset of X \times X, the Cartesian square of X. This is a very general concept, and the binary relations that arise in practice are more structured. For example, a function f \colon X \times X is a special type of binary relation on X. Also familiar are equivalence relations. Formally, we say that R \subseteq X \times X is an equivalence relation if it is:

  • Reflexive: for all x \in X we have (x,x) \in \mathsf{R}.
  • Symmetric: for all x,y \in X we have (x,y) \in \mathsf{R} iff (y,x) \in \mathsf{R}.
  • Transitive: if x,y,z \in X are such that (x,y) \in \mathsf{R} and (y,z) \in \mathsf{R}, then (x,z) \in \mathsf{R}.

The simplest and most obvious example of an equivalence relation is equality,

R = \{(x,x) \colon x \in X\}.

A different type of equivalence relation generalizes our intuitive notion of inequality. A partial on X is an relation R \subseteq X \times X which is reflexive and transitive, but antisymmetric rather than symmetric: (x,y) \in R and (y,x) \in R iff x=y. For partial orders, the notation x \leq y is used to indicate that (x,y) \in R because it suggestively makes the antisymmetry into

x \leq y \text{ and }y \leq x \iff x=y.

A set X equipped with a partial order \leq is called a partially ordered set, often abbreviated to poset. If X and Y are posets, a function f \colon X \to Y is said to be order-preserving if

x_1 \leq x_2 \text{ in }X \implies f(x_1) \leq f(x_2) \text{ in }Y.

We can now give a categorical definition of one more branch of mathematics.

Definition 3.1. Order theory is the study of the category \mathbf{PSet} whose objects are posets and whose morphisms are order-preserving functions.

We now define a functor

\mathcal{P} \colon \mathbf{Set} \longrightarrow \mathbf{PSet}

as follows. First, for any set X we declare

\mathcal{P}(X) = \{S \subseteq X\},

so \mathcal{P}(X) is the power set of X. We equip \mathcal{P}(X) with the partial order defined by set containment,

S \leq T \iff S \subseteq T.

If I was allowed to assign problems on Fridays, I would ask you to verify that the above really is a partial order; this is easy but worth doing. In order for \mathcal{P} to be a functor, it remains to stipulate how it acts on morphisms in \mathbf{Set}, i.e. how it converts a function f \colon X \to Y between sets into an order-preserving function \mathcal{P}(f) \colon \mathcal{P}(X) \to \mathcal{P}(Y). As with the functor \mathcal{F}, the recipe is extremely simple: if S \in \mathcal{P}(X) is a subset of X, we simply define

[\mathcal{P}(f)](S) = f(S) = \{f(x) \colon x \in S\}.

If not for the Friday ban I would ask you to verify that \mathcal{P}(f) \colon \mathcal{P}(X) \to \mathcal{P}(Y) is an order-preserving function, but I don’t want to risk a civil rights case.

In fact, \mathcal{P}(X) is a special kind of poset in which every pair of elements has both a least upper bound and a greatest lower bound defined by

\sup(S,T) = S \cup T \quad\text{ and }\quad \inf(S,T) = S \cap T.

A poset equipped with a sup and an inf is called a lattice. We define the category \mathbf{Lat} to be the full subcategory of \mathbf{PSet} whose objects are lattices, so that in fact

\mathcal{P} \colon \mathbf{Set} \longrightarrow \mathbf{Lat}.

Next week, we will see an analogous functor from vector spaces to lattices.

Published by Jonathan Novak

Mathematician at UC San Diego.

Leave a Reply