To invert a Matrix, Condition number should be less than what? I see that there is a matlab tag in this site, so I ask my question here and not in stackoverflow although it is also related to programming in matlab.
I am going to invert a positive definite matrix in matlab and I should consider multicolinearity too. I read this in Wikipedia 's Multicollinearity:

If the Condition Number is above 30, the regression is said to have significant multicollinearity.

and something similar in Greene's Econometrics book (condition number must be less than 20).
But there are some links that says different, like PlanetMath's Matrix Condition Number:

Matrices with condition numbers much greater than one (such as around $10^5$ for a $5 \times 5$ Hilbert matrix) are said to be ill-conditioned.

or Wikipedia's Condition_number:

As a general rule of thumb, if the condition number $\kappa(A) = 10^k$, then you may lose up to $k$ digits of accuracy on top of what would be lost to the numerical method due to loss of precision from arithmetic methods

Which one is correct? (both? I mean something is different and I do not get it?)
Update
I used the answer and the comment to update my question:
Consider $\mathbf{X}$ to be the matrix of observations. Ordinary Least square estimates vector is $\mathbf{b=(X'X)}^{-1}\mathbf{X'y}$. If $\mathbf{X'X}$ is non-singular, we can not calculate this vector. The matrix $\mathbf{X'X}$ is non-singular if 2 columns of $\mathbf{X}$ are linearly dependant. It is sometimes called Perfect Multicollinearity.
I think this discussion is used to conclude Multicolinearity and $\mathbf{X'X}$ inversion and as a result the condition number of $\mathbf{X'X}$ are related.
It means sometimes we can invert $\mathbf{X'X}$ with acceptable precision, but it does not mean that two columns of $\mathbf{X}$ are linearly dependant.
Is the last paragraph correct?
Thanks.
 A: Mathematically, if the condition number is less than $\infty$, the matrix is invertible. Numerically, there are roundoff errors which occur. A high condition number means that the matrix is almost non-invertible. For a computer, this can be just as bad. But there is no hard bound; the higher the condition number, the greater the error in the calculation. For very high condition number, you may have a number round to 0 and then be inverted, causing an error. This is the same thing that would happen if you tried to invert a truly non-invertible matrix, which is why I say that a high condition number may as well be infinite in some cases.
In order to find out if the matrix is really too ill-conditioned, you should invert the matrix, and then check that $AA^{-1}=I$, to an acceptable precision. There is simply no hard cap on the condition number, just heuristics, which is why your references differ.
A: The problem of fitting a linear function which minimises the residuals is given by
$$\min\limits_\beta \|X\beta-y\|_2^2,$$
which corresponds to solving the linear system $X\beta=\mathcal{P}_X(y)$. Here $\mathcal{P}_X(y)$ is the projection of $y$ onto the space spanned by the columns of $X$. This corresponds to the linear system $X^TX\beta=X^Ty$.
The columns of $X$ are linearly dependent when there are two variables which are perfectly correlated; in that case, $X^TX$ is singular i.e. $\kappa(X^TX)=\infty$. Usually this will not occur and the correlation is not perfect, but there is still significant correlation between two variables. This corresponds to a large condition number, but not infinite. See also the comment by Mario Carneiro.
In terms of MATLAB computation, the smallest floating point value is approximately $\epsilon=2.26\times10^{-16}$. You comment that a condition number of $10^k$ loses $k$ digits of precision indicates that the condition number should be less than $1/{\epsilon}$. MATLAB's mldivide function will warn you if this is the case.
To solve this problem, you have proposed using the normal equations. A more numerically stable algorithm is to use a qr factorisation; this is the approach taken by mldivide.
