For an m× n matrix A, the mathematical property that the rank of A is equal to r for 0 < r< min (m, n) is an ill-posed problem. In this note we show that, regardless of this circumstance, it is possible to solve the strongly related problem of computing a nearby matrix with at least rank deficiency k in a mathematically rigorous way and using only floating-point arithmetic. Given an integer k and a real or complex matrix A, square or rectangular, we first present a verification algorithm to compute a narrow interval matrix Δ with the property that there exists a matrix within A- Δ with at least rank deficiency k. Subsequently, we extend this algorithm for computing an inclusion for a specific perturbation E with that property but also a minimal distance with respect to any unitarily invariant norm. For this purpose, we generalize Wedin’s sin (θ) theorem by removing its orthogonality assumption. The corresponding result is the singular vector space counterpart to Davis and Kahan’s generalized sin (θ) theorem for eigenspaces. The presented verification methods use only standard floating-point operations and are completely rigorous including all possible rounding errors and/or data dependencies.
