Math 202A: Lecture 13

In this Lecture, building on the exposition in Lecture 12, we will take our first pass at the singular value decomposition of a linear transformation A \colon V \to W whose source and target are finite-dimensional Hilbert spaces.

In Lecture 12, we worked in the classical computational category \mathbf{FSet} whose objects are finite sets and whose morphisms are functions. Given any two finite sets X,Y and any function f\in \mathrm{Hom}(X,Y) we showed that the matrix of f can be brought into a certain canonical form by choosing appropriate orderings of X and Y. Namely, we can choose orderings so that the matrix [f] is block diagonal, with blocks being square matrices with first row consisting entirely of 1’s and all other entries equal to zero. The number of blocks is equal to the cardinality of the image \mathrm{Im}(f), i.e. the “rank” of the set function f. For each y \in \mathrm{Im}(f), the dimension of the corresponding block is the cardinality of the fiber f^{-}(y).

Now let us quantize this situation: let V=\mathcal{F}(X) and W=\mathcal{F}(Y) be the free Hilbert spaces over X and Y, in which X and Y live on as orthonormal bases, and let A =\mathcal{F}(f) \in \mathrm{Hom}(V,W) be the linear transformation defined by

Ax = f(x), \quad x \in X.

This situation contains exactly the same information as the set-theoretic one, where the original function f can be visualized as a bipartite graph on two disjoint sets of vertices X and Y. Now, A = \mathcal{F}(f) is (a version of) the adjacency matrix of this graph. More precisely, the matrix elements of A relative to the bases X \subset V and Y \subset W are

\langle y,Ax \rangle = [x \text{ adjacent to }y], \quad x \in X,\ y \in Y.

The difference now is that we can form superpositions of vertices in V=\mathcal{F}(X) and W=\mathcal{F}(Y) to construct new orthonormal bases which have additional advantages allow us to achieve a very canonical form for A=\mathcal{F}(f) which is not attainable for f, namely a diagonal form. The following problems will guide you through this process, which is a special case of the Singular Value Decomposition.

Problem 13.1. Consider the vectors in V = \mathcal{F}(X) defined by

e_y = \sum\limits_{x \in f^{-1}(y)} x, \quad y \in Y,

and for each of these vectors compute Ae_y.

Problem 13.2. Construct an orthonormal basis X^\prime of V such that the off-diagonal matrix elements of A relative to the bases X^\prime \subset V and Y \subset W are zero, and the diagonal matrix elements are the square roots of the cardinalities of the fibers of the function f \in \mathrm{Hom}(X,Y).

Problem 13.3. Show that the operator norm of A=\mathcal{F}(f)\in \mathrm{Hom}(V,W) is the square root of the cardinality of the largest fiber of f \in \mathrm{Hom}(X,Y).

Published by Jonathan Novak

Mathematician at UC San Diego.

Leave a Reply