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')$?

$\endgroup$
5
  • 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$ Oct 27, 2012 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$ Oct 27, 2012 at 21:00
  • $\begingroup$ No. The $n\le d$ points could be linearly dependent, in which case $rank(X)<n\le d$. $\endgroup$ Oct 27, 2012 at 23:20
  • $\begingroup$ Interpret ''$X$ exists in Euclidean space'' as $X$ spans the space, and the forumula becomes correct. $\endgroup$ Oct 28, 2012 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$ Oct 30, 2012 at 8:54

2 Answers 2

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$.

$\endgroup$
4
  • $\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, 2012 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$ Oct 29, 2012 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, 2012 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$ Oct 29, 2012 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.

$\endgroup$
3
  • $\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, 2012 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$ Oct 30, 2012 at 8:52
  • $\begingroup$ New question at: scicomp.stackexchange.com/questions/3576/… Please consider a contradiction with your above statement. $\endgroup$
    – usero
    Oct 30, 2012 at 11:02

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.