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.

• I think you might be confusing two different ideas here. Multicollinearity refers to the correlation between the predictor variables. The condition number helps to estimate how difficult a matrix will be to numerically invert. So you can have a condition number for the matrix corresponding to your model greater than 20/30/whatever, but still small enough that it is numerically invertible. That doesn't mean however that it is a good model to start with. – Daryl Dec 18 '12 at 7:49
• @Daryl: would you please read the update. thanks – Ramin Dec 18 '12 at 9:16
• With a "small" condition number in the range of 20, precision is not a concern. Rather you are using the condition number to indicate high collinearity of your data. In this case, it means that your data is very linear, and if 2 columns are linearly dependent (or even 3 or more being linearly dependent without any pair being linearly dependent), then the matrix is said to be singular (you have that part backwards). – Mario Carneiro Dec 18 '12 at 9:29

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.

• thanks a lot. If I want to calculate $(\mathbf{X'X})^{-1}$, can I use $\mathbf{X'X}$ \ ones{size($\mathbf{X'X}$,1)} in matlab? – Ramin Dec 18 '12 at 13:12
• @Ron yes, you can so that. In MATLAB, the best way to solve the linear system is $\beta=X\backslash y$, which corresponds to $\beta=(X^TX)\backslash (X^Ty)$. The way you mentioned will indeed obtain the inverse. – Daryl Dec 18 '12 at 13:16
• I don't think your definition of linear dependency is correct. The columns of X are linearly dependent when there is a column of the matrix that can be expressed with linear combination of some of the other columns. – Tae-Sung Shin Feb 27 '14 at 16:29
• @Tae-SungShin My definition, in this context, is correct, especially in terms of multicollinearity. It does not cover the breadth of the standard definition, but is sufficient here. To see this, suppose that variables $x_3$ and $x_7$ are linearly dependent. This means that $x_7=kx_3$, for some $k$. This relationship I have called perfectly correlated, i.e. $r=\pm1$ depending on the sign of $k$. – Daryl Feb 27 '14 at 20:34

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.

• Would you please read the update. thanks – Ramin Dec 18 '12 at 9:17