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

Abstract

Given a set of full-rank matrices A1,A2,…,Ar∈Rp×n, this brief paper proposes a method based on linear feasibility tests to determine whether a convex combination A(α)=∑i=1rαiAi, with α=[α1α2⋯αr]T in the unit simplex Λr, may result in a rank-deficient matrix. The method is based on a sequence of linear programs with increasingly tightened constraints, and is guaranteed to reach an outcome after a finite number of iterations. Given a tolerance ɛ>0 arbitrarily chosen by the user, the method will either (i) certify that ∄α∈Λr such that A(α) is rank-deficient or (ii) yield α∈Λr, v≠0 such that ‖A(α)v‖/‖v‖<ɛ, which certifies that the smallest singular value of A(α) is less than ɛ. This method bridges a gap in the literature, as no other numerically verifiable test for generic p, n, r has been proposed to reach the conclusion (ii). Three numerical examples are provided to showcase the advantages of the proposed method with respect to other tests reported in previous papers. The code employed in this work is available at https://github.com/rubensjma/full-rank-characterization.