Tails of Condition Number Distributions.

Let $\kappa$ be the condition number of an $m$-by-$n$ matrix with independent standard Gaussian entries, either real ($\beta = 1$) or complex ($\beta = 2$). The major result is the existence of a constant $C$ (depending on $m$, $n$, and $\beta$) such that $P[\kappa > x] n$. Traditional methods for solving such nonsquare generalized eigenvalue problems $(A - \lambda B)\underline{v} = \underline{0}$ are expected to lead to no solutions in most cases. In this paper we propose a different treatment: We search for the minimal perturbation to the pair $(A,B)$ such that these solutions are indeed possible. Two cases are considered and analyzed: (i) the case when $n=1$ (vector pencils); and (ii) more generally, the $n>1$ case with the existence of one eigenpair. For both, this paper proposes insight into the characteristics of the described problems along with practical numerical algorithms toward their solution. We also present a simplifying factorization for such nonsquare pencils, and some relations to the notion of pseudospectra. [ABSTRACT FROM AUTHOR]