The Lumber Room

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

Archive for October 3rd, 2007

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 , ,

Postfix operators we learnt in kindergarten

with 8 comments

I don’t know about your school, but in our school we kids went through several years without ever realising what the multiplication table we were saying actually said. As a result, we were all familiar with at least one postfix operator — the postfix multiplication operator “zar” (pronounced “zawr”). As we recited our “tables”:

Two one zar two,
Two two zar four,
Two three zar six,

and so on (always ending with a singsong, triumphant, “two ten zar twenty”.)

“Zar” was routinely treated as an operator (“what is six seven zar?”), and it was quite an epiphany to me (in class seven I think) when I suddenly realised what had been going on; I suspect many of my classmates still haven’t caught on. (BTW, what is the technical name for this, where “ones are” → “one zar”? Closest I know is Allomorph.)

Also, our “into” (for multiplication) is used for division in the US (at least), so our “five into twenty is hundred”, but their “five into twenty goes four [times]”. And the “by” — “thirty by forty is 0.75”, but a thirty-by-forty site is 30 × 40.

More to ponder — which parts of India say “by” in fractions and which say “over”? (Is “3/4” “three by four” or “three over four”? Of course it’s “three-fourths”…) Which ones say “aitch” and which ones say “hetch”? We always learnt it with the aspirated “h”, and that’s the way it seems to be in Chennai too.

“Pronunciation /heɪtʃ/ (and hence spelling haitch) is […] standard in Hiberno-English. In Northern Ireland it is a shibboleth as Protestant schools teach aitch and Catholics haitch.”

Meanwhile, I’ve always wanted to slaughter the (incorrect) Hindi-inspired “give exam” speakers, but it looks like the battle is being lost (in CMI, it had spread to even proper Bangalore/Chennai types). Maybe I should also find and resurrect my old zedzee and emptyset-not-phi rants while I’m in the mood…

Written by S

Wed, 2007-10-03 at 09:24:15

Posted in Uncategorized

Tagged with , , , , ,