# Possible change of rank of a Gram matrix

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

-

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

-
Note that the shift means that all points are shifted by the same value, i.e, $X'=X+(c_1, c_2, \dots, c_d)1_n$, meaning that each column of $X$ 'receives' a shift. So, my question is: could it be that by shifting the data, the matrix of inner products may receive additional positive eigenvalues (increased rank?) – user506901 Oct 8 '12 at 15:59
Only if the original is of deficient rank, but you started with rank($G$)=$d$ which is full rank for $d$ number of points. So, no it could not have increased rank. – adam W Oct 8 '12 at 16:02
Ok, could you edit your answer to the following: let $G$ define a gram matrix for some configuration $X$, ie. $G=XX^T$. Could it be the case that by shifting $X'\leftarrow X$, a new Gram matrix $G'=X'(X')^T$ has rank different from $G$, ie. $rank(G)\neq rank(G')$? – user506901 Oct 8 '12 at 16:16
It would help to be certain, is $n\ge d$ or other way around, or neither? keeping it general for the case of neither is a little tricky, but $G$ can have no more rank than $X$ regardless. – adam W Oct 8 '12 at 16:52
It holds that $n>d$. Now I'm a bit confused with your "so in that case, the rank could only be reduced by one". How do you explain this? This means that by shifting the configuration $X$ one might change the rank of a Gram matrix, or? – user506901 Oct 9 '12 at 9:41