The Lumber Room

"Consign them to dust and damp by way of preserving them"

Posts Tagged ‘maths

All functions are continuous

leave a comment »

…or else they are uncomputable :)

here and at What does topology have to do with computability?

Written by S

Mon, 2008-01-07 at 03:07:21

Posted in Uncategorized

Tagged with

Understanding monads

leave a comment »

“Sigfpe” (Dan Piponi) has written some helpful posts on his blog. Together with other stuff, I understand it… somewhat. Or maybe I understand it perfectly, I don’t know.

Although they are in descending order of “simpleness”, this is the order in which I saw them:
First, read the definition of monads from here (only), and stop. It probably won’t make sense.

This excellent post:
You Could Have Invented Monads! (And Maybe You Already Have.)
explains monads with enough examples — they are a kind of “lift”. The definition makes sense now.

That, and Philip Wadler’s original paper should suffice.

There are too many monad tutorials, and quoting from Tell us why your language sucks:

So, things I hate about Haskell:

Let’s start with the obvious. Monad tutorials. No, not monads. Specifically the tutorials. They’re endless, overblown and dear god are they tedious. Further, I’ve never seen any convincing evidence that they actually help. Read the class definition, write some code, get over the scary name.

Finally, whether you’re trying to teach someone monads or anything else, you must read Brent Yorgey’s Abstraction, intuition, and the “monad tutorial fallacy”:

But now Joe goes and writes a monad tutorial called “Monads are Burritos,” under the well-intentioned but mistaken assumption that if other people read his magical insight, learning about monads will be a snap for them. “Monads are easy,” Joe writes. “Think of them as burritos.” […] Of course, exactly the opposite is true, and all Joe has done is make it harder for people to learn about monads…

[Random interesting stuff:
This post looks at them as “expressions” v/s “commands”:
The IO Monad for People who Simply Don’t Care

There’s also some interesting stuff in the first half of this post.]

Written by S

Fri, 2008-01-04 at 20:40:27

Posted in Uncategorized

Tagged with , ,

Who Can Name the Bigger Number?

leave a comment »

Written by S

Tue, 2007-12-18 at 19:11:23

Posted in Uncategorized

Tagged with , ,

A nice theorem, and trying to invert a function

with one comment

[Inspired by N, my first use of LaTeX on this blog… and it’s not as much of a pain as I had thought it would be.]

Here’s a nice theorem (“Levy–Desplanques theorem”):
Given a n \times n matrix A, if for every row i, \left|a_{ii}\right| > \sum_{j \ne i}\left|a_{ij}\right|, then \det A \ne 0.

It’s quite easy to prove: Suppose \det A = 0, then there exists a vector x = (x_1,x_2,\dots,x_n) such that Ax = 0. Pick a coordinate x_r that has maximum magnitude (i.e., let r \in \arg \max_{i}{|x_i|}). Then look at row r. We have a_{rr}x_r + \sum_{j \ne i}{a_{rj}x_j} = 0, so |a_{rr}||x_r| = \left|\sum_{j \ne i}{a_{rj}x_j}\right| \le \sum_{j \ne i}{|a_{rj}||x_j|} \le \left(\sum_{j \ne i}{|a_{rj}|}\right)|x_r|, which is a contradiction.

This theorem has apparently been discovered and rediscovered many times. According to Wikipedia:

This result has been independently rediscovered dozens of times. A few notable ones are Lévy (1881), Desplanques (1886), Minkowski (1900), Hadamard (1903), Schur, Markov (1908), Rohrbach (1931), Gershgorin (1931), Artin (1932), Ostrowski (1937), and Furtwängler (1936).

Olga Taussky has written a short paper on “A Recurring Theorem on Determinants“, in which she mentions 25 references. (This was in 1949… it’s probably been rediscovered a lot of times since.)

Applying this theorem to |A-\lambda I| gives us the Gershgorin circle theorem: For a matrix A, let R_i be \sum_{j \ne i}\left|a_{ij}\right|, then for any eigenvalue \lambda, there exists an i such that |\lambda-a_{ii}| < |R_i|.
That is, consider discs D(a_{ii},R_i) centred at a_{ii} and of radius R_i. Then every eigenvalue lies inside one of these “Gershgorin discs”.
(This theorem can also be proved directly in a similar way, in which case the original theorem follows directly.)

Where I encountered this: In an economics paper, where we have a function that is a demand system. That is, there are n (substitutable) varieties of a product, and the demand for each product is a function of all the n prices. So for a given vector of prices, there is a vector of demands, thus we have a function g: \mathbb{R}^n \to \mathbb{R}^n, such that g(p_1,p_2,\dots,p_n) is a vector whose ith component is the demand for the ith product when the prices are (p_1,p_2,\dots,p_n). In this case, it is “natural” to assume (rather not too implausible :-)) that in the Jacobian of this function (the matrix of partial derivatives whose (i,j)th entry is the partial derivative of the demand for the ith product with respect to the jth price), we have:

  1. J_{ii} < 0 : If you increase your price, fewer people will want it
  2. J_{ij} \ge 0 \text{ for } j \ne i: If someone else increases their price, you can expect to get at least a few converts to your product.
  3. \left|J_{ii}\right| > \sum_{j \ne i}\left|J_{ij}\right|, i.e. \sum_{j}{J_{ij}} < 0: If everyone increases their price, the total demand in the market does not go up. It also implies that the demand for your product depends more on your price than on everyone’s price put together!

Let’s look at the function f = -g instead, so that the three properties above say that J_f = -J_g has diagonal entries positive, off-diagonal entries nonpositive, and the positive dominant diagonal property in each row. It can be proved that any matrix with positive dominant diagonal property is a P-matrix, i.e., it has all principal minors positive. And there is a “global univalence theorem” due to Gale-Nikaido-Inada that a differentiable function defined on a rectangular region, whose Jacobian is a P-matrix at every point, is globally one-to-one. (So it is invertible if we ignore points outside its range.) (I see this theorem stated in the paper “The Jacobian matrix, global univalence and completely mixed games” by T. Parthasarathy and G. Ravindran — I vaguely remember TP mentioning something of this sort in class some time….)
So our demand system is globally invertible, and we can express the prices in terms of the demands. That was a lot of effort to get this!

Written by S

Wed, 2007-10-03 at 10:35:17

Posted in Uncategorized

Tagged with , ,