A method based on linear feasibility tests for full-rank characterization of convex combinations of matrices (Q6605987)

In this paper, the authors address the problem of determining whether a convex combination of a given set of full-rank matrices \(A_i \in \mathbb{R}^{p \times n}, i=1,2, \ldots, r\), may be rank-deficient. Specifically the goal is to establish whether there exists a vector \(\alpha=\left[\begin{array}{llll}\alpha_1 & \alpha_2 & \cdots & \alpha_r\end{array}\right]^T\) within the unit simplex \[\Lambda_r=\left\{\alpha \in \mathbb{R}^r: \alpha_1, \alpha_2, \ldots, \alpha_r \geq 0, \alpha_1+\alpha_2+\cdots+\alpha_r=1\right\}\] such that \(A(\alpha)=\sum_{i=1}^r \alpha_i A_i\) has rank smaller than \(n\). This problem is relevant for control systems. \N\NThe authors propose a method based on a sequence of linear programs which guarantees the following outcomes for given a tolerance \(\varepsilon>0\). The algorithm terminates after a finite number of iterations and provides one of two results:\N\begin{itemize}\N\item A certification that no \(\alpha \in \Lambda_r\) exists such that \(A(\alpha)\) is rank-deficient;\N\item An \(\alpha \in \Lambda_r\) and a vector \(v \neq 0\) such that \(\|A(\alpha) v\| /\|v\|<\varepsilon\) confirming that the smallest singular value of \(A(\alpha)\) is below \(\varepsilon\).\N\end{itemize}\NThe authors assert that, for a general number of matrices no other numerically verifiable method exists in the literature that achieves the second outcome. Numerical tests conducted in MATLAB demonstrate the feasibility of the new algorithm by comparing it with existing methods. In some cases, the proposed algorithm yields results even where other methods do not underscoring its effectiveness.