Why $p > n$ implies multicollinearity? Why $p > n$ implies multicollinearity ? $p$ is number of variables, and $n$ is number of samples. I know it has something to do with linear algebra concepts, but I am not sure how do linear algebra and correlations get connected here.
 A: Notation note: capital letters (eg. $X$) denote matrices, bold letters (eg. $\mathbf{x}$) denote vectors, and lowercase letters denote scalars.
The ordinary least squares optimization problem:
Let us have $n$ observations in $p$ variables. The ordinary least squares problem is to solve:
\begin{equation}
 \begin{array}{*2{>{\displaystyle}r}}
 \mbox{minimize (over $b_i$)} & \sum_{i=1}^n \left(y_i - \mathbf{x}_i'\mathbf{b} \right)^2
 \end{array}
\end{equation}
Intuitive approach:


*

*Remember we're solving for length $p$ vector $\mathbf{b}$ 

*Observe that $\mathbf{y} = X \mathbf{b}$ is an $n$ equation linear system in $p$ variables.


If $n < p$, the linear system of equations $\mathbf{y} = X \mathbf{b}$ has an infinite number of solutions! Hence you can find an infinite number of vectors $\mathbf{b}$ such that $\sum_i \left(y_i - \mathbf{x}_i'\mathbf{b} \right)^2= 0$. Hence the ordinary least squares problem has an infinite number of solutions. 
Linear algebra approach:
It can be shown that the solution to ordinary least squares problem above is given by the solution to the linear system in $p$ variables:
$$ \left( X'X \right) \mathbf{b} = X'\mathbf{y}$$
The problem is that the matrix $X'X$ has at most rank $n$ and if $n < p$, then it is inherently rank deficient. To show this, observe:
$$ X'X = \sum_{i=1}^n \mathbf{x}_i\mathbf{x}_i'$$
That is, $X'X$ is the sum of $n$ outer products. Recall two linear algebra facts:


*

*$\mathrm{rank}(A + B) \leq \mathrm{rank}(A) + \mathrm{rank}(B) \quad $(i.e. rank is subadditive) 

*$\mathrm{rank}(\mathbf{x}\mathbf{x'}) = 1$ for $\mathbf{x} \neq \mathbf{0} \quad $(i.e. a vector outer product creates a rank 1 matrix)


Hence:
\begin{align*}
\mathrm{rank}(X'X) &\leq \sum_{i=1}^n \mathrm{rank}\left(\mathbf{x}_i\mathbf{x}_i' \right) \\
&\leq n
\end{align*}
Another point...
Let's say we're in the situation $n > p$ and we calculate our estimate $\hat{\mathbf{b}} = (X'X)^{-1}X'\mathbf{y}$ and a residual vector $\mathbf{e} = \mathbf{y} - X'\hat{\mathbf{b}}$. The degrees of freedom in the residuals is $n-p$. We have $n$ residuals but we actually only have $n-p$ unique values. (Intuition is that for $n=p$, $\mathbf{e} = \mathbf{0}$.)
A: Suppose $p = n$ and that the $n$-vectors $x_1, \ldots , x_p$ are linearly independent.  Then all we have to show is that $x_{p + 1}$ must be a linear combination of $x_1, \ldots , x_p$.
To do this call the matrix comprised of these column vectors $X$ and note that $X$ is invertible because again we've assumed that $x_1 , \ldots , x_p$ are linearly independent.  Then $x_{p + 1} = X X^{-1} x_{p + 1}$, so $x_{p + 1}$ is indeed a linear combination of $x_1, \ldots , x_p$.
