×

Linear independences in bottleneck algebra and their coherences with matroids. (English) Zbl 0848.90122

Summary: 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,\dots, 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,\dots, d_r\), \(r\geq 0\), such that for each vector \(b\) the system \((a_1,\dots, a_n, d_1,\dots 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 coherence with definition of matroids.

MSC:

90C48 Programming in abstract spaces
05B35 Combinatorial aspects of matroids and geometric lattices
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: EuDML EMIS