Tropical patterns of matrices and the Gondran-Minoux rank function (Q445842)

The tropical ring \({\mathbb R}_{\max}\) of nonnegative real numbers carries the tropical addition \(a\oplus b:=\max\{a,b\}\), while real multiplication is unchanged, and it contains the Boolean subring \({\mathbb B}:=\{0,1\}\). If \({\mathbb S}\) is either of these rings, then an \(m\)-tuple of vectors \(a_i:=[a_{i1},\dots,a_{in}]\in{\mathbb S}^n\) is called Gondran-Minoux (GM) dependent, if there are \([\lambda_1,\dots,\lambda_m]\in{\mathbb S}^m\) and disjoint subsets \(I,J\subseteq\{1,\dots,m\}\) such that \(\bigoplus_{i\in I}\lambda_i\neq 0\neq\bigoplus_{j\in J}\lambda_j\) and \(\bigoplus_{i\in I}\lambda_ia_{ik}=\bigoplus_{j\in J}\lambda_ja_{jk}\) for all \(k\). The GM row rank of a matrix \(A\in{\mathbb S}^{m\times n}\) is the maximum cardinality of a GM independent set of rows of \(A\). In the present paper, the tropical pattern of a matrix \(A=[a_{ij}]\in{\mathbb R}^{m\times n}\) is defined as the matrix \(B=[b_{ij}]\in{\mathbb B}^{m\times n}\) given by \(b_{ij}=1\) if and only if \(a_{ij}=\bigoplus_{k=1}^ma_{kj}>0\). Then the main result says that \(A\) has GM row rank \(m\) if and only if there is a diagonal matrix \(D\in{\mathbb R}^{m\times m}\) with non-vanishing diagonal entries such that the tropical pattern of \(DA\) has GM row rank \(m\). As applications, various new inequalities between the GM row rank and other rank notions from tropical algebra, namely the tropical rank and the determinantal rank, are proved.