CSR expansions of matrix powers in max algebra (Q2844737)

In tropical convexity, one firstly defines the tropical segment joining the points \(x,y \in {\mathbb T}^n\) as the set \(\{ \alpha x \oplus \beta y\in {\mathbb T}^n \mid \alpha,\beta \in {\mathbb T} , \alpha\oplus \beta = 1\}\), and then calls a set \(C\subseteq {\mathbb T}^n\) tropically convex if it contains a tropical segment joining any two of its points. Similarly, the notions of cone, half space, semispace, hemispace, convex hull, linear span, convex and linear combination, can be transferred to the tropical setting. In this paper, the authors investigate hemispaces in \({\mathbb T}^n\), which are convex sets in \({\mathbb T}^n\) whose complements in \({\mathbb T}^n\) are also convex. Hemispaces also appear in the literature under the names of halfspaces, convex halfspaces, generalized halfspaces. The definition of the hemispace makes sense in other structures once the notion of a convex set is defined.NEWLINENEWLINELet \(P, R \subseteq {\mathbb T}^n\). If for a convex set \(C\subseteq {\mathbb T}^n\) it holds that NEWLINE\[NEWLINEC= \mathrm{conv}(P)\oplus \mathrm{span}(R),\tag{1}NEWLINE\]NEWLINE where \(\mathrm{conv}(\cdot) \) and \(\mathrm{span}(\cdot)\) denote the tropical convex hull and tropical linear span, correspondingly, then (1) is called a \((P,R)\)-decomposition of \(C\). The paper provides a complete characterization of hemispaces in \({\mathbb T}^n\) by means of the \((P,R)\)-decompositions. In particular, in the dimension 2, the border is described explicitly and all types of hemispaces in \({\mathbb T}^2\) that may appear are presented.