🔢 mathematics

Eigenvalues of locally positive semidefinite matrices: Non-convexity and Geometry

This paper provides a basic semialgebraic description of the eigenvalue vectors for $4 \times 4$ $2$-locally positive semidefinite matrices by establishing a Fischer-type inequality and proves the non-convexity of such eigenvalue sets for general dimensions where $n \geq 4$ and $d \in \{2, n-2\}$ .

Original authors: Jose Acevedo, Grigoriy Blekherman, Sebastian Debus, Seokbin Lee, Cordian Riener

Published 2026-08-18

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Jose Acevedo, Grigoriy Blekherman, Sebastian Debus, Seokbin Lee, Cordian Riener

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

In the vast landscape of mathematics, there is a class of objects known as symmetric matrices. You can think of these as square grids of numbers that look the same if you flip them across their diagonal, like a reflection in a mirror. These grids are not just abstract puzzles; they are the workhorses of modern science, appearing everywhere from optimizing traffic flow to analyzing the stability of bridges. A special and highly useful group of these matrices is called "positive semidefinite." These are the grids that behave in a very predictable, stable way, ensuring that systems built upon them do not collapse or behave erratically. However, checking whether a large matrix belongs to this stable group is a computationally heavy task, often too slow for the massive datasets used in today's technology.

To solve this, mathematicians have developed a shortcut. Instead of checking the entire grid at once, they check smaller pieces of it. If every small square section of a certain size within the big grid is stable, they call the whole thing "locally positive semidefinite." The hope is that if all the small pieces are good, the whole must be good too. This approach creates a spectrum of possibilities: at one end, the rule is very strict and guarantees stability; at the other, it is very loose and allows for many unstable grids. The question that has puzzled researchers is how the collection of all possible outcomes for these "locally stable" grids looks when you map them out. Specifically, if you take all the possible patterns of numbers that can appear as the "fingerprint" (or eigenvalues) of these grids, do they form a single, smooth, connected shape, or do they break apart into jagged, disconnected islands?

A team of researchers has now answered this question for several important cases, revealing that the shape is far more complex than previously hoped. They discovered that for grids of a certain size, the collection of these fingerprints is not a smooth, solid shape. Instead, it has holes and gaps, meaning that you can find two valid fingerprints where the average of the two is not a valid fingerprint at all. This non-convexity is a significant finding because it proves that the shortcut of checking small pieces does not always preserve the smooth, predictable geometry that mathematicians rely on to solve problems efficiently.

The researchers focused their investigation on grids of different sizes, looking specifically at the relationship between the size of the whole grid and the size of the small pieces they check. They had already known that for the smallest and largest possible piece sizes, the shape of the fingerprints is perfectly smooth and convex. But for the middle ground, the picture was unclear. Using a combination of algebraic reasoning and geometric problem-solving, they provided a complete description for the case of a four-by-four grid where they checked the two-by-two pieces. They found that the boundary of this shape is defined by a specific, intricate rule involving the numbers in the grid. By mapping out this boundary, they could see exactly where the shape bends inward, creating a gap that breaks the smoothness.

To understand why this happens, the team translated the problem into a different language: the geometry of points in a complex plane. They imagined placing points on a flat surface and asking how to arrange them so that the sum of their distances and the distance of their sum met a certain minimum requirement. This turned out to be a difficult, non-smooth optimization problem. By solving this geometric puzzle, they were able to prove that for grids of size four and larger, the set of valid fingerprints is never a simple, solid shape when checking two-by-two pieces or pieces that are two smaller than the whole grid.

One of the most striking results came from analyzing the specific case of a four-by-four grid. The researchers showed that if you take two valid fingerprints that sit on opposite sides of a gap, the point exactly in the middle between them is not a valid fingerprint. This means that if you have two matrices that pass the local stability test, their average might fail the test entirely. This breaks a fundamental assumption that often simplifies mathematical analysis. The team proved that this behavior is not a fluke of the four-by-four case but is a general rule for any grid size of four or larger, provided the pieces being checked are of size two or size two less than the whole grid.

The researchers also explored the boundaries of these shapes to see if they could find the "extremal" points—the most extreme valid fingerprints. They found that the optimal arrangements of points in their geometric model were not random but followed a very specific pattern. For the case of checking two-by-two pieces, the optimal points formed a configuration where most points were identical, with just a few distinct ones balancing the equation. For the case of checking pieces that are two smaller than the whole grid, the optimal points formed a perfect regular polygon, like the vertices of a star or a hexagon, centered around the origin. These precise geometric arrangements dictated the exact shape of the gaps in the fingerprint sets.

While the team has fully mapped the shape for the four-by-four case, the story becomes more mysterious for larger grids. For grids of size five and above, they do not yet have a complete algebraic description of the boundary. However, they have made strong conjectures based on numerical experiments. They suspect that for larger grids, the optimal point configurations that define the shape's boundary are not the perfect regular polygons one might expect, but rather slightly distorted shapes. For instance, in the case of a five-by-five grid, they propose that the optimal shape resembles a "house" with a rectangular base and a triangular roof, rather than a perfect pentagon. For even larger grids, they suggest the optimal shape looks like a rectangle with a few specific adjustments. These conjectures remain unproven, but the numerical evidence is compelling.

The implications of these findings are subtle but important for the field of optimization. The fact that the set of valid fingerprints is not convex means that algorithms designed to find the best solution within this set cannot rely on simple, straight-line paths. They must navigate around the gaps and holes in the shape. This adds a layer of difficulty to problems involving these matrices, suggesting that the "local" check is a powerful tool but one that introduces a specific kind of geometric complexity. The researchers have provided the first clear map of this complexity for small grids and a strong hypothesis for larger ones, turning a vague question about the shape of mathematical stability into a concrete, visualizable reality. Their work shows that even when every small part of a system is stable, the system as a whole can have a jagged, unpredictable geometry that defies simple intuition.

Technical Summary: Eigenvalues of Locally Positive Semidefinite Matrices: Non-Convexity and Geometry

Problem Statement
The paper investigates the spectral geometry of $d$ -locally positive semidefinite (psd) matrices. A real symmetric matrix $X \in \text{Sym}_n$ is defined as $d$ -locally psd if every $d \times d$ principal submatrix is positive semidefinite. The set of such matrices, denoted $S_{n,d}$ , forms a convex cone that interpolates between matrices with nonnegative diagonals ( $d=1$ ) and the full cone of psd matrices ( $d=n$ ).

The central object of study is the set of symmetric spectra $\lambda(S_{n,d})$ , defined as the set of all $n$ -tuples of eigenvalues (unordered) of matrices in $S_{n,d}$ . While it is known that $\lambda(S_{n,d})$ is convex for the extreme cases $d \in \{1, n-1, n\}$ , the geometry for intermediate values of $d$ remains largely unexplored. Specifically, the paper addresses the non-convexity of $\lambda(S_{n,d})$ and seeks a semialgebraic description of these sets, focusing on the smallest non-trivial case $n=4, d=2$ and generalizing to $n \ge 4$ for $d \in \{2, n-2\}$ .

Methodology
The authors employ a combination of algebraic inequalities, semialgebraic geometry, and optimization over point configurations in the complex plane.

Algebraic Inequalities: For the specific case of $n=4, d=2$ , the authors derive a Fischer-type inequality involving the determinants of $2 \times 2$ principal submatrices and the determinant of the full matrix. This inequality is used to establish a relationship between the elementary symmetric polynomials of the eigenvalues, specifically $e_2(\lambda)^2 \ge 4e_4(\lambda)$ .
Semialgebraic Descriptions: Using the derived inequalities, the paper constructs explicit semialgebraic descriptions for the set $\lambda(S_{4,2})$ and its two-dimensional slice $L_{4,2}$ (where the spectrum is of the form $(1, \dots, 1, s, t)$ ).
Optimization and Complex Geometry: To address the general case $n \ge 4$ $n \geq 4$ , the authors reformulate the problem of finding extremal eigenvalues as a min-max point configuration problem in the complex plane. They define optimization problems $\mu^{\max}_{n,d}$ $μ_{n, d}^{m a x}$ and $\pi^{\max}_{n,d}$ $π_{n, d}^{m a x}$ involving the maximum of sums of moduli and sums of complex numbers over subsets of size $d$ $d$ .
- The problem is linked to the existence of matrices in $S_{n,d}$ via a "complex squaring" trick, where the eigenvalues of a matrix $I - M$ are related to the singular values of a factorization involving complex numbers $z_k$ .
- The authors analyze optimal configurations for these min-max problems, utilizing trigonometric inequalities and geometric arguments (e.g., properties of regular polygons and convex hulls).

Key Contributions and Results

Explicit Description for $n=4, d=2$ :
The paper provides a complete basic semialgebraic description of $\lambda(S_{4,2})$ . The set is characterized by the inequalities:
$e_1(\lambda) \ge 0, \quad e_2(\lambda) \ge 0, \quad e_2(\lambda)^2 \ge 4e_4(\lambda).$
This result generalizes previous non-convexity proofs for this specific case by fully describing the boundary and the set's geometry.
Proof of Non-Convexity:
The authors prove that $\lambda(S_{n,d})$ is non-convex for all $n \ge 4$ and $d \in \{2, n-2\}$ .
- For $d=2$ , they explicitly construct two points in $\lambda(S_{n,2})$ such that their convex hull intersects the set only at the endpoints. The optimal configurations minimizing the sum of the last two eigenvalues (in a normalized slice) are shown to be of the form $(0, \frac{3-n}{2})$ and $(\frac{3-n}{2}, 0)$ , demonstrating that the midpoint is not contained in the set.
- For $d=n-2$ , non-convexity is established by showing that the optimal configurations for the constrained problem (sum of eigenvalues equals zero, corresponding to $\pi^{\max}_{n,n-2}$ ) correspond to the vertices of a regular $n$ -gon, which yields a strictly different value than the unconstrained case ( $\mu^{\max}_{n,n-2}$ ).
Optimal Point Configurations:
The paper solves the min-max point configuration problems for specific cases:
- For $d=2$ , the optimal configurations for the unconstrained problem $\mu^{\max}_{n,2}$ are characterized as having $n-2$ equal complex numbers and three numbers summing to zero (specifically related to an ellipse condition).
- For $d=n-2$ , the optimal configurations for the constrained problem $\pi^{\max}_{n,n-2}$ are proven to be the vertices of a regular $n$ -gon centered at the origin.
Conjectures and Open Problems:
The authors formulate Conjecture 3.5 regarding a lower bound for the min-max problem for general $d$ . While proven for $d=1, n-1, 2$ , and $n-2$ , the general case remains open. Furthermore, they propose specific non-regular polygon configurations that they conjecture are optimal for the constrained problem $\pi^{\max}_{n,2}$ :
- For $n=5$ , they conjecture that "the house" (a specific convex pentagon) is the optimal polygon.
- For even $n \ge 6$ , they conjecture that a "3-4 rectangle" configuration is optimal.
  These conjectures suggest that regular polygons are suboptimal for $d=2$ when $n \ge 5$ .

Significance
The paper resolves the open question of whether the set of symmetric spectra $\lambda(S_{n,d})$ is convex for intermediate $d$ , confirming non-convexity for $n \ge 4$ and $d \in \{2, n-2\}$ . By providing a basic semialgebraic description for the $n=4, d=2$ case, it offers the first complete geometric understanding of this specific spectral set. The reduction of spectral geometry problems to min-max point configuration problems in the complex plane provides a new methodological framework that connects matrix theory to problems in discrete geometry and optimization, such as finding small polygons of maximal perimeter. The results highlight the intricate structure of locally psd matrices, showing that their spectral properties deviate significantly from the convex geometry of the full psd cone.

More like this