A nice theorem, and trying to invert a function

[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 $i$ th component is the demand for the $i$ th 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 $i$ th product with respect to the $j$ th price), we have:

$J_{ii} < 0$ : If you increase your price, fewer people will want it
$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.
$\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 economics, latex, maths

One Response

Subscribe to comments with RSS.

aha :P

N

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

Reply

S	M	T	W	T	F	S
	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28	29	30	31

The Lumber Room