Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Preserving positivity for matrices with sparsity constraints


Authors: Dominique Guillot, Apoorva Khare and Bala Rajaratnam
Journal: Trans. Amer. Math. Soc. 368 (2016), 8929-8953
MSC (2010): Primary 15B48; Secondary 26E05, 05C50, 26A48
DOI: https://doi.org/10.1090/tran6669
Published electronically: January 6, 2016
MathSciNet review: 3551594
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Functions preserving Loewner positivity when applied entrywise to positive semidefinite matrices have been widely studied in the literature. Following the work of Schoenberg [Duke Math. J. 9], Rudin [Duke Math. J. 26], and others, it is well-known that functions preserving positivity for matrices of all dimensions are absolutely monotonic (i.e., analytic with nonnegative Taylor coefficients). In this paper, we study functions preserving positivity when applied entrywise to sparse matrices, with zeros encoded by a graph $ G$ or a family of graphs $ G_n$. Our results generalize Schoenberg and Rudin's results to a modern setting, where functions are often applied entrywise to sparse matrices in order to improve their properties (e.g. better conditioning, graphical models). The only such result known in the literature is for the complete graph $ K_2$. We provide the first such characterization result for a large family of non-complete graphs. Specifically, we characterize functions preserving Loewner positivity on matrices with zeros according to a tree. These functions are multiplicatively midpoint-convex and superadditive. Leveraging the underlying sparsity in matrices thus admits the use of functions which are not necessarily analytic nor absolutely monotonic. We further show that analytic functions preserving positivity on matrices with zeros according to trees can contain arbitrarily long sequences of negative coefficients, thus obviating the need for absolute monotonicity in a very strong sense. This result leads to the question of exactly when absolute monotonicity is necessary when preserving positivity for an arbitrary class of graphs. We then provide a stronger condition in terms of the numerical range of all symmetric matrices, such that functions satisfying this condition on matrices with zeros according to any family of graphs with unbounded degrees are necessarily absolutely monotonic.


References [Enhancements On Off] (What's this?)

  • [1] Jim Agler, J. William Helton, Scott McCullough, and Leiba Rodman, Positive semidefinite matrices with a given sparsity pattern, Proceedings of the Victoria Conference on Combinatorial Matrix Analysis (Victoria, BC, 1987), 1988, pp. 101-149. MR 960140 (90h:15030), https://doi.org/10.1016/0024-3795(88)90240-6
  • [2] Gautam Bharali and Olga Holtz, Functions preserving nonnegativity of matrices, SIAM J. Matrix Anal. Appl. 30 (2008), no. 1, 84-101. MR 2399570 (2009b:15051), https://doi.org/10.1137/050645075
  • [3] Rajendra Bhatia and Ludwig Elsner, Positivity preserving Hadamard matrix functions, Positivity 11 (2007), no. 4, 583-588. MR 2346444 (2008f:15072), https://doi.org/10.1007/s11117-007-2104-8
  • [4] Richard A. Brualdi, The mutually beneficial relationship of graphs and matrices, CBMS Regional Conference Series in Mathematics, vol. 115, American Mathematical Society, Providence, RI, 2011. MR 2808017 (2012i:05159)
  • [5] Jens Peter Reus Christensen and Paul Ressel, Functions operating on positive definite matrices and a theorem of Schoenberg, Trans. Amer. Math. Soc. 243 (1978), 89-95. MR 502895 (81f:15031), https://doi.org/10.2307/1997755
  • [6] Carl H. FitzGerald and Roger A. Horn, On fractional Hadamard powers of positive definite matrices, J. Math. Anal. Appl. 61 (1977), no. 3, 633-642. MR 0506356 (58 #22121)
  • [7] Carl H. FitzGerald, Charles A. Micchelli, and Allan Pinkus, Functions that preserve families of positive semidefinite matrices, Linear Algebra Appl. 221 (1995), 83-102. MR 1331791 (96c:15032), https://doi.org/10.1016/0024-3795(93)00232-O
  • [8] Dominique Guillot, Apoorva Khare, and Bala Rajaratnam, The critical exponent conjecture for powers of doubly nonnegative matrices, Linear Algebra Appl. 439 (2013), no. 8, 2422-2427. MR 3091314, https://doi.org/10.1016/j.laa.2013.06.031
  • [9] Dominique Guillot, Apoorva Khare, and Bala Rajaratnam,
    On fractional Hadamard powers of positive block matrices,
    Technical Report, Department of Mathematics, Stanford University, submitted (arXiv: 1404.6839), 2014.
  • [10] Dominique Guillot, Apoorva Khare, and Bala Rajaratnam, Preserving positivity for rank-constrained matrices, Trans. Amer. Math. Soc., to appear (arXiv: 1406.0042).
  • [11] Dominique Guillot, Apoorva Khare, and Bala Rajaratnam, Complete characterization of Hadamard powers preserving Loewner positivity, monotonicity, and convexity, J. Math. Anal. Appl. 425 (2015), no. 1, 489-507. MR 3299675, https://doi.org/10.1016/j.jmaa.2014.12.048
  • [12] Dominique Guillot and Bala Rajaratnam, Retaining positive definiteness in thresholded matrices, Linear Algebra Appl. 436 (2012), no. 11, 4143-4160. MR 2915274, https://doi.org/10.1016/j.laa.2012.01.013
  • [13] Dominique Guillot and Bala Rajaratnam, Functions preserving positive definiteness for sparse matrices, Trans. Amer. Math. Soc. 367 (2015), no. 1, 627-649. MR 3271272, https://doi.org/10.1090/S0002-9947-2014-06183-7
  • [14] Frank Hansen, Functions of matrices with nonnegative entries, Linear Algebra Appl. 166 (1992), 29-43. MR 1152486 (92k:15040), https://doi.org/10.1016/0024-3795(92)90268-F
  • [15] Carl S. Herz, Fonctions opérant sur les fonctions définies-positives, Ann. Inst. Fourier (Grenoble) 13 (1963), 161-180 (French). MR 0152832 (27 #2806)
  • [16] Fumio Hiai, Monotonicity for entrywise functions of matrices, Linear Algebra Appl. 431 (2009), no. 8, 1125-1146. MR 2547900 (2010h:15011), https://doi.org/10.1016/j.laa.2009.04.001
  • [17] Leslie Hogben, Spectral graph theory and the inverse eigenvalue problem of a graph, Electron. J. Linear Algebra 14 (2005), 12-31. MR 2202430 (2006k:05133)
  • [18] Roger A. Horn, The theory of infinitely divisible matrices and kernels, Trans. Amer. Math. Soc. 136 (1969), 269-286. MR 0264736 (41 #9327)
  • [19] Steffen L. Lauritzen, Graphical models, Oxford Statistical Science Series, vol. 17, The Clarendon Press, Oxford University Press, New York, 1996. MR 1419991 (98g:62001)
  • [20] Charles A. Micchelli and R. A. Willoughby, On functions which preserve the class of Stieltjes matrices, Linear Algebra Appl. 23 (1979), 141-156. MR 520618 (80b:15022), https://doi.org/10.1016/0024-3795(79)90098-3
  • [21] Constantin P. Niculescu and Lars-Erik Persson, Convex functions and their applications: A contemporary approach, CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC, 23, Springer, New York, 2006. MR 2178902 (2006m:26001)
  • [22] Allan Pinkus, Strictly positive definite functions on a real inner product space, Adv. Comput. Math. 20 (2004), no. 4, 263-271. MR 2032278 (2004j:42003), https://doi.org/10.1023/A:1027362918283
  • [23] Walter Rudin, Positive definite sequences and absolutely monotonic functions, Duke Math. J 26 (1959), 617-622. MR 0109204 (22 #91)
  • [24] I. J. Schoenberg, Positive definite functions on spheres, Duke Math. J. 9 (1942), 96-108. MR 0005922 (3,232c)
  • [25] Harkrishan Vasudeva, Positive definite matrices and absolutely monotonic functions, Indian J. Pure Appl. Math. 10 (1979), no. 7, 854-858. MR 537245 (81a:26007)
  • [26] Joe Whittaker, Graphical models in applied multivariate statistics, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Ltd., Chichester, 1990. MR 1112133 (93f:62002)
  • [27] David Vernon Widder, The Laplace Transform, Princeton Mathematical Series, v. 6, Princeton University Press, Princeton, N. J., 1941. MR 0005923 (3,232d)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 15B48, 26E05, 05C50, 26A48

Retrieve articles in all journals with MSC (2010): 15B48, 26E05, 05C50, 26A48


Additional Information

Dominique Guillot
Affiliation: Departments of Mathematics and Statistics, Stanford University, Stanford, California 94305
Address at time of publication: Department of Mathematical Sciences, University of Delaware, Newark, Delaware 19716
Email: dguillot@udel.edu

Apoorva Khare
Affiliation: Departments of Mathematics and Statistics, Stanford University, Stanford, California 94305
Email: khare@stanford.edu

Bala Rajaratnam
Affiliation: Departments of Mathematics and Statistics, Stanford University, Stanford, California 94305
Email: brajaratnam01@gmail.com

DOI: https://doi.org/10.1090/tran6669
Keywords: Matrices with structure of zeros, entrywise positive maps, absolutely monotonic functions, multiplicatively convex functions, positive semidefiniteness, Loewner ordering, fractional Schur powers
Received by editor(s): November 27, 2014
Published electronically: January 6, 2016
Additional Notes: This work was partially supported by US Air Force Office of Scientific Research grant award FA9550-13-1-0043, US National Science Foundation under grant DMS-0906392, DMS-CMG 1025465, AGS-1003823, DMS-1106642, DMS-CAREER-1352656, Defense Advanced Research Projects Agency DARPA YFA N66001-111-4131, the UPS Foundation, SMC-DBNKY, and an NSERC postdoctoral fellowship
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society