1
$\begingroup$

Let certain configuration of $n$ points exist in $d-$dimensional space, $X\in\mathbb{R}^{n\times d}$, $d<<n$. Also, let the corresponding Gram matrix be defined as $G=XX^T$.

Since $X$ exists in Euclidean space, rank of $G$ is, $rank(G)=rank(X)=d$. Now, suppose that the configuration $X$ is shifted to matrix $X'$ (shift corresponds to the origin translation). Could it be possible that the Gram matrix, $G'=X'(X')^T$, has rank different from $G$, ie, $rank(G)\neq rank(G')$?

Improve this question
$\endgroup$
  • 1
    $\begingroup$ The statement: "Since $X$ exists in Euclidean space, rank of $G$ is, $rank(G)=rank(X)=d$" is not obvious to me. Are you assuming the rank of the original configuration $G$ is $d$ and interested in if it could ever decrease by linear shift? This is trivially true if there are $d$ points and one of the points is shifted onto the origin. $\endgroup$ – Aron Ahmadia Oct 27 '12 at 15:25
  • $\begingroup$ @AronAhmadia: The wording is a little strange, but $d \le n$ does imply that $\text{rank}(X) \le \min\{n,d\} = d$. $\endgroup$ – Jack Poulson Oct 27 '12 at 21:00
  • $\begingroup$ No. The $n\le d$ points could be linearly dependent, in which case $rank(X)<n\le d$. $\endgroup$ – Wolfgang Bangerth Oct 27 '12 at 23:20
  • $\begingroup$ Interpret ''$X$ exists in Euclidean space'' as $X$ spans the space, and the forumula becomes correct. $\endgroup$ – Arnold Neumaier Oct 28 '12 at 11:04
  • $\begingroup$ @usero, you've effectively written a new, more interesting question, down in your third paragraph. Do you mind splitting this off into a new question? Continuously modifying a question makes it very difficult for people who come by this page later to understand the answers (because they are targetting the first paragraph). $\endgroup$ – Aron Ahmadia Oct 30 '12 at 8:54
2
$\begingroup$

As @AronAhmadia mentioned, shifting one of the points to the origin provides a simple example where the rank changes. Consider the following case where $n=2$ and $d=2$:

$$ X = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} = I, $$

where clearly $\text{rank}(X)=2$, and $G=XX^T=I$ has the same rank. But, if we shift the origin to the point $[1,0]^T$ to define

$$ \tilde X = \begin{pmatrix} 0 & 0 \\ -1 & 1 \end{pmatrix}, $$

then $\text{rank}(\tilde X)=\text{rank}(\tilde G)=1$.

Improve this answer
$\endgroup$
  • $\begingroup$ Thanks. However, this is a bit confusing: Original Gram matrix has $rank(G)=2$, meaning that it has 2 positive eigenvalues. Configuration $X$ is therefore in 2D. But, by eigendecomposition of $\tilde{G}$ which has only one eigenvalue, the configuration is 1D. Am I missing something? $\endgroup$ – usero Oct 29 '12 at 10:29
  • $\begingroup$ I think your confusion comes from mixing the spatial dimension (in this case, the width of $X$) with the rank of the matrix. Consider the case where all of the points are sampled from the origin: then, no matter what the dimension of the points, the rank of $X$ and $XX^T$ is zero. $\endgroup$ – Jack Poulson Oct 29 '12 at 15:45
  • $\begingroup$ This is a bit strange. 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$? As you stated, different shifts would imply different ranks of $G$ that correspond to different dimensionalities. What if shifts are restricted to the form $PX$, $P=I_n-1_nw^T$, where $1_n^Tw=1$? This is raised from: convexoptimization.com/TOOLS/Gower1.pdf (Sect. 3, very short, please consider). $\endgroup$ – usero Oct 29 '12 at 18:01
  • $\begingroup$ According to that paper, the "dimension" of the distance matrix $D$ is the minimum rank over the entire set of matrices of configurations $X$ which generate $D$. Thus, in the previous case, we know that the dimension of the distance matrix $D$, which is generated by both $X$ and $\tilde X$, is at most $1$, since the rank of $\tilde X$ is 1. If you would like to directly compute the dimension of $D$, it is equivalent to the rank of $F$, which is defined by Equation 1 of the paper you linked. $\endgroup$ – Jack Poulson Oct 29 '12 at 18:33
1
$\begingroup$

With your updated question, the answer still remains the same, you can still lose rank due to configuration shift if the points are trivially distributed. Appealing back to Jack Poulson's answer, imagine now a case where $n >> 2$, but every point except for one is along the axis $(1,0)$. Assume this last point is on the other axis $(0,1)$. If your linear shift moves the point on $(0,1)$ to $(0,0)$, the rank of the shifted Gram operator becomes one-dimensional.

Improve this answer
$\endgroup$
  • $\begingroup$ I'll try to simplify the question: Suppose a configuration $X\in\mathbb{R}^{n\times 3}$ is given, and $G=XX^T$, $rank(G)=rank(X)=3$. This would mean that a 3D configuration is obtained by eigendecomp. of $G=(U\Lambda^{1/2})(U\Lambda^{1/2})^T$ because there are 3 eigenvalues. However, the above statements indicate that by just shifting $X$, one could obtain $G_1$ that has rank of 2, hence with a configuration actually being 2D. Does there exist a particular choice of shift (origin) for which $rank(X)=rank(XX^T)$ is the true dimensionality of $X$? $\endgroup$ – usero Oct 29 '12 at 17:28
  • $\begingroup$ As long as we are talking about shifts and not rotations, any shift that does not move one of the points onto the origin is guaranteed to preserve dimensionality of the space. By the same principle, the most dimensionality you could lose is 1. $\endgroup$ – Aron Ahmadia Oct 30 '12 at 8:52
  • $\begingroup$ New question at: scicomp.stackexchange.com/questions/3576/… Please consider a contradiction with your above statement. $\endgroup$ – usero Oct 30 '12 at 11:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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