1
$\begingroup$

Let certain configuration of $n$ points exist in $d-$dimensional space, $X\in\mathbb{R}^{n\times d}$. 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$. However, suppose that the configuration $X$ is shifted to matrix $X'$. Could it be possible that the new Gram matrix, $G'=X'(X')^T$, has rank different from $G$, ie, $rank(G)\neq rank(G')$?

1 Answers 1

2

Regardless of the points in the $d-dimensional$ space (shifted or not) they can define a basis with rank of at most $n$. Thus $X'=(X + S)$ could denote your shift, but it still has the same number of points, does it not? If you are meaning to say that you are adding points, which would be making the basis set a larger set, then yes, provided they are independent additions to the set of vectors $X$.

In regards to changing the basis to become of lesser rank, then yes, I would say definitely that is a possibility with a shift. Just shift all points to zero for example, that gives rank $0$.

And I just now realized you might mean a shift of all points by the same point, so in that case, the rank could only be reduced by one.

Let G define a gram matrix for some configuration $X \in \mathbb{R}^{n \times d}$, ie. $G=XX^T$. The rank of $X$ is at most $v=min(n,d)$. The rank of the matrix $G$ is at most $min(n,v)$.

Argument:

A vector $\mathbf y$ can be found such that $\mathbf y G \mathbf {y}^T = 0$, just choose $\mathbf y$ in the null space of $X$ (or $X'$ makes no difference) and we have:

$\mathbf y G \mathbf {y}^T = \mathbf y XX^T \mathbf {y}^T = \mathbf 0 \mathbf 0^T=0$

There are $d - v$ such of these vectors ($X$ is of dimension $d$, and has rank $v$), if not more (when $X$ is not full rank), giving $G$ with the same null space ax $X$, thus has at most rank $n$.

If $rank(X) \ne rank(X')$ we do indeed have $rank(G) \ne rank(G')$.

  • 0
    If all in $X$ are shifted by the same vector, the only way to reduce the span of $X$ is to shift so that one of its vectors becomes the zero point, reducing span/rank by one. If d then rank($G$) because rank($G$) $\le d$2012-10-12