Math 202A: Lecture 2

In this lecture we formulate the basic organizing principle of Math 202A: linear algebra quantizes combinatorics. We will make this precise using the language of category theory, which we began to introduce in Lecture 1. In particular, we defined combinatorics as the study of the category \mathbf{FSet} whose objects are finite sets and whose morphisms are functions. It remains to give a corresponding definition of linear algebra.

Definition 2.1. Linear algebra is the study of the category \mathbf{FVec} whose objects are finite-dimensional complex vector spaces equipped with a scalar product, and whose morphisms are linear transformations.

We are going to call objects in \mathbf{FVec} “Hilbert spaces,” so that we don’t have to say “finite-dimensional complex vector spaces equipped with a scalar product” every time we reference such an object. However, you should be aware that in the world outside Math 202A the term Hilbert space is used in a broader sense and also includes infinite-dimensional complex inner product spaces which are complete for the norm induced by the scalar product. In the finite-dimensional case, completeness is automatic but for infinite-dimensional spaces it is an extra assumption. I repeat: in Math 202A the term Hilbert space exclusively refers to finite-dimensional complex vector spaces which come with a given scalar product. Note that two Hilbert spaces which have the same underlying vector space but different scalar products are distinct objects of \mathbf{FVect}, but they are isomorphic with the identity transformation being a particular isomorphism. In particular, isomorphisms in \mathbf{FVect} are not required to preserve scalar products, but those which do (isometric isomorphisms) are particularly important and useful. Also note that we sometimes (often) reference Hilbert spaces without explicitly mentioning their scalar product.

Problem 2.1. Prove that two Hilbert spaces are isomorphic if and only if there exists a linear bijection between them.

We will commence a careful discussion of \mathbf{FVec} next week. Right now, we want to construct some sort of a mapping

\mathbf{FSet} \longrightarrow \mathbf{FVec}

which will justify our statement that linear algebra is quantized combinatorics. Therefore, we first need to introduce a the general notion of mapping from one category to another. As discussed in Lecture 1, categories generalize sets insofar as \mathbf{Set} is just one example of a category, so mappings between categories generalize functions — they are called functors and defined as follows.

Let \mathbf{Cat} and \mathbf{Dat} be categories. A functor 

\mathcal{F} \colon \mathbf{Cat} \longrightarrow \mathbf{Dat}

is first of all a rule which assigns to each object X \in \mathrm{Ob}(\mathbf{Cat}) a corresponding object \mathcal{F}(X) \in \mathrm{Ob}(\mathbf{Dat}). Second, \mathcal{F} should map morphisms f in \mathbf{Cat} to morphisms \mathcal{F}(f) in \mathbf{Dat} in a way which is compatible with the composition laws in these categories. More precisely, we require that for any objects X,Y,Z \in \mathrm{Ob}(\mathbf{Cat}) and morphisms f \in \mathrm{Hom}(X,Y) and g \in \mathrm{Hom}(Y,Z), the corresponding morphisms \mathcal{F}(f) \in \mathrm{Hom}(\mathcal{F}(X),\mathcal{F}(Y)) and \mathcal{F}(g) \in \mathrm{Hom}(\mathcal{F}(Y),\mathcal{F}(Z)) satisfy the equality

\mathcal{F}(g \circ f) = \mathcal{F}(g) \circ \mathcal{F}(f)

in \mathrm{Hom}(\mathcal{F}(X),\mathcal{F}(Z)).

We are now ready to define a specific functor

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

which we will refer to as the quantization functor. The quantization \mathcal{F}(X) of a given finite set X is the Hilbert space whose vectors are functions \varphi \colon X \to \mathbb{C}, with the vector space operations defined pointwise and the scalar product given by

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

We should verify that \mathcal{F}(X) is in fact a finite-dimensional Hilbert space. First, this requires us to check that the putative scalar product introduced above really is one.

Problem 2.2. Prove that \langle \varphi,\psi\rangle as defined above really is a scalar product on \mathcal{F}(X).

Second, we need to show that \mathcal{F}(X) really is a finite-dimensional vector space, and we do this by giving an explicit basis. For each x \in X define the corresponding Dirac function

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

Thus, \Delta=\{\delta_x\colon x \in X\} is a set of |X| functions in \mathcal{F}(X), and in fact it is an orthonormal set,

\langle \delta_x,\delta_y\rangle = \sum\limits_{z \in X} \delta_x(z)\delta_y(z) = \delta_x(y).

So \Delta is a linearly independent set in \mathcal{F}(X) and only one check remains.

Problem 2.3. Prove that \Delta spans \mathcal{F}(X).

With Problem 2.3 in hand, we can introduce an alternative point of view for the space \mathcal{F}(X) which is often favored by algebraists: we can think of it as the “space of formal linear combinations” of points in X. That is, elements of \mathcal{F}(X) are linear combinations

\varphi = \sum\limits_{x \in X} \varphi_x x,

where \varphi_x \in \mathbb{C} are scalars. This doesn’t really mean anything since we have no notion of scaling a point x \in X by a number \varphi \in \mathbb{C}, and such a formal linear combination is really just a shorthand for the coordinate decomposition

\varphi = \sum\limits_{x \in X} \varphi(x) \delta_x

of a function \varphi \colon X \to \mathbb{C} with respect to the Diract basis \Delta = \{\delta_x \colon x \in X\}.

We are not yet done with defining the functor \mathcal{F} because we need to say how it assigns a linear transformation \mathcal{F}(f) to a given set function f. Before doing this let us explain why we are referring X \mapsto \mathcal{F}(X) as quantization. Consider the canonical finite set X=\{1,\dots,n\}. We can view this as the state space of a particle \bullet which can occupy any one position on a finite lattice of n sites. Equivalently, you can think of \bullet being a ball which may be in any one of n labeled boxes or, as probabilists like to say, “urns.” So X is the state space of a classical particle, which is certain to be in one these boxes. On the other hand, \mathcal{F}(X) is the state space of a quantum particle \bullet, whose state is a superposition of classical states until a measurement is performed. More precisely, a (pure) quantum state is a unit vector \psi \in \mathcal{F}(X), the physical meaning of which is that the probability to observe the quantum particle in state x is given by the amplitude |\langle \delta_x,\psi \rangle|^2.

Now to complete the definition of quantization as a functor \mathcal{F} from \mathbf{FSet} to \mathbf{FVect} it remains to say how a function f \colon X \to Y between finite sets becomes a corresponding linear transformation \mathcal{F} \colon \mathcal{F}(X) \to \mathcal{F}(Y) between the corresponding Hilbert spaces. As in Lecture 1, let

\lambda \colon \{1,\dots,n\} \to X \quad\text{and}\quad \mu\colon \{1,\dots,m\} \to Y

of X and Y, write x_1=\lambda(1),\dots,x_n=\lambda(n) and y_1=\mu(1),\dots,y_m=\mu(m). Then, the function f is encoded by a corresponding lookup table, namely the m \times n matrix [f] whose (i,j)-entry is 1 if f(x_j)=y_i and 0 otherwise. Now for any f \in \mathrm{Hom}(X,Y) we simply define the corresponding linear transformation

\mathcal{F}(f) \colon \mathcal{F}(X) \longrightarrow \mathcal{F}(Y)

to be the linear transformation whose matrix with respect to the bases \{\delta_x \colon x \in X\} and \{\delta_y \colon y \in Y\} is the matrix of the original set function f. That is,

\mathcal{F}(f)\delta_x=\delta_{f(x)}.

In fact, we can give a coordinate free description of the linear transformation \mathcal{F}(f) \in \mathrm{Hom}(\mathcal{F}(X),\mathcal{F}(Y) — for every function \varphi \colon X \to \mathbb{C}, the function \mathcal{F}(f)\varphi \colon Y \to \mathbb{C} is the pushforward of \varphi through f.

Problem 2.4. Show that

[\mathcal{F}(f)\varphi](y) = \sum\limits_{x \in f^{-1}(y)} \varphi(x).

Now that we have justified our contention that linear algebra is quantized combinatorics, let us indicate briefly why this might be a useful functor to apply to a combinatorial problem. The first reason is that there are many more linear transformations between \mathcal{F}(X) \to \mathcal{F}(Y) then there are functions X \to Y. Technically one says that the functor \mathcal{F} is not full, and while this sounds like a negative it is actually a good thing. Indeed if X,Y are two finite sets of combinatorial objects which we suspect have the same cardinality, then working in the category \mathbf{FSet} our only option is to demonstrate the existence of a bijection f \colon X \to Y, and this could be hard. However, if we quantize our problem we now have the option of showing that there exists a linear isomorphism A \colon X \to Y, and this opens up a whole new realm of possibilities since we are allowed to map superpositions of objects in X onto superpositions of objects in Y. Another example comes from graph theory, where we can replace a graph with vertex set X by the function space \mathcal{F}(X), and encode the adjacency relation \sim in X as the operator

A \delta_x = \sum\limits_{y \sim x} \delta_y.

By thinking about the adjacency operator A in different bases of \mathcal{F}(X) we may be able to gain more insight into our graph. In particular, if we can find a superposition of vertices on which A acts diagonally we have access to some very useful information, as we will discuss later in the course.

A few more remarks. First, every Hilbert space V is isomorphic to a space of the form \mathcal{F}(X) for some finite set X. Indeed, every vector space has a basis, and hence by the Gram-Schmidt procedure every Hilbert space has an orthonormal basis. Now, V is isomorphic to \mathcal{F}(X) for any set X we use to label the elements of this ordered basis. Second, there is a different functor

\mathcal{F}^* \colon \mathbf{FSet} \longrightarrow \mathbf{FVec}

worth mentioning. As the notation suggests this is closely related to the functor latex \mathcal{F} and indeed \mathcal{F}^*(X)= \mathcal{F}(X) for every X \in \mathrm{Ob}(\mathbf{Fset}). The difference is that we send a function f \in X \to Y to its pullback along f, which is the linear transformation

\mathcal{F}^*(f) \colon \mathcal{F}^*(Y) \to \mathcal{F}^*(X)

defined by

\mathcal{F}^*(f)\psi=\psi \circ f, \quad \psi \in \mathcal{F}^*(Y).

Technically this does not match our definition of a functor given above, since it reverses arrows. Our initial definition in fact specifies the notion of a covariant functor, whereas this new construction is an example of a contravariant functor.

Problem 2.5. Show that the the matrix of the pullback \mathcal{F}^*(f) of a set function f \in \mathrm{Hom}(X,Y) is the adjoint of the lookup table of f.

Published by Jonathan Novak

Mathematician at UC San Diego.

Leave a Reply