🔢 mathematics

Perfect Copositive Matrices

This paper introduces the concept of perfect copositive matrices, explores their structural properties and differences from classical perfect matrices, and utilizes them to derive a new characterization of the cone of completely positive matrices.

Original authors: Valentin Dannenberg, Achill Schürmann

Published 2026-06-09

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Valentin Dannenberg, Achill Schürmann

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 are trying to solve a giant, complex puzzle made of numbers. In the world of mathematics, there is a special type of puzzle piece called a "matrix." For over a century, mathematicians have been obsessed with a specific kind of puzzle piece called a Perfect Matrix. These are special because they are the "perfect fit" for a specific set of rules involving whole numbers (integers).

This paper introduces a new, slightly more flexible version of these puzzle pieces called Perfect Copositive Matrices. Think of them as the "cousins" of the classic perfect matrices. They play by slightly different rules, but they are incredibly useful for solving a different, very tricky type of puzzle involving "completely positive" numbers.

Here is a breakdown of what the authors discovered, using simple analogies:

1. The Old Rules vs. The New Rules

The Classic Version: Imagine a strict club where the members (matrices) must be "positive definite." This is like a club that only lets in members who are strictly "upward" pointing. The rules for this club are very well-known and have been studied since the 1800s.
The New Version (Copositive): The authors opened a new club. This club is more relaxed. It allows members that are "upward" only when looking at specific, non-negative directions (like only looking at the positive side of a mirror).
The Discovery: The authors found that while these two clubs look similar, they behave very differently once the puzzle gets big enough (specifically, when the matrix size is 3x3 or larger).
- In the old club, all members were "tall" and "stable."
- In the new club, they found members that are "shorter" (lower rank) and even some that are "wobbly" (indefinite), which never happened in the old club.

2. The "Perfect Fit" Concept

To understand what makes a matrix "perfect," imagine you are trying to build a structure using only specific Lego bricks (integer vectors).

A Perfect Matrix is like a unique blueprint. If you tell a mathematician, "This is the smallest structure I can build with these specific bricks," and they can reconstruct your exact blueprint just from that description, your matrix is "perfect."
The paper studies these blueprints in the new, relaxed club (the copositive setting). They found that while the blueprints look similar to the old ones, the new setting allows for some strange, new shapes that the old setting never produced.

3. The Neighborhood Map

The authors created a "neighborhood graph." Imagine every perfect matrix is a house on a map.

Contiguous Neighbors: Some houses are right next to each other. You can walk from one perfect matrix to another by making a tiny change.
The Surprise: In the old club, you could always walk to a neighbor in every direction. In the new club, the authors found that sometimes, if you try to walk in a certain direction, you hit a dead end. You can't find a neighbor there. This is a brand-new phenomenon that only happens in this relaxed setting.

4. The "Universal Translator"

One of the most important findings is a bridge between the old and new worlds.

The authors proved that every single classic perfect matrix has a "twin" in the new copositive world.
Even if a classic matrix doesn't look like it fits the new rules, you can rearrange its numbers (using a specific mathematical shuffle) to make it fit perfectly. This means the new world is big enough to contain a version of every old puzzle piece.

5. The Ultimate Goal: Certifying the Impossible

Why do we care about these matrices?

There is a huge, difficult problem in math called the "Completely Positive" problem. It's like trying to prove a shape is made of only positive ingredients.
Usually, it's hard to prove something is a certain shape. But it's easier to prove something isn't by finding a "certificate" (a witness) that says, "No, this doesn't fit."
The authors found a new way to describe the "Completely Positive" shape. They showed that this shape is exactly the set of all matrices that get along (have a positive relationship) with all the new Perfect Copositive Matrices.
Think of it like this: If you want to know if a person is "good," you don't just look at them; you see how they interact with a specific group of "Perfect Copositive" people. If they get along with all of them, they are "Completely Positive."

Summary

In short, this paper takes a classic mathematical concept (Perfect Matrices) and adapts it for a more modern, flexible setting (Copositive Matrices). They found that while the new setting is more complex and allows for stranger shapes (especially in larger sizes), it is powerful enough to contain all the old shapes and provides a new, clearer way to identify and certify "Completely Positive" matrices. It's like discovering a new, larger universe that includes our old one but offers new tools to solve old problems.

Technical Summary: Perfect Copositive Matrices

Problem Statement
The paper addresses the systematic study of "perfect copositive matrices," a generalization of classical perfect positive definite matrices within the context of copositive optimization. The primary motivation is the algorithmic solution to the problem of finding rational certificates for completely positive (CP) matrices. A matrix $Q$ is completely positive if it admits a decomposition $Q = \sum \alpha_i x_i x_i^\top$ with non-negative coefficients and vectors. Determining membership in the cone of completely positive matrices ( $CP_n$ ) is difficult; however, duality theory suggests that a certificate for $Q \notin CP_n$ is a copositive matrix $B$ such that $\langle B, Q \rangle < 0$ . The authors investigate the structure of perfect copositive matrices to facilitate algorithms (specifically a Voronoi-like simplex-type algorithm) that can traverse the space of copositive matrices to find such certificates or CP-factorizations.

Methodology
The authors extend the classical reduction theory of Voronoi, which analyzes the polyhedral structure of the Ryshkov polyhedron for positive definite matrices, to the cone of copositive matrices ( $COP_n$ ).

Definitions: They define the copositive minimum of a symmetric matrix $B$ as $\min_{COP} B = \inf \{ B[v] : v \in \mathbb{Z}^n_{\geq 0} \setminus \{0\} \}$ . A strictly copositive matrix is termed perfect copositive if it is uniquely determined by its copositive minimum and the set of integer non-negative vectors attaining this minimum.
Polyhedral Structure: They define the copositive Ryshkov polyhedron ( $R_{COP}$ ) as the set of matrices $B$ where $B[v] \geq 1$ for all non-zero $v \in \mathbb{Z}^n_{\geq 0}$ . The vertices of $R_{COP}$ correspond to perfect copositive matrices.
Graph Traversal: The study involves analyzing the neighborhood graph of these vertices. Neighboring perfect copositive matrices are found by moving along extreme rays of the dual of the copositive Voronoi cone.
Dimensional Analysis: The paper conducts a detailed structural analysis for low dimensions ( $n=2$ and $n=3$ ) to identify similarities and differences with the classical theory, and then generalizes findings for $n \geq 3$ .
Lifting Techniques: The authors employ a "lifting" operation (Lemma 5.1) to construct higher-dimensional perfect copositive matrices from lower-dimensional ones, preserving specific properties like rank and copositive minimum.

Key Contributions and Results

Differences from Classical Theory ( $n \geq 3$ ):
- Unlike the classical case where perfect matrices are positive definite, perfect copositive matrices can be indefinite or positive semidefinite with rank strictly less than $n$ .
- For $n \geq 3$ , there exist perfect copositive matrices in all components of the copositive cone, including the set of exceptional copositive matrices ( $COP_n \setminus (S^n_{\geq 0} + N^n)$ ), which only exist for $n \geq 5$ .
- A new phenomenon is identified where certain directions from a perfect copositive matrix lead to an extreme ray of $R_{COP}$ rather than a contiguous perfect matrix, a situation that does not occur in the classical theory.
- For $n=2$ , the perfect copositive matrices are exactly the classical perfect matrices with negative off-diagonal entries.
Embedding of Classical Theory:
- The paper proves that every classical perfect positive definite matrix is arithmetically equivalent to a perfect copositive matrix (Theorem 6.1). This is achieved by showing that for any classical perfect matrix, there exists a unimodular transformation that maps its minimal vectors into the non-negative orthant (up to sign), thereby making it perfect copositive.
Polyhedral Decomposition and Characterization:
- The authors establish a polyhedral representation for the copositive Ryshkov polyhedron $R_{COP}$ . Unlike the classical case, $R_{COP}$ is not merely the convex hull of its vertices; it requires the addition of a cone generated by matrices $E_{ij}$ (where $i \neq j$ ) to account for unbounded directions (Theorem 7.1).
- They prove that the union of copositive Voronoi cones of perfect copositive matrices forms a polyhedral decomposition of the completely positive cone $CP_n$ .
New Characterization of $CP_n$ :
- A significant result is a new characterization of the cone of completely positive matrices. The paper demonstrates that $CP_n$ is exactly the set of non-negative matrices that have a non-negative inner product with all perfect copositive matrices (Corollary 7.7). This provides a dual description of $CP_n$ analogous to how $COP_n$ is the dual of $CP_n$ .

Significance and Claims
The paper claims to provide the "first systematic study" of perfect copositive matrices. Its significance lies in bridging classical number-theoretic reduction theory with modern copositive optimization. By establishing the polyhedral structure of $R_{COP}$ and the existence of perfect copositive matrices across various components of the copositive cone, the authors lay the theoretical groundwork for the algorithmic approach mentioned in their previous work [10]. Specifically, the results support the feasibility of using neighborhood graphs of perfect copositive matrices to generate rational certificates for CP-factorizations or to prove non-membership in $CP_n$ . The authors modestly note that while they find infinitely many perfect copositive matrices (even up to equivalence), the classification problem remains open for higher dimensions, similar to the classical case.