Why do we say PCA reduces dimensionality? Suppose we have a set of $m$ data points in $n$ dimensional space (they are just vectors of length $n$). As far as I understand Principal component analysis, we want to 'rotate' the data vectors so that two different components are very little correlated and at the same time we want this rotation to cause biggest variance along the axes.
It's just representing those vectors in a different basis. It has been proved that maximum variance is in the direction of the eigenvector with the largest eigenvalue of covariance matrix. So we want the new basis to be those eigenvectors with the largest eigenvalues. The eigenvalue says what's the variance along its eigenvector.
But again, why do we say it reduce dimensionality? If I change the basis, I will still have $n$ linearly independent vectors as the basis (they will just be those eigenvectors). I'd be able to reduce dimensionality if for example I knew that the last component in all my data is zero (it has zero variance). But I can't do that, because eigenvalues are always non-zero!
I've been reading about PCA for a few days and still don't grasp it, so I'd rather be given an explicit answer.
 A: You can think about PCA like this:
Let's say we're given a bunch of vectors $x_1,\ldots, x_m \in \mathbb R^n$.
And let's suppose that $n$ is a very large number.
PCA finds a small orthonormal set of vectors $v_1,\ldots,v_d \in \mathbb R^n$
such that each vector $x_i$ is (to a good approximation)
a linear combination of the vectors $v_1,\ldots,v_d$.
Each vector $x_i$ is then described (approximately) by only $d$
numbers (the coefficients in this linear combination),
rather than by $n$ numbers.
Since $d \ll n$, this is a big improvement.
A: basically PCA lets you ignore vectors/dimension which doesn't add enough useful information. It lets you do more simple analysis. Dimensionality is reduced because you are looking at fewer dimensions and losing whatever information is contained in it. Hopefully this is very little information because you chose the new vectors to maximize information/variance in them.
For example, we have 2 dimensions and the data plots like this:

We do PCA and get 1 vector and the data plots like this:

There are two groups in our original data and we are able to just as easily discern them after transforming and throwing out the vertical vector. After PCA we have a 1 dimension set of data, but contains all the information we need, and is that much more simple to work with than the 2D original data.
