This lecture is the most important lecture in Math 202A: we will obtain a remarkably transparent of morphisms in 
Take any two objects 
This is yet another opportunity to point out that the quantum category is better than the classical one. Indeed, suppose we can find a subspace
But linear algebraically, in order to complete our understanding of
For example in three dimensions, this is the difference between extending from the line of understanding to the whole space with that line deleted, and extending only to the plane orthogonal to the line of understanding. The latter is a dimension reduction, the former is not.
There is one obvious candidate for an “exactly solvable” subspace 
we tautologically have that 
![[A] =\begin{bmatrix} 0 & [A]\end{bmatrix},](https://s0.wp.com/latex.php?latex=%5BA%5D+%3D%5Cbegin%7Bbmatrix%7D+0+%26+%5BA%5D%5Cend%7Bbmatrix%7D%2C&bg=FFFFFF&fg=000&s=0&c=20201002)
where the row echelon form of the nested ![[A]](https://s0.wp.com/latex.php?latex=%5BA%5D&bg=FFFFFF&fg=000&s=0&c=20201002)
The basic lesson to be learned from this failure is that in order to implement our bootstrap strategy we need to identify an exactly solvable subspace 
whose nonzero vectors maximize the norm ratio 
Proposition 16.1. The set
The key idea of the Singular Value Decomposition is that 
First, let us explain why 
![[U_1] = \begin{bmatrix} 1 & {} & {} \\ {} & \ddots & {} \\ {} & {} & 1\end{bmatrix}.](https://s0.wp.com/latex.php?latex=%5BU_1%5D+%3D+%5Cbegin%7Bbmatrix%7D+1+%26+%7B%7D+%26+%7B%7D+%5C%5C+%7B%7D+%26+%5Cddots+%26+%7B%7D+%5C%5C+%7B%7D+%26+%7B%7D+%26+1%5Cend%7Bbmatrix%7D.&bg=FFFFFF&fg=000&s=0&c=20201002)
Thus, the morphism 
![[A_1] = \begin{bmatrix} 1 & {} & {} \\ {} & \ddots & {} \\ {} & {} & 1\end{bmatrix},](https://s0.wp.com/latex.php?latex=%5BA_1%5D+%3D+%5Cbegin%7Bbmatrix%7D+1+%26+%7B%7D+%26+%7B%7D+%5C%5C+%7B%7D+%26+%5Cddots+%26+%7B%7D+%5C%5C+%7B%7D+%26+%7B%7D+%26+1%5Cend%7Bbmatrix%7D%2C&bg=FFFFFF&fg=000&s=0&c=20201002)
so considering the restriction of 
Now we want to bootstrap our local understanding of 
We now proceed with the case where 
where by definition 
and since 
Proposition 16.2. We have
Proof: A more geometrically suggestive equivalent statement is to take the complement and write the claim as 
The counterpart of Proposition 16.3 in the target space decomposition 
Now consider the extreme case of Proposition 16.2 where 
becomes
and we have achieved our goal of understanding how 
Definition 16.3. A morphism 
Equivalently, 
What we have shown is that any nonzero morphism 
The extremal case of Proposition 16.2 is just that – an extreme case. In general
Proposition 16.4. We have 
The force of proposition 16.4 is that in conjunction with the decompositions
it reduces our problem to a genuinely lower-complexity version of the same problem: we have
where 
We now repeat our analysis of 
Let us carry out this iteration. Let 
where 
As in our first iteration, 
which lifts back up to the level of
If not, we repeat the process on the restriction of 
Continuing the process until we exhaust 
Theorem 16.5. (SVD, chunky geometric form) For any morphism 
and numbers
such that, for each 
The paired spaces 
In general, the worst case scenario for the runtime of the recursive routine which establishes the SVD occurs when 
Even when the worst case scenario is not what occurs, we can write the Singular Value Decomposition in a form where all subspaces involved are one-dimensional, simply by choosing a basis within each
Theorem 16.6. (SVD, fine-grained geometric version) For any morphism 
and numbers
such that, for each 
What is confusing in the way the two versions of the SVD are stated is that the symbols
sends a finite set 
to the free Hilbert space 
containing 
to the linear transformation 
whose action on this basis is
matches 
has no direct counterpart in 
In the classical computational category, you can identify a function 
with the ordered list of its fibers, but the fibers of 
which is literally a point of the domain of 
It is precisely this fact which allowed us to establish the Singular Value Decomposition for quantized set functions with no additional technology.
and 
. A function 
is![[A] = \begin{bmatrix} 0_{m \times n} & \mathcal{F}^*(f) \\ \mathcal{F}(f) & 0_{n \times m} \end{bmatrix}.](https://s0.wp.com/latex.php?latex=%5BA%5D+%3D+%5Cbegin%7Bbmatrix%7D+0_%7Bm+%5Ctimes+n%7D+%26+%5Cmathcal%7BF%7D%5E%2A%28f%29+%5C%5C+%5Cmathcal%7BF%7D%28f%29+%26+0_%7Bn+%5Ctimes+m%7D+%5Cend%7Bbmatrix%7D.&bg=FFFFFF&fg=000&s=0&c=20201002)
and 
; write 
and 
Show that
which satisfies
exists, we want a geometric interpretation of it.
and 
. However, it is not necessarily true that we can select 
such that our pre-selected 
by declaring its matrix elements to be what we want them to be. More precisely, set
and 
we have
is the nullity of 
is the corank of 
is the zero transformation. Now let us define a corresponding transformation 
by 
to 
for 
and the restriction of 
is the zero transformation into 
Deduce 
and 
defined by
is defined by inverting the invertible part of 
is an isomorphism onto 
with inverse 
holds in 
holds in 
No doubt you are familiar with the transpose of a matrix, so I will make the following remark: the transpose of the matrix of 
the corresponding matrices of 
Recall that for every finite dimensional Hilbert space 
, the space of linear functionals on 
from a vector space to a Hilbert space by defining the scalar product
consisting of the linear functionals 
defined by 
really is a linear transformation 
Taking orthonormal bases 
show that the matrix of 
and 
Let 
and 
and we can view 
there exists an isometric isomorphism 
such that 
it maps 
This fact will allow us to prove the Singular Value Decomposition geometrically, by induction on the rank of 
be any vector which is orthogonal to every vector 
We have to show that 
this is true simply because 
then we can assume without loss in generality that 
, again because 
is orthogonal to 
So, let 
be arbitrary, and consider the scalar product 
. First, let us show this under the following assumption.
, and consider the corresponding perturbation 
of the stretch optimizer 
As with every vector in 
the definition of 
and 
this becomes
for every 
which forces 
. (Hint: this is not hard, so don’t make it hard).
is strictly less than the rank of 
and orthogonal decompositions
for 
, whose objects are finite sets with morphisms being functions. Concretely, we are given finite sets 
Our objective is to choose orderings 
and 
of 
matrix ![[f]](https://s0.wp.com/latex.php?latex=%5Bf%5D&bg=FFFFFF&fg=000&s=0&c=20201002)
of 
distinct fibers are disjoint, and the union of all fibers is 
In combinatorial parlance, the function 
-part set composition of 
, is the number of nonempty fibers of 
The type of 
with 
cells and 
and 
in any order, then listing the elements of 
and so on. Then, the matrix of 
which can be described explicitly as follows: the first row of 
entries equal to 
and all remaining entries equal to 
; the second row of 
entries equal to 
, and all remaining entries equal to 
entries equal to 
rows are all zero rows. 
we invoke the functor
For brevity let us write 
Thus, 
is a linear transformation with the special feature that
and 
may be even simpler than matrix of 
which is the binary matrix 
The capstone problem last week shows that we can construct an ordered orthonormal basis 
of 
,
nonzero entries. This is potentially much 
, the sparsity of 
.
and 
such that 
The remaining vectors 
are an orthonormal basis for the kernel of 
for every 
is the operator norm of 
are those which are maximally stretched by applying 
, and observe that 
if and only if 
since we have already proved 
We then have
Now
To do so, it is sufficient to show that 
is a continuous function on 
whose supremum is 
By the Extreme Value Theorem, there exists 
such that 
whence 
which is a topological assertion.
of finite-dimensional Banach spaces.
whose source and target are finite-dimensional Hilbert spaces.
we showed that the matrix of 
Namely, we can choose orderings so that the matrix 
i.e. the “rank” of the set function 
For each 
the dimension of the corresponding block is the cardinality of the fiber 
be the linear transformation defined by
![\langle y,Ax \rangle = [x \text{ adjacent to }y], \quad x \in X,\ y \in Y.](https://s0.wp.com/latex.php?latex=%5Clangle+y%2CAx+%5Crangle+%3D+%5Bx+%5Ctext%7B+adjacent+to+%7Dy%5D%2C+%5Cquad+x+%5Cin+X%2C%5C+y+%5Cin+Y.&bg=FFFFFF&fg=000&s=0&c=20201002)
defined by
of 
and 
is the square root of the cardinality of the largest fiber of 
where 
is an 
unitary matrix, 
is an 
unitary matrix. Let’s check we got the dimensions right here: we write down the word 
and observe that matrix multiplication simplifies it to 
and then to 
which is indeed the shape of 
whose objects are finite sets and whose morphisms are functions. Let 
and let 
numbers![f_{yx} = [f(x)=y], \quad x \in X,\ y \in Y,](https://s0.wp.com/latex.php?latex=f_%7Byx%7D+%3D+%5Bf%28x%29%3Dy%5D%2C+%5Cquad+x+%5Cin+X%2C%5C+y+%5Cin+Y%2C&bg=FFFFFF&fg=000&s=0&c=20201002)
![[P]=\begin{cases} 1, \text{ if }P\text{ true}\\ 0, \text{ if }P\text{ false} \end{cases}](https://s0.wp.com/latex.php?latex=%5BP%5D%3D%5Cbegin%7Bcases%7D+1%2C+%5Ctext%7B+if+%7DP%5Ctext%7B+true%7D%5C%5C+0%2C+%5Ctext%7B+if+%7DP%5Ctext%7B+false%7D+%5Cend%7Bcases%7D&bg=FFFFFF&fg=000&s=0&c=20201002)
![[f]_{ij} = f_{y_ix_j}, \quad 1 \leq i \leq m,\ 1 \leq j \leq n.](https://s0.wp.com/latex.php?latex=%5Bf%5D_%7Bij%7D+%3D+f_%7By_ix_j%7D%2C+%5Cquad+1+%5Cleq+i+%5Cleq+m%2C%5C+1+%5Cleq+j+%5Cleq+n.&bg=FFFFFF&fg=000&s=0&c=20201002)
the matrix 
it is tall and skinny (aka 
it is short and fat (aka 
so that possibly 
if and only if 
such that ![I_n = P[f]Q](https://s0.wp.com/latex.php?latex=I_n+%3D+P%5Bf%5DQ&bg=FFFFFF&fg=000&s=0&c=20201002)
if and only if 
matrix of zeros to the bottom of 
and an 
such that ![P[f]Q](https://s0.wp.com/latex.php?latex=P%5Bf%5DQ&bg=FFFFFF&fg=000&s=0&c=20201002)
is in this canonical form if and only if 
Now letting 
with edges going between two disjoint sets of vertices 
is an edge if and only if 
The connected components of 
are 
in which the hub vertex 
has degree equal to the cardinality 
of the fiber of 
The surjectivity condition means that each of these star graphs has at least one edge or, equivalently, two vertices. The type of 
whose components are the positive numbers
is a 
and let 
be an ordering of its elements. Let 
and let 
be an ordering of its elements. Let 
The matrix of this function with respect to these ordering is![[f]=\begin{bmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 \end{bmatrix}.](https://s0.wp.com/latex.php?latex=%5Bf%5D%3D%5Cbegin%7Bbmatrix%7D+1+%26+1+%26+1+%26+0+%26+0+%5C%5C+0+%26+0+%26+0+%26+1+%26+1+%5Cend%7Bbmatrix%7D.&bg=FFFFFF&fg=000&s=0&c=20201002)
and let 
be an ordering of its elements. Let 
be an ordering of its elements. Let 
The matrix of this function with respect to these ordering is![[f]=\begin{bmatrix} 1 & 1 & 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1\end{bmatrix}.](https://s0.wp.com/latex.php?latex=%5Bf%5D%3D%5Cbegin%7Bbmatrix%7D+1+%26+1+%26+1+%26+0+%26+0+%26+0%5C%5C+0+%26+0+%26+0+%26+1+%26+1+%26+0+%5C%5C+0+%26+0+%26+0+%26+0+%26+0+%26+1%5Cend%7Bbmatrix%7D.&bg=FFFFFF&fg=000&s=0&c=20201002)
from finite sets to finite 
is containment, meaning that for 
we define
and the largest set contained in both 
respectively.
and 
bijectively onto 
which is why
we have 
is not complete until we say where it sends a given set function 
. The corresponding 
is defined by = f(Y) = \{f(x) \colon x \in y\}.](https://s0.wp.com/latex.php?latex=%5B%5Cmathcal%7BP%7D%28f%29%5D%28Y%29+%3D+f%28Y%29+%3D+%5C%7Bf%28x%29+%5Ccolon+x+%5Cin+y%5C%7D.&bg=FFFFFF&fg=000&s=0&c=20201002)
really is a morphism in 
is said to be a 
for all 
and 
for all 
whose objects are 
in 
consisting of a finite set 
a specific retraction 
of 
denote the subgroup of 
consisting of all automorphisms (permutations) 
of 
Call a rule 
which assigns to set/subset pairs a corresponding retraction canonical if 
and 
is nonempty, no canonical retraction exists. 
Then, for every 
we have 
as a fixed point and permutes the points of 
to be fixed by every permutation of 
a contradiction. 
Then, for any nonempty 
we can define a retraction of 
to be the point of 
However, even here we need to impose a rule for breaking ties (two distinct minimizers). Once we do this, the retraction 
which preserve tie breakers.
Conversely, show that if 
denote the set of idempotent functions in 
. Define an equivalence relation on 
![[f]_Y = \{f \in \mathrm{End}(X) \colon \mathrm{Im}(f)=Y,\ f^2=f\}.](https://s0.wp.com/latex.php?latex=%5Bf%5D_Y+%3D+%5C%7Bf+%5Cin+%5Cmathrm%7BEnd%7D%28X%29+%5Ccolon+%5Cmathrm%7BIm%7D%28f%29%3DY%2C%5C+f%5E2%3Df%5C%7D.&bg=FFFFFF&fg=000&s=0&c=20201002)
![Y \mapsto [f]_Y](https://s0.wp.com/latex.php?latex=Y+%5Cmapsto+%5Bf%5D_Y&bg=FFFFFF&fg=000&s=0&c=20201002)
is a bijection 
defined by 
is a bijection (binary encoding of subsets). 
inside of which 
only includes subsets of 
The meet and join operations in 
is a linear transformation the corresponding order homomorphism 
is defined by  = A(W) = \{Aw \colon w \in W\} = \mathrm{Im}(A).](https://s0.wp.com/latex.php?latex=%5B%5Cmathcal%7BL%7D%28A%29%5D%28W%29+%3D+A%28W%29+%3D+%5C%7BAw+%5Ccolon+w+%5Cin+W%5C%7D+%3D+%5Cmathrm%7BIm%7D%28A%29.&bg=FFFFFF&fg=000&s=0&c=20201002)
antichains
Although each 
is uncountably infinite set, it has much more structure than just being a very big set. In fact, these sets are important enough that they have a special name.
quantizes to 
giving 
special subspaces of 
Complementary subsets of 
Moreover, prove that we have the internal direct sum decomposition 
is a coordinate subspace of 
the line in 
does not contain any point of 
(Hint: you can deduce this directly from Problem 10.3 by constructing an appropriate unitary operator on 
a linear retraction of 
such that 
and the restriction of 
to 
is a retraction onto its image if and only if it is idempotent, 
denote the set of idempotent operator on ![W \mapsto [P]_W](https://s0.wp.com/latex.php?latex=W+%5Cmapsto+%5BP%5D_W&bg=FFFFFF&fg=000&s=0&c=20201002)
which sends a subspace 
to the equivalence class ![[P]_W](https://s0.wp.com/latex.php?latex=%5BP%5D_W&bg=FFFFFF&fg=000&s=0&c=20201002)
of idempotent operators with image 
or 
In the quantum setting, given a vector 
is or is not 
with 
such that 
That is, we have 
where 
For any vector 
consider its expansion in the orthonormal basis 
We claim that 
and that 
is the unique point of 
unless we have
and that 
![[f]_Y](https://s0.wp.com/latex.php?latex=%5Bf%5D_Y&bg=FFFFFF&fg=000&s=0&c=20201002)
of idempotents with image 
i.e. 
Let 
and for any 
That is, the orthogonal projection 
as its diagonal.
meaning that we would have to compute its image 
and check that 
In fact, there is an algebraic characterization of which idempotents actually are orthogonal projections: it is precisely the selfadjoint ones. I mention this because you probably already know it. If you don’t that’s even better, because we will prove this characterization as a theorem after we establish the singular value decomposition, which we shall use to define the 
In this lecture we continue our proof of the fact that all 
is in fact independent of the chosen coordinate systems 
we showed in Lecture 8 that the above scalar product coincides with the Riesz scalar product on 
which is canonically defined through vector/covector duality. 
has no dependence on 
and let 
. Then, a basic formula we can write down and keep in mind is
is an orthonormal basis for 
the 
in 
In symbols, we have the 
is a Hilbert space and 
are subspaces which are pairwise orthogonal and whose union spans 
which decomposes as a disjoint union 
a (necessarily orthonormal) basis of 
, then we say that 
In particular, the basis 
is adapted to the orthogonal decomposition 
has no dependence on 
and 
Namely, by induction the Frobenius scalar product 
on 
on 
.
be Hilbert spaces. Their 
has underlying set 
and 
Second, let 
be orthonormal bases.
and 
are disjoint sets whose union constitutes an orthonormal basis of 
on 
has no dependence on 
of 
we have
is essentially the finite-dimensional 
containing a unit vector 
Thus, 
and 
Because the target space 
is one-dimensional, there are only 
elementary transformations in 
is the linear transformation defined by
as defining a function 
forces 
The Riesz mapping is not linear but antilinear,
be an arbitrary transformation. Then, for each 
we have 
for some 
Thus, for any 
we have
Note that 
where 
may be any complex number of modulus one: the orthonormal bases of 
are exactly singleton sets containing a point on the unit circle. The standard definition of covectors is made assuming that we take 
as the basis of 
Thus, we may define a scalar product on 
It is defined solely in terms of the scalar product in 
the Riesz scalar product 
on 
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, 
Indeed, for any finite set 
such that an isomorphism 
Any such isomorphism is called an ordering of 
Once an ordering is fixed, we can encode 
as the column vector ![[x_j]_i= \begin{cases} 1, \text{ if }j=i \\ 0, \text{ if } j \neq i \end{cases}.](https://s0.wp.com/latex.php?latex=%5Bx_j%5D_i%3D+%5Cbegin%7Bcases%7D+1%2C+%5Ctext%7B+if+%7Dj%3Di+%5C%5C+0%2C+%5Ctext%7B+if+%7D+j+%5Cneq+i+%5Cend%7Bcases%7D.&bg=FFFFFF&fg=000&s=0&c=20201002)
then a function ![[f]_{ij} = \begin{cases} 1, \text{ if }f(x_j)=y_i \\ 0,\text{ if } f(x_j) \neq y_i \end{cases}.](https://s0.wp.com/latex.php?latex=%5Bf%5D_%7Bij%7D+%3D+%5Cbegin%7Bcases%7D+1%2C+%5Ctext%7B+if+%7Df%28x_j%29%3Dy_i+%5C%5C+0%2C%5Ctext%7B+if+%7D+f%28x_j%29+%5Cneq+y_i+%5Cend%7Bcases%7D.&bg=FFFFFF&fg=000&s=0&c=20201002)
![[f(x_j)]_i.](https://s0.wp.com/latex.php?latex=%5Bf%28x_j%29%5D_i.&bg=FFFFFF&fg=000&s=0&c=20201002)
For any two functions 
such that 
is defined, it can be computed as the matrix product ![[g][f].](https://s0.wp.com/latex.php?latex=%5Bg%5D%5Bf%5D.&bg=FFFFFF&fg=000&s=0&c=20201002)
So our conclusion early on was that everything about 
-scalar product. The functor 
are isomorphic objection in 
Not full means that there are many more morphisms in 
then there are in 
, and this is a good thing. For example, in order to show that 
is said to be 
if for every 
we have 
which is the same thing as saying that 
whose objects are complex vector spaces and whose morphisms are linear maps. 
the full subcategory of 
let 
by
relative to the orthonormal bases 
and all other matrix elements are equal to zero.
is a basis of 
and show that the expansion of any 
Another useful consequence of having an explicit basis for this space is the following.
and let 
and 
is a norm on 
