In recent joint work (2021), we introduced a novel multivariate polynomial attached to every metric space - in particular, to every finite simple connected graph $G$ - and showed it has several attractive properties. First, it is multi-affine and rea
l-stable (leading to a hitherto unstudied delta-matroid for each graph $G$). Second, the polynomial specializes to (a transform of) the characteristic polynomial $chi_{D_G}$ of the distance matrix $D_G$; as well as recovers the entire graph, where $chi_{D_G}$ cannot do so. Third, the polynomial encodes the determinants of a family of graphs formed from $G$, called the blowups of $G$. In this short note, we exhibit the applicability of these tools and techniques to other graph-matrices and their characteristic polynomials. As a particular case, we will see that the adjacency characteristic polynomial $chi_{A_G}$ is in fact the shadow of a richer multivariate blowup-polynomial, which is similarly multi-affine and real-stable. Moreover, this polynomial encodes not only the aforementioned three properties, but also yields additional information for specific families of graphs.
To every finite metric space $X$, including all connected unweighted graphs with the minimum edge-distance metric, we attach an invariant that we call its blowup-polynomial $p_X({ n_x : x in X })$. This is obtained from the blowup $X[{bf n}]$ - which
contains $n_x$ copies of each point $x$ - by computing the determinant of the distance matrix of $X[{bf n}]$ and removing an exponential factor. We prove that as a function of the sizes $n_x$, $p_X({bf n})$ is a polynomial, is multi-affine, and is real-stable. This naturally associates a delta-matroid to each metric space $X$ (and another delta-matroid to every tree), which also seem to be hitherto unexplored. We moreover show that the homogenization at $-1$ of $p_X({bf n})$ is Lorentzian (or strongly/completely log-concave), if and only if the normalization of $p_X(-{bf n})$ is strongly Rayleigh, if and only if a modification of the distance matrix of $X$ is positive semidefinite. We next specialize to the case of $X = G$ a connected unweighted graph - so $p_G$ is partially symmetric in ${ n_v : v in V(G) }$ - and show two further results: (a) We show that the univariate specialization $u_G(x) := p_G(x,dots,x)$ is a transform of the characteristic polynomial of the distance matrix $D_G$; this connects the blowup-polynomial of $G$ to the well-studied distance spectrum of $G$. (b) We show that the polynomial $p_G$ is indeed a graph invariant, in that $p_G$ and its symmetries recover the graph $G$ and its isometries, respectively.
Hirschman and Widder introduced a class of Polya frequency functions given by linear combinations of one-sided exponential functions. The members of this class are probability densities, and the class is closed under convolution but not under pointwi
se multiplication. We show that, generically, a polynomial function of such a density is a Polya frequency function only if the polynomial is a homothety, and also identify a subclass for which each positive-integer power is a Polya frequency function. We further demonstrate connections between the Maclaurin coefficients, the moments of these densities, and the recovery of the density from finitely many moments, via Schur polynomials.
A matrix-compression algorithm is derived from a novel isogenic block decomposition for square matrices. The resulting compression and inflation operations possess strong functorial and spectral-permanence properties. The basic observation that Hadam
ard entrywise functional calculus preserves isogenic blocks has already proved to be of paramount importance for thresholding large correlation matrices. An array of applications to current investigations in computational matrix analysis arises, touching concepts such as symmetric statistical models, hierarchical matrices and coherent matrix organization induced by partition trees.
We prove that certain possibly non-smooth Hermitian metrics are Griffiths-semipositively curved if and only if they satisfy an asymptotic extension property. This result answers a question of Deng--Ning--Wang--Zhou in the affirmative.
We prove the converse to a result of Karlin [Trans. AMS 1964], and also strengthen his result and two results of Schoenberg [Ann. of Math. 1955]. One of the latter results concerns zeros of Laplace transforms of multiply positive functions. The other
results study which powers $alpha$ of two specific kernels are totally non-negative of order $pgeq 2$ (denoted TN$_p$); both authors showed this happens for $alphageq p-2$, and Schoenberg proved that it does not for $alpha<p-2$. We show more strongly that for every $p times p$ submatrix of either kernel, up to a shift, its $alpha$th power is totally positive of order $p$ (TP$_p$) for every $alpha > p-2$, and is not TN$_p$ for every non-integer $alphain(0,p-2)$. In particular, these results reveal critical exponent phenomena in total positivity. We also prove the converse to a 1968 result of Karlin, revealing yet another critical exponent phenomenon - for Laplace transforms of all Polya Frequency (PF) functions. We further classify the powers preserving all TN$_p$ Hankel kernels on intervals, and isolate individual kernels encoding these powers. We then transfer results on preservers by Polya-Szego (1925), Loewner/Horn (1969), and Khare-Tao (in press), from positive matrices to Hankel TN$_p$ kernels. Another application constructs individual matrices encoding the Loewner convex powers. This complements Jains results (2020) for Loewner positivity, which we strengthen to total positivity. Remarkably, these (strengthened) results of Jain, those of Schoenberg and Karlin, the latters converse, and the above Hankel kernels all arise from a single symmetric rank-two kernel and its powers: $max(1+xy,0)$. We also provide a novel characterization of PF functions and sequences of order $pgeq 3$, following Schoenbergs 1951 result for $p=2$. We correct a small gap in his paper, in the classification of discontinuous PF functions.
The composition operators preserving total non-negativity and total positivity for various classes of kernels are classified, following three themes. Letting a function act by post composition on kernels with arbitrary domains, it is shown that such
a composition operator maps the set of totally non-negative kernels to itself if and only if the function is constant or linear, or just linear if it preserves total positivity. Symmetric kernels are also discussed, with a similar outcome. These classification results are a byproduct of two matrix-completion results and the second theme: an extension of A.M. Whitneys density theorem from finite domains to subsets of the real line. This extension is derived via a discrete convolution with modulated Gaussian kernels. The third theme consists of analyzing, with tools from harmonic analysis, the preservers of several families of totally non-negative and totally positive kernels with additional structure: continuous Hankel kernels on an interval, Polya frequency functions, and Polya frequency sequences. The rigid structure of post-composition transforms of totally positive kernels acting on infinite sets is obtained by combining several specialized situations settled in our present and earlier works.
By a result of Schur [J. Reine Angew. Math. 1911], the entrywise product $M circ N$ of two positive semidefinite matrices $M,N$ is again positive. Vybiral [Adv. Math. 2020] improved on this by showing the uniform lower bound $M circ overline{M} geq E
_n / n$ for all $n times n$ real or complex correlation matrices $M$, where $E_n$ is the all-ones matrix. This was applied to settle a conjecture of Novak [J. Complexity 1999] and to positive definite functions on groups. Vybiral (in his original preprint) asked if one can obtain similar uniform lower bounds for higher entrywise powers of $M$, or for $M circ N$ when $N eq M, overline{M}$. A natural third question is to obtain a tighter lower bound that need not vanish as $n to infty$, i.e. over infinite-dimensional Hilbert spaces. In this note, we affirmatively answer all three questions by extending and refining Vybirals result to lower-bound $M circ N$, for arbitrary complex positive semidefinite matrices $M, N$. Specifically: we provide tight lower bounds, improving on Vybirals bounds. Second, our proof is conceptual (and self-contained), providing a natural interpretation of these improved bounds via tracial Cauchy-Schwarz inequalities. Third, we extend our tight lower bounds to Hilbert-Schmidt operators. As an application, we settle Open Problem 1 of Hinrichs-Krieg-Novak-Vybiral [J. Complexity, in press], which yields improvements in the error bounds in certain tensor product (integration) problems.
Graham-Pollak showed that for $D = D_T$ the distance matrix of a tree $T$, det$(D)$ depends only on its number of edges. Several other variants of $D$, including directed/multiplicative/$q
This survey contains a selection of topics unified by the concept of positive semi-definiteness (of matrices or kernels), reflecting natural constraints imposed on discrete data (graphs or networks) or continuous objects (probability or mass distribu
tions). We put emphasis on entrywise operations which preserve positivity, in a variety of guises. Techniques from harmonic analysis, function theory, operator theory, statistics, combinatorics, and group representations are invoked. Some partially forgotten classical roots in metric geometry and distance transforms are presented with comments and full bibliographical references. Modern applications to high-dimensional covariance estimation and regularization are included.
