One of the most interesting patterns that has ever been constructed in Conway’s Game of Life is primer, a gun that fires lightweight spaceships that represent exactly the prime numbers. It was constructed by Dean Hickerson way back in 1991, yet arguably no pattern since then has been constructed that’s as interesting. It seems somewhat counter-intuitive at first that the prime numbers, which seem somehow “random” or “unpredictable”, can be generated by this (relatively simple) pattern in the completely deterministic Game of Life.

Primer, the prime-generating gun

The gun works by firing lightweight spaceships westward, and destroying them via glider guns that emulate the Sieve of Eratosthenes. A lightweight spaceship makes it past the left edge of the gun at generation 120N if and only if N is a prime number (though for technical reasons, 2 and 3 are not outputted).

The first six lightweight spaceships output by primer

It wasn’t too long after making primer that Hickerson realized that he could attach a gun to the bottom-left corner of it to turn it into a twin prime calculator by allowing each lightweight spaceship through only if another lightweight spaceship passed through 240 generations earlier. Similarly, Jason Summers constructed a Fermat prime calculator in 2000 by shooting a glider at the lightweight spaceship stream every generation of the form 120(2^N + 1), which ends up detecting exactly the Fermat primes.

So what other families of primes can we compute in Life by altering the output of the original prime-generating gun?

Mersenne Primes

Mersenne primes can easily be computed using the exact same method as was used in the Fermat prime calculator — use a 7-engine Cordership (in blue below) to bounce a glider back at the stream of lightweight spaceships, with the time required for the glider to reach the stream doubling each time. An inverter (in green below) eliminates all lightweight spaceships that try to get past it unless it just received a glider from the Cordership. By fiddling around with timing a tiny bit, we then have a Mersenne prime calculator:

Mersenne Prime Calculator

• Java link: here
• RLE file: here

Prime Quadruplets

Four prime numbers are said to form a prime quadruplet if they are of the form (p, p+2, p+6, p+8) for some prime number p, which is the closest that four prime numbers can be together (except for the degenerate cases of (2,3,5,7) and (3,5,7,11)). Prime quadruplets are easy to compute because they can be thought of as consecutive pairs of twin primes. Since we already have a twin prime calculator, we can just repeat its reaction.

The twin prime calculator works by attaching a period 240 gun (in green below) to the bottom-left corner of primer. If it is timed correctly, it has the effect of allowing a lightweight spaceship through at generation 240N if and only if a lightweight spaceship tried to pass through at generation 240(N-1). Thus, it will only allow a lightweight spaceship through if it represents a prime number of the form p+2, where p is another prime number. Well, simply attaching a period 720 gun (in blue below) then allows a spaceship through at generation 720N if and only if a lightweight spaceship tried to pass through at generation 720(N-1). This has the effect of allowing a lightweight spaceship to pass through only if it represents a twin prime pair (p,p+2), and there is another twin prime pair of the form (p-6,p-4). That is, the only lightweight spaceships allowed through are those representing the upper members of prime quadruplets.

Prime quadruplet calculator

• Java link: here
• RLE file: here

Prime Pairs of the Form (p, p+2k)

The twin prime calculator mentioned earlier gives a way of computing prime pairs of the form (p,p+2), but what about pairs where the gap is larger than 2? For example, the k=2 case gives what are known as cousin primes, and the k=3 case gives sexy primes (yes, really).

For the case of cousin primes, the thing to notice is that every pair of cousin primes (except for the first pair, (3,7)) must be of the form (6n+1, 6n+5) for some natural number n. Thus, we can use two period 720 guns (in blue below) to allow only the upper prime in a cousin prime pair to pass through. This is achieved by having the top gun fire at the lightweight spaceships representing primes of the form 6n+1 — if a lightweight spaceship is hit, then a block is created in the path of the other gun, which is fired at lightweight spaceships representing primes of the form 6n+5. If a prime was present at 6n+1, then the lightweight spaceship makes it through unharmed at 6n+5. If there was no prime present at 6n+1, then the bottom gun destroys the lightweight spaceship representing 6n+5.

Cousin prime calculator

• Java link: here
• RLE file: here

Extending this idea to prime pairs of the form (p,p+2k) for k ≥ 3 is a bit more challenging, however, because it is possible for pairs to overlap. For example, (37,43) is a sexy prime pair, as is (41,47). Up until now we have only been able to detect single pairs at a time, since the block that acts as our “counter” that keeps track of whether a prime was detected earlier is placed in the stream of incoming lightweight spaceships. Thus, if it’s possible for two pairs to overlap, we will get lightweight spaceships colliding with the block, causing a mess.

To get around this problem, we use a device (known as a fanout, in green below) that duplicates the stream of lightweight spaceships. We then check for certain pairs on one stream, and the rest of the pairs on the other stream (these devices are outlined in blue below). Once we’re done, we merge the resulting streams of lightweight spaceships back together (using the devices in purple below).

To make this process a bit more explicit, I present a gun that computes prime pairs of the form (p,p+8). In particular, a lightweight spaceship will make it past the left edge of this pattern at about generation 1620+120N if and only if both N and N+8 are prime.

(p, p+8) prime calculator

• Java link: here
• RLE file: here

We now have all of the tools needed to build any pattern that computes prime pairs of the form (p, p+2k) as long as k = 1 or 2 (mod 3), though we may need to use the fanout device multiple times if it’s possible for more than one pair to overlap. If k = 0 (mod 3), however, it’s much more difficult to construct the desired pattern, because not only can you have overlapping prime pairs like (5, 11) and (7, 13), but you can have prime pairs in sequence such as (5, 11) and (11, 17). This problem can be remedied using the same tools as used in the (p,p+8) prime calculator, though you may need to use a lot of fanout devices to make things work. For example, computing the sexy primes using these tools would require at least four fanouts, and some clever elimination logic on each of the resulting five lightweight spaceship streams. I don’t feel up to that task myself, but it’s nice to know that we have a method for constructing a sexy prime calculator.

In matrix analysis, there are several different matrix norms that you might use depending on the context of your particular problem. If you are treating the matrix as an operator acting on a the complex vector space Cⁿ, then you would likely use the operator norm. If you are considering the matrix as a density operator (i.e., if you’re a quantum information nerd like me) then you might want to use the trace norm. If you just want something that’s easy to calculate, you might be better off going with the Frobenius norm. These are three of the most well-studied and well-used matrix norms, and they have one very important thing in common — they are unitarily invariant. That is, if X ∈ M_n, then

Unitarily-invariant norms are particularly “nice” in that they satisfy submultiplicativity as well as various other desirable properties. Here I will present two particular families of unitarily-invariant norms, briefly discuss some of their applications, and then define a family of norms that encompass all of the other norms mentioned in this post as special cases.

Before proceeding, recall that for any matrix X ∈ M_n we can define the absolute value |X| of X to be the positive matrix square root of X^*X. Then the singular values of X, s₁(X), s₂(X), …, s_n(X), are defined to be the eigenvalues of |X|. Throughout this post we will assume that the singular values are ordered from largest to smallest (this is pretty standard practice when dealing with singular values):

Ky Fan Norms

Given a natural number k such that 1 ≤ k ≤ n, the Ky Fan k-norm of a matrix X ∈ M_n is defined to be the sum of the k largest singular values of X:

While Ky Fan norms aren’t extremely well-known, they have applications is matrix theory as well as quantum information theory. For example, they have recently appeared in [1] as a tool for determining whether a linear map from M_n to M_m is k-positive, which is one of the difficult open problems in quantum information. If P_k ⊆ M_n denotes the space of rank-k orthogonal projections (i.e., matrices such that P² = P^* = P), then it is not difficult to show that

Several properties of these norms are obvious from the definition — for example, the Ky Fan k-norm is upper-bounded by the Ky Fan (k+1)-norm and each Ky Fan norm is unitarily-invariant. One property that isn’t immediately obvious, however, is the following very cool result:

Fan Dominance Theorem [2, Section IV.2]. Let X, Y ∈ M_n. Then

if and only if

Schatten Norms

Given a real number p ≥ 1, the Schatten p-norm of a matrix X ∈ M_n is defined to be the standard vector p-norm of the vector of singular values of X:

There are numerous applications of Schatten norms in quantum information theory. For example, they are used to define completely bounded norms for linear maps acting on matrices, which are probably the most important norms for maps in quantum information (see [3] for a particular paper that deals with these norms). As with the Ky Fan norms, the Schatten norms are unitarily-invariant and can be equivalently defined via an expression involving the trace:

One of the other nice properties of the Schatten p-norms is a modified submultiplicativity result, which states that if X,Y ∈ M_n then

Everything In Between

We have now seen two families of norms based on the singular values of a matrix, both of which are very important in matrix analysis as well as quantum information theory. The Ky Fan norms are given by summing the first k singular values, while the Schatten norms are given by computing the standard vector p-norm of the vector of singular values. So why have I never seen the natural generalization of these two families of norms – the vector p-norm of the first k singular values – defined? (Update [May 14, 2012]: See the comments for a few references that study these norms.)

Definition. Let X ∈ M_n, p ≥ 1 and 1 ≤ k ≤ n, with k a natural number. Then I define the (p,k)-singular norm of X to be

Notice that these norms are also unitarily-invariant, and as with the previously-defined norms, they are given by a relatively simple trace expression:

One particular case of these norms – the p = 2 case – actually appeared implicitly in [1], though they were referred to as Ky Fan norms. I have also found a need for the p = 2 case of these norms in a recent project of mine that will hopefully be wrapped up in the next month or so.

I will finish by pointing out some special cases of this norm:

• If we allow p = ∞ by taking the limit as p → ∞ in the above definition, then the (∞,k)-singular norm coincides with the standard operator norm, regardless of k.
• When p = 1, the (1,k)-singular norm is exactly the Ky Fan k-norm.
• When k = n, the (p,n)-singular norm is exactly the Schatten p-norm.
• When p = 1, k = n (i.e., the Schatten 1-norm, which equals the Ky Fan n-norm), we recover exactly the trace norm.
• When p = 2, k = n (i.e., the Schatten 2-norm), we recover exactly the Frobenius norm.
• When p = 1, k = 1 (i.e., the Ky Fan 1-norm), we again obtain the operator norm.

References

1. D. Chruscinski, A. Kossakowski, Spectral Conditions for Positive Maps. Commun. Math. Phys. 290, 10511064 (2009). arXiv:0809.4909 [quant-ph]
2. R. Bhatia, Matrix analysis. Volume 169 of Graduate texts in mathematics (1997).
3. I. Devetak, M. Junge, C. King, M. B. Ruskai, Multiplicativity of completely bounded p-norms implies a new additivity result. Commun. Math. Phys. 266, 37-63 (2006). arXiv:quant-ph/0506196

This week I presented a poster at the Mathematics in Experimental Quantum Information Processing Workshop at the Institute for Quantum Computing in Waterloo, Ontario, and I will admit that I had a few fleeting moments when I was considering using Microsoft Publisher to create it. I couldn’t find any poster templates in LaTeX that I liked, and frankly LaTeX just seemed like it wouldn’t work well for something moderately graphics-heavy like a poster.

However, as it always does, the desire for easy-to-integrate mathematics won the battle and it wasn’t long before I was scrounging the depths of the tenth page of Google search results for LaTeX poster templates. Eventually I did find a template that I was able to modify to my liking, and this is the result:

Since I’m such a nice guy, you can download the .tex and .sty files used to create the poster here if you would like to. The poster is based on the template created by the Computational Pysics and Biophysics Group at Jacobs University with the following minor modifications:

• Four column landscape layout instead of three column portrait layout.
• Changed from A0 (33.1″ × 46.8″) paper to 48″ × 36″ poster paper (which is a bit more standard in my experience).
• Removed the blue border around the poster (I hate borders, and it’s cheaper to print this way!).
• Used a serif font rather than a sans-serif font for small (i.e., non-header) text.
• Messed around with the header.
• Moved the university logo from the header down to the “Acknowledgements” section.

Update [April 12, 2011]: I have updated the template (thanks John Mahoney and Fei) so that, among other things, the issue with summation and integration signs not scaling properly is now fixed.

Update [April 25, 2011]: The template has been updated again – it now includes 68 common color definitions in the style file as a workaround for the fact that this template doesn’t play nicely with the colordvi package. Thanks to Nishan Mudalige for the fix!

Update [August 4, 2011]: Nishan has been nice enough to provide another update for the template, which causes automatic figure numbering to work properly (you had to enter figure numbers manually in the past).

Download:

• LaTeX poster template [.zip of LaTeX files]
• My poster: The multiplicative domain in quantum error correction [.zip of LaTeX files]

Recall for matrices that a similarity transformation is one that takes a (square) matrix A to SAS^-1, where S is some invertible matrix of the same size as A. Standard linear algebra courses like to beat into students just how important similarity transformations are, which makes sense from their point of view because linear algebra is really more about studying operators than matrices themselves, and similarity transformations correspond to just a change of basis. The downside is that many people end up thinking of similarity as the equivalence relation among matrices and hence the Jordan canonical form as the canonical form. This month’s Lemma of the Month is about the canonical form under a different equivalence relation: *-congruence.

What is *-Congruence?

Two square matrices A and B are said to be *-congruent if there is an invertible matrix S such that SAS^* = B. Even though no inverses are present in that equation, invertibility really is required for any nice results to be obtained (for example, *-congruence would not even define an equivalence relation if S were allowed to be singular). For people who like knowing applications of mathematical tools before knowing the tools themselves, *-congruence has an important role when dealing with quadratic forms. Also, the inertia of a matrix, which will be defined in the next paragraph, comes into play when looking at sign pattern matrices (apologies for the lack of a wiki link; it seems as though sign pattern matrices are at that ugly stage after there are lots of papers written about them but before there is a Wikipedia page written about them).

Sylvester’s Law of Inertia

By far the most well-known result about *-congruence is Sylvester’s Law of Inertia, which gets its name from the seldom-used inertia of a matrix. The inertia of a Hermitian matrix A is defined to be the tuple

where n₊ is the number of positive eigenvalues of A, n₀ is the number of zero eigenvalues of A, and n_– is the number of negative eigenvalues of A (recall that Hermitian matrices have real eigenvalues, so this definition makes sense). Sylvester’s Law of Inertia is as follows:

Theorem [1,2]. Let A, B ∈ M_n be Hermitian. Then A and B are *-congruent if and only if they have the same inertia.

One obvious corollary of this theorem is that every Hermitian matrix A is *-congruent to a diagonal matrix with n₊ ones, n₀ zeroes, and n_– negative ones on the diagonal; this is the canonical form for Hermitian matrices under *-congruence.

Generalizations of Sylvester’s Law

If you’re a linear algebra nerd like me, then you might be thinking to yourself that Sylvester’s Law of Inertia seems trivial in light of the Spectral Decomposition Theorem; for any Hermitian A we could find a unitary so that UAU^* is real and diagonal, and then we could find a diagonal D such that DUAU^*D^* is scaled appropriately to satisfy the theorem. Setting S = DU then shows us that we can always arrive at the canonical form.

Notice, however, that the Spectral Decomposition Theorem applies not only to Hermitian matrices, but to normal matrices as well. Thus, using the same logic outlined in the previous paragraph, it stands to reason that the canonical form under *-congruence for normal matrices should be a diagonal matrix in which each diagonal entry either has modulus one or zero. Indeed, this is essentially the content of the following theorem of Ikramov, which was proved in 2001.

Theorem [3]. Let A, B ∈ M_n be normal. Then A and B are *-congruent if and only if they have the same number of eigenvalues on each open ray from the origin in the complex plane.

This theorem truly generalizes Sylvester’s Law of Inertia; in the Hermitian case, the only two open rays that eigenvalues can lie on are the positive real line and the negative real line. What I would like to know, though, is why on Earth this theorem was first proved/published so recently — it seems like such a natural generalization of Sylvester’s Law of Intertia that it seems like it should be a very old result! Is it just a hole in the literature that wasn’t noticed until recently?

Anyway, for the really interested reader, there is a generalization of these results to the case when A and B need not even be normal, but it’s quite technical so I won’t present it here. See [4] if you’re curious.

Thanks to Roger Horn for his great series of lectures at the Summer School and Advanced Workshop on Trends and Developments in Linear Algebra, which introduced me to the generalizations of Sylvester’s Law.

References:

1. Sylvester, J. J., A demonstration of the theorem that every homogeneous quadratic polynomial is reducible by real orthogonal substitutions to the form of a sum of positive and negative squares. Philosophical Magazine IV: 138–142 (1852).
2. Horn, R. and Johnson, C., Matrix analysis. Cambridge University Press (1990).
3. Ikramov, Kh. D., On the inertia law for normal matrices. Doklady Math. 64 (2001) 141-142.
4. Horn, R. and Sergeichuk, V., Canonical forms for complex matrix congruence and *congruence. Linear Algebra Appl. 416 (2006) 1010-1032. arXiv:0709.2473v1 [math.RT]