A Strict Gap Between Relaxed and Partition-Constrained Spectral Compression in a Six-State Lumpable Markov Chain

This paper demonstrates that for a specific six-state reversible lumpable Markov chain, the maximum determinant achievable through partition-constrained spectral compression using indicator vectors is strictly less than that of relaxed orthonormal spectral compression, proving that indicator-based frames are fundamentally weaker than general orthonormal frames even after global optimization.

The Gist

Imagine you have a giant, bustling city with six distinct neighborhoods. People move around these neighborhoods every day, following certain rules (like a Markov chain). Your goal is to understand the "big picture" of how people move without getting lost in the details of every single street.

To do this, you want to group the six neighborhoods into three larger "super-districts."

This paper is about a specific mathematical puzzle: What is the best way to group these neighborhoods, and does it matter how you do the grouping?

Here is the story in simple terms:

1. The Two Ways to Group

The author compares two different strategies for creating these super-districts:

• Strategy A: The "Magic Lens" (Relaxed Spectral Compression)
  Imagine you have a magical pair of glasses that can look at the city and blend the neighborhoods together in any way you want. You can mix parts of Neighborhood 1 with parts of Neighborhood 2, or blend them in fractions. You aren't forced to keep whole neighborhoods together. You just want to find the perfect mathematical blend that captures the most "energy" or "information" about how the city moves.

  • The Goal: Find the absolute best possible view, even if it looks weird or unnatural.

• Strategy B: The "Real Estate Agent" (Partition-Constrained Compression)
  Imagine you are a strict real estate agent. You can only group whole neighborhoods together. You cannot split Neighborhood 1 in half. You must take Neighborhood 1, Neighborhood 2, and Neighborhood 3 and say, "Okay, these three are now one super-district." You have to pick from the 90 possible ways to group the six whole neighborhoods into three groups.

  • The Goal: Find the best grouping, but you are limited to keeping the neighborhoods intact.

2. The Big Question

The paper asks: Is the "Magic Lens" (Strategy A) actually better than the "Real Estate Agent" (Strategy B)?

In many simple cases, the answer is "No, they are the same." The best way to group whole neighborhoods happens to be the same as the best mathematical blend.

But this paper proves that for a specific, tricky city, the answer is a loud "YES."

3. The Discovery: The "Strict Gap"

The author built a specific model of a six-neighborhood city. When they ran the numbers:

• The Magic Lens found a way to group things that captured a "score" (mathematically called a determinant) of 0.088.
• The Real Estate Agent tried every single possible way to group the whole neighborhoods (all 90 combinations). The best they could do was a score of 0.070.

The Result: There is a "Strict Gap." The flexible, mathematical method captured significantly more information than the method that forced whole neighborhoods to stay together.

4. Why Does This Matter?

Think of it like taking a photo of a crowd.

• Strategy B is like taking a photo where you can only blur whole people together. If you blur Person A and Person B, they become one blob.
• Strategy A is like using a special lens that can blur parts of people together to create the smoothest, most informative image possible.

The paper shows that sometimes, if you force yourself to keep "whole people" (whole neighborhoods) together, you lose important details. You can't get the perfect picture just by rearranging whole blocks; you need the freedom to mix and match the pieces.

5. The "Six-Neighborhood" Puzzle

The author didn't just guess this. They:

1. Designed a specific city with six neighborhoods.
2. Calculated the "Magic Lens" score (the theoretical maximum).
3. Wrote a computer program to check all 90 ways to group the neighborhoods (the "Real Estate" limit).
4. Proved mathematically that even the best grouping of whole neighborhoods falls short of the theoretical maximum.

The Takeaway

In the world of data and complex systems, sometimes the "natural" way of grouping things (keeping whole chunks together) is strictly worse than a more abstract, flexible mathematical approach.

This paper is a "proof of concept" that says: "Don't assume that keeping things in their natural boxes is the best way to simplify a problem. Sometimes, you have to be willing to break the boxes to see the true picture."

Technical Summary

1. Problem Statement

The paper investigates the fundamental difference between two methods of spectral compression (state aggregation) in reversible, lumpable Markov chains:

1. Relaxed Spectral Compression: Optimizing over any orthonormal frame (arbitrary subspace) to maximize the determinant of the compressed operator.
2. Partition-Constrained Compression: Optimizing only over frames generated by the normalized indicator vectors of genuine partitions of the state space (state aggregation).

Core Question: Does the restriction to partition-based frames result in a strict loss of spectral information (measured by the determinant of the compressed operator) compared to the relaxed, unconstrained optimum? While intuition suggests partition constraints are a subset of the relaxed space, the paper seeks to prove that this subset is not dense enough to achieve the global optimum in specific, structured scenarios.

2. Methodology

The author employs a hybrid approach combining analytical derivation with exhaustive computational verification on a concrete model.

A. The Model

The study focuses on a symmetric, six-state lumpable Markov chain defined by a stochastic matrix $P$.

• Structure: The state space is naturally divided into three blocks of size 2 ($B_1, B_2, B_3$).
• Operator: The analysis uses the positive operator $T = P^2$.
• Spectral Decomposition: The spectrum of $T$ consists of:
  • Macro-eigenvalues derived from the quotient matrix $K$ (squared): $1, \kappa_2^2, \kappa_3^2$.
  • Local-mode eigenvalues derived from the internal structure of blocks: $t_1, t_2, t_3$ (where $t_r = \beta_r^2$).
• Regime: The analysis assumes a "local-mode-dominated" regime where $\kappa_2^2 > t^* > \kappa_3^2$, with $t^* = \max(t_r)$.

B. Benchmarks

• Relaxed Benchmark ($D_{rel}$): Defined as $\sup_{U^*U=I_3} \det(U^*TU)$. By the Poincaré separation theorem, this equals the product of the three largest eigenvalues of $T$: $\kappa_2^2 t^*$.
• Partition-Constrained Benchmark: Defined as $\sup_{A} \det(Q_A(T))$, where $Q_A(T) = H_A^* T H_A$ and $H_A$ contains normalized indicator vectors of a partition $A$ into 3 non-empty cells.

C. Analytical Strategy

1. Classification: The author classifies the 90 possible partitions of a 6-element set into 3 non-empty cells (Stirling number $S(6,3)=90$).
2. Structured Subfamilies: Two specific families of partitions are identified as analytically dominant:
   • (1, 1, 4) Family: Splitting one true block into singletons and merging the other two.
   • (1, 2, 3) Family: Keeping one block intact, splitting another, and merging a singleton with the third.
3. Closed-Form Derivation: The paper derives exact closed formulas for the determinants of these two structured families in terms of the matrix entries of $L=K^2$ and the local eigenvalues $t_r$.
4. Inequality Proofs: Using spectral bounds on the entries of $L$, the author proves that for these structured families, the determinant is strictly less than the relaxed benchmark under the specified regime.

D. Computational Certificate

To address the remaining 87 partitions (which do not fit the simple structured formulas), the author performs an exhaustive enumeration of all 90 partitions using a specific set of decimal parameters. This serves as a finite certificate to prove the global gap.

3. Key Contributions

1. Proof of Strict Gap: The paper provides the first explicit counterexample showing that partition-constrained optimization yields a strictly smaller determinant than relaxed optimization ($\sup_A \det Q_A(T) < D_{rel}(T)$).
2. Closed-Form Formulas: Derivation of exact determinant formulas for the two most complex structured partition families:
   • For (1, 1, 4): $\det = t_r \frac{3\ell_{rr} - 1}{2}$.
   • For (1, 2, 3): $\det = \frac{1}{3} (\det L + t_r(3\ell_{pp} - 1))$.
3. Analytical Bounds: Proof that in the local-mode-dominated regime, the structured families cannot reach the relaxed optimum.
4. Finite Certificate: A reproducible computational verification for a specific six-state model, isolating the "non-analytic" step to a finite enumeration of 90 cases.

4. Results

Using a specific parameter set (defined in Section 8), the paper calculates:

• Relaxed Benchmark ($D_{rel}$): $0.0883986324$ (Product of the three largest eigenvalues).
• Optimal Partition-Constrained Determinant: $0.0702908835$.
• Natural Block Partition Determinant: $0.0480638931$.

Key Finding: The maximum determinant achievable by any partition (even the optimal one, which happens to be a (1, 1, 4) type partition: [[0, 1, 4, 5], [2], [3]]) is strictly lower than the relaxed optimum.
$$0.0702908835 < 0.0883986324$$

5. Significance

• Theoretical Implication: This result challenges the assumption that state aggregation (partitioning) is always sufficient to capture the dominant spectral content of a lumpable Markov chain. It demonstrates that "indicator-based" frames are strictly weaker than general orthonormal frames, even after global optimization over all possible partitions.
• Methodological Impact: The paper establishes a framework for separating analytic bounds (for structured cases) from finite certificates (for the remainder), offering a blueprint for analyzing similar spectral compression problems in larger systems.
• Practical Relevance: For applications relying on state aggregation (e.g., model reduction in physics, chemistry, or machine learning), this suggests that forcing a hard partition of states may inherently discard significant spectral information that could be captured by a "soft" or relaxed projection.

In conclusion, the paper rigorously proves that partition constraints induce a strict information loss in spectral compression for reversible Markov chains, quantifying this loss via a determinant gap in a concrete six-state model.