On tropical matrices of small factor rank (Q1758472): Difference between revisions

Define \(\oplus\) and \(\otimes\) on the real numbers \(\mathbb{R}\) via: \(a\oplus b:=\min\left\{ a,b\right\} \) and \(a\otimes b:=a+b\). Then \((\mathbb{R} ,\oplus,\otimes)\) is called the tropical semiring. Tropical operations are defined on matrices and vectors in a natural way where \(\oplus\) and \(\otimes\) are used in place of \(+\) and \(\cdot\). The factor rank of an \(m\times n\) tropical matrix \(A\) is the least integer \(k\) such that \(A\) can be written as a tropical matrix product \(B\otimes C\) where \(B\) is \(m\times k\) and \(C\) is \(k\times n\). It is known that a tropical matrix \(A\) has factor rank \(\leq2\) if and only if \(A\) has two rows such that every row of \(A\) is a (tropical) linear combination of these two rows [see \textit{M. Develin, F. Santos} and \textit{B. Sturmfels}, Mathematical Sciences Research Institute Publications 52, 213--242 (2005; Zbl 1095.15001)]. In the present paper it is shown that if \(A\) has tropical rank \(>2\) then there is a linear time algorithm to show this by exhibiting a \(3\times3\) submatrix of factor rank \(3\). On the other hand the author gives an example of a \(5\times4\) tropical matrix with factor rank \(4\) which has no \(4\times4\) submatrix of factor rank \(4\).