Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 (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?

share|improve this question
@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? – usero Oct 30 '12 at 11:01
What do you mean by the true dimensionality of $X$? Is it the dimension of the affine space spanned by the columns? – Arnold Neumaier Oct 30 '12 at 14:32
@ArnoldNeumaier The question has been edited: "true" dimensionality is the "minimum" dimensionality needed to represent a configuration. – usero Oct 30 '12 at 15:52
up vote 2 down vote accepted

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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