Apoorva Khare and I have just uploaded to the arXiv our paper “On the sign patterns of entrywise positivity preservers in fixed dimension“. This paper explores the relationship between positive definiteness of Hermitian matrices, and entrywise operations on these matrices. The starting point for this theory is the Schur product theorem, which asserts that if and are two Hermitian matrices that are positive semi-definite, then their Hadamard product

is also positive semi-definite. (One should caution that the Hadamard product is *not* the same as the usual matrix product.) To prove this theorem, first observe that the claim is easy when and are rank one positive semi-definite matrices, since in this case is also a rank one positive semi-definite matrix. The general case then follows by noting from the spectral theorem that a general positive semi-definite matrix can be expressed as a non-negative linear combination of rank one positive semi-definite matrices, and using the bilinearity of the Hadamard product and the fact that the set of positive semi-definite matrices form a convex cone. A modification of this argument also lets one replace “positive semi-definite” by “positive definite” in the statement of the Schur product theorem.

One corollary of the Schur product theorem is that any polynomial with non-negative coefficients is *entrywise positivity preserving* on the space of positive semi-definite Hermitian matrices, in the sense that for any matrix in , the entrywise application

of to is also positive semi-definite. (As before, one should caution that is *not* the application of to by the usual functional calculus.) Indeed, one can expand

where is the Hadamard product of copies of , and the claim now follows from the Schur product theorem and the fact that is a convex cone.

A slight variant of this argument, already observed by Pólya and Szegö in 1925, shows that if is any subset of and

is a power series with non-negative coefficients that is absolutely and uniformly convergent on , then will be entrywise positivity preserving on the set of positive definite matrices with entries in . (In the case that is of the form , such functions are precisely the absolutely monotonic functions on .)

In the work of Schoenberg and of Rudin, we have a converse: if is a function that is entrywise positivity preserving on for all , then it must be of the form (1) with . Variants of this result, with replaced by other domains, appear in the work of Horn, Vasudeva, and Guillot-Khare-Rajaratnam.

This gives a satisfactory classification of functions that are entrywise positivity preservers in all dimensions simultaneously. However, the question remains as to what happens if one fixes the dimension , in which case one may have a larger class of entrywise positivity preservers. For instance, in the trivial case , a function would be entrywise positivity preserving on if and only if is non-negative on . For higher , there is a necessary condition of Horn (refined slightly by Guillot-Khare-Rajaratnam) which asserts (at least in the case of smooth ) that all derivatives of at zero up to order must be non-negative in order for to be entrywise positivity preserving on for some . In particular, if is of the form (1), then must be non-negative. In fact, a stronger assertion can be made, namely that the first non-zero coefficients in (1) (if they exist) must be positive, or equivalently any negative term in (1) must be preceded (though not necessarily immediately) by at least positive terms. If is of the form (1) is entrywise positivity preserving on the larger set , one can furthermore show that any negative term in (1) must also be *followed* (though not necessarily immediately) by at least positive terms.

The main result of this paper is that these sign conditions are the *only* constraints for entrywise positivity preserving power series. More precisely:

Theorem 1For each , let be a sign.

- Suppose that any negative sign is preceded by at least positive signs (thus there exists with ). Then, for any , there exists a convergent power series (1) on , with each having the sign of , which is entrywise positivity preserving on .
- Suppose in addition that any negative sign is followed by at least positive signs (thus there exists with ). Then there exists a convergent power series (1) on , with each having the sign of , which is entrywise positivity preserving on .

One can ask the same question with or replaced by other domains such as , or the complex disk , but it turns out that there are far fewer entrywise positivity preserving functions in those cases basically because of the non-trivial zeroes of Schur polynomials in these ranges; see the paper for further discussion. We also have some quantitative bounds on how negative some of the coefficients can be compared to the positive coefficients, but they are a bit technical to state here.

The heart of the proofs of these results is an analysis of the determinants of polynomials applied entrywise to rank one matrices ; the positivity of these determinants can be used (together with a continuity argument) to establish the positive definiteness of for various ranges of and . Using the Cauchy-Binet formula, one can rewrite such determinants as linear combinations of squares of magnitudes of generalised Vandermonde determinants

where and the signs of the coefficients in the linear combination are determined by the signs of the coefficients of . The task is then to find upper and lower bounds for the magnitudes of such generalised Vandermonde determinants. These determinants oscillate in sign, which makes the problem look difficult; however, an algebraic miracle intervenes, namely the factorisation

of the generalised Vandermonde determinant into the ordinary Vandermonde determinant

and a Schur polynomial applied to , where the weight of the Schur polynomial is determined by in a simple fashion. The problem then boils down to obtaining upper and lower bounds for these Schur polynomials. Because we are restricting attention to matrices taking values in or , the entries of can be taken to be non-negative. One can then take advantage of the *total positivity* of the Schur polynomials to compare these polynomials with a monomial, at which point one can obtain good criteria for to be positive definite when is a rank one positive definite matrix .

If we allow the exponents to be real numbers rather than integers (thus replacing polynomials or power series by Pusieux series or Hahn series), then we lose the above algebraic miracle, but we can replace it with a geometric miracle, namely the *Harish-Chandra-Itzykson-Zuber identity*, which I discussed in this previous blog post. This factors the above generalised Vandermonde determinant as the product of the ordinary Vandermonde determinant and an integral of a positive quantity over the orthogonal group, which one can again compare with a monomial after some fairly elementary estimates.

It remains to understand what happens for more general positive semi-definite matrices . Here we use a trick of FitzGerald and Horn to amplify the rank one case to the general case, by expressing a general positive semi-definite matrix as a linear combination of a rank one matrix and another positive semi-definite matrix that vanishes on the last row and column (and is thus effectively a positive definite matrix). Using the fundamental theorem of calculus to continuously deform the rank one matrix to in the direction , one can then obtain positivity results for from positivity results for combined with an induction hypothesis on .

## 9 comments

Comments feed for this article

18 August, 2017 at 4:53 am

LarsonTerry, what do you think of Norbert Blum’s proof that P is not equal to NP? It has recently gained a rather heavy amount of attention and even may be correct. Several people have remarked that it is a far more “sound” attempt than Deolalikar’s. What do you think about it? See https://arxiv.org/abs/1708.03486

18 August, 2017 at 5:51 am

Terence TaoThere are some discussions, including expert commentary, on this paper elsewhere on the internet, for instance over at Luca’s blog https://lucatrevisan.wordpress.com/2017/08/15/on-norbert-blums-claimed-proof-that-p-does-not-equal-np/ , or Richard and Ken’s blog https://rjlipton.wordpress.com/2017/08/17/on-the-edge-of-eclipses-and-pnp/#comment-83680 . I myself am happy to wait a few more days for the experts to reach consensus, though I gather from these discussions that there already are some significant concerns with the paper.

18 August, 2017 at 8:38 am

AnonymousIn the paper, is the explicit value given by (3.5) for the threshold in (1.4) the best possible one?

18 August, 2017 at 9:06 am

Terence TaoThis is probably not the case in general, because of the presence of Schur polynomials in both the numerator and denominator; but in the special case then the denominator is trivial and the bounds are indeed sharp, as was observed in the previous paper of Belton et al..

18 August, 2017 at 3:55 pm

MackHi Terence,

maybe this is the wrong blog post to comment this on, but I rushed over to your blog after watching “Terence Tao: Structure and Randomness in the Prime Numbers, UCLA” on youtube. One of the best colloquiums I’ve “attended”.

After watching it I started thinking about Chen’s theorem.

Maybe this is a dumb question, but why is Chen’s theorem something that has to be proven? Shouldn’t it be obvious, that there are infinitely many pairs p, p + 2 where p is a prime and p+2 is the product of at most two primes, if there are infinetly many prime numbers? Isn’t Chen’s theorem something that should automatically be included in the infinite amount of primes?

18 August, 2017 at 5:42 pm

thegregmartinMack: Suppose I claim that every prime p larger than 10^1000 has the property that p+2 has at least 14 prime factors. That would contradict Chen’s theorem, right? So if Chen’s theorem is to be true, then my claim would have to be false; and if Chen’s theorem is obvious, then my claim must be obviously false. Do you find my claim obviously false? (not in terms of intuition, but in terms of what can be mathematically justified)

24 August, 2017 at 10:39 pm

Rachid Ait-HaddouDear Terence,

I very much enjoyed reading the paper. I have the following comments: Using the theory of Chebyshev blossoming in Muntz spaces, one can show that the functions

are strictly increasing in each variable on . Using this fact, one ends up with a sharp threshold constant in Proposition 3.4, i.e.;

The constant carries itself well in the inductive arguments with the extension principle. This means that is also a sharp constant in the inequality (1.4). More importantly, blossoming

in Muntz spaces does not distinguish between integer and real powers. Thus, is also sharp in Theorem 5.12. With this approach, one can avoid the use of the Harish-Chandra-Itzykson-Zuber identity.

Here are two references on Chebyshebv blossoming in Muntz spaces.

https://link.springer.com/article/10.1007/s10208-016-9334-8

http://www.sciencedirect.com/science/article/pii/S0377042713000289

I hope this help and many thanks for such a great blog.

26 August, 2017 at 10:22 am

Apoorva KhareThank you for pointing out the blossoming approach, Rachid. In fact we have been working on an algebraic approach this past week, to derive the exact constants for tuples of all real powers. Apart from obtaining the sharp bound, it also recovered what you mentioned: the coordinatewise monotonicity of the ratio whenever dominates coordinatewise, and both are tuples of real powers. (By the way, by this I assume you meant the ratio of the generalized Vandermondes.) A third consequence of our new results is an algebraic proof of the Cuttler-Greene-Skandera conjecture, which was shown by Sra (and you Remark a different proof with Mazure), both of these proofs using the Harish-Chandra-Itzykson-Zuber formula. There are also other additions and we will update the preprint shortly. Thanks again, and we’re glad to hear further thoughts from you. Best regards, Apoorva.

5 September, 2017 at 10:20 pm

Continuous analogues of the Schur and skew Schur polynomials | What's new[…] noted that it essentially appears in this paper of Shatashvili; Apoorva Khare and I also used it in this recent paper.) Again we induct on ; the case is trivial, so suppose and the claim has already been proven for […]