ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

Vol. 64,   2   (1995)
pp.   265-271

LINEAR INDEPENDENCES IN BOTTLENECK ALGEBRA AND THEIR COHERENCES WITH MATROIDS
J. PLAVKA

Abstract.  Let $(B,\leq)$ be a dense, linearly ordered set with maximum and minimum element and $(\oplus,\otimes)=(\max, \min)$. We say that an $(m,n)$ matrix $A=(a_1,a_2,\ldots,a_n)$ has: (i) weakly linearly independent $(WLI)$ columns if for each vector $b$ the system $A\otimes x=b$ has at most one solution; (ii) regularly linearly independent columns $(RLI)$ if for each vector $b$ the system $A\otimes x = b$ is uniquely solvable; (iii) strongly linearly independent columns $(SLI)$ if there exist vectors $d_1,d_2,\ldots,d_r$, $r\geq0$ such that for each vector $b$ the system $(a_1,\ldots, a_n, d_1,\ldots,d_r)\otimes x = b$ is uniquely solvable. For these linear independences we derive necessary and sufficient conditions which can be checked by polynomial algorithms as well as their coherences with definition of matroids.

AMS subject classification.  90C27; Secondary 05B35
Keywords.  bottleneck algebra, linear independences, matroid