The generic canonical form of a regular structured matrix pencil Original Research Article

We consider a matrix pencil consisting of two square structured matrices of the same dimensions, where we call a matrix structured if we only know its zero/nonzero pattern. Replacing each nonzero by a parameter, we obtain a parametrization of the matrix pencil. In this paper we assume that for almost all possible parameter values the matrix pencil is regular, i.e. has a nonzero determinant. Given such a regular structured matrix pencil, we present graph theoretic methods to obtain its so-called generic canonical form, described by the zero structures at s=0 (zero structure at the point zero) and s=∞ (zero structure at the point infinity), and the number of finite zeros outside s=0 (zeros outside s=0 and s=∞) which will be shown to be mutually distinct. Here the word generic indicates that the obtained canonical form will be of the same shape for almost all possible parameter values. The presented methods are related to well-known and efficient methods from combinatorial optimization.