9
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ In your random samples, are the eigenvalues always positive? $\endgroup$
    – Will Sawin
    Commented May 10, 2013 at 5:43

1 Answer 1

Reset to default
8
$\begingroup$

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.)

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ Will, you forgot to add the diagonals! $\endgroup$
    – Suvrit
    Commented May 10, 2013 at 6:35
  • 2
    $\begingroup$ (but replacing the 1s by 1/4 and 3/4, in the M and S parts, respectively does the trick) $\endgroup$
    – Suvrit
    Commented May 10, 2013 at 6:40
  • $\begingroup$ 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$. $\endgroup$
    – Will Sawin
    Commented May 10, 2013 at 6:43
  • $\begingroup$ @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! $\endgroup$
    – Santiago
    Commented May 10, 2013 at 21:05
  • $\begingroup$ @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). $\endgroup$
    – Suvrit
    Commented May 10, 2013 at 22:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .