# Probability for a random positive-semidefinite matrix to not be positive-definite?

If I take $A^TA$, where $A$ is a full-rank random matrix (let's say with Gaussian-distributed independent entries), can I expect it to be positive-definite? It will be positive semi-definite trivially, since $x^TA^TAx = \|Ax\|^2$, so I guess it will not be positive-definite only if the random matrix $A$ is rank-deficient, which should almost never happen.

But from numerical stability point of view, things might look different, because the matrix $A^TA$ could be close to a p.s.d. non-p.d. matrix with some probability.

So: is it generally safe to apply Cholesky decomposition to such a matrix, or is there a nontrivial chance of that leading to numerical instability? (I.e. without stronger conditions which would force the matrix away from the problematic boundary of p.d. matrices with non-p.d. matrices?)

• you're asking for the probability that $A^T A$ has an eigenvalue identical to zero; this probability is vanishingly small. Nov 19, 2013 at 7:24
• @CarloBeenakker Is it then typical to apply Cholesky decomposition without fearing numerical instability? I mean, given the above information alone? Nov 19, 2013 at 7:28
• There is a robust Cholesky's method. math.berkeley.edu/~cinnawu/hss.pdf Nov 19, 2013 at 10:18
• @CarloBeenakker: The probability is not just "vanishingly small", it is zero. Nov 19, 2013 at 17:34
• @NateEldredge what if you run an uncountably infinite number of trials in parallel, where the infinity is of high enough cardinality, isn't it possible that the expected value of trials with an exact zero eigenvalue will be some non-zero number, for example 3 or 4? Nov 19, 2013 at 22:02

Not sure if this is what you are really after, but anyway: The paper by Rudelson and Vershynin that Igor Rivin linked to contains lots of things which may be helpful for you. For example, for random $N\times n$ matrices ($N>n$) with iid Gaussian entries, there is Theorem 2.6 there which says that for the smallest singular value $s_\text{min}(A)$ it holds that $$\sqrt{N} - \sqrt{n}\leq \mathbb{E}s_\text{min}(A).$$ Also, there is a the quantitative bound $$\mathbb{P}(\sqrt{N}-\sqrt{n} - t \leq s_\text{min}(A)) \geq 1 - 2\exp(-t^2/2).$$ The case of square (but not necessarily symmetric) matrices is more difficult. There is also a probability for a lower bound on the smallest singular value: For square (subgaussian) matrices, Theorem 3.2 says that for some $C>0$, $0<c<1$ and any $\epsilon>0$ it holds that $$\mathbb{P}(s_\text{min}(A)\leq \epsilon n^{-1/2})\leq C\epsilon + c^n.$$
• Right, in a small case we might have N=24 and n=3, so if we assume that the quantitative bound above is a good approximation to the actual probability cdf, which is probably a very bad assumption, then the probability of $|s_{min}| < 10^{-3}$ can be estimated to be around (where t0 = $\sqrt{N} - \sqrt{n}$) 2*exp(-(t0-1e-3)**2/2) - 2*exp(-(t0+1e-3)**2/2), which is 5.73e-24. Even if we're out by a factor of a trillion, that's still pretty good. Nov 20, 2013 at 21:39