Discrete norms of a matrix and the converse to the expander mixing lemma

DOI10.1016/J.LAA.2015.05.031MaRDI QIDQ490884zbMATH OpenOpenAlexWikidataFDO

Authors Vsevolod F. Lev

Publication date 21 August 2015

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

graph eigenvaluesmatrix normssecond singular value

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Eigenvalues, singular values, and eigenvectors (15A18) Norms of matrices, numerical range, applications of functional analysis to matrix theory (15A60)

Abstract: We define the discrete norm of a complex $mimesn$ matrix $A$ by ${\displaystyle }$ |A|_Delta := max_{0

exiin{0,1}^n} frac{|Axi|}{|xi|}, ${\displaystyle }$ and show that ${\displaystyle }$ frac c{sqrt{log h(A)+1}},|A| le |A|_Delta le |A|, ${\displaystyle }$ where $c>0$ is an explicitly indicated absolute constant, $h(A)=sqrt|A{|}_1|A{|}_{i}nfty/|A|$, and $|A{|}_1,|A{|}_{i}nfty$, and $|A|=|A{|}_2$ are the induced operator norms of $A$. Similarly, for the emph{discrete Rayleigh norm} ${\displaystyle }$ |A|_P := max_{substack{0 exiin{0,1}^m \ 0

eetain{0,1}^n}} frac{|xi^tAeta|}{|xi||eta|} ${\displaystyle }$ we prove the estimate ${\displaystyle }$ frac c{log h(A)+1},|A| le |A|_P le |A|. ${\displaystyle }$ These estimates are shown to be essentially best possible. As a consequence, we obtain another proof of the (slightly sharpened and generalized version of the) converse to the expander mixing lemma by Bollobas-Nikiforov and Bilu-Linial.

Recommendations

• scientific article; zbMATH DE number 4101383
• Lifts, discrepancy and nearly optimal spectral gap
• scientific article; zbMATH DE number 994544
• Polynomial control on stability, inversion and powers of matrices on simple graphs
• On the norm of a random jointly exchangeable matrix

Cites work

• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• Extremal norms of graphs and matrices
• Hermitian matrices and graphs: Singular values and discrepancy
• Lifts, discrepancy and nearly optimal spectral gap
• On the Early History of the Singular Value Decomposition
• SYMMETRIC GAUGE FUNCTIONS AND UNITARILY INVARIANT NORMS
• Set systems with few disjoint pairs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.

Cited in

(2)

• A unified framework for the expander mixing lemma for irregular graphs and its applications
• Discretization and anti-discretization of rearrangement-invariant norms

This page was built for publication: Discrete norms of a matrix and the converse to the expander mixing lemma

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