کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4598934 1631112 2015 24 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Discrete norms of a matrix and the converse to the expander mixing lemma
ترجمه فارسی عنوان
هنجارهای گسسته یک ماتریس و متضاد به لمس اختلاط گسترده
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات اعداد جبر و تئوری
چکیده انگلیسی

We define the discrete norm   of a complex m×nm×n matrix A by‖A‖Δ:=max0≠ξ∈{0,1}n⁡‖Aξ‖‖ξ‖, and show thatclog⁡h(A)+1‖A‖≤‖A‖Δ≤‖A‖, where c>0c>0 is an explicitly indicated absolute constant, h(A)=‖A‖1‖A‖∞/‖A‖, and ‖A‖1‖A‖1, ‖A‖∞‖A‖∞, and ‖A‖=‖A‖2‖A‖=‖A‖2 are the induced operator norms of A. Similarly, for the discrete Rayleigh norm‖A‖P:=max0≠ξ∈{0,1}m0≠η∈{0,1}n⁡|ξtAη|‖ξ‖‖η‖ we prove the estimateclog⁡h(A)+1‖A‖≤‖A‖P≤‖A‖. 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 Bollobás–Nikiforov and Bilu–Linial.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Linear Algebra and its Applications - Volume 483, 15 October 2015, Pages 158–181
نویسندگان
,