Min-plus Bruhat decomposition

Introduction

We consider min-plus algebra over $\mathbb{R}_{\infty} := \mathbb{R} \cup\{\infty\}$ with operations $\oplus:= \min$, $\odot:= +$ (one can find basic concepts of min-plus algebra in [7], [6]). Our goal is to study a min-plus analogue of Bruhat decomposition. Recall that the latter in classical algebra states that every $n \times n$ matrix $M$ belongs to Bruhat cell $M \in B^{(n)}pB^{(n)}$ for a permutation $p \in S_n$, where $B^{(n)}$ denotes the set of upper-triangular matrices. When $M$ is a non-singular matrix, the permutation is unique. We identify $p$ with the matrix $p$ whose $(i,p(i))$-entries equal $0$ for $1 \le i \le n$, and all other entries equal $\infty$. Chevalley’s theorem [10], [3] states that the closure

where $\prec$ denotes Bruhat order on $S_n$. Originally, Chevalley’s theorem provided this equality after restricting to non-singular matrices, the extension to arbitrary matrices one can find in [4], [5].

Denote by $B_{\mathrm{trop}}^{(n)}$ the set of all $n \times n$ upper-triangular matrices over $\mathbb{R}_{\infty}$.

Observe that a min-plus Bruhat cell $B_{\mathrm{trop}}^{(n)} \odot p \odot B_{\mathrm{trop}}^{(n)}$ is a min-plus (or tropical) prevariety [7], [6]. If a min-plus matrix $A=b\odot p\odot c$ for some $p\in S_n$ and $b,c\in B_{\mathrm{trop}}^{(n)}$, we say that $A$ admits a min-plus Bruhat decomposition. Note that not every min-plus matrix admits a min-plus Bruhat decomposition. For example, one can easily see that for $n=2$ the min-plus Bruhat cell $B_{\mathrm{trop}}^{(2)}\odot(12)\odot B_{\mathrm{trop}}^{(2)}$ consists exactly of matrices $(a_{i,j})_{1\leq i,j\leq2}$ such that $a_{1,1}+a_{2,2}\geq a_{1,2}+a_{2,1}$.

For a permutation $p\in S_n$ by $l(p)$ denote its length in Coxeter generators $(i\ i+1)$, $1\leq i<n$ [10] (which equals the number of inversions in $p$). In § 2 we prove the following

In § 3 we study the highest min-plus Bruhat cell $B_{\mathrm{trop}}^{(n)}\odot p_0\odot B_{\mathrm{trop}}^{(n)}$ where $p_0=(1\ n)(2\ n-1)\cdots$ is the (unique) permutation with the largest possible length $l(p_0)=\frac{n(n-1)}{2}$, being the highest in Bruhat order: $p\prec p_0$ for every permutation $S_n\ni p\ne p_0$. Theorem 1.1 implies that $\dim\left(B_{\mathrm{trop}}^{(n)}\odot p_0\odot B_{\mathrm{trop}}^{(n)}\right)=n^2$. Let $A=(a_{i,j})_{1\leq i,j\leq n}$, $a_{i,j}\in\mathbb{R}$ be a finite matrix. Denote

Note that $\Delta_{q,s}^{k,m}=0$ means that the corresponding $2\times2$ tropical submatrix of $A$ is tropically singular (see e.g. [1]). The following theorem provides an explicit description of the cell $B_{\mathrm{trop}}^{(n)}\odot p_0\odot B_{\mathrm{trop}}^{(n)}\cap\mathbb{R}^{n^2}$ up to a subset of dimension less than $n^2$. Note that not finite matrices constitute a tropical prevariety of dimension less than $n^2$ as well.

ii) Conversely, if $A \in B_{\mathrm{trop}}^{(n)} \odot p_0 \odot B_{\mathrm{trop}}^{(n)}$ then either all the inequalities (1) are strict:

or $\Delta_{q,s}^{k,m}=0$ for some $1 \le q < s \le n$, \$1 \le k < m \le n$, $k+s=n+1$.

iii) If (3) holds then the canonical decomposition (2) is unique. Namely, if

then $b'_{i,j}=b_{i,j}$, $c'_{i,j}=c_{i,j}$, $1\le i,j\le n$ where $b_{i,j}$, $c_{i,j}$ are from (2).

In section 4 for a tropically non-singular (see e.g. [1]) matrix $A$ we show the uniqueness of a permutation $p_A$ (provided that it does exist) such that

This is a min-plus analogue of the assertion that

We mention that in [9] a min-plus version of Bruhat decomposition was considered for matrices over the semi-ring $\mathbb{R}_{\infty}\cup G$ where $G$ is a set of ”ghosts” isomorphic to $\mathbb{R}$ and ”merged” with $\mathbb{R}$, so that between any pair of ”adjacent” real numbers a ”ghost” is inserted.

Dimension of a min-plus Bruhat cell

Proof of Theorem 1.1. First we prove the upper bound on the dimension

Now we denote by $B^{(n)}$ the set of all upper-triangular $n\times n$ matrices over the field $\mathbb{C}((t^{1/\infty}))$ of Newton-Puiseux series of the form $\sum_{i_0\le i\in\mathbb{Z}}\alpha_i t^{i/q}$, $\alpha_i\in\mathbb{C}$, $q\in\mathbb{Z}_{\ge1}$.

We claim that

where $\operatorname{Trop}$ denotes the tropicalization [7], [6]. Indeed, for any matrix

with $b_{i,j},c_{i,j}\in\mathbb{Q}_{\infty}$ consider (classical) matrices $(t^{b_{i,j}})_{1\le i,j\le n}$, $(t^{c_{i,j}})_{1\le i,j\le n}$. As usually, we agree that $t^\infty:=0$. Observe that if for a matrix $A$ over the semi-ring $\mathbb{Q}_{\infty}$ it holds

for some $b_{i,j}, c_{i,j} \in\mathbb{R}_{\infty}$ then there exists a solution of (4) for suitable $b_{i,j}, c_{i,j} \in\mathbb{Q}_{\infty}$ since (4) is a system of (classical) linear inequalities. Thus, we obtain the equality

which justifies the claim.

On the other hand, it holds

For the first equality see [7, 6]. For the second equality see [10, 3] (one can deduce it by induction on Bruhat order from Chevalley’s theorem, see also [4, 5]). Together with the claim above this implies the upper bound on the dimension.

Now we proceed to the lower bound. We consider the equality

It holds

We impose equalities $b_{i,i}=0$, $b_{i,k}=\infty$, $1\le i<k\le n$, $p(i)<p(k)$.

Let us construct a min-plus prevariety of entries $a_{i,j}$ by recursion on $n-i$ (simultaneously we construct matrices $(b_{i,j})_{1\le i,j\le n}$, $(c_{i,j})_{1\le i,j\le n}$). For the base of recursion $i=n$ we have

which determines $c_{p(n),j}$, $p(n)\le j\le n$ for arbitrary $a_{n,j}$, $p(n)\le j\le n$.

For the recursive hypothesis assume that for some $1\le i<n$ for all $n\ge m>i$ entries $a_{m,r}, b_{m,q}, c_{p(m),j}$, $1\le r,q,j\le n$ are already determined, and $b_{m,q}<\infty$, $m\le q$, $p(m)\ge p(q)$, $c_{p(m),j}<\infty$, $p(m)\le j$. Let $p(m_1)<\cdots<p(m_s)<p(i)$ for $m_1,\ldots,m_s>i$, and $p(m)>p(i)$ for any $m>i$, $m\notin\{m_1,\ldots,m_s\}$. For $q<p(m_1)$ it holds $a_{i,q}=\infty$. For $p(m_1)\le q<p(m_2)$ it holds $a_{i,q}=b_{i,m_1}+c_{p(m_1),q}$. Therefore, for an arbitrary value of $a_{i,p(m_1)}<\infty$ we determine $b_{i,m_1}:=a_{i,p(m_1)}-c_{p(m_1),p(m_1)}$. This determines also $a_{i,q}$, $p(m_1)<q<p(m_2)$. After that for $p(m_2)\le q<p(m_3)$ it holds $a_{i,q}=\min\{b_{i,m_1}+c_{p(m_1),q}, b_{i,m_2}+c_{p(m_2),q}\}$. For an arbitrary value of $a_{i,p(m_2)}<b_{i,m_1}+c_{p(m_1),p(m_2)}$ we have $a_{i,p(m_2)}=b_{i,m_2}+c_{p(m_2),p(m_2)}$, which determines $b_{i,m_2}:=a_{i,p(m_2)}-c_{p(m_2),p(m_2)}$. This also determines $a_{i,q}$, $p(m_2)<q<p(m_3)$. Continuing in this way, we take arbitrary values of $a_{i,p(m_1)},a_{i,p(m_2)},\ldots,a_{i,p(m_s)}$ (in suitable semi-infinite intervals), which determine $b_{i,m_1},\ldots,b_{i,m_s}$, respectively, and $a_{i,q}$, $1\le q<p(i)$. Then for every $p(i) \le q \le n$ it holds

For an arbitrary value of $a_{i,q}<\min\{b_{i,m_1}+c_{p(m_1),q},\ldots,b_{i,m_s}+c_{p(m_s),q}\}$ it holds $a_{i,q}=c_{p(i),q}$, which determines $c_{p(i),q}$. This completes the recursive step.

Summarizing the recursive construction, the values of $a_{i,q}$, $1\le i\le n$, $p(i)\le q\le n$ were taken arbitrarily (each of them from a semi-infinite interval), in addition, the values of $a_{i,p(m)}$, $m>i$, $p(m)<p(i)$ also were taken arbitrarily (each of them from a semi-infinite interval). This provides the lower bound

□

The highest min-plus Bruhat cell

Proof of Theorem 1.2. i) First assume (1). We prove (2) by induction on $n-i$. For the base of induction $i=n$ we take $c_{1,j}:=a_{n,j}$, $1\le j\le n$.

For the inductive step assume that (2) and the canonical decomposition are already established for all rows $r>i$. It holds $a_{i,1}=(a_{i,1}-a_{n,1})+a_{n,1}=b_{i,n}+c_{1,1}$. After that we have

which is true since $\Delta_{i,n}^{1,2}\ge0$. Similarly, for $j\le n-i+1$ we get

which is valid because $\Delta_{i,n}^{1,j},\ \Delta_{i,n-1}^{2,j},\ldots,\Delta_{i,n-j+2}^{j-1,j}\ge0$.

For $n-i+2\le j\le n$ we have

which is true since $\Delta_{i,n}^{1,j},\ \Delta_{i,n-1}^{2,j},\ldots,\Delta_{i,i+1}^{n-i,j}\ge0$. This completes the inductive step and proves (2) and i).

ii) Now conversely, assume that

for some $b_{i,j}$, $c_{i,j} \in\mathbb{R}_{\infty}$. We conduct the proof by induction on $n-i$. For the base of induction $i=n$ we note that $b_{n,n}<\infty$, therefore we replace $b_{n,n}$ by $0$ and $c_{1,j}$, $1\leq j\leq n$ by $c_{1,j}+b_{n,n}$. Thus, $c_{1,j}=a_{n,j}$. As the inductive hypothesis assume that for all $q>i$ it holds

At the inductive step we have $a_{i,1}=b_{i,n}+c_{1,1}=b_{i,n}+a_{n,1}$, hence $b_{i,n}=a_{i,1}-a_{n,1}$. After that we have

provided that $i\leq n-2$ (the case $i\geq n-1$ will be considered below as a part of a more general setting). Therefore, it holds $\Delta_{i,n}^{1,2}\geq0$. If $\Delta_{i,n}^{1,2}=0$, ii) is justified. Suppose that $\Delta_{i,n}^{1,2}>0$. Then it holds $b_{i,n-1}=a_{i,2}-a_{n-1,2}$. Continuing in this way by induction on $1\leq j\leq n-i$, we obtain that either

• $\Delta_{i,u}^{n+1-u,r}=0$ for some $1\leq r<j$, $1\leq i<u\leq n$, $n+1-u<r$ or

• $\Delta_{i,u}^{n+1-u,r}>0$ for all $1\leq r<j$, $1\leq i<u\leq n$, $n+1-u<r$ and in addition, $b_{i,n+1-r}=a_{i,r}-a_{n+1-r}$.

Then (5) implies that

Hence it holds $\Delta_{i,n}^{1,j},\Delta_{i,n-1}^{2,j},\ldots,\Delta_{i,n-j+2}^{j-1,j}\geq0$. If one of the latter expressions vanishes then ii) is justified. Suppose that $\Delta_{i,n}^{1,j},\Delta_{i,n-1}^{2,j},\ldots,\Delta_{i,n-j+2}^{j-1,j}>0$. This entails that $b_{i,n-j+1}=a_{i,j}-a_{n-j+1,j}$.

Now consider the case $j=n-i+1$. Then (5) implies that

Therefore, it holds $\Delta_{i,n}^{1,n-i+1},\ldots,\Delta_{i,i+1}^{n-i,n-i+1}\geq0$. Again, if one of the latter expressions vanishes then ii) is justified. Suppose that $\Delta_{i,n}^{1,n-i+1},\ldots,\Delta_{i,i+1}^{n-i,n-i+1}>0$. Then $a_{i,n-i+1}=b_{i,i}+c_{n-i+1,n-i+1}$. Hence $b_{i,i}<\infty$, so we replace $b_{i,i}$ by $0$ and $c_{n-i+1,j}$ by $c_{n-i+1,j}+b_{i,i}$, $n-i+1\leq j\leq n$. Thus, we obtain that $c_{n-i+1,n-i+1}=a_{i,n-i+1}$.

Finally, consider the case $j\geq n-i+2$. Then (6) entails that

Arguing as above we obtain that either one of $\Delta_{i,n}^{1,j},\ldots,\Delta_{i,i+1}^{n-i,j}$ vanishes, or they all are positive, and in this case it holds $c_{n-i+1,j}=a_{i,j}$. This completes the inductive step and the proof of ii).

Observe that to prove iii) one can follow the proof of ii), taking into account that the case of vanishing one of $\Delta_{i,m}^{n-i+1,j}$ never emerges. ✷

Uniqueness of a min-plus Bruhat cell for a tropically non-singular matrix

Recall (see [1]) that $n \times n$ matrix $A$ is tropically non-singular if there exists a (unique) permutation $p_A \in S_n$ such that $\sum_{1 \le i \le n} a_{i,p_A(i)} < \sum_{1 \le i \le n} a_{i,p(i)}$ for any permutation $p \ne p_A$.

Proof. We use the following statement: if $A=U\odot V$ for some $n \times n$ matrices $U$, $V$ then $U$, $V$ are also tropically non-singular and $p_A=p_U\circ p_V$ (see Proposition 3.4 [8], implicitly one can also find it in [2]). Therefore $p_A=p$.

For a classical (not necessarily non-singular) $n \times n$ matrix $D$ there exists a (unique) permutation $p_D$ such that $D \in B^{(n)}p_DB^{(n)}$, and if $D \in B^{(n)}pB^{(n)}$ then $p_D \preceq p$ [4], [5]. Is there a tropical analogue of this assertion?