Math 202A: Lecture 14

Last week, we considered the problem of canonical forms for the classical computational category \mathbf{FSet}, whose objects are finite sets with morphisms being functions. Concretely, we are given finite sets X,Y and a function f \in \mathrm{Hom}(X,Y). Our objective is to choose orderings x_1,\dots,x_n and y_1,\dots,y_m of X and Y such that the m \times n matrix [f] of f with respect to these orderings assumes a simple, transparent form.

As with everything having to do with \mathbf{FSet} this is a combinatorial question and it is not too difficult to analyze. The basic idea is that taking any ordering y_1,\dots,y_m allows us to look at f backwards, as the ordered list of its fibers,

f=(f^{-1}(y_1),\dots,f^{-1}(y_m)).

Each fiber is a (possibly empty) subset of X, distinct fibers are disjoint, and the union of all fibers is X. In combinatorial parlance, the function f becomes a weak m-part set composition of X. The rank r of f, which is by definition the cardinality of the image \mathrm{Im}(f) = \{f(x) \colon x \in X\}, is the number of nonempty fibers of f, and clearly r \leq \min(m,n). The type of f is an integer partition of \lambda \vdash n with r parts, or equivalently a Young diagram with n cells and r rows; it is simply the list of the cardinalities of the nonempty fibers of f sorted in non-increasing order.

To obtain a canonical form for f, choose an ordering y_1,\dots,y_m of Y such that \mathrm{Im}(f) = \{y_1,\dots,y_r\} and

|f^{-1}(y_1)| \geq \dots \geq |f^{-1}(y_r)|.

Thus, the type of f is the Young diagram with r rows of lengths

\lambda_i = |f^{-1}(y_i)|, \quad 1 \leq \leq r.

Then, let x_1,\dots,x_n be any ordering of X obtained by first listing the elements of f^{-1}(y_1) in any order, then listing the elements of f^{-1}(y_2), and so on. Then, the matrix of f with respect to these orderings is an m \times n matrix over \{0,1\} which can be described explicitly as follows: the first row of [f] begins with \lambda_1 entries equal to 1, and all remaining entries equal to 0; the second row of [f] begins with \lambda_1 entries equal to 0, followed by \lambda_2 entries equal to 1, and all remaining entries equal to 0; and so on until row r of [f], which has its final \lambda_r entries equal to 1 and all other entries equal 0. Finally, if there are any rows in [f] remaining (i.e. f is not surjective), then these remaining m-r rows are all zero rows.

The main point of last week’s material is that we can do much better than the above by quantizing. Instead of looking at f \in \mathrm{Hom}(X,Y), we invoke the functor

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

and look at \mathcal{F}(f) \in \mathrm{Hom}(\mathcal{F}(X),\mathcal{F}(Y)). For brevity let us write V=\mathcal{F}(X) and W = \mathcal{F}(Y). Thus, X \subset V and Y \subset W are orthonormal bases, and A = \mathcal{F}(f) \in \mathrm{Hom}(V,W) is a linear transformation with the special feature that

Ax \in Y, \quad x \in X.

We have now opened up the option to look at alternative orthonormal bases in V=\mathcal{F}(f) and W=\mathcal{F}(Y) such that the corresponding matrix of A = \mathcal{F}(f) may be even simpler than matrix of A relative to X and Y, which is the binary matrix [f] of the function f\in \mathrm{Hom}(X,Y). The capstone problem last week shows that we can construct an ordered orthonormal basis e_1,\dots,e_n of X such that the matrix elements of A \in \mathrm{Hom}(V,W) relative to the ordered orthonormal bases e_1,\dots,e_n and y_1,\dots,y_m satisfies

\langle y_1,Ae_1 \rangle = \sigma_1,\dots,\langle y_r,Ae_r\rangle=\sigma_r,

where

\sigma_i=\sqrt{|f^{-1}(y_i)|}, \quad 1 \leq i \leq r,

and all other matrix elements of A are equal to 0. The difference here is that the binary matrix [f] of f always contains n nonzero entries, and the best we can do is arrange these 1‘s in a convenient pattern. However, in the quantum category we can obtain a matrix representation of A = \mathcal{F}(f) which only has r \leq \min(m,n) nonzero entries. This is potentially much sparser. Indeed, the number of nonzero entries of the binary matrix [f] is always

\frac{n}{mn}= \frac{1}{m},

whereas the number of nonzero entries in [A] is

\frac{r}{mn} \leq \frac{\min(m,n)}{mn}.

In the extreme case, for A=\mathcal{F}(f) the functorial image of rank one (i.e. constant) function f \colon X \to Y, the sparsity of [A] is

\frac{1}{mn}.

The above amounts to a combinatorial proof of a special case of an extremely useful canonical form for morphisms in the quantum computational category \mathbf{FHil}.

Theorem 14.1. (Singular Value Decomposition) For any finite-dimensional Hilbert spaces V,W and any linear transformation A \in \mathrm{Hom}(V,W) of rank r, there exist ordered orthonormal bases E \subset V and F \subset W such that

Ae_i = \sigma_i f_i, \quad 1 \leq i \leq r,

where \sigma_1 \geq \dots \geq \sigma_r >0. The remaining vectors e_{r+1},\dots,e_n are an orthonormal basis for the kernel of A.

Last week’s material is effectively a proof of Theorem 14.1 in the special case where A \in \mathrm{Hom}(V,W) happens to be the functorial image of a set function, meaning that there happen to be orthonormal bases X \subset V and Y \subset W such that Ax \in Y for every x \in X.

In order to prove Theorem 14.1 in full generality, we need to use the full structure of objects in \mathbf{FHil}, meaning algebra and geometry as opposed to combinatorics. The image of a set function f \in \mathrm{Hom}(X,Y) is related to the image of its quantization \mathcal{F}(f) \in \mathrm{Hom}(\mathcal{F}(X),\mathcal{F}(Y)) by

\mathrm{Im}(\mathcal{F}(f)) = \mathrm{Span} \mathrm{Im}(f),

and in this sense the image of a linear transformation is a combinatorial subspace of its target space. However, for every A \in \mathrm{Hom}(V,W) there are two associate subspaces of V which are not of a combinatorial nature. The first is the kernel of A,

\mathrm{Ker}(A) = \{v \in V \colon Av=0_W\},

which is algebraic in the sense that it is defined in terms of the additive identity in the target space W of A. The second is the optimizer space of A,

\mathrm{Opt}(A) = \{v \in V \colon \|Av\| = \|A\| \|v\|\},

which is geometric in the sense that it is defined using the metric structure of both the source and target spaces. Here \|A\| is the operator norm of A, so vectors v \in \mathrm{Opt}(A) are those which are maximally stretched by applying A, in the sense that they force equality in the inequality

\|Av\| \leq \|A\|\|v\|

which holds for all vectors in V.

Theorem 14.2. For every A \in \mathrm{Hom}(V,W), the set \mathrm{Opt}(A) is a nonzero subspace of V.

Proof: Fix an arbitrary linear transformation A \in \mathrm{Hom}(V,W), and for brevity write

\sigma_1 = \|A\| \quad\text{and}\quad V_1=\mathrm{Opt}(A).

The zero vector in V belongs to V_1 because

\|A0_V\|=0=\sigma_1\|0_V\|.

The nonempty set V_1 is closed under scalar multiplication: if v \in V_1 then

\|A(\lambda v)\|=|\lambda|\|Av\|=|\lambda|\sigma_1\|v\| = \sigma_1\|\lambda v\|

for any \lambda \in \mathbb{C}.

Now we show that V_1 is closed under vector addition. Let u,v \in V_1, and observe that u+v \in V_1 if and only if u-v \in V_1, since we have already proved V_1 closed under scalar multiplication. Suppose that u,v \in V_1 but u+v,u-v\not\in V_1. We then have

\sigma_1^2\|u+v\|^2+\sigma_1^2\|u-v\|^2=2\sigma_1^2\|u\|^2+2\sigma_1^2\|v\|^2=2\|Au\|^2+2\|Av\|^2,

where the first equality is the Parallelogram Law and the second is the hypothesis u,v \in V_1. Now

2\|Au\|^2+2\|Av\|^2=\|A(u+v)\|^2+\|A(u-v)^2\|<\sigma_1^2\|u+v\|^2+\sigma+1^2\|u-v\|^2,

where the equality is the Parallelogram Law and the inequality is the hypothesis u+v,u-v\not\in V_1. But then we have

\sigma_1^2\|u+v\|^2+\sigma_1^2\|u-v\|^2<\sigma_1^2\|u+v\|^2+\sigma_1^2\|u-v\|^2,

which is absurd.

We have now shown that V_1 is a subspace of V, and it remains to show that V_1\neq \{0_V\}. To do so, it is sufficient to show that V_1 contains a vector of norm one. The unit sphere

S_1 =\{u \in V \colon \|u\|=1\},

is a compact set (in the norm topology on V), and the function u \mapsto \|Au\| is a continuous function on S_1 whose supremum is \sigma_1. By the Extreme Value Theorem, there exists u \in S_1 such that \|Au\|=\sigma_1=\sigma_1\|u\|, whence u \in V_1. \square

The proof above uses a purely geometric argument to prove that V_1 is a subspace of V. In particular, this part of the argument does not require finite-dimensionality. However, to show V_1 nonzero we needed compactness of the unit sphere in V, which is a topological assertion.

Problem 14.1. Prove that the unit sphere S_1 in a finite-dimensional Hilbert space V really is a compact set.

Another feature of the proof of Theorem 14.1 is its use of the Parallelogram Law, which as we have discussed characterizes Banach spaces whose norm is induced by a scalar product. There are less clever ways to prove this result which do not rely on the Parallelogram Law, and this leads one to wonder whether Theorem 14.1 holds more generally, in the larger category \mathbf{FBan} of finite-dimensional Banach spaces.

Problem 14.2. Prove that Theorem 14.2 does not hold in \mathbf{FBan}.

Published by Jonathan Novak

Mathematician at UC San Diego.

Leave a Reply