ChapterZero

One of my assignments for this week is to show the stability of the Lax-Friedrichs scheme when applied to the nonlinear 1-d advection equation: up to a time T, where we can assume smoothness of the solution up to T, and that , so CFL holds (here is the time increment over the space increment).

I’ve been attempting to follow the analysis in Strang’s paper; he assumes that the first variation of the difference scheme is stable in his proof, but I must show this is true for this particular scheme. While attempting to show this, I ran into an interesting linear algebra problem– one that I doubt I’ll have solved by Thursday, so I have to find another approach– that leads me to make the following conjecture:

Let be tridiagonal hollow matrices such that and all the entries of lie in . Then there is a constant depending only on , such that for any , .

I haven’t a clue how to prove this– the obvious approach with Gerschgorin’s theorem only bounds the norms of each matrix by 2–, but running a couple of lines of Matlab code:

n = 200;
mp = eye(200);
kstop = 2000;

for k=1:kstop
        b = rand(n-1,1);
        m = diag(b, 1) + diag(b,-1);
        mp = mp * m;
        norms(k) = norm(mp);
end

plot(norms);

and varying n, kstop gives pretty convincing results. I also found that if you let the entries get even slightly above 1, say up to 1.1, the norms blowup.

Any ideas on how to prove this? My next idea is to look at the minimax theorem.

Update This conjecture can’t be true– just take to have a spectral radius > 1, then the norms of the products will diverge. So, maybe it’s just true with high probability. Ugh.

Imagine you have points in , then construct the ‘Euclidean distance matrix’ . has some interesting properties: all its entries are positive, it is hollow (the diagonal entries are all zero), its entries satisfy , and most interesting, is nonsingular. The latter is particularly interesting– why it is true is an interesting question in its own right– because it makes EDMs a useful tool for interpolation.

As my officemate pointed out to me recently from looking at my facebook account, my friendship graph contains few triangles. I like that as a euphemism for my antisocial tendencies. Hmm… why doesn’t facebook have an application that lets you look at these types of graphs? Maybe they do and I just haven’t come across it. Now that I think about it, that would be a nice excuse for learning the Facebook API– I’m sure there are people out there who’d be willing to pay for that kind of (anonymized) data.

I came across paperbackswap.com, another book swapping site, while reading a blog. It sounds good: you post books that are occupying valuable shelf space, and anyone who desires them can ask for them, you send them the books and get a credit per book. These credits can in turn be redeemed to get books from others’ bookshelves.

Good in principle, but after my first bout of sending off books, I’ve found that the system is in practice annoying. First, anyone can request your books– something I thought I could handle, but after packing off 6 books to an equal number of total strangers, I’ve found that I’d really like to know who are getting my books. Did these people put up books of an equal caliber, and in equally good condition, or are they getting their credits by offering up rubbish? The person who requested my copy of Troll: A Love Story had a special condition attached to the request, that the book should be in top shape with no marks or creases. Not an unreasonable request, but instead of referring to the specific book, it said ‘all childrens books should be …’. That tells me two things: first, this person has no clue what the book is about– Troll is definitely not a children’s book: I think most parents wouldn’t want to corrupt their children with its subject matter– and second, said person is attempting to collect children’s books for reselling.

Second, as soon as you post a book, it is available for asking. Which means if you post 17 books at once, like I did, they get requested immediately (assuming here that you didn’t post utter trash), and you have to send them off in a batch. Not counting the cost of printing out the mailing labels, and packing tape, and a media envelope if you want to be nice, each book costs at least $2.13 in postage. One of the purposes of using a book swap is, I presume, to save money. Each book you send earns you a credit, and each credit is worth a book, so essentially you get a new paperback by trading an old one, plus paying $2.13– this is a good deal in the abstract, but when you have to shell out a heap of money at once, it doesn’t look as attractive. Especially if, as happened to me, none of the books you’re interested in reading are available.

Maybe a better system would allow for person-to-person swapping, instead of the current system of almost anonymity (the only point at which you get to know who the requestor is, is when you print out the mailing label). That way, I could be sure the person receiving my book is posting books of equal value, and not just taking advantage of a broken system. Also, it would be convenient if you could add a bunch of books at once, but mark them as unavailable until you need credit, and they you could activate them.

I haven’t been writing much here lately. Mostly because I’ve been busy juggling four courses, TAing, and finding an advisor. I’ve decided to drop at least one of the math courses– combinatorics– there just aren’t enough hours in a week for me to handle the material in there: the first lecture covered the Erdos-Stone theorem… enough said. I’m also considering merely auditing topology, the other math course.

That decision partially hinges on the meeting I have tomorrow morning with Joel Tropp, the latest professor in our department. This is his first term here, so I want an idea of what he has planned for his future research directions, and whether he’s taking grad students. Going from his statement of research goals in his CV, we’re almost a perfect match– I too am interested problems which have a geometrical, harmonic analysis, or probabilistic aspect, or all three at once. Perusing his publications has only reinforced this impression: his spikes and sines paper, the one on the conditioning of random subdictionaries, and the one on the random paving property for uniformed bounded matrices seem like the type of combination linear algebra/probability that I’d enjoy doing, his thesis is intriguing enough that I want to read it in its entirety, and his paper on constructing packings in Grassmanian manifolds has an elegant geometric/analytic flavor to it.

… I talked to him. Unfortunately, he’s not taking students now, but his description of his future research directions fits so well with what I’m interested in, that I’m considering waiting for him. He said he’ll probably be taking students by the end of the year, so I need to decide whether I can wait that long to start actively researching, and what I’ll do in the meantime. Maybe I’ll just read — he didn’t want to recommend specifics, on the basis that the background material (e.g. probability in Banach spaces) is abstract enough that looking at it without a concrete application in mind is painful– but I could just bone up on my probability, functional analysis, and linear algebra.

I printed out the first assignment for my combinatorics course today, and after looking at it, decided that I should start studying immediately. Those problems look scary: I can only imagine how much more involved they get after the first week.

Here’s another problem I came across while reading the textbook (A Course in Combinatorics):

The complete bipartite graph has vertices and , and as edges all pairs . Show that is not planar.

At this point, all that has been mentioned about planarity of a graph is the basic definition: a graph is planar if it can be drawn on the plane in such a manner that no two edges cross, so I’m confused as to whether I’m supposed to actually be able to figure this out in a reasonable amount of time given what I already know. Or is this a motivational question?

Note that the unit ball of a norm satisfies the following properties: it is symmetric about the origin, convex, closed, bounded, and has a nonempty interior. Now show that any set with these properties is the unit ball of some norm (come up with an exact formula).

If is a positive definite symmetric matrix, then define the quadratic norm . Show that any norm on is equivalent to some quadratic norm, with constants 1 and :