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.

• Note also that multicollinearity appears either if your design matrix is rank deficient or is by some mishap during the experimental design two of the measures variables are highly correlated. In other words, multicollinearity appears in at least two different instances: 1) too few observations compared to number of recorded variables 2) by design (whether intentional or not). Oct 21 '16 at 8:04

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{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}$$

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}$.)

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$.

• I honestly do not understand why that makes sense. The last sentence >>> Then $x_{P+1} = XX^{-1}...$<<< does not makes sense to me. Without actually digging into the calculation myself my general line of though is that the rank of a matrix is at most $min(n,p)$. So any linear combination of either rows or columns of that matrix will also be at most rank( min(n,p)). In fact I tried building a 3*11 runif matrix X, in R and did an SVD on X, X'X and XX' and got at most a rank 3 in all three cases, since one SVD returns 8 singular values close to machine epsilon. Oct 21 '16 at 7:53
• @Beyer $X = \begin{bmatrix} \mathbf{x}_1& \mathbf{x}_2 & \ldots & \mathbf{x}_p\end{bmatrix}$. Let $\mathbf{c} = X^{-1} \mathbf{x}_{p+1}$. Observe that $x_{p+1} = c_1 \mathbf{x}_1 + c_2 \mathbf{x}_2 + \ldots + c_p \mathbf{x}_p$ since $\mathbf{x}_{p+1}=XX^{-1}\mathbf{x}_{p+1}$. Oct 21 '16 at 11:42