Blog of Matthew Daws

Overleaf and Git

More of a note to myself than anything else. Lancaster University has recently obtained a uni-wide Overleaf license. Overleaf is of course the online LaTeX editing system (as an aside, I didn't realise until now that the underlying web-app is Open Source). I haven't used Overleaf much, as I don't like the idea of needing a stable internet connection to work on my LaTeX files, and have a reasonable system going with MikTeX and VSCode with the LaTeX plugin.

One advantage, however, is collaboration, especially as I can't convince collaborators to work with GitHub. The license is needed to have more than one collaborator, but it also gets you Git integration. Basically, the Overleaf project will act as a Git repository which you can push/pull from (but not branch; still, if I get a collaborator who is up for using branches, then (a) we can just use GitHub; and (b) I need to worry about why my Mathematics article is some complex...)

Travelling and a New Year

Somehow it is 2024 already. I spent the week before Christmas at a pleasant conference in Besançon, France. A photo of us all in the initial lecture theatre:

Cheap analysis

This is a follow-on to an older post prompted by a comment from Yemon Choi (an old friend who is now a colleague). There are of course many examples of monotone Galois connections in Functional Analysis. Here is one example which I like.

Let \( E \) be a Banach space. Let \( \mathcal X \) be the collection of all linear subspaces of \( E \), ordered by inclusion. Let \( \mathcal Y \) be the collection of all linear subspaces of \( E^* \) (the dual space of all continuous linear functionals) ordered by reverse inclusion.

Given \( F\in\mathcal X \) we define \[ \mathcal L(F) = \{ f\in E^* : f(x)=0 \ (x\in F) \} \in \mathcal Y, \] the annihilator of \( F \), easily seen to be a subspace. If \( F_1 \leq F_2 \) then \( F_1 \subseteq F_2 \) and so \( \mathcal L(F_1) \supseteq \mathcal L(F_2) \) (if \( f \) vanishes on \( F_2 \) it will vanish on \( F_1 \)). So \( \mathcal L(F_1) \leq \mathcal L(F_2) \) and \( \mathcal L \) is order-preserving.

Similarly given \( F\in\mathcal Y \) define \[ \mathcal R(F) = \{ x\in E : f(x)=0 \ (f\in F) \}\in \mathcal X, \] the pre-annihilator of \( F \). This is again an order-preserving map.

From pinchings to quantum colourings

Finally, I can combine the last post with a post 3 ago. This argument is from a paper of Elphick and Wocjan, attributed there to Roberson.

Fix a graph \( G \) with adjacency matrix \( A \).

Theorem: Let \( \mathcal C \) be a pinching on \( \mathbb M_n\otimes\mathcal B(H) \) with \( \mathcal C(A\otimes 1_H)=0 \) and \( \mathcal C(D\otimes 1_H)=D\otimes 1_H \) for each diagonal matrix \( D \). Then \( \mathcal C \) arises from a quantum colouring of \( G \), in the manner described before.

Quantum chromatic numbers

Continuing from the last post I want to now consider the Quantum Chromatic Number of a graph. These ideas arose from Quantum Information Theory, which explore how quantum entanglement can be used in certain two-person "games", which are very similar to Interactive proof systems. While the motivation can be a little hard to explain, the resulting mathematical formalism is straightforward.

Definition: A quantum \( c \)-colouring of \( G \) is a collection of orthogonal projections \( \{P_{v,k} : v\in V_G, k\in [c] \} \) on some Hilbert space \( H \) (usually assumed finite-dimensional) such that:

1. \( \sum_{k=1}^c P_{v,k} = 1_H \) for each \( v \);
2. \( P_{v,k} P_{w,k} = 0 \) for each \( k \) and each edge \( v\sim w \) in \( G \).

There is a more complicated (but motivated) definition in [Cameron et al.] (see references below) where the reduction to this definition is essentially shown Proposition 1 and the later observations. It is also shown there that, when \( H \) is finite dimensional, we can always assume that each projection has the same rank (though this is sometimes not natural.) The following is the same spectral bound which we discussed before, but now for the quantum chromatic number \( \chi_q(G) \), the least \( c \) for which \( G \) has a quantum \( c \)-colouring.

Theorem: [Elphick-Wocjan] \( \chi_q(G) \geq 1+\frac{\lambda_1}{-\lambda_n} \).

Spectral bounds on the chromatic number

Recently Clive Elphink gave us a nice seminar where he discussed some of his "conjectures in spectral graph theory". Clive has an interesting history: after a career in business, he is now semi-retired and returned to research mathematics. By his own admission, he is more on the experimental side, and his talk said almost nothing about proofs. Here is a old result in this area:

Theorem [Hoffman]: We have that \( \chi(G) \geq 1 + \frac{\lambda_1}{-\lambda_n} \).

I explain the notation shortly, but in words, this result relates a vertex colouring of a graph to the eigenvalues of the adjacency matrix. To me, this seems hugely surprising, as why would the spectrum of \( A \) have anything to do with a vertex colouring? I want to explain the elegant arguments of Elphick and Wocjan, and also some generalisations to quantum colourings (in part 2).

Fixed points of complete positive maps

The first of hopefully a few posts about actual Mathematics, the context of which will follow. In Watrous's QIT book, Theorem 4.25 states the following:

Let \( \Phi:\mathbb M_n\rightarrow\mathbb M_n \) be a unital quantum channel with Kraus representation \( \Phi(x) = \sum_a A_a x A_a^* \). Then \( \Phi(x)=x \) if and only if \( A_a x = x A_a \) for each \( a \).

(Here I translate slightly the language). Whenever I see a statement about quantum channels, I ask myself if I can translate it into a more Operator Algebraic statement making more use of the Stinespring representation theorem, for example. After much messing about, I realised that the key property is that \( \Phi \) is trace preserving, and that this, together with multiplicative domain theory, can be used to give a simple proof. (Well, maybe not simple, but one adding some context.)

Cheap mathematics

A long-time-coming comment on a post by John Baez about "bargin-basement mathematics". (But let's not do ourselves down-- the rest of the system is more than happy enough to do that for us-- so I shall say "cheap" not quite "bargain-basement").

The setup here is a (monotone Galois connection), which consists of two posets \( X \) and \( Y \), and order-preserving maps \[ L:X\rightarrow Y, \qquad R:Y\rightarrow X, \] which satisfy \( L(x)\leq y \) if and only if \( x\leq R(y) \). The exercise, whose solution I'll give below, is that while \( L \) and \( R \) may of course fail to be mutual inverses, if we define \( X'=R(Y) \) and \( Y'=L(X) \) then \( L,R \) restrict to \( X',Y' \) respectively to become mutual inverses.