Conference abstracts

Session S05 - Rings and Algebras

No date set

On the max-plus algebra of non-negative exponent matrices

Makar Plakhotnyk

postdoctoral researcher (University of S\~ao Paulo), Brasil   -

An integer $n\times n$-matrix $A=(\alpha_{pq})$ is called exponent if all its diagonal entries are equal to zero and for all possible $i,\, j$ and $k$ the inequality $\alpha_{ij} +\alpha_{jk}\geqslant \alpha_{ik}$ holds. The study of exponent matrices is important because of their crucial role in the theory of tiled orders.

We show that the set $\mathcal{T}$ of minimal non-negative exponent $n\times n$-matrices can be described as follows. The matrix $T=(t_{ij})\in \mathcal{E}_n$ belongs to $\mathcal{T}$ if and only if $t_{ij}\in \{0,\, 1\}$ for all $i,\, j$ and there exists a proper subset $\mathcal{I}$ of $\{1,\ldots,\, n\}$ such that $t_{ij}=1$ is equivalent to $i\in \mathcal{I}$ and $j\not\in \mathcal{I}$.

Let $\oplus$ be the element-wise maximum of matrices and let $\otimes$ be a sum of matrices. Clearly, $A\otimes (B\oplus C) = (A\otimes B) \oplus (A\otimes C)$ for all $A,\, B,\, C\in \mathcal{E}_n$, whence $\mathcal{E}_n$ can be considered as an algebra $(\mathcal{E}_n,\, \oplus, \otimes)$, with respect to operations $\oplus$ and $\otimes$.

We prove the following result.

\textbf{Theorem}. \emph{For any non-zero $A\in \mathcal{E}_n$ there exist a decomposition $$ A = B_1\otimes \ldots \otimes B_l\oplus \ldots \oplus C_1\otimes \ldots\otimes C_m, $$ where all matrices $B_1,\ldots,\, C_m$ belong to $\mathcal{T}$ and as usual $\otimes$ performed prior to $\oplus$}.

Thus, $\mathcal{T}$ can be considered as a basis of $(\mathcal{E}_n,\, \oplus, \otimes)$. This basis is unique. Nevertheless, there is no uniqueness of the decomposition of $A\in (\mathcal{E}_n,\, \oplus, \otimes)$ into the max-plus expression of matrices from $\mathcal{T}$.

The work is supported by FAPESP.

Joint work with Mikhailo Dokuchaev (University of S\~ao Paulo, Brasil), Volodymyr Kirichenko (Taras Shevchenko National University of Kyiv, Ukraine) and Ganna Kudryavtseva (University of Ljubljana, Slovenia).

View abstract PDF