# Why are there only $n-1$ principal components for $n$ data if the number of dimensions is $\ge n$?

In PCA, when the number of dimensions $d$ is greater than (or even equal to) the number of samples $N$, why is it that you will have at most $N-1$ non-zero eigenvectors? In other words, the rank of the covariance matrix amongst the $d\ge N$ dimensions is $N-1$.

Example: Your samples are vectorized images, which are of dimension $d = 640\times480 = 307\,200$, but you only have $N=10$ images.

• Imagine $N=2$ points in 2D or in 3D. What is the dimensionality of the manifold that these points are occupying? The answer is $N-1=1$: two points always lie on a line (and a line is 1-dimensional). The exact dimensionality of the space does not matter (as long as it is larger than $N$), your points only occupy 1-dimensional subspace. So the variance is only "spread" in this subspace, i.e. along 1 dimension. This remains true for any $N$. – amoeba Nov 9 '14 at 19:44
• I'd add just an additional precision to @amoeba's comment. Origin point also matters. So, if you have N=2 + origin, the number of dimensions is at utmost 2 (not 1). However, in PCA we usually center the data, which means that we put the origin inside the space of the data cloud - then one dimension gets consumed and the answer will be "N-1", as shown by amoeba. – ttnphns Nov 9 '14 at 19:58
• This is what confuses me. It's not the centering per se that destroys the dimension, right? If you have exactly N samples and N dimensions, then even after centering you still have N eigenvectors..? – GrokingPCA Nov 9 '14 at 20:39
• Why? It is centering that destroys one dimension. Centering (by arithmetic mean) "moves" the origin from "outside" into the space "spanned" by the the data. With the example of N=2. 2 points + some origin generally span a plane. When you center this data, you put the origin on a straight line halfway between the 2 points. So, the data now span only the line. – ttnphns Nov 9 '14 at 20:59
• Euclid already knew this 2300 years ago: two points determine a line, three points determine a plane. Generalizing, $N$ points determine an $N-1$ dimensional Euclidean space. – whuber Nov 10 '14 at 0:15

Consider what PCA does. Put simply, PCA (as most typically run) creates a new coordinate system by:

1. shifting the origin to the centroid of your data,
2. squeezes and/or stretches the axes to make them equal in length, and
3. rotates your axes into a new orientation.

(For more details, see this excellent CV thread: Making sense of principal component analysis, eigenvectors & eigenvalues.) However, it doesn't just rotate your axes any old way. Your new $X_1$ (the first principal component) is oriented in your data's direction of maximal variation. The second principal component is oriented in the direction of the next greatest amount of variation that is orthogonal to the first principal component. The remaining principal components are formed likewise.

With this in mind, let's examine @amoeba's example. Here is a data matrix with two points in a three dimensional space:
$$X = \bigg[ \begin{array}{ccc} 1 &1 &1 \\ 2 &2 &2 \end{array} \bigg]$$ Let's view these points in a (pseudo) three dimensional scatterplot:

So let's follow the steps listed above. (1) The origin of the new coordinate system will be located at $(1.5, 1.5, 1.5)$. (2) The axes are already equal. (3) The first principal component will go diagonally from $(0,0,0)$ to $(3,3,3)$, which is the direction of greatest variation for these data. Now, the second principal component must be orthogonal to the first, and should go in the direction of the greatest remaining variation. But what direction is that? Is it from $(0,0,3)$ to $(3,3,0)$, or from $(0,3,0)$ to $(3,0,3)$, or something else? There is no remaining variation, so there cannot be any more principal components.

With $N=2$ data, we can fit (at most) $N-1 = 1$ principal components.

Let's say we have a matrix $$X=[x_1, x_2, \cdots, x_n]$$ , where each $$x_i$$ is an obervation (sample) from $$d$$ dimension space, so $$X$$ is a $$d$$ by $$n$$ matrix, and $$d > n$$.

If we first centered the dataset , we have $$\sum\limits_{i=1}^n x_i = 0$$, which means: $$x_1=-\sum\limits_{i=2}^n x_i$$, so the column rank of $$X \leq n-1$$ , then $$rank(X)\leq n-1$$.

We know that $$rank(XX^T)=rank(X)\leq n-1$$ , so $$XX^T$$ has at most $$n-1$$ non-zero eigenvalues.