What would then be the way to determine a true dimensionality of a configuration of points $X\in\mathbb{R}^{n\times k}$ based on its Gram matrix $G=XX^T$? The "true" dimensionality refers to the minimum number of dimensions needed to represent a configuration (eg, a line is 1D, but can be represented in 2D).

Different shifts would imply different ranks of $G$ that correspond to different dimensionalities. Consider, for instance, the paper http://convexoptimization.com/TOOLS/Gower1.pdf (Sect. 3, very short, please consider)

If I understand correctly, as long as the shifts are of the form $X'=PX$, $P=I_n-1_nw^T$, where $1_n^Tw=1$, the rank of $G'=X'(X')^T$ is the true dimensionality of $X$? If you consider the 2x2 example from the above paper, a shift where one point is the origin reduces the dimensionality to 1D, which is the true dimensionality (same holds for a centroid origin) Does that mean that, in order to recover the "true" configuration, one is restricted to the above form of the shift?

  • $\begingroup$ @AronAhmadia Isn't your "any shift that does not move one of the points onto the origin is guaranteed to preserve dimensionality of the space" contradicting with the above statement? $\endgroup$
    – usero
    Oct 30, 2012 at 11:01
  • $\begingroup$ What do you mean by the true dimensionality of $X$? Is it the dimension of the affine space spanned by the columns? $\endgroup$ Oct 30, 2012 at 14:32
  • $\begingroup$ @ArnoldNeumaier The question has been edited: "true" dimensionality is the "minimum" dimensionality needed to represent a configuration. $\endgroup$
    – usero
    Oct 30, 2012 at 15:52

1 Answer 1


Yes. You need to move the affine subspace to the origin by subtracting from the points (rows of $X$) some point in this affine subspace, i.e., a linear combination of the given points. This leads to the form of $P$. The rank of the matrix $PX$ formed by the shifted points then gives the dimension of the subspace. As the rank of $X$ and $G=XX^T$ is the same, the rank of $PGP^T$ gives the correct dimension.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.