This month’s Lemma of the Month comes all the way from the Summer School and Advanced Workshop on Trends and Developments in Linear Algebra in Trieste, Italy, where Professor Rajendra Bhatia presented a lecture that introduced several simple yet endlessly interesting matrix inequalities. I will briefly present the various results here without proof, though the proof of the first “stepping stone” lemma is provided in the PDF attached to the bottom of this post. The truly interested reader can find full proofs in Professor Bhatia’s notes (follow the link above) or in [1].

Recall that one of the defining properties of a matrix norm is that it satisfies the triangle inequality:

So what can we say about generalizing the backward triangle inequality to matrices? We can of course replace A by A – B in the above equation to find the following backward triangle inequality:

However, what happens if we swap the roles of the absolute value and the matrix norm on the left-hand side? That is, if we recall that |A| is the positive semidefinite part of A (i.e., the square root of A^*A), then can we say something like

It turns out that the answer to this question is heavily norm-dependent, so we will focus on the norm that gives the simplest answer: the Frobenius norm, which I will denote by ||•||₂.

Theorem [Araki-Yamagami]. Let A, B ∈ M_n. Then

Building Up to the Result

In order to prove the result, one can proceed by proving a series of simple commutant-type matrix norm inequalities, which are interesting in their own right.

Lemma. Let A, B ∈ M_n be positive semi-definite and let X ∈ M_n be arbitrary. Then

Lemma. Let A ∈ M_n be Hermitian. Then

Lemma. Let A, B ∈ M_n be Hermitian. Then

Finally, it just wouldn’t seem right to post from Italy without sharing a bit of it. Thus, I leave you with a taste of the highlight of the trip (excepting the mathematics, of course).

The colosseum as of eight hours ago

Related Links

• Lemma of the Month #2: A Backward Triangle Inequality for Matrices [pdf]

References

1. H. Araki and S. Yamagami, An inequality for the Hilbert-Schmidt norm, Commun. Math. Phys., 81 (1981) 89-98.

In Conway’s Game of Life, a simple way to learn about the general dynamics of the game are to study what happens to soup – patterns made up of a random assortment of ON and OFF cells. Two particularly interesting questions that we can ask are “What types of stable patterns arise most frequently from soup?” and “How long does soup generally last before stabilizing?” I will focus on the latter question for today’s post, as the former has become the bud of a more ambitious project that I will announce in the near future.

The question of how long soup generally lasts before stabilizing is quite vague, because there are two important considerations that we have not specified:

1. How dense should the soup be? Clearly soup with ON density of 5% will survive only a fraction as long as soup with ON density of 50%.
2. How large of a region of soup should we let evolve? Smaller regions will stabilize much more quickly than large regions, and infinite regions will likely never stabilize(?), not to mention we can’t effectively simulate an infinite field of random cells.

For #2, I will choose the region to be of size 20×20. This decision is pretty arbitrary, but part of the reason I chose such a small size is as a desire to make this script kill two birds with one stone; any particularly long-lived patterns of this size that are discovered can likely be considered methuselahs, while larger patterns can not.

For #1, we might naively expect that patterns will live longest if they have density 37.5%, since cells are born if and only if they have exactly three ON neighbours (out of a possible eight = 37.5%). To test this theory, I created a Golly script that creates regions of varying density and checks how long it takes for them to stabilize. The following graph shows the average lifespan of 20×20 patterns with densities ranging from 1% to 99%, based on 5000 generated patterns for each percentage point.

Indeed, it looks like the longest-lived density estimate of 37.5% isn’t too far off. The true maximum in this set-up might actually be slightly higher, but that is most likely caused by the same thing that is causing the hump centered at 90%: edge effects. Roughly speaking, because we are simulating a finite region of soup on an infinite grid (as opposed to on a toroidal universe), patterns of higher density will tend to expand out very quickly in their first few generations, giving them longer lifespans in general than they would have on a toroidal universe. Alas, Golly doesn’t support toroidal universes, so the toroidal lifespan results will have to wait for another day.

Update [July 8, 2009]: I have attached to the end of this post the Python script used to generate these results.

Update [July 11, 2009]: See this post, which deals with the “more ambitious project” that I mentioned.

Update [July 19, 2009]: See this post, which deals with soup longevity on a torus.

Downloads:

• Methuselah 14042 – A methuselah with lifespan 14042 found during the search [.zip of an RLE file]
• Methuselah Search Script [.zip of a Golly Python script]
• Soup Density Data [Excel spreadsheet — 26.0kB]

The Collatz conjecture (or hailstone problem or 3n+1 problem) is a problem that is so simple to state that grade-schoolers can understand it, yet has been approached from an innumerable variety of angles and has resisted mathematicians for decades now. The problem is as follows:

Pick a positive integer. If it’s even then divide it by 2. If it’s odd, multiply it by 3 and add 1. Now apply this procedure to the result. Repeat. Will you always eventually hit 1 if you continue in this way?

For example, if you start with 11 then you multiply by 3 and add 1 to get 34, divide by 2 to get 17, and continuing similarly gets you the rest of the sequence: 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Before you go trying to find a counterexample to the conjecture, know that it has been verified by computer search for all starting numbers up to 20 × 2⁵⁸ ≈ 5.764 × 10¹⁸. The way that we are going to look at this problem today is the “pretty” approach; we’re going to extend the Collatz conjecture over the complex plane and look at the fractal defined by its iteration.

Define the Collatz function f(x) as follows:

Take a moment or two to convinve yourself that if x is a positive integer, then f(x) is the next number after x in its Collatz sequence (e.g., f(11) = 34, f(34) = 17, and so on). To extend this function to the real numbers, simply recall that (-1)^x = cos(πx). In fact, this gets us an extension to the complex numbers at the same time, and after some simplification we arrive at:

Well hey, that’s a holomorphic function so it has a notion of a Julia set and we can study the fractal that its iterates induce. Indeed, we can obtain the following image pretty easily with standard fractal-generation software:

The Collatz f(z) fractal

The fractal is located on the complex plane, and the horizontal line through the middle of the image is the real line. Black regions are regions in which the orbit of that number is bounded, while other colours indicate that the orbit of that number is unbounded (notice the large region of bounded numbers around z = 0). The big “spikes” that occur along the real line are, as we would expect, located at the integers (the image above is wide enough that you can see the spikes at z = -2, -1, 1, and 2). Instead of proceeding with the Collatz function as I have defined it, I’m going to introduce a modified Collatz function g(z) as follows:

Observe that this function, like f(z), always maps natural numbers to terms that appear later in their Collatz sequence (e.g., g(11) = 17, g(17) = 13). The benefit of this function is that it has the additional property that g(1) = 1. That is, 1 is a fixed point of g(z), whereas it is part of a period-3 cycle of f(z). The fractal induced by g(z) is:

The Collatz g(z) fractal

Close-up of the g(z) fractal at z = 1

I originally moved to using g(z) instead of f(z) because the plot of the f(z) fractal from earlier indicated to me that there may be a ball of black (i.e., boundedness) of non-zero radius around each of the integers, but proving this for f(z) seemed to be quite difficult (as we would expect, since it would basically imply half of the Collatz conjecture). Somewhat strangely, even though there appear to be balls around the integers in the fractal induced by f(z), these balls vanish in the fractal induced by g(z). The image to the right is a close-up of the above fractal (the point of convergence is z = 1).

Nonetheless, the real line still seems to behave reasonably nicely under the action of g(z); it’s not difficult to prove that the fractal contains the real line segment [0,N] for some large number N that is similar in magnitude to the least M such that the conjecture is true for all n ≤ M (known to be at least 5×10¹⁸ or so, as mentioned earlier). However, many (non-natural number) points in that interval do not converge to 1.

So what now? If the Collatz conjecture is true, then z = 1 is the unique natural number fixed point of g(z), yet there seem to be points arbitrarily close to z = 1 that don’t even converge under iteration of g(z). Why are there smaller spikes between the integers in both of these fractals, and where are the spikes centered? Does the restriction of the Collatz function to the numbers at the center of those spikes have any simple interpretation? Who knows, I’ll explore some more in the future. Until then, enjoy some pretty pictures.

g(z) fractal at z = 4

g(z) fractal at z = 8

g(z) fractal at z = 16

g(z) fractal at z = -8

There’s an old math paradox that says that all natural numbers are interesting, since otherwise there would have to be a smallest uninteresting number, and that in itself is pretty interesting. Of course, this is meant to show that ideas in the English language do not always translate to well-defined mathematical concepts, but let’s ignore our better mathematical sense and tinker with the idea of how interesting different numbers are a little bit. In particular, I claim that 11630 is utterly bland and uninteresting.

Why 11630?

Before saying why 11630 is uninteresting, I should probably say what I consider “interesting” to even mean. Interesting, to me, means that it has some (semi-unique) mathematical property that sets it apart from other numbers. 11 is interesting because it is prime, 16 is interesting because it is a perfect power (16 = 4²), and so on. Clearly, there is some ambiguity in this definition, since one could consider composite numbers interesting, just as I considered prime numbers interesting. Additionally, do we consider 2719 interesting simply because it is prime? I’d say no, since there are hundreds of prime numbers that come before it — perhaps only the first few numbers that satisfy a given property should be considered interesting as a result of it?

Using these ideas, it seems like determining how interesting a number is would be a task perfectly suited to the Online Encyclopedia of Integer sequences (OEIS). If you’re unfamiliar with it (i.e., if you’re not a math person and have no place reading my blog), the OEIS is a database containing thousands of (you guessed it) integer sequences that have been submitted by users over the last decade or so (such as the sequence of prime numbers 2, 3, 5, 7, 11,… and the sequence of perfect powers 1, 4, 8, 9, 16,…). Presumably, if an integer is interesting then it will appear in at least one or two of the 159437 sequences contained in the database, right? Indeed, it seems that we can get a rough idea of how interesting a number is by looking at how many sequences that number appears in in the database compared to other numbers of similar size.

11630 is the first number that is not listed in a single sequence in the OEIS. It is not prime, nor is it highly composite (11630 = 2×5×1163). It doesn’t have any particularly notable residue properties, and it doesn’t come up in counting problems. It’s boring in every way, and it seems as though not a single mathematician has found a use for it in the last dozen or so years (let me know if you’ve discovered otherwise).

What Numbers are Interesting?

First off, I’m not going to deal with particularly small numbers (say in the range of 1 – 50) since, as the strong law of small numbers quips, these numbers will appear all over the place just because they’re small. You could probably argue that most (if not all) of them are interesting, so I’ll instead take a look at a couple larger numbers that are particularly interesting.

The number 421 appears in some 1894 sequences, while most numbers that size appear in about 940 sequences. This seems to indicate that 421 is a particularly interesting number, but why? What’s so special about 421? Well, it’s prime (in fact, it’s a twin prime, Pythagorean prime, cuban prime, lucky number of Euler prime, additive prime, and irregular prime), it’s congruent to 1 mod 2,3,4, 5, 6,7, 10, 12, it’s the sum of five primes, and 421² = 420² + 29². Similarly, 512 appears in 2116 sequences even though most numbers around 512 appear in about 800 sequences. This is perhaps less surprising than 421, since 512 = 2⁹ = 8³ = 16² + 16² is a number that somehow seems “nice” due to it being a perfect power. Additionally, 512 is a Leyland number, Harshad number, and it comes up in all sorts of counting problems.

What of the Paradox?

Recalling the paradox from earlier, we are now forced to ask ourselves whether or not 11630 is now interesting as a result of it being the first number not included in the OEIS. Rather than come up with an answer, I’m going to take the easy way out and let the OEIS decide. The sequence of uninteresting numbers is 11630, 12067, 12407, 12887, 13258, 13794, 13882, 13982, 14018, 14163,… Let’s submit that to the OEIS and see if they consider it to be interesting or not.

Update [June 13, 2009]: I got word back via e-mail today that this sequence didn’t make the cut. So there you have it — these numbers truly are uninteresting.

Update [November 12, 2009]: It looks like 11630 is now listed in the OEIS. Additionally, 12067 was recently added, meaning that 12407 is now the first uninteresting number.

Update [October 7, 2011]: Interested readers might want to check out this paper, which explores similar questions and mentions the numbers computed here.

Update [November 14, 2011]: The British television show QI recently aired a segment on exactly this topic. See the video here.

Update [November 22, 2013]: A whole bunch of these numbers have been added to the OEIS lately, making 14228 the new first uninteresting number.

Downloads:

• OEIS counts (1 – 50000) [Excel spreadsheet — 6.81MB]
• OEIS counts (1 – 50000) [.txt — 444kB]

I’ve decided that, starting today, I will once a month post a mathematical result that I find interesting and/or useful, but I feel sadly gets less attention than it deserves (Update: well, that lasted about four months). I will try to present all relevant preliminaries along with the result to provide context, so hopefully the results and proofs will be accessible to someone at the upper undergraduate level.

Since I’m a quantum kinda guy, it seems natural that the first such lemma deals with quantum information science. In particular, it helps quantify the behaviour of unital quantum channels acting on density operators. Before delving into the result, let’s begin with…

Quantum Preliminaries

Given the complex matrix space M_n, a quantum channel E is defined to be a completely positive, trace-preserving map. That is, it is a map of the form

where {A_j} ∈ M_n is a family of matrices. Trace-preservation of E is equivalent to the requirement that

In many physical situations we are interested in unital quantum channels; that is, channels that satisfy E(I) = I. Such channels in general exhibit much nicer behaviour than arbitrary quantum channels, and this month’s lemma will show one particular instance of this fact.

The Hardy-Littlewood-Polya Theorem

The proof of the lemma relies on a classical result known as the Hardy-Littlewood-Polya Theorem. The result explains how doubly stochastic matrices act on vectors. Since it seems to be surprisingly difficult to find on Wikipedia and other popular (read: non-research) websites, I will state it here.

Theorem [Hardy-Littlewood-Polya]. Let x,y ∈ Rⁿ be real vectors. Then x majorizes y if and only if y = Dx for some doubly stochastic matrix D ∈ M_n.

It might be worth mentioning that the “if” direction of the proof is borderline trivial; the real meat and potatoes of the theorem is the “only if” direction.

The Lemma Itself

The lemma makes precise something that feels quite natural when thought of physically: a unital channel (that is, a completely positive, trace-preserving map E for which E(I) = I) can only increase the impurity (or “mixedness”) of quantum states. It has several simple consequences that are of great use when dealing with unital channels, and furthermore its proof makes excellent use of classical machinery. It was originally due to Uhlmann [1,2], but has recently appeared in [3]. The proof provided in the PDF attached at the end of this post is from the latter source.

Lemma [Unital Channel Eigenvalue Majorization]. Suppose ρ = E(σ) for a unital channel E. Then the ordered spectrum r of ρ is majorised by the ordered spectrum s of σ.

One particularly useful corollary of this lemma is presented here, and its proof is omitted (and dare I say left as an exercise for the reader?)

Corollary. If E is a unital quantum channel and ρ is a positive operator, then rank(E(ρ)) ≥ rank(ρ).

Related Links

• Lemma of the Month #1: Unital Channel Eigenvalue Majorization [pdf]

References

1. A. Uhlmann, Commun. Math. Phys. 54, 21 (1977).
2. I. Bengtsson, and K. Zyczkowski, Geometry of quantum states, Cambridge University Press (2006).
3. D. W. Kribs, R. W. Spekkens, Phys. Rev. A 74, 042329 (2006). arXiv:quant-ph/0608045v2

Over the last few days, the internet news has been filled with stories of an Iraq-born 16-year-old boy who “cracked the mystery of the Bernoulli numbers”. This has of course been promptly been picked up by dozens of blogs and regurgitated all over the place. However, if you’re mathematically-inclined like me, this might lead you to wonder “there was a mystery of the Bernoulli numbers?” Well, wonder no more, because no there was not. The formula for B_n, the n^th Bernoulli number, that was “discovered” by the boy is as follows:

This formula was originally derived by a mathematician named Julius Worpitzky in 1883. Some sources have tried half-heartedly to correct the article by appending a sentence to the bottom of the story:

Later, a clarification was given‚ by the mathematical community that the probable solution to this century old problem was available in mathematical circuits though not openly available to all.

– thaindian.com

The problem is that this isn’t even true; the “probable solution” (what does that mean, exactly?) was not under some mysterious mathematical lock-and-key. It was well-known and even included on the Wikipedia page describing the Bernoulli numbers (at the time of this writing, it is about halfway down the page under the section titled “Connection with the Worpitzky number”). Uppsala University has even issued an official statement saying that the news articles are false.

So while the boy’s derivation of the formula is indeed impressive considering his age (if he did indeed derive it himself rather than following the steps outlined on the wiki page), the story about this “puzzle” being solved is almost entirely false.

Update [June 6, 2009]: The Mathematical Association of America has now posted an article about this same topic.