Determinantally equivalent nonzero functions

This paper refutes a conjecture regarding the classification of functions with identical principal minors by constructing a counterexample, while simultaneously proving that the conjecture holds under natural additional conditions using elementary combinatorial techniques and algebraic identities.

The Gist

The Big Picture: The "Fingerprint" of a Group

Imagine you have a group of people at a party. You want to describe how they interact with each other.

• The Kernel (K): This is a "friendship chart." It's a giant grid where every cell tells you how close two specific people are. If Person A and Person B are best friends, the number is high. If they hate each other, the number is low.
• The Determinant: In math, there's a special calculation called a "determinant." Think of this as a group fingerprint. If you pick any small group of people (say, 3 or 4) from the party and look at their friendship chart, the determinant gives you a single number that summarizes the entire dynamic of that specific subgroup.

The Problem:
The paper asks a simple question: If two different friendship charts (let's call them Chart K and Chart Q) produce the exact same "group fingerprints" for every possible subgroup of people, are the charts essentially the same?

In other words, if the "vibe" of every possible group is identical in both charts, can we transform Chart Q into Chart K using simple, standard rules?

The Previous Belief (The Conjecture)

A previous researcher (Marco Stevens) guessed that there are only two ways to turn one chart into another while keeping the fingerprints the same:

1. The "Flip" (Transposition): Imagine taking the chart and swapping the rows and columns. It's like looking at the friendship chart in a mirror. If A is friends with B, B is friends with A. This works perfectly if the friendship is mutual.
2. The "Re-labeling" (Conjugation): Imagine everyone at the party has a secret "popularity score." If you multiply Person A's row by their score and divide Person B's column by their score, the overall group dynamics (the fingerprints) stay the same. It's like changing the units of measurement (e.g., from "dollars" to "cents") but keeping the relative value the same.

The Catch: This guess was proven true only if the friendship chart was perfectly symmetrical (i.e., if A likes B, B likes A). But what if the chart is messy? What if A likes B, but B hates A? The previous paper didn't know if those two rules were enough for messy, non-symmetric charts.

The Twist: The Counterexample

The author of this paper, Harry, says: "Wait a minute. That guess is wrong for messy charts."

He builds a counterexample (a "Gotcha!" moment).
Imagine a party with 4 people. Harry creates two charts, K and Q.

• He arranges them so that for every group of 2, 3, or 4 people, the "group fingerprint" (determinant) is identical.
• However, you cannot turn Chart Q into Chart K just by flipping it or re-labeling the popularity scores.
• The Analogy: It's like having two different recipes for a cake that taste exactly the same, but you can't get from one recipe to the other just by swapping ingredients or changing the measuring cups. There's a hidden "partial flip" happening that the old rules didn't account for.

The Solution: Adding a "No-Zero" Rule

Since the old rules failed, Harry asks: "What if we add a simple rule to stop these weird counterexamples?"

He proposes a condition: No Zeroes.
In the messy counterexample, there were blocks of "ones" (neutral values) that allowed the weird "partial flip" to happen. Harry says, "Let's assume that for any two different people, their interaction value is never zero. They must have some connection, positive or negative."

He also adds a condition about 4-person groups: If you pick any 4 people, the way they interact in a specific square pattern must be "strong" (non-zero determinant).

The Result:
With these two simple extra rules (No Zeroes + Strong 4-person groups), the old guess becomes TRUE again!
If two charts have the same fingerprints and follow these rules, then one chart is definitely just a "Flip" or a "Re-labeling" of the other.

How They Proved It: The Detective Work

Harry didn't use heavy, complex machinery (like a sledgehammer). Instead, he used a combinatorial magnifying glass.

1. The Graph Theory: He treated the people as dots and their interactions as lines connecting them.
2. The Cycles: He looked at loops in the graph.
   • 3-Cycles: Triangles (A→B→C→A).
   • 4-Cycles: Squares (A→B→C→D→A).
3. The Algebraic Identities: He discovered that if the "group fingerprints" are the same, the products of numbers around these loops must follow strict mathematical laws.
   • He proved that if you know the rules for triangles (3-cycles) and squares (4-cycles), you can deduce the rules for the whole party.
   • He used a clever trick: If two numbers add up to the same total and multiply to the same total, they must be the same numbers (just maybe swapped).

Why Does This Matter?

This paper is important for Machine Learning and Data Science.

• DPPs (Determinantal Point Processes): These are algorithms used to pick diverse sets of items. For example, if you ask a search engine for "photos of dogs," it doesn't want to show you 10 photos of the same Golden Retriever. It wants 10 different dogs. DPPs use these "friendship charts" to ensure diversity.
• The Takeaway: This paper tells data scientists that as long as their data isn't "broken" (has no zero connections), they can trust that their models are unique and stable. If two models look different but produce the same results, they are actually just the same model wearing a different hat.

Summary in One Sentence

Harry proved that if two complex interaction maps produce identical "group vibes" and have no "dead zones" (zeros), then they are mathematically identical, provided you only allow for simple flips or re-labeling of the data.

Technical Summary

1. Problem Statement and Context

The paper addresses a fundamental problem in the theory of Determinantal Point Processes (DPPs) and linear algebra: characterizing the relationship between two "equivalent" kernels.

• The Core Problem: Let $\Lambda$ be a set and $F$ a field. Consider two functions $K, Q: \Lambda^2 \to F$. They are defined as determinantally equivalent if, for any $n \in \mathbb{N}$ and any distinct points $x_1, \dots, x_n \in \Lambda$, the determinants of the matrices formed by these functions are identical:
  $$\det(Q(x_i, x_j))_{1 \le i,j \le n} = \det(K(x_i, x_j))_{1 \le i,j \le n}$$
  The central question is: What transformations relate $Q$ to $K$?

• Previous Work:

  • In the finite case ($\Lambda$ is finite), this relates to Loewy's problem regarding diagonal similarity of matrices with equal principal minors.
  • In the context of DPPs, a previous paper by Marco Stevens [20] conjectured that for symmetric functions, the only transformations preserving determinant equivalence are:
    1. Conjugation: $Q(x, y) = g(x)g(y)^{-1}K(x, y)$ for some nowhere-zero function $g$.
    2. Transposition: $Q(x, y) = K(y, x)$.
  • Stevens proved this conjecture for symmetric functions but left the non-symmetric (general) case open.

• The Challenge: The author investigates whether this classification holds for general (non-symmetric) functions without additional constraints.

2. Methodology

The paper employs a blend of elementary combinatorics, graph theory, and algebraic identities to solve the problem. The approach avoids heavy linear-algebraic machinery (such as the specific rank conditions used by Loewy) in favor of a more accessible, combinatorial framework.

• Graph-Theoretic Framework:

  • The author models the domain $\Lambda$ as a set of vertices.
  • Functions $K$ and $Q$ are treated as edge weights on directed cycles.
  • Key objects are $n$-cycles (sequences of distinct vertices $p_0, \dots, p_n=p_0$).
  • The product of function values along a cycle $p$ is denoted as $h[p] = \prod h(p_{i-1}, p_i)$.

• The "Cocycle" Concept:

  • A function $c$ is a cocycle if $c[p] = 1$ for all cycles $p$.
  • Proposition 4.3 establishes a crucial "shortcut": A function is a full cocycle if and only if it satisfies the cocycle property for cycles of length 1, 2, and 3. This reduces the infinite verification problem to checking small cycles.

• Algebraic Identities:

  • The proof relies on three specific algebraic identities involving products of determinants and cycle products on sets of 4 vertices. These identities link 4-cycles to combinations of 3-cycles.

• Proof Strategy:

  1. Construct a ratio function $S(x, y) = Q(x, y)/K(x, y)$ (or involving transposition).
  2. Show that $S$ (or its transposed variant) satisfies the cocycle property for 3-cycles.
  3. Use the "shortcut" (Prop 4.3) to conclude $S$ is a full cocycle, implying $Q$ is a conjugation of $K$ (or $K^T$).

3. Key Contributions and Results

A. Disproof of the General Conjecture (Counterexample)

The author first demonstrates that the conjecture from [20] fails in the general non-symmetric setting without extra assumptions.

• Counterexample: A $4 \times 4$ matrix case is constructed where $K$ and $Q$ are determinantally equivalent but cannot be related by simple conjugation or full transposition.
• Mechanism: The counterexample relies on a "partial transposition" enabled by a block structure where certain sub-determinants (specifically $2 \times 2$ blocks in off-diagonal positions) are zero. This allows for a transformation that is neither a full conjugation nor a full transposition.

B. The Main Theorem (Theorem 1.1)

The paper provides a corrected classification under specific, natural conditions.

Theorem 1.1: Let $K, Q$ be nowhere-zero functions (except possibly on the diagonal). If they satisfy the non-degeneracy condition:
$$\det \begin{pmatrix} Q(x, y) & Q(x, w) \\ Q(z, y) & Q(z, w) \end{pmatrix} \neq 0$$
for all distinct $x, y, z, w \in \Lambda$, then $K$ and $Q$ are related only by:

1. Conjugation: $Q(x, y) = g(x)g(y)^{-1}K(x, y)$, OR
2. Transposition + Conjugation: $Q(x, y) = g(x)g(y)^{-1}K(y, x)$.

Significance of Conditions:

• Nowhere-zero: Essential to avoid division by zero when defining the ratio function $S$.
• Non-degenerate $2 \times 2$ minors: This condition explicitly rules out the "partial transposition" counterexamples by ensuring the off-diagonal blocks are not singular in a way that permits the pathological transformation.

C. Technical Innovations

• Elementary Proof: Unlike Loewy's proof which required irreducibility and rank conditions, this proof uses only elementary algebra and graph cycles.
• Reduction to 4-Vertex Subsets: The proof reduces the global problem to analyzing subsets of size 4 ($|M|=4$). By proving that all 3-cycles within any 4-element subset must belong to the same "Case" (either all direct or all transposed), the global consistency is established via transitivity.
• Case Analysis: The proof rigorously handles the interaction between 3-cycles and 4-cycles using Lemmas 6.4–6.7, showing that assuming a mix of "Cases" leads to a contradiction with the non-degeneracy hypothesis.

4. Significance and Implications

• Resolution of an Open Problem: The paper settles the open question regarding the classification of equivalent kernels for non-symmetric DPPs, clarifying exactly when the symmetric-case intuition holds.
• Connection to Linear Algebra: It provides a new, elementary proof for a result related to Loewy's work on diagonal similarity, offering a perspective that is more accessible to researchers in combinatorics and probability than the original linear-algebraic approach.
• DPP Theory: For the machine learning and statistics communities using DPPs, this result clarifies the identifiability of non-symmetric kernels. It establishes that under mild non-degeneracy conditions, the kernel is unique up to a gauge transformation (conjugation) and time-reversal (transposition).
• Methodological Contribution: The use of graph-theoretic cycle decompositions to solve determinant equivalence problems offers a new toolkit that may be adaptable to other problems involving matrix minors and combinatorial structures.

Summary Conclusion

Harry Sapranidis Mantelos proves that while the conjecture that "equivalent kernels are only related by conjugation and transposition" is false in the general non-symmetric case (due to partial transposition anomalies), it becomes true under the natural assumption that all $2 \times 2$ off-diagonal minors are non-zero. The proof is notable for replacing complex linear algebra with a clean, combinatorial argument based on cycle products in graphs.