The maximum row length nonsingularity radius (Q2564958)

The spectrum of a real \(n\times n\) matrix \(M\) with respect to a subspace \(Q\) of the \(n\times n\) matrices is defined as the set of matrices \(S\) such that \(M-S\) is singular. The nonsingularity radius for \(M\) with respect to \(Q\) is the shortest matrix in the spectrum for \(M\) with respect to \(Q\) in some norm on the \(n\times n\) matrices. The norm in this case is the maximum row-length and the subspace of matrices consists of those who have zeroes in the lower right corner in some decomposition. The nonsingularity radius is computed in this case. The computation is reduced to a simple comparison test, which nevertheless is NP-complete.