Using discrepancy to control singular values for nonnegative matrices (Q865410): Difference between revisions

This paper combines ideas and results by \textit{B. Bollobás} and \textit{V. Nikiforov} [Discrete Math. 285, No. 1, 1--3, 17--32 (2004; Zbl 1050.05081)] and \textit{Y. Bilu} and \textit{N. Linial} [Proc. 45th Annual IEEE Symposium on Foundations of Computer Science, 17--19 October 2004, Rome, Italy, 404--412 (2004)] to obtain a result for nonnegative rectangular matrices on discrepancy that can be bounded by the second largest singular value and conversely. By defining the discrepancy of alternating \(t\)-walks this becomes applicable to weighted digraphs without sources of sinks.