A characterization of partition systems of \(\mathbb R^n\) and application (Q2275795)

The author tries to find tools for studying the theory of complementarity problems. Given a real matrix \(M\) of size \(n\) and a vector \(q\in \mathbb{R}^n\), the linear complementarity problem consists of finding orthogonal vectors \(x,z\in\mathbb{R}_{\geq0}^n\) such that \(q=-Mx+z\). The author first states a technical result which will be used at the end of the paper to prove that the number of solutions (the number of pairs \((x,z)\)) is at most \(2^k\) if it is possible to replace \(k\) columns of \(M\) by their opposite ones such that the resulting matrix has all its principal minors strictly positive. In case \(k=0\), the set of solutions is non-empty, so that the solution is unique, and moreover, the converse is also true. The mentioned technical result is a characterization of partition systems in \(\mathbb{R}^n\). Given a system of \(m+n\) column vectors \(U=\{u^{1,0}, u^{1,1}, u^{2,0}, u^{2,1}, \dots, u^{m,0}, u^{m,1}, u^{m+1}, \dots, u^n\} \subset\mathbb{R}^n\), such set \(U\) is an \(m\)-partition of \(\mathbb{R}^n\) if for every \(x\in \mathbb{R}^n\) there is a unique \(\lambda=(\lambda^{ 1,0},\lambda^{1,1},\dots,\lambda^{m,0},\lambda^{m,1},\lambda^{m+1},\dots,\lambda^{n})^t\in\mathbb{R}^{m+n}\) such that \(x=U\lambda\) with \(\lambda^{i,0},\lambda^{i,1}\geq0\) and \(\lambda^{i,0}\lambda^{i,1}=0\) for all \(i\in I=\{1,\dots,m\}\). For each \(\alpha\subset I\), we take the matrix \(U(\alpha)\) whose \(i\)th column is \(u^{i,0}\) if \(i\in\alpha\), \(u^{i,1}\) if \(i\in I\setminus\alpha\) and \(u^{i}\) if \(i>m\). It is said that the matrices \(U(\alpha)\) and \(U(\beta)\) are adjacent at the \(i\)th column if \((\alpha\cup \beta)\setminus (\alpha\cap \beta)=\{i\}\) (the remaining columns of such matrices coincide). The obtained characterization is that \(U\) is an \(m\)-partition of \(\mathbb{R}^n\) if and only if \(\text{det}(U(\alpha))\cdot \text{det}(U(\beta))<0\) for any pair of adjacent matrices \(U(\alpha)\) and \(U(\beta)\). The proof considers first the case of complete partitions.