An improved algorithm on the content of realizable fuzzy matrices (Q416271)

Let \(L=[0,1]\) and let \(\odot\) denote the max-min composition of fuzzy matrices over \(L\), i.e., \(E=C\odot D\) when \(E_{ij}=\max_k(\min(C_{ik},D_{kj}))\). A matrix \(A\in L^{n\times n}\) is realizable if there is a matrix \(B\in L^{n\times t}\) such that \(A=B\odot B^T\). The content of \(A\) is defined as \(r(A)=\min\{t:A=B\odot B^T, B\in L^{n\times t}\}\). Computing \(r(A)\) is an NP-complete problem [\textit{X. Wang} and \textit{Y. Yang}, ``On the computational complexity of the Schein rank of fuzzy matrices'', Math. Numer. Sin. 29, No.\ 3, 273--284 (2007; Zbl 1140.65328)]. The first author has proposed an algorithm to compute \(B\) and \(r(A)\) in \(O([r(A)]^{n^2})\) steps [\textit{X. Wang}, ``How to calculate the content for a given realizable fuzzy matrix'', Chin.\ Ann.\ Math., Ser.\ A 20, No.~6, 701--706 (1999; Zbl 0939.03510)]. In the current paper the symmetry of the problem is used to simplify the algorithm and reduce the complexity to \(O([r(A)]^{n(n+1)/2})\) steps.