Search

A graph G is said to be determined by its generalized spectrum (DGS for short) if whenever Γ is a graph such that Γ and G are cospectral with cospectral complements, then Γ is isomorphic to G . Let G ∪ H be the disjoint union of graphs G and H . In this paper, we give a simple sufficient condition, under which we show that G ∪ H is DGS if and only if both G and H are DGS. In particular, let H = { x } be a singleton graph, we show that if gcd ⁡ ( a n , det ⁡ ( W ( G ) ) ) = 1 and a n is square-free, then G ∪ { x } is DGS if and only if G is DGS, where a n is the constant term of the characteristic polynomial of G and W ( G ) is the walk-matrix of G . It is noticed that in Wang and Xu [9] , the authors gave a sufficient condition for G ∪ { x } to be DGS if G is DGS. However, they missed the condition that a n is square-free in their theorem, and the result obtained is incorrect. We found a counterexample to their result without this condition and give a correct version of the result accordingly in this paper. [ABSTRACT FROM AUTHOR]

Abstract: This paper studies Symmetric Determinantal Representations (SDR) in characteristic 2, that is the representation of a multivariate polynomial P by a symmetric matrix M such that , and where each entry of M is either a constant or a variable. We first give some sufficient conditions for a polynomial to have an SDR. We then give a non-trivial necessary condition, which implies that some polynomials have no SDR, answering a question of Grenet et al. A large part of the paper is then devoted to the case of multilinear polynomials. We prove that the existence of an SDR for a multilinear polynomial is equivalent to the existence of a factorization of the polynomial in certain quotient rings. We develop some algorithms to test the factorizability in these rings and use them to find SDRs when they exist. Altogether, this gives us polynomial-time algorithms to factorize the polynomials in the quotient rings and to build SDRs. We conclude by describing the case of Alternating Determinantal Representations in any characteristic. [Copyright &y& Elsevier]

A classical result due to Eneström and Kakeya gives some bounds for the moduli of the zeros of polynomials having a monotone sequence of non-negative (real) coefficients. The main subject of the present paper is a study of this fact with a view to the recurrence relations fulfilled by systems of orthogonal polynomials on the unit circle. In particular, we will be interested in the special case, where the zeros of the polynomials in question are not located on the boundary of the estimate which occurs in the Eneström–Kakeya theorem. Among other things, we will give characterizations of this case in terms of orthogonal polynomials and present an alternative approach to a well-known characterization due to Hurwitz. Furthermore, we will give some insight how one can apply the main results of this paper in the context of positive Hermitian Toeplitz matrices. [ABSTRACT FROM AUTHOR]

Abstract: Propositions 24 and 25 of Book I of Euclid’s Elements state the fairly obvious fact that if an angle in a triangle is increased without changing the lengths of its arms, then the length of the opposite side increases, and conversely. A satisfactory analogue that holds for orthocentric tetrahedra is established by S. Abu-Saymeh, M. Hajja, M. Hayajneh in a yet unpublished paper, where it is also shown that no reasonable analogue holds for general tetrahedra. In this paper, the result is shown to hold for orthocentric d-simplices for all . The ingredients of the proof consist in finding a suitable parametrization (by a single real number) of the family of orthocentric d-simplices whose edges emanating from a certain vertex have fixed lengths, and in making use of properties of certain polynomials and of Gram and positive definite matrices and their determinants. [Copyright &y& Elsevier]

Abstract: Let be a solvable Lie subalgebra of the Lie algebra ( as a vector space). Let be polynomials in the commuting variables with coefficients in . For matrices , let and letIn this paper, we prove that, for , if one value of the matrix-valued function (the value depends on the product order of the variables) is nilpotent, then, (a) all values of are nilpotent; (b) all values of (again depends on the product order of the variables) are nilpotent, and one value is 0. This generalizes the recent result in and makes his result accurate. The main tool we use in this paper is the representation theory of solvable Lie algebras. [Copyright &y& Elsevier]

Abstract: Let G be a simple undirected graph with the characteristic polynomial of its Laplacian matrix , . Aleksandar Ilić [A. Ilić, Trees with minimal Laplacian coefficients, Comput. Math. Appl. 59 (2010) 2776–2783] identified n-vertex trees with given matching number q which simultaneously minimize all Laplacian coefficients. In this paper, we give another proof of this result. Generalizing the approach in the above paper, we determine n-vertex trees with given matching number q which have the second minimal Laplacian coefficients. We also identify the n-vertex trees with a perfect matching having the largest and the second largest Laplacian coefficients, respectively. Extremal values on some indices, such as Wiener index, modified hyper-Wiener index, Laplacian-like energy, incidence energy, of n-vertex trees with matching number q are obtained in this paper. [Copyright &y& Elsevier]

Abstract: In this paper, robust semi-definite programs are considered with the goal of verifying whether a particular LMI relaxation is exact. A procedure is presented showing that verifying exactness amounts to solving a polynomial system. The main contribution of the paper is a new algorithm to compute all isolated solutions of a system of polynomials. Standard techniques in computational algebra, often referred to as Stetter’s method [H.J. Stetter, Numerical Polynomial Algebra, SIAM, 2004], involve the computation of a Gröbner basis of the ideal generated by the polynomials and further require joint eigenvector computations in order to arrive at the zeros of the polynomial system. Our algorithm does neither require structural knowledge on the polynomial system, nor does it rely on the computation of joint eigenvectors. [Copyright &y& Elsevier]

The analysis of any Hessenberg matrix as a product of a companion matrix and a triangular matrix is presented in this paper. The factors are explicitly given on terms of the entries of the Hessenberg matrix and, further, various factorizations are undertaken. Applications to comrade and confederate matrices, as well as for the corresponding block cases, are included. [ABSTRACT FROM AUTHOR]

This paper considers solvability and feasibility of interval linear equations and inequalities. The new concepts of solvability and feasibility are introduced in a unified framework. Some existing concepts such as weak solvability, strong solvability, weak feasibility and strong feasibility are special cases in this framework. Necessary and sufficient conditions for checking new types of solvability and feasibility are developed. [ABSTRACT FROM AUTHOR]

Abstract: A ray pattern is spectrally arbitrary if given any monic polynomial of order n with complex coefficients, there exists such that the characteristic polynomial of B is . In [1], the authors first presented that a family of irreducible ray patterns with exactly 3n nonzeros is spectrally arbitrary. Then they proved that every irreducible spectrally arbitrary ray pattern has at least nonzeros. So as pointed in [1], the minimum number of nonzeros in an irreducible spectrally arbitrary ray pattern is either 3n or . In this paper, we provide an irreducible spectrally arbitrary ray pattern of order n with nonzeros. So the minimum number of nonzeros in an irreducible spectrally arbitrary ray pattern is . [Copyright &y& Elsevier]

Abstract: In Suzuki (1998) [7] Suzuki gave a classification of association schemes with multiple Q-polynomial structures, allowing for one exceptional case which has five classes. In this paper, we rule out the existence of this case. Hence Suzukiʼs theorem mirrors exactly the well-known counterpart for association schemes with multiple P-polynomial structures, a result due to Eiichi Bannai and Etsuko Bannai in 1980. [Copyright &y& Elsevier]

Abstract: It is clear that a given rational canonical form can be further resolved to a Jordan canonical form with entries from the splitting field of its minimal polynomial. Conversely, with an a priori knowledge of the existence and uniqueness of the rational canonical form of a matrix with entries from a general field, one can modify its Jordan canonical form in the splitting field of its minimal polynomial to construct its rational canonical form in the original field. No author has tried this converse with the a priori existence–uniqueness condition removed. It is feared that “in many occasions when, after a result has been established for a matrix with entries in a given field, considered as a matrix with entries in a finite extension of that field, we cannot go back from the extension field to get the desired information in the original field” [I.N. Herstein, Topics in Algebra, Ginn and Company, Waltham, MA, 1964 (pp. 262–263)]. The present paper removes this a priori condition and uses a “symmetrization” to “integrate” back the Jordan canonical form of a matrix to its rational canonical form in the original field. [Copyright &y& Elsevier]

Abstract: The Fiedler matrices of a monic polynomial p(z) of degree n are n × n matrices with characteristic polynomial equal to p(z) and whose nonzero entries are either 1 or minus the coefficients of p(z). Fiedler matrices include as particular cases the classical Frobenius companion forms of p(z). Frobenius companion matrices appear frequently in the literature on control and signal processing, but it is well known that they posses many properties that are undesirable numerically, which limit their use in applications. In particular, as n increases, Frobenius companion matrices are often nearly singular, i.e., their condition numbers for inversion are very large. Therefore, it is natural to investigate whether other Fiedler matrices are better conditioned than the Frobenius companion matrices or not. In this paper, we present explicit expressions for the condition numbers for inversion of all Fiedler matrices with respect the Frobenius norm, i.e., . This allows us to get a very simple criterion for ordering all Fiedler matrices according to increasing condition numbers and to provide lower and upper bounds on the ratio of the condition numbers of any pair of Fiedler matrices. These results establish that if , then the Frobenius companion matrices have the largest condition number among all Fiedler matrices of p(z), and that if , then the Frobenius companion matrices have the smallest condition number. We also provide families of polynomials where the ratio of the condition numbers of pairs of Fiedler matrices can be arbitrarily large and prove that this can only happen when both Fiedler matrices are very ill-conditioned. We finally study some properties of the singular values of Fiedler matrices and determine how many of the singular values of a Fiedler matrix are equal to one. [Copyright &y& Elsevier]

Abstract: This paper introduces the notions of approximate and optimal approximate zero polynomial of a polynomial matrix by deploying recent results on the approximate GCD of a set of polynomials Karcaniaset al. (2006) 1 and the exterior algebra Karcanias and Giannakopoulos (1984) 4 representation of polynomial matrices. The results provide a new definition for the “approximate”, or “almost” zeros of polynomial matrices and provide the means for computing the distance from non-coprimeness of a polynomial matrix. The computational framework is expressed as a distance problem in a projective space. The general framework defined for polynomial matrices provides a new characterization of approximate zeros and decoupling zeros Karcanias et al. (1983) 2 and Karcanias and Giannakopoulos (1984) 4 of linear systems and a process leading to computation of their optimal versions. The use of restriction pencils provides the means for defining the distance of state feedback (output injection) orbits from uncontrollable (unobservable) families of systems, as well as the invariant versions of the “approximate decoupling polynomials”. The overall framework that is introduced provides the means for introducing measures for the distance of a system from different families of uncontrollable, or unobservable systems, which may be feedback dependent, or feedback invariant as well as the notion of “approximate decoupling polynomials”. [Copyright &y& Elsevier]

Abstract: Crouzeix’s conjecture is that for any square matrix A and any polynomial p we havewhere is the field of values of A and denotes the spectral norm. In this paper, we show that the conjecture holds for the matrices of the formwhere and . [Copyright &y& Elsevier]

Abstract: An investigation is made of the Krylov matrices associated to the companion matrix C of a monic polynomial of degree . In this paper, we propose a new approach to the study of Hankel matrices as Krylov matrices of . Firstly we focus on algebraic structures of Krylov matrices of C over a field . We then discuss an equivalent condition for the Hankel matrix to be a Krylov matrix of by the notion of compatibility. As a result, we derive new determinant formulas for such Hankel matrices in terms of eigenvalues and eigenvectors of C respectively. [Copyright &y& Elsevier]

Abstract: Let G σ be an oriented graph obtained by assigning an orientation σ to the edge set of a simple undirected graph G such that G σ becomes a directed graph. Let S(G σ ) be the skew adjacency matrix of G σ . The skew energy of G σ is defined as the sum of the absolute values of all eigenvalues of S(G σ ). In this paper, we provide a new method to compare the skew energies of two oriented graphs whose skew characteristic polynomials satisfy a given recurrence relation and determine the oriented unicyclic graphs of order n with the first largest skew energies for . [Copyright &y& Elsevier]

Abstract: Let be the characteristic polynomial of the signless Laplacian matrix of a graph G. Due to the nice properties of the signless Laplacian matrix, , in comparison with the other matrices related to graphs, -ordering, an ordering based on the coefficients of the signless Laplacian characteristic polynomial, is of interest. In this paper, using graph transformations, we establish some relations between the graph structure and its coefficients of the signless Laplacian characteristic polynomial. So, we express some results about -ordering of graphs, focusing our attention to the unicyclic graphs. Finally, as an application of these results, we discuss the ordering of graphs based on their incidence energy. [Copyright &y& Elsevier]

Abstract: The development of new classes of linearizations of square matrix polynomials that generalize the classical first and second Frobenius companion forms has attracted much attention in the last decade. Research in this area has two main goals: finding linearizations that retain whatever structure the original polynomial might possess, and improving properties that are essential for accurate numerical computation, such as eigenvalue condition numbers and backward errors. However, all recent progress on linearizations has been restricted to square matrix polynomials. Since rectangular polynomials arise in many applications, it is natural to investigate if the new classes of linearizations can be extended to rectangular polynomials. In this paper, the family of Fiedler linearizations is extended from square to rectangular matrix polynomials, and it is shown that minimal indices and bases of polynomials can be recovered from those of any linearization in this class via the same simple procedures developed previously for square polynomials. Fiedler linearizations are one of the most important classes of linearizations introduced in recent years, but their generalization to rectangular polynomials is nontrivial, and requires a completely different approach to the one used in the square case. To the best of our knowledge, this is the first class of new linearizations that has been generalized to rectangular polynomials. [Copyright &y& Elsevier]

Abstract: We say that the product of a row vector and a column vector is intrinsic if there is at most one non-zero product of corresponding coordinates. Analogously we speak about intrinsic product of two or more matrices, as well as about intrinsic factorizations of matrices. Since all entries of the intrinsic product are products of entries of the multiplied matrices, there is no addition. The class of complementary basic matrices (CB-matrices) was recently introduced as matrices, if of order n, , where is a permutation of and the matrices , have the formfor some matrices . It was observed that (1). independently of the permutation, all such matrices with given ’s have the same spectrum (though they do not form a similarity class), (2) the classical companion matrix belongs to the class of CB-matrices, (3) the multiplication of the ’s is intrinsic. Connections between the matrices and the resulting CB-matrix have been explored, in particular, the properties which are inherited from the to the . Two situations were considered, for the ordinary real CB-matrices and for the corresponding sign pattern matrices. In this paper, we consider generalized complementary basic matrices, where the matrices are replaced by square matrices of arbitrary sizes. Some interesting facts and results about the permanents and permanental polynomials of such matrices are obtained. [Copyright &y& Elsevier]

Abstract: Let A be n × n matrix of rank r. Then x n−r divides the characteristic polynomial det(xI − A) of A in the ring of polynomials in x over the complex field . Let δ A (x)= x r−n det(xI − A). Then δ A (A)A = O (Segercrantz (1992) ). Let A, B be n × n matrices of rank r and s respectively. If AB = BA, then x n−s y n−r divides the polynomial det(xA − yB) in the ring of polynomials in x, y over the complex field. Let δ A,B (x, y)= x s−n y r−n det(xI − A). In this paper, we prove that δ A,B (B, A)AB = O under these conditions. [Copyright &y& Elsevier]

Abstract: Let be a graph of order and the Laplacian characteristic polynomial of . Zhou and Gutman proved that among all trees of order , the th coefficient is largest when the tree is a path and is smallest for a star. In this paper, for two given positive integers and , we characterize the trees with a given bipartition which have the minimal and second minimal Laplacian coefficients. [Copyright &y& Elsevier]

Abstract: Let be the lollipop graph obtained by appending a g-cycle to a pendant vertex of a path on vertices. In 2002, Fallat, Kirkland and Pati proved that for and , . In this paper, we prove that for , for all n, where is the algebraic connectivity of . [Copyright &y& Elsevier]

Abstract: In this paper, the notion of Birkhoff–James approximate orthogonality sets is introduced for rectangular matrices and matrix polynomials. The proposed definition yields a natural generalization of standard numerical range and q-numerical range (and also of recent extensions), sharing with them several geometric properties. [Copyright &y& Elsevier]

Abstract: In this paper, we first consider the problem of determining the robust positivity of a real function as the real vector varies over a box . We show that, it is sufficient to check a finite number of specially constructed points. This is accomplished by using some results on sign-definite decomposition. We then apply this result to determine the robust Hurwitz stability of a family of complex polynomials whose coefficients are polynomial functions of the parameters of interest. We develop an eight polynomial vertex stability test that is a sufficient condition of Hurwitz stability of the family. This test reduces to Kharitonov’s well known result for the special case where the parameters are just the polynomial coefficients. In this case, the result is tight. This test can be recursively and modularly used to construct an approximation of arbitrary accuracy to the actual stabilizing set. The result is illustrated by examples. [Copyright &y& Elsevier]

Abstract: For a simple graph , let denote the complement of relative to the complete graph and let where denotes the adjacency matrix of . The complete product of two simple graphs and is the graph obtained from and by joining every vertex of to every vertex of . In is represented in terms of , , and . In this paper we extend the notion of complete product of simple graphs to that of generalized complete product of matrices and obtain their characteristic polynomials. [ABSTRACT FROM AUTHOR]

Abstract: A family of square matrices of the same order is called a quasi-commuting family if for all where need not be distinct. Let , be polynomials in the indeterminates with coefficients in the complex field , and let be matrices over which are not necessarily distinct. Let and let . In this paper, we prove that, for matrices over , if is a quasi-commuting family, then implies that . [ABSTRACT FROM AUTHOR]

Abstract: The paper presents an algebraic approach, using polynomial and rational models over an arbitrary field, to tangential interpolation problems, both by polynomial as well as rational matrix functions. Appropriate extensions of scalar problems, associated with the names of Lagrange (first order), Hermite (high order) and Newton (recursive) are derived. The relation of interpolation problems to the matrix Chinese remainder theorem are clarified. Some two sided interpolation problems are discussed, using the theory of tensored functional models. [ABSTRACT FROM AUTHOR]

Abstract: This paper applies the theory of tensor products of functional models to the study of the Stein equation. We analyse the connections between the Sylvester and Stein equations, as well as those between the Anderson–Jury Bezoutian associated with the polynomial Sylvester equation and the -Bezoutian associated with the homogeneous polynomial Stein equation. The functional setting allows us to extend the theory of finite section Toeplitz matrices and their inversion. [Copyright &y& Elsevier]

Abstract: The spectral excess theorem provides a quasi-spectral characterization for a (regular) graph with distinct eigenvalues to be distance-regular graph, in terms of the excess (number of vertices at distance ) of each of its vertices. The original approach, due to Fiol and Garriga in 1997, was obtained by using a local approach, so giving a characterization of the so-called pseudo-distance-regularity around a vertex. In this paper we present a new simple projection method based in a global point of view, and where the mean excess plays an essential role. [Copyright &y& Elsevier]

Abstract: The theme of the present paper is to introduce and study two different versions of tensor products of functional models, one over the underlying field and the other over the corresponding algebra of polynomials, as well as related models based on the Kronecker product of polynomial matrices. In the process, we study the Sylvester equation and its reduction to a polynomial matrix equation. We analyse the relation between the two tensor products and use this to elucidate the role of the Anderson-Jury generalized Bezoutians in this context. [Copyright &y& Elsevier]

Abstract: Let denote a field and let denote a vector space over with finite positive dimension. We consider a pair of linear transformations and that satisfy the following conditions: (i) each of is diagonalizable; (ii) there exists an ordering of the eigenspaces of such that for , where and ; (iii) there exists an ordering of the eigenspaces of such that for , where and ; (iv) there is no subspace of such that , , , . We call such a pair a tridiagonal pair on . It is known that and for the dimensions of , , , coincide; we denote this common dimension by . In this paper we prove that for . It is already known that if is algebraically closed. [Copyright &y& Elsevier]

Abstract: Thirty years ago, G. N. de Oliveira has proposed the following completion problems: Describe the possible characteristic polynomials of , where and are square submatrices, when some of the blocks are fixed and the others vary. Several of these problems remain unsolved. This paper gives the solution, over the field of real numbers, of Oliveira’s problem where the blocks are fixed and the others vary. [Copyright &y& Elsevier]

Abstract: In this paper, we shall follow a companion matrix approach to study the relationship between zeros of a wide range of pairs of complex polynomials, for example, a polynomial and its polar derivative or Sz.-Nagy’s generalized derivative. We shall introduce some new companion matrices and obtain a generalization of the Weinstein–Aronszajn Formula which will then be used to prove some inequalities similar to Sendov conjecture and Schoenberg conjecture and to study the distribution of equilibrium points of logarithmic potentials for finitely many discrete charges. Our method can also be used to produce, in an easy and systematic way, a lot of identities relating the sums of powers of zeros of a polynomial to that of the other polynomial. [Copyright &y& Elsevier]

Abstract: In this paper, we characterize symmetric Sobolev bilinear forms defined on , where is the space of polynomials. More specifically we show that symmetric Sobolev bilinear forms, like symmetric matrices, can be re-written with a diagonal representation. As an application, we introduce the notion of a ghost matrix, extending some classic work of Stieltjes. [Copyright &y& Elsevier]

Abstract: Throughout the last decades, several results have been published in the area of the so-called Matrix Completion Problems. In this paper, we survey several results in this field. In particular, we describe the possible eigenvalues, the characteristic polynomial, the invariant polynomials, or the number of nontrivial invariant polynomials of a square matrix, over a field, when some of its entries are prescribed and the others vary. Finally, we present our contribution, generalizing some of the previous cases, to an matrix partitioned into blocks, with entries in a field, when some of its blocks are prescribed and the others vary. [Copyright &y& Elsevier]

Abstract: It is well-known that when a polynomial whose coefficients are continuous functions of a parameter loses its degree then some of its zeros must vanish at infinity. In this paper, we consider such a situation: we examine how roots of a complex polynomial tend to infinity as some of its coefficients, including the leading one, tend to zero. We show, among other things, that in such a situation the unbounded paths traced by the roots of the polynomial have asymptotes; we also obtain their formulas. Some examples are presented to complete and illustrate the results. [Copyright &y& Elsevier]

Abstract: The linear complementarity problem whose defining feature is the extended -step property is known to be solvable in polynomial time. This paper focuses on the investigation of the subclass of -matrices that possess this particular property. We present a necessary condition and a (separate) sufficient condition for membership in the class. It is shown that each of the conditions defines a set of matrices that properly contains the (transposed) hidden Minkowski set, thus generalizing previous work developed in Ref. [J.-S. Pang, R. Chandrasekaran, Linear complementarity problems solvable by a polynomially bounded pivoting algorithm, Math. Program. Study 25 (1985) 13–27] and in Ref. [W.D. Morris, Jr., J. Lawrence, Geometric properties of hidden Minkowski matrices, SIAM J. Matrix Anal. Appl. 10 (1989) 229–232]. To prove the necessity result we use a matrix-analytical approach instead of a geometric argument as in the previous case. To prove the sufficiency result we first establish two characterizations of singular irreducible -matrices. [Copyright &y& Elsevier]

Abstract: In this paper, an extension of the Hermite matrix polynomials is introduced. Some relevant matrix functions appear in terms of the two-variable Hermite matrix polynomials. Furthermore, in order to give qualitative properties of this family of matrix polynomials, the Chebyshev matrix polynomials of the second kind are introduced. [Copyright &y& Elsevier]

Abstract: In this paper we investigate the polynomial identities of an important subalgebra of the PI-algebra UT 3 of 3×3 upper triangular matrices in characteristic zero. Moreover we prove that the five algebras which were used in Giambruno and La Mattina [A. Giambruno, D. La Mattina, PI-algebras with slow codimension growth, J. Algebra 284 (2005) 371–391] to classify (up to PI-equivalence) the algebras whose sequence of codimensions is bounded by a linear function generate the only five minimal varieties of quadratic growth. [Copyright &y& Elsevier]

Abstract: This paper deals with the zeros of polynomials generated by a certain three term recurrence relation. The main objective is to find bounds, in terms of the coefficients of the recurrence relation, for the regions where the zeros are located. In most part, the zeros are explored through an Eigenvalue representation associated with a corresponding Hessenberg matrix. Applications to Szegö polynomials, para-orthogonal polynomials and polynomials with non-zero complex coefficients are considered. [Copyright &y& Elsevier]

Abstract: Let be any field and let B a matrix of . Zaballa found necessary and sufficient conditions for the existence of a matrix with prescribed similarity class and such that . In an earlier paper [A. Borobia, R. Canogar, Constructing matrices with prescribed off-diagonal submatrix and invariant polynomials, Linear Algebra Appl. 424 (2007) 615–633] we obtained, for fields of characteristic different from 2, a finite step algorithm to construct A when it exists. In this short note we extend the algorithm to any field. [Copyright &y& Elsevier]