# Configuration shift to change the rank of a Gram matrix

Suppose a matrix $D\in\mathbb{R}^{n\times n}$ of Euclidean distances between $n$ points is given. To obtain a Gram matrix (matrix of inner-products of points that give rise to distances in $D$), one performs $$G=-1/2\cdot PD^{(2)}P^T,$$ where $D^{(2)}$ contains squared entries of $D$, and $P=(I_n-1_nw^T)$, $w^T1_n=1$. It is known (see http://www.sciencedirect.com/science/article/pii/0024379585901879) that in case $w^T1_n=1$, the rank of all Gram matrices is identical, and corresponds to true dimensionality of the data.

However, I wonder what happens when $w^T1_n\neq 1$. Could there be a choice of two different $P$ for which the ranks of associated $G$ are different?

also, why is the constraint $w^T1_n=1$ imposed?

The only formulas that give the correct Gram matrix is the one derived from the relation $d_{ik}^2=g_{ii}-2g_{ik}+g_{kk}$. The simplest version declares a point (wlog with index $0$) to be the zero point; thus $g_{0k}=0$ for all $i$, which gives $g_{kk}=d_{i0}^2$ and then $g_{ik}=(g_{ii}-d_{ik}^2+g_{kk})/2$.
• Such solution would correspond to $w$ (in the formula above) being a column of identity matrix. However, Gram matrix could be constructed with any $w$, $w^T1_n=1$, but the reconstruction would place the origin at different location (linear combination of positions of other points). Still, I wonder what happens if $w^T1_n\neq 1$; could it be that the rank of such obtain Gram matrix is different than from those obtained with a point-origin (as you described). Oct 10, 2012 at 9:39
• @usero: Why should it be a Gram matrix at all when $w^T1\ne 1$? You can test your ideas easily by playing with two or three points only. Oct 10, 2012 at 9:59