🔢 mathematics

Min-plus Bruhat decomposition

This paper investigates min-plus Bruhat cells by proving a dimension formula involving permutation length, providing an explicit description for the longest permutation, and establishing the uniqueness of the permutation associated with a tropically non-singular matrix.

Original author: Dima Grigoriev

Published 2026-11-04✓ Author reviewed ⓘ

📖 5 min read🧠 Deep dive

CC BY 4.0

Original author: Dima Grigoriev

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 by the author. For technical accuracy, refer to the original paper. Read full disclaimer

In the vast landscape of mathematics, there is a branch dedicated to understanding how things can be broken down into simpler, fundamental pieces. One of the most famous ways to do this is called the Bruhat decomposition, a method that has long helped mathematicians sort through complex grids of numbers, known as matrices, by organizing them according to specific patterns. This classical approach works beautifully in the world of standard arithmetic, where numbers add and multiply in the ways we learn in school. However, mathematicians have also developed a different kind of arithmetic, often called tropical or min-plus algebra, where the rules of the game change. In this alternative universe, the operation of addition is replaced by finding the minimum of two numbers, and multiplication is replaced by simple addition. This shift might sound like a small tweak, but it completely transforms the geometry of the space, turning smooth curves into sharp, angular shapes. The question that has intrigued researchers is whether the elegant sorting method of the classical world still holds up when we switch to these new, stricter rules.

A mathematician named Dima Grigoriev from the University of Lille in France has taken a deep dive into this question, exploring how these special grids of numbers behave under the min-plus system. His work focuses on specific regions, or "cells," within this mathematical space. Imagine a room filled with every possible arrangement of numbers in a square grid. The goal is to see which of these arrangements can be built by combining two simpler, triangular grids with a specific shuffling pattern in between. In the classical world, every non-singular grid fits neatly into one of these rooms, and the shuffling pattern is unique. Grigoriev set out to see if this same clarity exists in the min-plus world, where the rules are different and the shapes are more rigid.

The researcher proved that these min-plus rooms do exist and have a precise size that depends on the complexity of the shuffling pattern used to create them. The size of the room is determined by two factors: the inherent number of degrees of freedom in the triangular grids and the number of swaps required to achieve the specific shuffling pattern. He showed that for any given pattern, the size of the resulting room is exactly the sum of the triangular grid's capacity and the number of swaps needed for that pattern. This finding establishes a clear, predictable structure for these spaces, confirming that even in this altered arithmetic, there is a rigorous order to how these grids can be constructed.

The study went further to examine the largest and most complex of these rooms, the one created by the most intricate shuffling pattern possible. For this specific case, Grigoriev provided a detailed map of exactly which grids belong inside. He discovered that if a grid satisfies a specific set of conditions regarding its internal numbers—comparing the sums of numbers in different corners of small squares within the grid—then it can be built using the required triangular pieces and the complex shuffle. However, the reverse is not a simple "if and only if" relationship. While grids that strictly meet these conditions are guaranteed to fit, the paper notes that grids fitting into this largest room might also exist where these conditions are met with equality rather than strict inequality. Furthermore, the researcher provided a counterexample demonstrating that a grid can belong to this largest room even if it fails to satisfy the specific inequality conditions entirely. This highlights that the conditions for entry are sufficient but not strictly necessary in all cases. If the inequalities are strict, meaning the sums are not just equal but distinctly different in a specific way, then there is only one single way to build that grid from the pieces. This uniqueness is a powerful result, showing that for the most complex patterns, the path to construction is singular and unambiguous.

Perhaps the most significant finding concerns the identity of the shuffling pattern itself. In the classical world, if a grid is non-singular, it belongs to exactly one room. Grigoriev demonstrated that this property holds true in the min-plus world as well. If a grid is non-singular in the tropical sense—meaning it has a unique best way to be arranged according to the min-plus rules—then it can belong to only one of these specific rooms. It cannot fit into two different rooms defined by different shuffling patterns. This confirms that the min-plus version of the decomposition maintains the uniqueness found in the classical version, providing a solid foundation for understanding these complex structures.

The work also clarifies what happens when things do not fit perfectly. The researcher showed that if a grid does not meet the strict conditions for the largest room, it might still belong to a smaller, less complex room, but it cannot belong to the largest one. Furthermore, he provided examples where a grid might appear to fit a pattern but fails a specific internal check, proving that the conditions for entry are precise and not merely suggestive. This level of detail ensures that the boundaries between these mathematical rooms are sharp and well-defined.

Ultimately, this paper brings a sense of order to a specialized corner of tropical mathematics. By proving the exact dimensions of these cells, describing the precise conditions for the largest one, and confirming the uniqueness of the shuffling pattern for non-singular grids, the author has mapped out a territory that was previously less understood. The results show that despite the strange rules of min-plus arithmetic, the underlying logic of decomposition remains robust, offering a clear and structured way to analyze these numerical grids.

Technical Summary: Min-plus Bruhat Decomposition

Problem Statement

The paper investigates the min-plus analogue of the classical Bruhat decomposition within the framework of tropical (min-plus) algebra. In classical algebra over a field, every non-singular $n \times n$ matrix $M$ belongs to a unique Bruhat cell $B^{(n)} p B^{(n)}$ , where $B^{(n)}$ is the set of upper-triangular matrices and $p$ is a permutation. The closure of these cells follows Chevalley's theorem regarding the Bruhat order on the symmetric group $S_n$ .

The author seeks to determine if a similar decomposition holds for matrices over the min-plus semi-ring $\mathbb{R}_{\infty} := \mathbb{R} \cup \{\infty\}$ , where addition is defined as $\min$ and multiplication as standard addition ( $\odot$ ). Specifically, the paper addresses:

The dimension of the min-plus Bruhat cells $B^{(n)}_{\text{trop}} \odot p \odot B^{(n)}_{\text{trop}}$ .
The explicit geometric description of the highest cell corresponding to the longest permutation $p_0$ .
The uniqueness of the permutation $p$ associated with a tropically non-singular matrix $A$ within such a decomposition.

It is noted that, unlike the classical case, not every min-plus matrix admits a min-plus Bruhat decomposition.

Methodology

The paper employs a combination of tropical geometry techniques and inductive constructive proofs:

Tropicalization and Upper Bounds: To establish the upper bound on the dimension of a min-plus Bruhat cell, the author utilizes the relationship between min-plus algebra and the field of Newton-Puiseux series $\mathbb{C}((t^{1/\infty}))$ . By mapping min-plus matrices to classical matrices via the valuation map (replacing entries $x$ with $t^x$ ), the author demonstrates that the min-plus cell is contained within the tropicalization of the classical Bruhat cell. This allows the transfer of dimension results from classical algebraic geometry to the tropical setting.
Recursive Construction for Lower Bounds: To prove the lower bound on dimension, the author constructs a min-plus prevariety of matrix entries recursively. By fixing specific constraints on the upper-triangular factors (setting diagonal elements to 0 and specific off-diagonal elements to $\infty$ ), the author shows that a sufficient number of entries can be chosen arbitrarily from semi-infinite intervals, thereby establishing the dimension formula.
Inductive Analysis of the Highest Cell: For the specific case of the longest permutation $p_0$ (the anti-diagonal permutation), the paper uses induction on the matrix rows to derive explicit formulas for the factors $b$ and $c$ in the decomposition $A = b \odot p_0 \odot c$ . This involves analyzing $2 \times 2$ tropical submatrices and their singularity conditions, defined by the quantity $\Delta_{q,s}^{k,m}$ .
Uniqueness via Tropical Non-Singularity: The uniqueness of the permutation for non-singular matrices is proven by leveraging the property that the product of tropically non-singular matrices preserves the associated permutation (the "tropical determinant" permutation).

Key Contributions and Results

1. Dimension of Min-plus Bruhat Cells

The paper proves Theorem 1.1, which establishes the dimension of the min-plus Bruhat cell associated with a permutation $p$ :
$\dim(B^{(n)}_{\text{trop}} \odot p \odot B^{(n)}_{\text{trop}}) = \frac{n(n+1)}{2} + l(p)$
where $l(p)$ is the length of the permutation $p$ in terms of Coxeter generators (equivalent to the number of inversions). This result mirrors the dimension of the classical Bruhat cell, confirming that the tropicalization preserves the dimensional structure of these varieties.

2. Explicit Description of the Highest Cell

For the permutation $p_0$ with the maximal length $l(p_0) = \frac{n(n-1)}{2}$ , the cell has dimension $n^2$ . Theorem 1.2 provides an explicit characterization of matrices $A \in \mathbb{R}^{n^2}$ belonging to this cell (up to a subset of dimension less than $n^2$ ):

Condition: A matrix $A$ admits a decomposition $A = b \odot p_0 \odot c$ if and only if specific inequalities involving $2 \times 2$ tropical minors hold:
$\Delta_{q,s}^{k,m} = a_{q,k} + a_{s,m} - a_{q,m} - a_{s,k} \ge 0$
for indices satisfying $1 \le q < s \le n$ , $1 \le k < m \le n$ , and $k + s = n + 1$ .
Canonical Decomposition: If these inequalities hold, the paper provides explicit formulas for the entries of the upper-triangular matrices $b$ and $c$ .
Uniqueness: If the inequalities are strict ( $\Delta > 0$ ), the canonical decomposition is unique. If some $\Delta = 0$ , the matrix lies on the boundary of the cell (a lower-dimensional subset).

3. Uniqueness of the Permutation

Proposition 4.1 asserts that for a tropically non-singular matrix $A$ (defined as having a unique permutation $p_A$ that minimizes the tropical permanent), if $A$ admits a min-plus Bruhat decomposition $A \in B^{(n)}_{\text{trop}} \odot p \odot B^{(n)}_{\text{trop}}$ , then $p$ must be exactly $p_A$ . This confirms that the permutation associated with the decomposition is unique for non-singular matrices, analogous to the classical case.

Significance and Claims

The paper positions its work as a foundational step in understanding the geometry of min-plus matrices.

Structural Analogy: It demonstrates that the fundamental structural properties of the classical Bruhat decomposition—specifically the dimension formula and the uniqueness of the permutation for non-singular elements—have direct analogues in the min-plus setting.
Explicit Geometry: By providing an explicit description of the highest cell via inequalities on $2 \times 2$ submatrices, the paper moves beyond abstract existence to concrete geometric characterization.
Limitations: The author modestly notes that not every min-plus matrix admits such a decomposition, and the paper focuses on characterizing those that do. The paper concludes by posing an open question regarding a tropical analogue of the classical inclusion property ( $D \in B^{(n)} p_D B^{(n)} \implies p_D \preceq p$ ), suggesting this as a direction for further inquiry rather than claiming a resolved result.

The work relies on standard references in tropical geometry (e.g., [7], [6]) and classical algebraic group theory (e.g., [10], [3], [4], [5]) to bridge the gap between classical and tropical algebraic structures.