Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I am trying to prove that a mapping has a unique fixed-point by showing that its Jacobian is a P-matrix. In this particular case the Jacobian can be decomposed as the sum of two matrices and I would like to show the following result:

Let $M \in \mathbb R^{n \times n}$ be a M-matrix and $S \in \mathbb R^{n \times n}$ be a S-matrix (positive definite matrix) with non-negative entries. Is it the case that $M + S$ is a P-matrix?

The result holds trivially for $n=1,2$, but I was wondering if it holds for arbitrary $n$. I generated millions of random matrices with $n \le 10$ and the result seems to be true. I would truly appreciate any comments, references or help!

Some definitions

A matrix $M \in \mathbb R^{n \times n}$ is a M-matrix if (i) all off-diagonal entries are less than or equal to zero, and (ii) all principal minors of $M$ are positive. A matrix $P \in \mathbb R^{n \times n}$ is a P-matrix if all principal minors of $P$ are positive. Horn Johnson's Topics in Matrix Analysis (1991, pp. 112-125) discusses various equivalent definitions for these matrices.

Interestingly, all M-matrices are P-matrices and all S-matrices are P-matrices, but P-matrices are not close under addition. For example, $A = \begin{bmatrix} \frac 1 2 & -1 \\ 0 & \frac 1 2 \end{bmatrix}$ and $B = \begin{bmatrix} \frac 1 2 & 0 \\ -1 & \frac 1 2 \end{bmatrix}$ are both P-matrices but the sum $A+B$ is not. This example is taken from Parthasarathy's On Global Univalence Theorems (1983, p. 15).

Some Background

In many equilibrium models one proves the uniqueness of an equilibrium by showing that an equation $F(x) = 0$ has at most one solution. In many cases the Jacobian of $F$ can be decomposed as the sum of a positive diagonal matrix and M- or P-matrix, which is again a P-matrix. Then one invokes the univalence result of Gale and Nikaido's The Jacobian matrix and global univalence of mappings (1965) to show that the mapping admits at most one solution. The previous result would allow one to prove uniqueness in more general mappings and may be of interest to the community.

share|improve this question
    
In your random samples, are the eigenvalues always positive? –  Will Sawin May 10 '13 at 5:43

1 Answer 1

up vote 6 down vote accepted

This is not true in general.

$\left(\begin{array}{ccc} 4 & 0 & -16 \\ 2 & 4 & 0 \\ 0 & 2 & 4 \end{array}\right)= \left(\begin{array}{ccc} 1 & -2 & -16 \\ 0 & 1 & -2 \\ 0 & 0 & 1 \end{array}\right) +\left(\begin{array}{ccc} 3 & 2 & 0 \\ 2 & 3 & 2 \\ 0 & 2 & 3 \end{array}\right)$

A matrix with determinant $0$ is $M+S$. (Thanks to S. Sra for the correction. I multiplied by $4$ so everything's an integer now.)

share|improve this answer
2  
Will, you forgot to add the diagonals! –  Suvrit May 10 '13 at 6:35
2  
(but replacing the 1s by 1/4 and 3/4, in the M and S parts, respectively does the trick) –  Suvrit May 10 '13 at 6:40
    
Oops, that was silly, but your fix certainly works! Or I could admit that the $1$s and the diagonals are really $2$, and turn the $-4$ into a $-32$. –  Will Sawin May 10 '13 at 6:43
    
@Will: Thanks for the answer! It is sad to hear that the conjecture is not true. The result is known to be true if $M$ is a diagonal matrix with positive entries. Does the fact that $M$ is highly asymmetric has something to do with it? Could the result we proven if $M$ is a symmetric matrix? I couldn't find any asymmetric counter-example. Thanks again for all your hard work! –  Santiago May 10 '13 at 21:05
    
@Santiago: A symmetric, nonsingular $M$-matrix is a Stieltjes matrix and a symmetric matrix over the integers is Stieltjes if and only if it is positive definite. So at least the integral counterexamples above will not extend to the case when we have symmetry (as the sum of two strictly (symmetric) positive definite matrices cannot lose rank). –  Suvrit May 10 '13 at 22:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.