Applications of the generalized Sylvester matrix

Recently a Sylvester matrix for several polynomials has been defined, establishing the relative primeness and the greatest common divisor of polynomials. Using this matrix, we perform qualitative analysis of several polynomials regarding the inners, the bigradients, Trudi's theorem, and the connection of inners and the Schur complement. Also it is shown how the regular greatest common divisor of m+1 (m>1) polynomial matrices can be determined.     

Generalized Hankel matrices of Markov parameters and their applications to control problems

The concept of Hankel matrices of Markov parameters associated with two polynomials is generalized for matrices. The generalized Hankel matrices of Markov parameters are then used to develop methods for testing the relative primeness of two matrices A and B, for determining stability and inertia of a matrix, and for constructing a class of matrices C such that A + C has a desired spectrum. Neither the method of construction of the generalized Hankel matrices nor the methods developed using these matrices require explicit computation of the characteristic polynomial of A (or of B).     

To Solving Multiparameter Problems of Algebra. 4. The AB-Algorithm and its Applications

The paper continues the investigation of methods for factorizing q-parameter polynomial matrices and considers their applications to solving multiparameter problems of algebra. An extension of the AB-algorithm, suggested earlier as a method for solving spectral problems for matrix pencils of the form A - λB, to the case of q-parameter (q ≥ 1) polynomial matrices of full rank is proposed. In accordance with the AB-algorithm, a finite sequence of q-parameter polynomial matrices such that every subsequent matrix provides a basis of the null-space of polynomial solutions of its transposed predecessor is constructed. A certain rule for selecting specific basis matrices is described. Applications of the AB-algorithm to computing complete polynomials of a q-parameter polynomial matrix and exhausting them from the regular spectrum of the matrix, to constructing irreducible factorizations of rational matrices satisfying certain assumptions, and to computing “free” bases of the null-spaces of polynomial solutions of an arbitrary q-parameter polynomial matrix are considered. Bibliography: 7 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 309, 2004, pp. 127–143.     

On the expressive power of CNF formulas of bounded tree- and clique-width

We study representations of polynomials over a field K from the point of view of their expressive power. Three important examples for the paper are polynomials arising as permanents of bounded tree-width matrices, polynomials given via arithmetic formulas, and families of so called CNF polynomials. The latter arise in a canonical way from families of Boolean formulas in conjunctive normal form. To each such CNF formula there is a canonically attached incidence graph. Of particular interest to us are CNF polynomials arising from formulas with an incidence graph of bounded tree- or clique-width.We show that the class of polynomials arising from families of polynomial size CNF formulas of bounded tree-width is the same as those represented by polynomial size arithmetic formulas, or permanents of bounded tree-width matrices of polynomial size. Then, applying arguments from communication complexity we show that general permanent polynomials cannot be expressed by CNF polynomials of bounded tree-width. We give a similar result in the case where the clique-width of the incidence graph is bounded, but for this we need to rely on the widely believed complexity theoretic assumption #P?FP/poly.     

An approach to solving multiparameter algebraic problems

An approach to solving the following multiparameter algebraic problems is suggested: (1) spectral problems for singular matrices polynomially dependent on q≥2 spectral parameters, namely: the separation of the regular and singular parts of the spectrum, the computation of the discrete spectrum, and the construction of a basis that is free of a finite regular spectrum of the null-space of polynomial solutions of a multiparameter polynomial matrix; (2) the execution of certain operations over scalar and matrix multiparameter polynomials, including the computation of the GCD of a sequence of polynomials, the division of polynomials by their common divisor, and the computation of relative factorizations of polynomials; (3) the solution of systems of linear algebraic equations with multiparameter polynomial matrices and the construction of inverse and pseudoinverse matrices. This approach is based on the so-called ΔW-q factorizations of polynomial q-parameter matrices and extends the method for solving problems for one- and two-parameter polynomial matrices considered in [1–3] to an arbitrary q≥2. Bibliography: 12 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 229, 1995, pp. 191–246. Translated by V. N. Kublanovskaya.     

Greatest common divisor of generalized polynomials and polynomial matrices

The comrade matrix was introduced recently as the analogue of the companion matrix when a polynomial is expressed in terms of a basis set of orthogonal polynomials. It is now shown how previous results on determining the greatest common divisor of two or more polynomials can be extended to the case of generalized polynomials using the comrade form. Furthermore, a block comrade matrix is defined, and this is used to extend to the generalized case another previous result on the regular greatest common divisor of two polynomial matrices.     

Polynomial numerical hulls of matrix polynomials,II

In this article, we study some algebraic and geometrical properties of polynomial numerical hulls of matrix polynomials and joint polynomial numerical hulls of a finite family of matrices (possibly the coefficients of a matrix polynomial). Also, we study polynomial numerical hulls of basic A-factor block circulant matrices. These are block companion matrices of particular simple monic matrix polynomials. By studying the polynomial numerical hulls of the Kronecker product of two matrices, we characterize the polynomial numerical hulls of unitary basic A-factor block circulant matrices.     

Banach Spaces Admitting a Separating Polynomial and L P Spaces

 We prove that in a Banach space admitting a separating polynomial, each weakly null normalized sequence has a subsequence which is equivalent to the usual basis of some , p an even integer. We show that for each even integer p, the Schatten class admits a separating polynomial. For a space with a basis admitting a 4-homogeneous separating polynomial, we relate the unconditionality of the basis with the existence of certain type of polynomials defined in terms of infinite symmetric matrices. We find relations between the properties of the entries of these matrices and the geometrical structure of the space. Finally we study the existence of convex 4-homogeneous separating polynomials. Received 3 January 2001     

On the characteristic polynomial of the adjacency matrix of the subdivision graph of a graph

The characteristic polynomial of the adjacency matrix of the subdivision graph G is related to the characteristic polynomials of the adjacency matrices of g and its line graph.     

To solving problems of algebra for two-parameter matrices. IV

This paper continues the series of publications devoted to surveying and developing methods for solving the following problems for a two-parameter matrix F (λ, μ) of general form: exhausting points of the mixed regular spectrum of F (λ, μ); performing operations on polynomials in two variables (computing the GCD and LCM of a few polynomials, division of polynomials, and factorization); computing a minimal basis of the null-space of polynomial solutions of the matrix F (λ, μ) and separation of its regular kernel; inversion and pseudo in version of polynomial and rational matrices in two variables, and solution of systems of nonlinear algebraic equations in two unknowns. Most of the methods suggested are based on rank factorizations of a two-parameter polynomial matrix and on the method of hereditary pencils. Bibliography: 8 titles.     

Banach Spaces Admitting a Separating Polynomial and L P Spaces

 We prove that in a Banach space admitting a separating polynomial, each weakly null normalized sequence has a subsequence which is equivalent to the usual basis of some , p an even integer. We show that for each even integer p, the Schatten class admits a separating polynomial. For a space with a basis admitting a 4-homogeneous separating polynomial, we relate the unconditionality of the basis with the existence of certain type of polynomials defined in terms of infinite symmetric matrices. We find relations between the properties of the entries of these matrices and the geometrical structure of the space. Finally we study the existence of convex 4-homogeneous separating polynomials.     

The resultant approach to computing vector characteristics of multiparameter polynomial matrices

Known types of resultant matrices corresponding to one-parameter matrix polynomials are generalized to the multiparameter case. Based on the resultant approach suggested, methods for solving the following problems for multiparameter polynomial matrices are developed: computing a basis of the matrix range, computing a minimal basis of the right null-space, and constructing the Jordan chains and semilattices of vectors associated with a multiple spectrum point. In solving these problems, the original polynomial matrix is not transformed. Methods for solving other parametric problems of algebra can be developed on the basis of the method for computing a minimal basis of the null-space of a polynomial matrix. Issues concerning the optimality of computing the null-spaces of sparse resultant matrices and numerical precision are not considered. Bibliography: 19 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 323, 2005, pp. 182–214.     

Problems of control and information theory (Hungary)

The bezoutian matrix, which provides information concerning co-primeness and greatest common divisor of polynomials, has recently been generalized by Heinig to the case of square polynomial matrices. Some of the properties of the bezoutian for the scalar case then carry over directly. In particular, the central result of the paper is an extension of a factorization due to Barnett, which enables the bezoutian to be expressed in terms of a Kronecker matrix polynomial in an appropriate block companion matrix. The most important consequence of this result is a determination of the structure of the kernel of the bezoutian. Thus, the bezoutian is nonsingular if and only if the two polynomial matrices have no common eigenvalues (i.e., their determinants are relatively prime); otherwise, the dimension of the kernel is given in terms of the multiplicities of the common eigenvalues of the polynomial matrices. Finally, an explicit basis is developed for the kernel of the bezoutian, using the concept of Jordan chains.     

Graph polynomials from principal pivoting

The recursive computation of the interlace polynomial introduced by Arratia, Bollobás and Sorkin is defined in terms of a new pivoting operation on undirected simple graphs. In this paper, we interpret the new pivoting operation on graphs in terms of standard pivoting (on matrices). Specifically, we show that, up to swapping vertex labels, Arratia et al.'s pivoting operation on a graph is equivalent to a principal pivot transform on the graph's adjacency matrix, provided that all computations are performed in the Galois field F₂. Principal pivoting on adjacency matrices over F₂ has a natural counterpart on isotropic systems. Thus, our view of the interlace polynomial is closely related to the one by Aigner and van der Holst.The observations that adjacency matrices of undirected simple graphs are skew-symmetric in F₂ and that principal pivoting preserves skew-symmetry in all fields suggest to extend Arratia et al.'s pivoting operation to fields other than F₂. Thus, the interlace polynomial extends to polynomials on gain graphs, namely bidirected edge-weighted graphs whereby reversed edges carry non-zero weights that differ only by their sign. Extending a proof by Aigner and van der Holst, we show that the extended interlace polynomial can be represented in a non-recursive form analogous to the non-recursive form of the original interlace polynomial, i.e., the Martin polynomial.For infinite fields it is shown that the extended interlace polynomial does not depend on the (non-zero) gains, as long as they obey a non-singularity condition. These gain graphs are all supported by a single undirected simple graph. Thus, a new graph polynomial is defined for undirected simple graphs. The recursive computation of the new polynomial can be done such that all ends of the recursion correspond to independent sets. Moreover, its degree equals the independence number. However, the new graph polynomial is different from the independence polynomial.     

To solving multiparameter problems of algebra. 9. The Ψ<Emphasis Type="Italic">F-q</Emphasis> method for factorizing invariant polynomials and its applications

A new method (the ΨF-q method) for computing the invariant polynomials of a q-parameter (q ≥ 1) polynomial matrix F is suggested. Invariant polynomials are computed in factored form, which permits one to analyze the structure of the regular spectrum of the matrix F, to isolate the divisors of each of the invariant polynomials whose zeros belong to the invariant polynomial in question, to find the divisors whose zeros belong to at least two of the neighboring invariant polynomials, and to determine the heredity levels of points of the spectrum for each of the invariant polynomials. Applications of the ΨF-q method to representing a polynomial matrix F(λ) as a product of matrices whose spectra coincide with the zeros of the corresponding divisors of the characteristic polynomial and, in particular, with the zeros of an arbitrary invariant polynomial or its divisors are considered. Bibliography: 5 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 334, 2006, pp. 165–173.     

Lyapunov,Bézout,and Hankel

Given a polynomial f of degree n, we denote by C its companion matrix, and by S the truncated shift operator of order n. We consider Lyapunov-type equations of the form X?SXC=>W and X?CXS=W. We derive some properties of these equations which make it possible to characterize Bezoutian matrices as solutions of the first equation with suitable right-hand sides W (similarly for Hankel and the second equation) and to write down explicit expressions for these solutions. This yields explicit factorization formulae for polynomials in C, for the Schur-Cohn matrix, and for matrices satisfying certain intertwining relations, as well as for Bezoutian matrices.     

One sided Hermite interpolation by piecewise different generalized polynomials

Piecewise generalized polynomials of different kinds of order n (ECT-splines of order n) are constructed from different ECT-systems of order n via connection matrices which are nonsingular and totally positive.A well-known zero count for polynomial splines is extended to ECT-splines. It is used to construct ECT-B-splines and to show under which conditions ECT-splines will solve modified Hermite-type interpolation problems. Also conditions are specified such that piecewise generalized polynomials form rECT-systems and the interpolation problems associated with may be solved recursively.     

Computing the Invariant Polynomials of a Polynomial Matrix. I

An algorithm for computing the invariant polynomials and the canonical triangular (trapezoidal) matrix for a polynomial matrix of full column rank is suggested. The algorithm is based on the Δ W-1 rank-factorization method for solving algebraic problems for polynomial matrices, previously suggested by the author. Bibliography: 3 titles.     

On the Behrens radical of matrix rings and polynomial rings

It is shown that the Behrens radical of a polynomial ring, in either commuting or non-commuting indeterminates, has the form of “polynomials over an ideal”. Moreover, in the case of non-commuting indeterminates, for a given coefficient ring, the ideal does not depend on the cardinality of the set of indeterminates. However, in contrast to the Brown-McCoy radical, it can happen that the polynomial ring R[X] in an infinite set X of commuting indeterminates over a ring R is Behrens radical while the polynomial ring R〈X〉 in an infinite set Y of non-commuting indeterminates over R is not Behrens radical. This is connected with the fact that the matrix rings over Behrens radical rings need not be Behrens radical. The class of Behrens radical rings, which is closed under taking matrix rings, is described.