ACTA MATHEMATICA UNIVERSITATIS COMENIANAE

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

Download: Adobe PDF

Compressed Postscript

Acta Mathematica Universitatis Comenianae
Institute of Applied Mathematics
Faculty of Mathematics, Physics and Informatics
Comenius University
842 48 Bratislava, Slovak Republic
Telephone: + 421-2-60295111 Fax: + 421-2-65425882
e-Mail: amuc@fmph.uniba.sk Internet: www.iam.fmph.uniba.sk/amuc