MDS: Link Squared Distance Matrix and Gram Matrix in Practice

Author

Lieven Clement

Published

Invalid Date

1 Data

Part of the iris dataset

X <- iris[1:5,1:4] |> as.matrix()
X

#>   Sepal.Length Sepal.Width Petal.Length Petal.Width
#> 1          5.1         3.5          1.4         0.2
#> 2          4.9         3.0          1.4         0.2
#> 3          4.7         3.2          1.3         0.2
#> 4          4.6         3.1          1.5         0.2
#> 5          5.0         3.6          1.4         0.2

2 Centering

\[ \mathbf{H} = \mathbf{I} - \frac{1}{n} \mathbf{1}\mathbf{1}^T , \] \[ \mathbf{X}_c = \mathbf{H}\mathbf{X} \] \[ \mathbf{H}\mathbf{X}_c = \mathbf{X}_c \]

H <- diag(nrow(X)) - matrix(1/nrow(X),nrow=nrow(X),ncol=nrow(X))
Xc <- H%*%X
colMeans(Xc)

#>  Sepal.Length   Sepal.Width  Petal.Length   Petal.Width 
#>  2.220446e-16  0.000000e+00  1.576517e-17 -8.326673e-18

H%*%Xc-Xc

#>       Sepal.Length   Sepal.Width  Petal.Length  Petal.Width
#> [1,] -2.220446e-16  5.551115e-17 -1.521006e-17 8.326673e-18
#> [2,] -2.289835e-16  0.000000e+00 -1.521006e-17 8.326673e-18
#> [3,] -2.498002e-16 -1.387779e-17 -2.775558e-17 8.326673e-18
#> [4,] -2.220446e-16 -2.775558e-17 -1.387779e-17 8.326673e-18
#> [5,] -2.220446e-16  0.000000e+00 -1.756928e-17 8.326673e-18

3 Gram matrix

Gram matrix: \(\mathbf{G}=\mathbf{X}\mathbf{X}^T\) Here we work on centered data so \(\mathbf{G}=\mathbf{X}_c\mathbf{X}_c^T\)

G <- Xc%*%t(Xc)

4 Squared Distance matrix

\[ \mathbf{D}_X = \mathbf{N} - 2\mathbf{X}\mathbf{X}^T + \mathbf{N}^T , \]

N <- matrix(diag(G),nrow(Xc),nrow(Xc))
N

#>       [,1]  [,2]  [,3]  [,4]  [,5]
#> [1,] 0.106 0.106 0.106 0.106 0.106
#> [2,] 0.080 0.080 0.080 0.080 0.080
#> [3,] 0.042 0.042 0.042 0.042 0.042
#> [4,] 0.110 0.110 0.110 0.110 0.110
#> [5,] 0.122 0.122 0.122 0.122 0.122

dist2 <- N-2*G+t(N)
dist2

#>      [,1] [,2] [,3] [,4] [,5]
#> [1,] 0.00 0.29 0.26 0.42 0.02
#> [2,] 0.29 0.00 0.09 0.11 0.37
#> [3,] 0.26 0.09 0.00 0.06 0.26
#> [4,] 0.42 0.11 0.06 0.00 0.42
#> [5,] 0.02 0.37 0.26 0.42 0.00

dist(Xc)^2

#>      1    2    3    4
#> 2 0.29               
#> 3 0.26 0.09          
#> 4 0.42 0.11 0.06     
#> 5 0.02 0.37 0.26 0.42

5 Link Gram Matrix and Squared Distance Matrix

\[\mathbf{G} =\mathbf{X}_c\mathbf{X}_c^T=-\frac{1}{2}\mathbf{H}\mathbf{D}_X\mathbf{H}\]

#>        [,1]   [,2]   [,3]   [,4]   [,5]
#> [1,]  0.106 -0.052 -0.056 -0.102  0.104
#> [2,] -0.052  0.080  0.016  0.040 -0.084
#> [3,] -0.056  0.016  0.042  0.046 -0.048
#> [4,] -0.102  0.040  0.046  0.110 -0.094
#> [5,]  0.104 -0.084 -0.048 -0.094  0.122

-1/2*H%*%dist2%*%H

#>        [,1]   [,2]   [,3]   [,4]   [,5]
#> [1,]  0.106 -0.052 -0.056 -0.102  0.104
#> [2,] -0.052  0.080  0.016  0.040 -0.084
#> [3,] -0.056  0.016  0.042  0.046 -0.048
#> [4,] -0.102  0.040  0.046  0.110 -0.094
#> [5,]  0.104 -0.084 -0.048 -0.094  0.122

-1/2*H%*%dist2%*%H - G

#>               [,1]          [,2]          [,3]          [,4]          [,5]
#> [1,] -8.326673e-17 -5.551115e-17  6.938894e-18 -4.163336e-17 -6.938894e-17
#> [2,] -8.326673e-17  0.000000e+00  3.122502e-17  5.551115e-17 -4.163336e-17
#> [3,] -1.387779e-17  3.469447e-17  7.632783e-17  9.714451e-17  0.000000e+00
#> [4,]  1.387779e-17  4.857226e-17  9.020562e-17  1.249001e-16  1.387779e-17
#> [5,] -8.326673e-17 -4.163336e-17 -1.387779e-17  4.163336e-17 -4.163336e-17

6 Show that N cancels out when multiplying with H

\[ \mathbf{H N H} = \mathbf{0}\]

\[ \mathbf{H N}^T \mathbf{H} = \mathbf{0}\]

N%*%H

#>               [,1]          [,2]          [,3]         [,4]          [,5]
#> [1,]  9.048318e-19  9.048318e-19 -6.034062e-18 9.048318e-19 -3.619327e-18
#> [2,] -8.520962e-18 -1.582068e-18  5.356826e-18 1.887379e-18  6.328271e-18
#> [3,] -4.662937e-19  3.003153e-18  3.003153e-18 1.268430e-18  1.865175e-18
#> [4,]  8.604228e-19  8.604228e-19  8.604228e-19 8.604228e-19 -3.441691e-18
#> [5,]  7.271961e-19  7.271961e-19  7.271961e-19 7.271961e-19 -2.908784e-18

H%*%t(N)

#>               [,1]          [,2]          [,3]          [,4]          [,5]
#> [1,]  9.048318e-19 -8.520962e-18 -4.662937e-19  8.604228e-19  7.271961e-19
#> [2,]  9.048318e-19 -1.582068e-18  3.003153e-18  8.604228e-19  7.271961e-19
#> [3,] -6.034062e-18  5.356826e-18  3.003153e-18  8.604228e-19  7.271961e-19
#> [4,]  9.048318e-19  1.887379e-18  1.268430e-18  8.604228e-19  7.271961e-19
#> [5,] -3.619327e-18  6.328271e-18  1.865175e-18 -3.441691e-18 -2.908784e-18

Session info

#> [1] "2026-09-15 16:30:57 CEST"

#> ─ Session info ───────────────────────────────────────────────────────────────
#>  setting  value
#>  version  R version 4.6.1 (2026-06-24)
#>  os       macOS Tahoe 26.1
#>  system   aarch64, darwin23
#>  ui       X11
#>  language (EN)
#>  collate  nl_BE.UTF-8
#>  ctype    nl_BE.UTF-8
#>  tz       Europe/Brussels
#>  date     2026-09-15
#>  pandoc   3.10.2 @ /opt/homebrew/bin/ (via rmarkdown)
#>  quarto   1.9.37 @ /usr/local/bin/quarto
#> 
#> ─ Packages ───────────────────────────────────────────────────────────────────
#>  package      * version date (UTC) lib source
#>  cli            3.6.6   2026-04-09 [1] CRAN (R 4.6.0)
#>  digest         0.6.39  2025-11-19 [1] CRAN (R 4.6.0)
#>  dplyr        * 1.2.1   2026-04-03 [1] CRAN (R 4.6.0)
#>  evaluate       1.0.5   2025-08-27 [1] CRAN (R 4.6.0)
#>  farver         2.1.2   2024-05-13 [1] CRAN (R 4.6.0)
#>  fastmap        1.2.0   2024-05-15 [1] CRAN (R 4.6.0)
#>  forcats      * 1.0.1   2025-09-25 [1] CRAN (R 4.6.0)
#>  generics       0.1.4   2025-05-09 [1] CRAN (R 4.6.0)
#>  ggplot2      * 4.0.3   2026-04-22 [1] CRAN (R 4.6.0)
#>  glue           1.8.1   2026-04-17 [1] CRAN (R 4.6.0)
#>  gtable         0.3.6   2024-10-25 [1] CRAN (R 4.6.0)
#>  hms            1.1.4   2025-10-17 [1] CRAN (R 4.6.0)
#>  htmltools      0.5.9   2025-12-04 [1] CRAN (R 4.6.0)
#>  htmlwidgets    1.6.4   2023-12-06 [1] CRAN (R 4.6.0)
#>  jsonlite       2.0.0   2025-03-27 [1] CRAN (R 4.6.0)
#>  knitr          1.51    2025-12-20 [1] CRAN (R 4.6.0)
#>  lifecycle      1.0.5   2026-01-08 [1] CRAN (R 4.6.0)
#>  lubridate    * 1.9.5   2026-02-04 [1] CRAN (R 4.6.0)
#>  magrittr       2.0.5   2026-04-04 [1] CRAN (R 4.6.0)
#>  otel           0.2.0   2025-08-29 [1] CRAN (R 4.6.0)
#>  pillar         1.11.1  2025-09-17 [1] CRAN (R 4.6.0)
#>  pkgconfig      2.0.3   2019-09-22 [1] CRAN (R 4.6.0)
#>  purrr        * 1.2.2   2026-04-10 [1] CRAN (R 4.6.0)
#>  R6             2.6.1   2025-02-15 [1] CRAN (R 4.6.0)
#>  RColorBrewer   1.1-3   2022-04-03 [1] CRAN (R 4.6.0)
#>  readr        * 2.2.0   2026-02-19 [1] CRAN (R 4.6.0)
#>  rlang          1.2.0   2026-04-06 [1] CRAN (R 4.6.0)
#>  rmarkdown      2.31    2026-03-26 [1] CRAN (R 4.6.0)
#>  S7             0.2.2   2026-04-22 [1] CRAN (R 4.6.0)
#>  scales         1.4.0   2025-04-24 [1] CRAN (R 4.6.0)
#>  sessioninfo    1.2.4   2026-06-04 [1] CRAN (R 4.6.0)
#>  stringi        1.8.7   2025-03-27 [1] CRAN (R 4.6.0)
#>  stringr      * 1.6.0   2025-11-04 [1] CRAN (R 4.6.0)
#>  tibble       * 3.3.1   2026-01-11 [1] CRAN (R 4.6.0)
#>  tidyr        * 1.3.2   2025-12-19 [1] CRAN (R 4.6.0)
#>  tidyselect     1.2.1   2024-03-11 [1] CRAN (R 4.6.0)
#>  tidyverse    * 2.0.0   2023-02-22 [1] CRAN (R 4.6.0)
#>  timechange     0.4.0   2026-01-29 [1] CRAN (R 4.6.0)
#>  tzdb           0.5.0   2025-03-15 [1] CRAN (R 4.6.0)
#>  vctrs          0.7.3   2026-04-11 [1] CRAN (R 4.6.0)
#>  withr          3.0.3   2026-06-19 [1] CRAN (R 4.6.0)
#>  xfun           0.59    2026-06-19 [1] CRAN (R 4.6.0)
#>  yaml           2.3.12  2025-12-10 [1] CRAN (R 4.6.0)
#> 
#>  [1] /Library/Frameworks/R.framework/Versions/4.6/Resources/library
#>  * ── Packages attached to the search path.
#> 
#> ──────────────────────────────────────────────────────────────────────────────