My big plans to write a proof of the day already tanked! On day #1. In my defense, I’ve been writing proofs all weekend and didn’t feel like writing another one for the blog. Primarily they have been proofs about linear algebra, algorithmic game theory, and microeconomics.  I think I have a good one on supermodularity coming later this afternoon. This is an econ concept that, for all I can tell, is not used outside of economics.

In other news, there is a really great post on the Lovasz Local Lemma over on Lance Fortnow’s blog.  I have to admit, I have had three different classes and own two books that talk about the local lemma. However, I still have no idea what it means. The blog post is a bit more insightful and I feel like I’m getting closer to full understanding; but still not there yet. The LLL is like this pinnacle of academic achievement for me. If I can understand the lemma, then there is nothing stopping me from conquering all of discrete mathematics.

In another epic fail moment, this blog has started getting hits for the search term “paul milgrom sucks”. For those who don’t know,  Paul Milgrom is a famous economist and researcher of auction theory. He’s one of the fathers of the modern day FCC spectrum auction and wrote much of the auction literature that exists. He was given an award here at Northwestern, which I blogged about at the time.  In a later blog post, I mentioned that “Windows Vista Sucks”. Google’s algorithm connected the terms and now I get hits for that search query.  So, I would like to clear the air here; I don’t think Paul Milgrom sucks, in fact, I own several of his books and think he is an excellent writer. His work on the FCC auctions is phenomenal (I think the companies he consults for probably agree) and he is a good speaker. In fact, I would argue that he is probably a good candidate for a Economics Nobel some day.

This is my very first proof of the day, so the proof is probably wrong (although, I hope not).

Source: Linear Algebra Done Right by Sheldon Axler – p.59 Question #9

Prerequisite: Some advanced linear algebra

Claim: Prove that if is a linear map from to such that , then is surjective.

Idea: In the problem, they give us a very specific null vector of T.  Since we know this, we can derive some information about . Then, we can construct a vector, put it through the function and show that it is surjective by construction by looking at the dimension of of the input and output.

Proof: We know that and that , and want to show that T is surjective.  By definition, for T to be surjective, its range must be equal to the codomain of the linear map. Therefore, if , then is surjective. To show this, let . Then, we know that .  Since and the dimension of the resulting mapping is 2, we have shown that and hence is surjective.

I’m going to try an experiment with this blog. In an effort to develop better proof writing skills, I am going to try to write a proof per day on here. Sometimes, it will be something assigned to me as homework and sometimes, it will be something random that I want to prove. Either way, at this moment, I feel like I am a horrible proof writer. Spending a dedicated amount of time each day (probably each weekday) will help be improve. I should disclose that sometimes my proofs will be really bad (or not even right), so caveat emptor.

At first, I considered starting a separate blog just for the proofs but then I realized that I’d have to reinstall all of my themes and modules that I already configured for this wordpress install. It took me long enough to get this one right that I don’t want to go through the process again. Maybe I’m lazy or maybe WordPress is not very scalable for this kind of thing.  So, I created a wordpress category “POTD” (Proof Of The Day).  I then went through and hacked all of my custom db calls to the wordpress library to separate posts with category=1 (uncategorized) versus category=92 (potd). Hopefully, it won’t be confusing for my readers.

You can view my first Proof of the Day!