3
$\begingroup$

Consider a 0-1 integer $n \times n$ matrix with coefficients chosen uniformly over $\{0,1\}$. The probability that it is singular is exponentially small, and so we expect that it has a well-defined condition number.

What is the expected condition number — or better yet, what probabilistic upper bounds are there on the condition number (for constant or better probability) — for such a matrix? Equivalently: given that we might naively expect $n/2$ to be close to being an eigenvalue (with the all-1s vector being the eigenvector), what sort of behaviour do we expect of the smallest singular value of a random 0-1 matrix?

$\endgroup$
1
  • $\begingroup$ No, because the entries of $A^t A$ are not i.i.d. normal... $\endgroup$
    – Igor Rivin
    Oct 15, 2013 at 0:18

1 Answer 1

2
$\begingroup$

For matrices with i.i.d. cenetered normal entries the condition number was studied by Alan Edelman in his thesis. For general subgaussian entries the state of the art is the work of Rudelson and Vershynin, as described in Vershynin's excellent lecture notes (I couldn't find a specific result on condition number, but he talks at length of minimal and maximal singular values).

$\endgroup$
5
  • $\begingroup$ This seems like an interesting tangent, but I don't detect the relation to the Bernoulli variables which I consider. I suppose asymptotically the matrix $A^{\mathsf T} A$ will look as though it has Gaussian coefficients, but as I think you're hinting (to a deleted comment?) in a comment to the original question, these are not independent. $\endgroup$ Oct 15, 2013 at 1:14
  • $\begingroup$ The Edelman thing is for Gaussian entries, the Rudelson/Vershynin work is for any subgaussian entries. Notice that a $0, 1$ variable is automatically subgaussian (it has VERY thin tails :)) The reason why Gaussian is relevant is that the more general results are generally inspired by gaussian results, and it is very likely that at least the asymptotics of the distribution are the same. The proofs are generally harder, so it is wise to read the gaussian proofs first. $\endgroup$
    – Igor Rivin
    Oct 15, 2013 at 2:01
  • $\begingroup$ And that's bad why? $\endgroup$
    – Igor Rivin
    Oct 15, 2013 at 3:16
  • $\begingroup$ Unfortunately, it is difficult to tell whether or not the results in Lecture 18 of Vershynin's notes apply. While these would be the sort of results that I want, a casual glance at the notes of Lecture 7 imply that he might be implicitly restricting to subgaussian distributions with mean 0. My Bernoulli variables have mean $\frac12$, of course, and while I can see how to translate the results for the largest singular value, I do not know how to perform this translation for the minimum singular value. Can you point me to results which explicitly accomodate distributions with non-zero mean? $\endgroup$ Oct 15, 2013 at 13:18
  • $\begingroup$ Because it's clear that this answer is still morally correct --- the 01 case is after all related to the symmetric case by a displacement by the all-1s matrix, which is very nearly orthogonal to all singular vectors but those of the largest singular value --- I'm accepting this answer. Perhaps these results also pertain exactly to the 01 case, though it's a bit frustrating that my certainty about this is undermined by a tacit but undeniable assumption of symmetry elsewhere in this work, which prevents me from being certain of the precise probabilistic lower bounds. $\endgroup$ Oct 17, 2013 at 6:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.