ChapterZero

Richard Stallman gave a talk on campus yesterday… and I’m now finding out today. Check out his story on Jinnetic Engineering.

Let be an analytic function in some domain containing the origin, with power series , then recall that the quantity is well-defined (the series converges) if you can find some matrix norm in which converges.

That’s the ’standard’ definition of a matrix function, as I’ve known it. But we learned a pretty neat definition in our linear algebra class recently, which has more of the feel of a definition than a generalization. When both definitions apply to a given matrix, the result *seems* to be the same. The algebraic definition depends on the spectral decomposition theorem– a pretty cool result in itself–, which says that if is a Hermitian matrix with unique eigenvalues then there is a partition of unity where the is the orthogonal projection unto the -th eigenspace of ; this partition satisfies . Then we define the application of an analytic function to as .

I have to check that the results of the two definitions are the same, but I suspect (strongly enough not to bother checking ) that they are, because of the mutual requirement for analyticity (why else would an analytic constraint be given in an algebraic definition?); beyond that, the fact(s) and strongly suggest that if you put the spectral decomposition into the standard definition and expanded you’d get the result of the linear algebraic definition.

Practically, this means if you’re computing matrix exponentials say, and you have the good fortune of dealing with a normal matrix, you can avoid getting its Jordan form by using the linear algebraic definition. Considering that the calculation of the is much more easily systematized and quicker than the calculation of the Jordan blocks, I think this is a pretty useful fact.

We found a really clever way yesterday of answering the first problem on our quiz: show that a given differential equation has a periodic solution, regardless of the value of its parameter. In the end, it boils down to some clever algebra tricks and the fact that the system is time-reversible, so if you find a center in its linearized approximation, then you’ve found a center for the system itself. The problem is, I believe the last assertion is true, because several books state it (without proof), but we didn’t learn it in class, so I’d like to understand/prove it if I’m going to use it. Since the system is reversible, it seems like all you have to show is that if you start close enough to the center on the positive side of the x-axis, you’ll reach the negative side of the x-axis in finite time.

And I can’t figure out why this should be the case. I’ve had two ideas: one to show that when you get arbitrarily close to the center point, the trajectories of the nonlinearized and linearized systems are so close that if the linear one crosses the axis, so must the nonlinear one. But the best estimate I can get of the distance between the trajectories is via Gronwall’s inequality, which gives an exponentially increasing term in time; not good enough. The other idea is to kind of use the trajectories of the linear system as trapping boundaries on the nonlinear trajectories, but this is very sketchy.

It’s incredible that none of the books I’ve read prove this. In fact, most of the ones I’ve seen didn’t even mention reversibility, and these are generally hard-hitting books. My de facto supplementary reference, by Chicone, has this assertion as an exercise near the very front of the book. I reread the sections before the exercise, and still have no idea what if anything they contribute towards solving it. I suppose if I can’t prove this, I’ll just have to reference it as a ‘known fact’.

Apparently Japanese scientists have worked out a way to store data in the DNA of a bacteria. They’re really on the ball when it comes to genetic engineering: they’ve also modified lettuce to produce miraculin, which may be the next great diet craze. Look for it in a store near you!

But seriously, imagine the possibilities that the informational bacteria open up. Assuming that the encoding and decoding processes can be streamlined sufficiently– it’s dubious that this will ever be feasible as a consumer technology, but one can hope– you could store information virtually invisibly, and diffuse it effortlessly. About a fourth of a megabyte of information can be geneered into a single bacteria.

This raises a lot of interesting math questions: if I wanted to ensure that the entirety of the Encylcopedia Brittanica was freely available within a square foot everywhere on the surface of the Earth (assuming the Earth is spherical, and that the bacteria could and would flourish on every surface, and each breed of bacteria carrying different information could coexist harmoniously with the other breeds, and that you addressed the problem of genetic drift corrupting the encoded information), how many geneered species of bacteria would I need, and given a population model for the bacteria, how would I perform optimum seeding? Or, if you’re into hard core stochastics, imagine coming up with models that could model the effects of genetic drift closely enough to facilitate the recovery of information corrupted by evolution/mutation.

Lots more questions I could think up, but the point is that this is so cool… and now I have to run home within 7 minutes to catch Heroes.

That is, if and is upper triangular, then is diagonal. Can you prove it?

You can do it by induction easily– the idea is the same as that used in proving that every normal matrix is diagonalizable (in complex space), using Schur’s theorem– but try for a way that uses less calculation. After all, one of the nice aspects of positivity, normality, self-adjointness, etc. is that often times arguments about matrices don’t need to appeal directly to their elements.

… is surprisingly elegant: we already know it is a contraction of the word faggot, as in the chunks of wood used to burn witches at the stake, etc. But apparently, the fire being referred to is the wrath of God:

… “FAGS” as the contraction of faggots, fueling the fires of God’s wrath …

Makes a twisted, amusing kind of sense. Is this website a joke? It seems serious, but with a domain name like godhatesfags.com, the unrelentingly vitrolic introductory material, and statements like

“GOD HATES FAGS” — though elliptical — is a profound theological statement, which the world needs to hear more than it needs oxygen, water and bread.

it comes across more as an Onion-like parody than anything else.

This is a milepost for me, so when I look back in a couple of months I can see how far I’ve progressed in my current goals.

I’ve started reading the first volume of Feller’s Intro to Probability and am pretty stoked about it– he’s a good writer. I plan on doing several *hard* problems from each chapter to stay dextrous. My primary goal is to make it through both of his volumes, then buy them (but not before finishing reading them, because then I’d probably just put them on the shelf and not read them, like I did to Bauer’s book). By next month, I hope to have at least half of volume 1 under my belt.

Next quarter, ACM is offering two probability related courses: Large Deviations and Stochastic Control. Take those.

Ok, so I had a thought on how to maybe add edges to the coloring graph mentioned in the previous post so that it would become connected. Namely, in addition to the previous neighbor relation ( if the colorings differ in exactly one vertex), we could say if the partitionings of the graph corresponding to the two colorings are the same, but they assign a different color to each partition. At least this would eliminate the previous counterexample: the graph of 4 colorings on a fully connected 4 vertex graph is connected in this new sense. Does this hold for general graphs and general -colorings?

Here’s an interesting, and at first glance research caliber, problem I came across in the process of doing one of my problem sets:

Let be a planar graph, and an integer. Then the set of ‘feasible -coloring’ of such that , i.e. the set of all possible assigment of distinct colors to the vertices of the graph so that neighbors have different colors, is non-empty (this is the content of the famous Four Color Theorem).

Here’s the question. We can consider this set to be the set of vertices for a new graph in which two colorings are neighbors iff they differ on exactly one vertex. When is this graph connected? I.e. when can I change an arbitrary feasible coloring into another one by sequentially changing the color of single vertices in such a way that at each step the resulting coloring remains feasible?

This problem came up because one of the assigned problems is to design a Metropolis algorithm that uniformly samples from the set of possible -colorings on a graph. In order for the associated Markov chain to be irreducible, we need the set of feasible colorings to be connected in the above sense. But this is not always the case. Take the set of 4-colorings of a fully connected 4 vertex graph– there are exactly 4 colorings, and not enough ‘wiggle’ room to move from one to the other.

On a related note, I recommend MatGraph for anyone using Matlab who wants to mess around with and visualize graphs. I spent so much time looking for an example of a large graph and a feasible 4-coloring on the Internet (for some reason people have posted ‘test’ graphs that are good for testing coloring algorithms, but without any colorings), before I realized that Matgraph can color graphs for you, and display them too.