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

DOI10.1016/J.LAA.2015.05.031zbMATH Open1319.05087arXiv1410.5968OpenAlexW2962942982WikidataQ125028803 ScholiaQ125028803MaRDI QIDQ490884FDOQ490884

Authors: Vsevolod F. Lev 

Publication date: 21 August 2015

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

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.

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

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

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)

Cites Work

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

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)