The Lumber Room

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

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

One Response

Subscribe to comments with RSS.

  1. aha :P

    N

    Sun, 2007-10-07 at 13:41:14


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s