What is the relation between k-means clustering and PCA?

It is true that K-means clustering and PCA appear to have very different goals and at first sight do not seem to be related. However, as explained in the Ding & He 2004 paper K-means Clustering via Principal Component Analysis, there is a deep connection between them. The intuition is that PCA seeks to represent all $n$ data vectors as linear combinations of a small number of eigenvectors, and doe