Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Calculations with linear relations

Aleks Kissinger (Aug 03 2020 at 13:51):

The category $LinRel(k)$ of linear relations is a handy category with lots of nice features and applications. In PROP form, it has as objects natural numbers (as always), morphisms $m \to n$ are subspaces of the vector space $R \subseteq k^m \oplus k^n$, and composition is done relation-style. That is, $(u,w) \in (R;S) \iff \exists v . (u,v) \in R \wedge (v,w) \in S$. One can then show $(R;S)$ forms a subspace whenever $R$ and $S$ do, so it all fits very nicely together into a (symmetric monoidal) category.

Aleks Kissinger (Aug 03 2020 at 13:56):

I'm interested in doing some basic, concrete calculations from efficient representations of linear relations. I more or less know how to do many of these in the graphical linear algebra way, by drawing diagrams to represent linear relations then applying graphical rewrite rules, but I'd like to also get some competence working with these using vectors and/or matrices and Gauss-Jordan type tricks.

Aleks Kissinger (Aug 03 2020 at 13:58):

A basic example is composing linear relations from their basis representations. For example, suppose $R = span(a,b,c)$ and $S = span(x,y)$, how can I efficiently get a spanning set of vectors for $R ; S$?

Aleks Kissinger (Aug 03 2020 at 14:01):

One can also ask the "perp" of this question. Suppose $R$ and $S$ are each described by a set of independent homogeneous linear equations, how can I compute the equations for $R ; S$?

In other words, given spanning sets for $R^\perp$ and $S^\perp$, what is a spanning set for $(R;S)^\perp$?

Aleks Kissinger (Aug 03 2020 at 14:05):

I think there are many ways to do this, possibly by doing some stuff that might seem quite weird in an undergrad linear algebra course, like computing a pullback of matrices. My question is, are there easy, elementary tricks for doing these kinds of calculations?

Maybe some of you who have been working with these categories a lot can shed some light on this. @Pawel Sobocinski @Brendan Fong @Cole Comfort

Cole Comfort (Aug 03 2020 at 22:54):

A map in $\sf FinRel$ can be (fully and faithfully) represented as a matrix over the Booleans. Therefore, given a prime $p$ and a map ${{\mathbb F}_p}^n\to {{\mathbb F}_p}^m$ in ${\sf LinRel}_{{\mathbb F}_p}$; forgetting the linear structure and strictyfying (via the functor ${\sf LinRel}_{{\mathbb F}_p}\xrightarrow{U} {\sf FinRel} \xrightarrow{\sim} {\sf Mat}({\mathbb{B}})$), this is just a $p^n \times p^m$ matrix over the Booleans because, the set $U({{\mathbb F}_p}^m)$ has cardinality $p^m$. So if you can explain matrix multiplication to an undergraduate, you could get them to crunch numbers and compute composition in linear relations over a finite field... they might not understand what is going on, though. I'm not sure if this answers the question or not.

Aleks Kissinger (Aug 04 2020 at 10:18):

The key word here is efficiently computing compositions. I'd like to be able to do pen-and-paper calculations up to $n = 5$ or so, and fast computer calculations up to maybe $n = 100$.

The benefit of linear relations over generic relations is you only need a quadratic amount of data to represent a linear relation (e.g. as a spanning set), and Gauss-based calculations tend to be cubic. As you say, if you have a finite field, you can always compute the entire subset and do normal relation composition, but this gets expensive very quickly.

Aleks Kissinger (Aug 04 2020 at 10:24):

Maybe here's a tack we can take:

Q: Suppose I have a linear relation $R = \langle (u_1, v_1), \ldots, (u_k, v_k) \rangle$, where $\langle \cdot \rangle$ is the linear span (not to be confused with "spans" in the CT sense). Can I represent this as a span of matrices $m \xleftarrow{M} k \xrightarrow{N} n$?

A first guess, based on the dimensions is the $u_i$ become the columns of $M$ and the $v_i$ become the columns of $N$. Is that right?

Cole Comfort (Aug 05 2020 at 05:23):

Quoting @Pawel Sobocinski https://graphicallinearalgebra.net/2016/02/03/28-subspaces-diagrammatically/#comment-3460 :

So the “Fundamental Theorem of Graphical Linear Algebra”, if there is such a thing, is that any diagram can be written in span form and in cospan form, i.e. as a span or a cospan of matrices. When you look at examples, to put a diagram into span form is to express the associated linear relation as a span of a list of basis vectors, and in cospan form as a solution of a list of homogenous linear equations.

So Pawel just confirms what you are saying.

If I were trying to explain this to undergraduates; perhaps I would take the cospan approach because computing the pushout corresponds to adding both sets of constraints together.

Perhaps this is the most amazing coincidence of terminology I have come upon, that both notions of spans coincide in this setting.

Aleks Kissinger (Aug 05 2020 at 10:20):

Yes, it's a very nice coincidence. However, I can't figure out if that makes the terminology clash better or worse. :)

Aleks Kissinger (Aug 05 2020 at 10:30):

Okay, I think I've found a suitably down-to-earth strategy for composing linear relations in span-form.

Take two linear relations $R : m \to n, S: n \to o$, given as $R = \langle (u_i, v_i) \rangle_i$ and $S = \langle (v_j', w_j) \rangle_j$. We need to compute a basis for $(R;S) : m \to o$.

Aleks Kissinger (Aug 05 2020 at 10:33):

Arrange the vectors into the columns of a matrix with $m + n + o$ rows, as follows:
$\left(\begin{matrix} v_1 & \cdots & v_k & -v_1' & \cdots & -v_l' \\ u_1 & \cdots & u_k & 0 & \cdots & 0 \\ 0 & \cdots & 0 & w_1 & \cdots &w_l \end{matrix}\right)$

Aleks Kissinger (Aug 05 2020 at 10:39):

For convenience, I've put all of the $v$'s at the top, because we want to "zero these out". That is, we perform Gaussian elimination on the columns to obtain:
$\left(\begin{matrix} p_1 & \cdots & p_a & 0 & \cdots & 0 \\ \cdots & \cdots & \cdots & u_1' & \cdots & u_b' \\ \cdots & \cdots & \cdots & w_1' & \cdots & w_b' \\ \end{matrix}\right)$
where all of the $p$'s are non-zero (i.e. they contain a pivot).

Aleks Kissinger (Aug 05 2020 at 10:42):

Now, we throw away the first $a$ columns (and any all-zero columns), and use the rest to form $(R;S)$:
$(R;S) = \langle (u_1', w_1'), \ldots, (u_b',w_b')\rangle$

Aleks Kissinger (Aug 05 2020 at 10:45):

So, where the hell did that come from? (you might ask). Actually, re-reading the post you linked on @Pawel Sobocinski's blog made it click.

Aleks Kissinger (Aug 05 2020 at 10:54):

As usual, it's easier to treat everything as a state, by bending some wires. N.b. "caps" and "cups" don't coincide for fields other than $\mathbb Z_2$, so we define them relative to the black dot, but convention.

This relation:
image.png

Aleks Kissinger (Aug 05 2020 at 10:54):

is spanned by the columns of:
$\left(\begin{matrix} u_1 & \cdots & u_k & 0 & \cdots & 0 \\ v_1 & \cdots & v_k & 0 & \cdots & 0 \\ 0 & \cdots & 0 & v_1' & \cdots & v_l' \\ 0 & \cdots & 0 & w_1 & \cdots &w_l \end{matrix}\right)$

Aleks Kissinger (Aug 05 2020 at 11:00):

This relation:
image.png

Aleks Kissinger (Aug 05 2020 at 11:01):

subtracts the $v$-primes from the $v$'s and swaps the middle row to the top. Giving:
$\left(\begin{matrix} v_1 & \cdots & v_k & -v_1' & \cdots & -v_l' \\ u_1 & \cdots & u_k & 0 & \cdots & 0 \\ 0 & \cdots & 0 & w_1 & \cdots &w_l \end{matrix}\right)$

Aleks Kissinger (Aug 05 2020 at 11:03):

Finally, the tricky bit is plugging a white dot into the first $n$ wires:
image.png

Aleks Kissinger (Aug 05 2020 at 11:07):

This is the "op" of the zero vector, which restricts to the largest subspace which is zero in the first $n$ rows. This is like a "partial kernel" of a matrix, which is exactly what the bit of Gauss-Jordan we did here:
$\left(\begin{matrix} p_1 & \cdots & p_a & 0 & \cdots & 0 \\ \cdots & \cdots & \cdots & u_1' & \cdots & u_b' \\ \cdots & \cdots & \cdots & w_1' & \cdots & w_b' \\ \end{matrix}\right)$
is used to compute.

Anything with a pivot in the first $n$ rows can't be involved in any linear combination in the resulting relation, so we throw them away and keep the rest.

Aleks Kissinger (Aug 05 2020 at 11:19):

This gives the "wire-bent" version of the composition $(R;S)$ because:
image.png

Pawel Sobocinski (Aug 05 2020 at 13:02):

This is super cool @Aleks Kissinger , but I guess there's a -1 missing? To turn the white cap to a black cap in your second last step.

Aleks Kissinger (Aug 05 2020 at 13:15):

ah ha! i thought there was something funny going on with the signs. I'm used to thinking in $\mathbb Z_2$, where plus = minus, and the two cups coincide.

(Note: the figures above have now been fixed to incorporate the $-1$ via an antipode.)

Pawel Sobocinski (Aug 05 2020 at 13:20):

I guess in your construction you should just start with -S and it will all be good.

Aleks Kissinger (Aug 05 2020 at 13:21):

rather the writing it again, i'm going to rewrite history above :)

Pawel Sobocinski (Aug 05 2020 at 13:26):

Right :) the v primes should be negated.

Aleks Kissinger (Aug 05 2020 at 13:28):

okay done. does that look right to you?

Aleks Kissinger (Aug 05 2020 at 13:32):

I was somewhat inspired by the concrete construction of the pullback of matrices from Fabio Zanasi's thesis (p.74 of https://arxiv.org/pdf/1805.03032.pdf ).

There, you can see a minus sign appearing in the $Ker(A | {-B})$. I think it's there for the same reason.

Pawel Sobocinski (Aug 05 2020 at 13:46):

Yeah, exactly! It's in whole bunch of control theory literature also for this reason. In fact, there the symmetry between spans and cospans breaks: cospans describe all behaviour (as Ker(A|-B)), spans only the controllable behaviours. This is explained in my LiCS16 paper with @Brendan Fong and Paolo Rapisarda.

Aleks Kissinger (Aug 05 2020 at 14:15):

Hmm, not sure I get that. But I haven't read the paper, and don't really understand the connection to dynamical systems that well.

Aleks Kissinger (Aug 05 2020 at 14:20):

I guess both spans and cospans of matrices give a (somewhat redundant) description of a linear relation. Spans as $Im\left(\begin{matrix} A \\ B \end{matrix} \right)$ and cospans as $Ker\left( \begin{matrix} A & {-B} \end{matrix}\right)$.

It seems any linear relation can be written in either form, but maybe you care about this extra, redundant data. The extra data can be thought of as a particular choice of presentation (either as a spanning set or a system of homogeneous equations).

Pawel Sobocinski (Aug 05 2020 at 14:56):

Yes. And the minimum size of the representation (which corresponds to the number of wires "in the middle") is the dimension (for the span case) and codimension (for the cospan case).

Aleks Kissinger (Aug 05 2020 at 16:13):

So, in terms of representing linear relations, they seem totally equivalent. What am I missing here? Does this talk about "behaviours" go outside of the LinRel world?

Cole Comfort (Aug 05 2020 at 16:37):

Perhaps this is related to the comment of Zanasi in his thesis?

Remark 3.18. It is worth mentioning that the same reasoning does not apply to pushouts: they
exist in MatR for purely formal reasons, being the category self-dual, but cannot be generally
calculated as in ModR. This asymmetry actually plays a role in our developments: we shall return
to it in Remark 3.54.

Pawel Sobocinski (Aug 05 2020 at 20:47):

@Aleks Kissinger you're referring to my previous comment about control theory? In that case yes, it's not LinRel anymore.

Aleks Kissinger (Aug 06 2020 at 09:12):

okay, that makes more sense. So, why the minus sign in kernel-form and not image-form?

Pawel Sobocinski (Aug 06 2020 at 11:40):

It's how you get from the span/cospan to the thing which has been rewired to have boundaries on one side only

In the case of cospan you get (A⊗B); black cap. For this entire thing to be in matrix form you want to turn this into a white cap. So you get
(A⊗-B);white cup. Now this expression is just $\mathsf{ker}\left(\begin{array}{cc} A & -B \end{array}\right)$.

In the case of span black cup;(A⊗B). This thing after the black unit is already in matrix form, and this expression already gives you $\mathsf{im}\left(\begin{array}{c} A \\ B\end{array}\right)$.

Pawel Sobocinski (Aug 06 2020 at 11:41):

I don't know how to latex here.. but it should be clear

Aleks Kissinger (Aug 06 2020 at 12:44):

that makes sense. It's basically because matrices want to have white-dot mult and black-dot comult. The asymmetry comes from the fact that we are using matrices in both cases, rather than treating a span of matrices as a cospan of "op-matrices", i.e. relations of the form { (Mv,v) | v in V }.

ps. i think its not showing the latex right because you have \begin{array} without \end{array} and some funny extra braces.

Aleks Kissinger (Aug 06 2020 at 12:46):

The fact that LinRel is equivalent to its op in (at least) 2 different ways is a bit mind-bending...

Morgan Rogers (he/him) (Aug 06 2020 at 14:00):

Pawel Sobocinski said:

I don't know how to latex here.. but it should be clear

You forgot \end{...}, and for some reason the extra curly braces around the contents of the matrix broke it! The bmatrix environment is another option if you don't mind square brackets around your matrices.

Pawel Sobocinski (Aug 07 2020 at 12:03):

Right, thanks :)

Pawel Sobocinski (Aug 07 2020 at 12:07):

@Aleks Kissinger Yes.. exactly. Matrices do a lot of work in traditional accounts, and the diagrams really help to explain it. Actually I just submitted a paper with João Paixão on Graphical Linear Algebra... we have a whole bunch of stuff in the pipeline that will hopefully result in a book, eventually. I should hit you up for book writing advice at some point!