Too many variables and multicollinearity in OLS regression

After reading material related to my topic, I understood that multicollinearity among predictors would result in singular matrix $X'X$, and that leads to noninvertible matrix. Thus, the solution will not be unique.

Now, I am confused after reading that having too many variables (number of predictors greater than number of observations) causes the matrix $X'X$ to be singular too.

Is that true in both situations? If yes, could you explain that, please?

• "Not acceptable" is quite an exaggeration. Concerning your question, see these related threads. – whuber Jul 15 '16 at 17:52
• Adding a regularization will make it work. see lasso regression and ridge regression – Haitao Du Jul 15 '16 at 17:53
• Do you have any remaining questions or concerns after reading see.stanford.edu/materials/lsoeldsee263/08-min-norm.pdf ? – Mark L. Stone Jul 15 '16 at 17:58
• What exactly do you not understand about why those are, in essence, the same problems? It is a math fact that if $p > n$, then any column of $X$ can be expressed as a linear combination of the other columns. That's multicollinearity. – AdamO Jul 15 '16 at 18:21
• @ AdamO, so that means multicollinearity = too many variables – jeza Jul 15 '16 at 18:31

The thing is that, for a given sample size, $N$, it's impossible to find more than $N$ independent predictors (including the column of 1s for the intercept). That's because for design matrix $X$ of size $N \times p$ its rank cannot be greater than $\text{min}\{N, p\}$. No matter how you pick the predictors, if you use more than $N$ of them, the $X'X$ will be non-invertible for sure.
Based on what we know from linear algebra, it's impossible for $X'X$ to have rank greater than that of $X$. So, with $p > N$ then $X'X_{p\times p}$ will be of rank $N$ at most, but in order for it to be invertible the rank has to be $p$.
• "if you use more than $N$ of them, the $X'X$ will be non-invertible for sure." , could please clarify this a little bit further ? – jeza Jul 15 '16 at 18:47
• @jeza: "Too many variables" (e.g. more than $N$) guarantees multicollinearity, for the linear algebra reasons Nik Tuzov gives. But you can face multicollinearity in some situations with very few variables too. – Henry Jul 15 '16 at 20:48