Math 202A: Lecture 7

I will start this lecture with a brief review, both because we have some new students joining us and because I am generally a proponent of the spiral method of learning.

In the beginning there was the category $\mathbf{FSet}$ whose objects are finite sets $X$ and whose morphisms are functions $f \colon X \to Y.$ Initially I called this the combinatorial category, but it could just as well be called the computational category because everything about it can be described using just two digits, $0$ and $1.$ Indeed, for any finite set $X$ there exists a unique $n \in \mathbb{N}$ such that an isomorphism $r \colon \{1,\dots,n\}.$ Any such isomorphism is called an ordering of $X,$ and typically one writes $r(1)=x_1,\dots,r(n)=x_n.$ Once an ordering is fixed, we can encode $x_i$ as the column vector

$[x_j]_i= \begin{cases} 1, \text{ if }j=i \\ 0, \text{ if } j \neq i \end{cases}.$

If $X$ and $Y$ are two finite sets with orderings $x_1,\dots,x_n$ and $y_1,\dots,y_n$ then a function $f \in \mathrm{Hom}(X,Y)$ is encoded as the $m \times n$ logical matrix

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

Note that the columns of this one-hot encoding of $f$ are nothing but the bit strings $[f(x_j)]_i.$ For any two functions $f,g$ such that $g \circ f$ is defined, it can be computed as the matrix product $[g][f].$ So our conclusion early on was that everything about $\mathbf{FSet}$ can be expressed in terms of matrix algebra, and only binary matrices are needed.

We then began to argue a case which we will continue to argue throughout the quarter. We claim that it is advantageous to move from the classical computational category $\mathbf{FSet}$ to the quantum computational category $\mathbf{FHil}$ whose objects are finite-dimensional Hilbert spaces and whose morphism are linear transformations. Here all computations can again be reduced to matrix algebra but the matrices used are no longer constrained to be built from two bits; rather they can involve arbitrary complex numbers. The passage from classical computation to quantum computation is one way to motivate the study of linear algebra. A more traditional way is to start with the desire to solve systems of linear equations, which I assume you have already been exposed to.

More formally, we introduced the quantization functor

$\mathcal{F} \colon \mathbf{FSet} \longrightarrow \mathbf{FHil}$

which sends each finite set $X$ to the Hilbert space $\mathcal{F}(X)$ containing $X$ as an orthonormal basis. This is called the free Hilbert space on $X,$ and it may be constructed concretely as the space of complex-valued functions on $X$ equipped with the $\ell^2$ -scalar product. The functor $\mathcal{F}$ also sends each function $f \in \mathrm{Hom}(X,Y)$ to the linear 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.$

The quantization functor is faithful but not full. Faithful means that $X$ and $Y$ are isomorphic objects in $\mathbf{FSet}$ if and only if $\mathcal{F}(X)$ and $\mathcal{F}(Y)$ are isomorphic objection in $\mathcal{FHil}.$ Not full means that there are many more morphisms in $\mathrm{Hom}(\mathcal{F}(X),\mathcal{F}(Y))$ then there are in $\mathrm{Hom}(X,Y)$ , and this is a good thing. For example, in order to show that $X$ and $Y$ are isomorphic sets we can try to show that $\mathcal{F}(X)$ and $\mathcal{F}(Y)$ are isomorphic Hilbert spaces, and there are many more ways in which this can happen. I even have a friend who claims that there are no bijections, only invertible linear transformations (he’s kidding but also kind of serious). The upshot is that we want to argue that $\mathbf{FHil}$ is better than $\mathbf{FSet}$ and we will use the category-theoretic perspective to guid us in understanding what “better” should mean.

Definition 7.1. A category $\mathbf{Cat}$ is said to be enriched over another category $\mathbf{Dat}$ if for every $X,Y \in \mathrm{Ob}(\mathbf{Cat})$ we have $\mathrm{Hom}(X,Y) \in \mathrm{Ob}(\mathbf{Dat}).$

For example, the category $\mathbf{FSet}$ is enriched over itself. The question we want to answer: is $\mathbf{FHil}$ enriched over itself?

Let us start with some obvious statements and work towards answering this question. First of all, $\mathbf{FHil}$ is enriched over $\mathbf{Set},$ which is the same thing as saying that $\mathbf{FHil}$ is a locally small category. But we can easily do better than this.

Proposition 7.2. The category $\mathbf{FHil}$ is enriched over the category $\mathbf{Vec}$ whose objects are complex vector spaces and whose morphisms are linear maps.

Proving this means showing that for any finite-dimensional Hilbert spaces $V,W$ the corresponding set $\mathrm{Hom}(V,W)$ can be made into a complex vector space, and equipping linear maps with addition and scalar multiplication defined point wise we get the desired vector space structure (this should be familiar, but you should still think about it).

Now let us see if we can do better than this and show that $\mathbf{FHil}$ is enriched over $\mathbf{FVec},$ the full subcategory of $\mathbf{Vec}$ whose objects are finite-dimensional complex vector spaces.

Definition 7.3. Given $V,W \in \mathrm{Ob}(\mathbf{FHil}),$ let $X \subset V$ and $Y \subset W$ be orthonormal bases. We define the corresponding elementary operators $\{E_{yx} \colon (x,y) \in X\times Y\} \subset \mathrm{Hom}(V,W)$ by

$E_{yx}\tilde{x} = y \langle x,\tilde{x}\rangle, \quad \tilde{x} \in X.$

To get a feel for the definition, let us compute the matrix elements of $E_{yx}$ relative to the orthonormal bases $X$ and $Y$ : we have

$\langle \tilde{y},E_{yx}\tilde{x}\rangle = \langle \tilde{y},y\langle x,\tilde{x}\rangle\rangle = \langle \tilde{y},y\rangle \langle x,\tilde{x}\rangle, \quad \tilde{x} \in X,\ \tilde{y} \in Y.$

Thus, $E_{yx}$ has exactly one matrix element equal to one, namely $\langle y,E_{yx} x\rangle,$ and all other matrix elements are equal to zero.

Problem 7.1. Prove that $\{E_{yx} \colon (x,y) \in X\times Y\}$ is a basis of $\mathrm{Hom}(V,W),$ and show that the expansion of any $A \in \mathrm{Hom}(V,W)$ is

$A = \sum\limits_{x \in X} \sum\limits_{y \in Y} \langle y,Ax \rangle E_{yx}.$

This expansion is one way to write down the information contained in the matrix of $A$ without actually writing down the matrix. An immediate consequence of Problem 7.1 is that $\mathbf{FHil}$ is enriched over $\mathbf{FVec}.$ Another useful consequence of having an explicit basis for this space is the following.

Theorem 7.4. Every $A \in \mathrm{Hom}(V,W)$ is a continuous function, with respect to the Hilbert space norms on $V$ and $W.$

Proof: It suffices to prove that the elementary transformations are continuous, since then every transformation is a sum of continuous functions and hence continuous. In fact, the elementary transformations are not just continuous, they are contractive mappings. To see this, we compute

$\|E_{yx}v\| = \left\| \sum\limits_{\tilde{x} \in X} \langle \tilde{x},v\rangle E_{yx} \tilde{x} \right\| = \left\| \sum\limits_{\tilde{x} \in X} \langle \tilde{x},v\rangle y \langle x, \tilde{x} \rangle\right\|=|\langle x,v\rangle |\|y\| \leq \|v\|,$

where the final inequality is Cauchy-Schwarz together with the fact that $x \in X$ and $y \in Y$ are unit vectors. $\square$

We still have not discovered a scalar product on the finite-dimensional vector space $\mathrm{Hom}(V,W),$ so it is not yet a Hilbert space. Instead of trying to find a scalar product immediately, let us first shoot for an intermediate goal: finding a norm.

Definition 7.5. A Banach space is a complex vector space equipped with a norm.

This definition has the same irregularity as our definition of Hilbert space, namely that we do not require completeness. This is because we are really only interested in finite-dimensional Banach spaces, which are always complete.

Problem 7.2. Let $V,W \in \mathrm{Ob}(\mathbf{FHil})$ and let $X\subset V$ and $Y \subset W$ be orthonormal bases. Define a function

$\langle \cdot,\cdot\rangle_{XY} \colon \mathrm{Hom}(V,W) \longrightarrow [0,\infty)$

$\|A\|_{XY} = \sum\limits_{x \in X}\sum\limits_{y \in Y} |\langle y,Ax \rangle|.$

Show that $\|\cdot\|_{XY}$ is a norm on $\mathrm{Hom}(V,W)$ , but that it is not induced by a scalar product.

An immediate consequence of Problem 7.2 is that $\mathbf{FHil}$ is enriched over the category $\mathbf{FBan}$ whose objects are finite-dimensional Banach spaces and whose morphisms are linear transformations. However, the norm $\|\cdot\|_{XY}$ is not a very good norm in that it depends on choosing orthonormal bases $X \subset V$ and $Y \subset W.$ In this sense it is not tethered to the intrinsic geometry of a linear transformation, but rather to the particular numerology of a specific matrix representation.

A better norm on $\mathrm{Hom}(V,W)$ can be obtained by observing that linear transformations are not just continuous functions, they are Lipschitz functions.

Theorem 7.5. Every $A \in \mathrm{Hom}(V,W)$ is Lipschitz.

Proof: Let $X \subset V$ and $Y \subset W$ be orthonormal bases. Using the solution to Problem 7.1 as well as the triangle inequality and Cauchy-Schwarz inequality for the Hilbert space norm in $W,$ we have

$\|Av\| = \left\| \sum\limits_{x \in X} \sum\limits_{y \in Y}\langle y,Av\rangle E_{yx}v \right\| = \left\| \sum\limits_{x \in X} \sum\limits_{y \in Y}\langle y,Av\rangle y \langle x,v \rangle \right\| \leq \|A\|_{XY}\|v\|,$

which shows that $A$ is Lipschitz. $\square$

Definition 7.6. The operator norm of $A \in \mathrm{Hom}(V,W)$ is defined to be its Lipschitz constant,

$\|A\|:=\inf\{C \geq 0 \colon \|Av\| \leq C\|v\| \text{ for all }v \in V\}.$

Problem 7.3. Prove that the operator norm on $\mathrm{Hom}(V,W)$ really is a norm, but that it is not induced by a scalar product.

Math 202A: Lecture 7

Like this:

Published by Jonathan Novak

Leave a ReplyCancel reply

Share this:

Like this:

Published by Jonathan Novak

Leave a ReplyCancel reply

Discover more from Jonathan Novak