  We give lower bounds on the largest singular value of arbitrary matrices,
some of which are asymptotically tight for almost all matrices. To study when
these bounds are exact, we introduce several combinatorial concepts. In
particular, we introduce regular, pseudo-regular, and almost regular matrices.
Nonnegative, symmetric, almost regular matrices were studied earlier by
Hoffman, Wolfe, and Hoffmeister.
