Bounds on the spectral sparsification of symmetric and off-diagonal nonnegative real matrices

DOI10.1142/S1793830921501093MaRDI QIDQ5063290zbMATH OpenOpenAlexFDO

Authors Sergio Mercado, Marcos Villagra

Publication date 17 March 2022

Published in Discrete Mathematics, Algorithms and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2009.11133

zbMATH Keywords

nonnegative matricesspectral graph theoryspectral sparsificationsymmetric matrices

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Inequalities involving eigenvalues and eigenvectors (15A42) Hermitian, skew-Hermitian, and related matrices (15B57) General topics of discrete mathematics in relation to computer science (68R01)

Abstract: We say that a square real matrix $M$ is emph{off-diagonal nonnegative} if and only if all entries outside its diagonal are nonnegative real numbers. In this note we show that for any off-diagonal nonnegative symmetric matrix $M$, there exists a nonnegative symmetric matrix $widehatM$ which is sparse and close in spectrum to $M$.

Recommendations

• scientific article; zbMATH DE number 1054822
• REALIZABILITY BY SYMMETRIC NONNEGATIVE MATRICES<A HREF="#tit">*</A>
• The spread of the spectrum of a nonnegative matrix with a zero diagonal element
• Twice-Ramanujan sparsifiers
• scientific article; zbMATH DE number 7692348

Cites work

• A matrix hyperbolic cosine algorithm and applications
• A useful variant of the Davis-Kahan theorem for statisticians
• Constructing linear-sized spectral sparsification in almost-linear time
• scientific article; zbMATH DE number 47363 (Why is no real title available?)
• scientific article; zbMATH DE number 967931 (Why is no real title available?)
• Principal component analysis.
• Quadratic programming with one negative eigenvalue is NP-hard
• Spectral sparsification of graphs
• The Rotation of Eigenvectors by a Perturbation. III

Cited in

(1)

• Remarks on completey positive matrices

This page was built for publication: Bounds on the spectral sparsification of symmetric and off-diagonal nonnegative real matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5063290)