🔢 mathematics

Completing the rank identity for Hadamard powers of Euclidean distance matrices

This paper resolves an open problem regarding Euclidean distance matrices by proving that the rank of their $n$ -th Hadamard power equals $R_d^n$ whenever no annihilating polynomial exists, achieved through a novel kernel factorization that demonstrates the non-singularity of a universal matrix with a block-diagonal structure.

Original authors: Boris Horvat, Alen Orbanić, Iztok Kavkler

Published 2026-07-14

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Boris Horvat, Alen Orbanić, Iztok Kavkler

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a group of friends standing in a park, and you want to measure how far apart everyone is. You write down all these distances in a giant grid called a Euclidean Distance Matrix. Now, imagine you decide to do something weird: you take every single number in that grid and raise it to a specific power, like squaring it or cubing it. This new grid is called the Hadamard power of the original matrix.

For a long time, mathematicians knew a rule about how "complex" (or what we call the "rank") this new grid could be. They knew it couldn't be too complex; it had an upper limit. But there was a nagging mystery: Was that limit always the exact answer, or could it sometimes be lower?

Previous research showed that if your friends were standing on a perfect circle (or sphere), the complexity hit a specific ceiling. But for a random scattering of friends anywhere in the park, the math got messy. The old proof relied on a special trick that only worked if everyone was the same distance from the center. When they weren't, the trick failed, and mathematicians were stuck. They knew the complexity was at most a certain number, but they couldn't prove it was exactly that number unless a very specific, rare condition happened (where a special polynomial equation made everything vanish).

The Big Breakthrough
In this paper, the authors finally solved that mystery. They proved that for any distinct arrangement of points, the complexity of this powered-up distance grid is exactly the maximum possible number, unless those points are "special" in a way that makes a specific polynomial equation equal zero everywhere.

Think of it like a musical instrument. The authors found a way to take the complex sound of the grid and break it down into a simple, universal recipe. They showed that the grid is just a combination of a "score" (a matrix they call M) and the positions of the points.

Here is the magic part: The "score" (M) is a universal constant. It doesn't care where your friends are standing. It's the same for everyone. The authors proved that this score is never broken (mathematically, it's "nonsingular"). It's like a perfectly tuned piano that always produces a full, rich sound. Because this score is always perfect, the only reason the final song (the grid) would sound "thin" or "broken" is if the sheet music (the points) was written in a way that cancels out the notes.

How They Did It
Instead of trying to force the old, broken trick to work, they built a new machine. They broke the problem down into three distinct blocks, like sorting a deck of cards into suits.

Block A: Simple terms.
Block B: The middle terms.
Block C: The mixed-up terms involving distances.

They discovered that the "score" matrix M has a neat, block-diagonal structure. It's like a row of independent light switches. They proved that every single switch is "on" (positive) when you look at it the right way. Because every switch is on, the whole machine works perfectly.

The Verdict
So, what does this mean for the real world?

The Rule: If you have a grid of distances raised to the $n$ -th power, its complexity is exactly equal to a specific formula involving the number of dimensions ( $d$ ) and the power ( $n$ ), provided the points are distinct and not annihilated by a polynomial.
The Exception: The only time this rule fails is if your points are arranged in a very specific, rare pattern where a special polynomial equation (involving the points and their distances) equals zero for every single point.
The Certainty: This isn't just a guess or a simulation. The authors provided a rigorous mathematical proof. They even wrote a computer program to check their work for small numbers (up to $d, n \le 7$ ), and the computer agreed perfectly with the math.

What's Next?
The paper leaves one tiny door open. They know that the score matrix works, but they don't yet have a simple, closed-form recipe to calculate the exact "volume" (determinant) of that score for every possible situation, though they suspect it follows a beautiful pattern similar to the simple one-dimensional case.

In short: The mystery is solved. The grid is as complex as it can possibly be, unless your points are doing something mathematically weird to cancel it out. The authors didn't just guess; they built a universal key that unlocks the answer for any configuration of points.

Technical Summary: Completing the Rank Identity for Hadamard Powers of Euclidean Distance Matrices

Problem Statement
The paper addresses a specific open problem regarding the rank of the $n$ -th Hadamard (entry-wise) power, denoted $D^{(n)}$ , of a Euclidean distance matrix (EDM) $D$ . Given $m$ points $x_1, \dots, x_m \in \mathbb{R}^d$ , the EDM is defined by entries $d_{ij} = \|x_i - x_j\|^2$ , and its $n$ -th power has entries $d_{ij}^n$ .

Previous work by Horvat et al. (2014) established an upper bound for the rank:
$\text{rank } D^{(n)} \leq R^n_d := \binom{d+n}{d} + \binom{d+n-1}{d}$
They proved that this inequality is strict if an "annihilating polynomial" exists within a specific polynomial space $V$ that vanishes on all points $x_i$ . However, the converse remained unresolved: it was unknown whether the absence of such an annihilating polynomial necessarily forces the rank to achieve the upper bound $R^n_d$ . The previous proof for the spherical case relied on a normality argument that failed for general point configurations because the diagonal matrix of squared norms is no longer scalar.

Methodology
The authors resolve the open problem by avoiding the normality obstruction entirely through a new approach based on kernel factorization. The core methodology involves:

Polynomial Space Construction: The authors define a polynomial space $V$ (Equation 1) and partition it into three degree-compatible blocks ( $A$ , $B$ , and $C$ ) based on homogeneous degrees.
- Block A: Polynomials of degree $0$ to $n-1$ .
- Block B: Homogeneous polynomials of degree $n$ .
- Block C: Mixed terms of the form $\|x\|^{2r}x^\alpha$ with total degrees $n+1$ to $2n$ .
  The total dimension of this space is $N = R^n_d$ .
Kernel Factorization: The authors express the kernel $K(x, y) = \|x - y\|^{2n}$ as a bilinear form over the basis of $V$ . Using a trinomial expansion of $\|x - y\|^{2n} = (\|x\|^2 - 2x^Ty + \|y\|^2)^n$ , they demonstrate that $D^{(n)}$ can be factorized as:
$D^{(n)} = \Phi_V M \Phi_V^T$
Here, $\Phi_V$ is the $m \times N$ evaluation matrix of the basis of $V$ on the points $x_i$ , and $M$ is an $N \times N$ matrix determined solely by the kernel and the basis choice, independent of the point configuration.
Structural Analysis of $M$ :
- Block Structure: Due to the joint homogeneity of the kernel (degree $2n$ ), the matrix $M$ exhibits a specific block structure where non-zero blocks only appear where the sum of the degrees of the basis functions equals $2n$ . This results in a structure where $M$ is composed of a central block $M_{BB}$ and off-diagonal blocks $M_{AC}$ and $M_{CA}$ (where $M_{CA} = M_{AC}^T$ ), with all other blocks being zero.
- Nonsingularity Proof: The authors prove that $M$ is nonsingular by analyzing its diagonal blocks. They show that each block $M^{(k)}$ (corresponding to degree pairings summing to $2n$ ) is a weighted sum of Gram matrices with positive coefficients. Specifically, they prove that $(-1)^k M^{(k)}$ is positive definite ( $\succ 0$ ). This uniform positivity ensures that $\det(M) \neq 0$ .

Key Contributions and Results

Resolution of the Open Problem: The paper proves that if no non-zero polynomial in $V$ vanishes on the set of points $\{x_i\}$ , then $\text{rank } D^{(n)} = R^n_d$ . This completes the rank identity for the generic case.
Universal Factorization: The derivation of $D^{(n)} = \Phi_V M \Phi_V^T$ with a configuration-independent matrix $M$ provides a robust algebraic framework for analyzing EDM powers without relying on geometric constraints like spherical symmetry.
Nonsingularity of the Universal Matrix: The proof that $M$ is nonsingular via block-diagonal analysis and positive definiteness of weighted sums of Gram matrices is the central technical achievement.
Characterization of Rank Deficiency: The paper clarifies that rank deficiency occurs if and only if there exists a non-trivial linear combination of the basis functions of $V$ that vanishes at all data points.

Significance
The paper claims to complete Theorem 2 of Horvat et al. (2014) by establishing the exact rank condition for general point configurations. The significance lies in bypassing the "normality obstruction" that previously prevented the extension of the spherical case results to general cases. By reducing the rank question to the nonsingularity of a universal matrix $M$ and the injectivity of the evaluation map $\Phi_V$ , the authors provide a definitive answer to the rank identity problem.

The authors note that for generic configurations (where $m \geq R^n_d$ ), the evaluation matrix $\Phi_V$ has full column rank with probability 1 (as rank-deficient configurations lie in a proper algebraic subset of measure zero). Consequently, for generic points, the rank is exactly $R^n_d$ . The paper also mentions that numerical implementations (NumPy) confirm the block structure and rank predictions for dimensions $d, n \leq 7$ .

The work leaves open the problem of finding a closed-form expression for $\det(M)$ for general $d$ and $n$ , analogous to the known product formula for the $d=1$ case.

Technical Summary: Completing the Rank Identity for Hadamard Powers of Euclidean Distance Matrices

More like this