Smith meets Smith: Smith normal form of Smith matrix

In 1861, Henry John Stephen Smith [H.J.S. Smith, On systems of linear indeterminate equations and congruences, Philos. Trans. Royal Soc. London. 151 (1861), pp. 293–326] published famous results concerning solving systems of linear equations. The research on Smith normal form and its applications started and continues. In 1876, Smith [H.J.S. Smith, On the value of a certain arithmetical determinant, Proc. London Math. Soc. 7 (1875/76), pp. 208–212] calculated the determinant of the n?×?n matrix ((i,?j)), having the greatest common divisor (GCD) of i and j as its ij entry. Since that, many results concerning the determinants and related topics of GCD matrices, LCM matrices, meet matrices and join matrices have been published in the literature. In this article these two important research branches developed by Smith, in 1861 and in 1876, meet for the first time. The main purpose of this article is to determine the Smith normal form of the Smith matrix ((i,?j)). We do this: we determine the Smith normal form of GCD matrices defined on factor closed sets.     

Jordan structures of alternating matrix polynomials

Alternating matrix polynomials, that is, polynomials whose coefficients alternate between symmetric and skew-symmetric matrices, generalize the notions of even and odd scalar polynomials. We investigate the Smith forms of alternating matrix polynomials, showing that each invariant factor is an even or odd scalar polynomial. Necessary and sufficient conditions are derived for a given Smith form to be that of an alternating matrix polynomial. These conditions allow a characterization of the possible Jordan structures of alternating matrix polynomials, and also lead to necessary and sufficient conditions for the existence of structure-preserving strong linearizations. Most of the results are applicable to singular as well as regular matrix polynomials.     

On the computation of the Smith normal form of compound matrices

Compound matrices are encountered in many fields such as Matrix Theory, Systems Theory, Control Theory, etc. In the present paper we develop an efficient algorithm computing the Smith normal form of compound matrices. This algorithm is based on a new theorem establishing an equivalence relation between the Smith normal form of the compounds of a given matrix and the compounds of the Smith normal form of the given matrix. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the reduction of a set of numerical matrices to quasi-diagonal form with one similarity transformation

We consider finite sets of numerical matrices and the polynomial matrices corresponding to them that have the Smith form diag (1, (x), ..., (x)). We solve the problem of reducing such sets to canonical form with one similarity transformation assuming that all the roots of the invariant polynomial (x) are simple.Translated fromMatematichni Metodi ta Fiziko-Mekhanichni Polya, Vol. 40, No. 4, 1997, pp. 101–105.     

Smith normal form of some distance matrices

We determine the Smith normal form of the distance matrices of unicyclic graphs and of the wheel graph with trees attached to each vertex.     

On Some “Tame” and “Wild” Aspects of the Problem of Semiscalar Equivalence of Polynomial Matrices

The problem of reducing polynomial matrices to canonical form by using semiscalar equivalent transformations is studied. This problem is wild as a whole. However, it is tame in some special cases. In the paper, classes of polynomial matrices are singled out for which canonical forms with respect to semiscalar equivalence are indicated. We use this tool to construct a canonical form for the families of coefficients corresponding to the polynomial matrices. This form enables one to solve the classification problem for families of numerical matrices up to similarity.     

Semiscalar equivalence and the factorization of polynomial matrices

One considers the problem of the factorization of polynomial matrices over an arbitrary field in connection with their reducibility by semiscalar equivalent transformations to triangular form with the invariant factors along the principal diagonal. In particular, one establishes a criterion for the representability of a polynomial matrix in the form of a product of factors (the first of which is unital), the product of the canonical diagonal forms of which is equal to the canonical diagonal form of the given matrix. There is given also a method for the construction of such factorizations.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 42, No. 5, pp. 644–649, May, 1990.     

The critical groups of the Peisert graphs

The critical group of a finite graph is an abelian group defined by the Smith normal form of the Laplacian. We determine the critical groups of the Peisert graphs, a certain family of strongly regular graphs similar to, but different from, the Paley graphs. It is further shown that the adjacency matrices of the two graphs defined over a field of order \(p^2\) with \(p\equiv 3\pmod 4\) are similar over the \(\ell \)-local integers for every prime \(\ell \). Consequently, each such pair of graphs provides an example where all the corresponding generalized adjacency matrices are both cospectral and equivalent in the sense of Smith normal form.     

A General Multiresolution Method for Fitting Functions on the Sphere

In [7], Lyche and Schumaker have described a method for fitting functions of class C ¹ on the sphere which is based on tensor products of quadratic polynomial splines and trigonometric splines of order three associated with uniform knots. In this paper, we present a multiresolution method leading to C ²-functions on the sphere, using tensor products of polynomial and trigonometric splines of odd order with arbitrary simple knot sequences. We determine the decomposition and reconstruction matrices corresponding to the polynomial and trigonometric spline spaces. We describe the general tensor product decomposition and reconstruction algorithms in matrix form which are convenient for the compression of surfaces. We give the different steps of the computer implementation of these algorithms and, finally, we present a test example.     

Quasidiagonal reduction of a class of polynomial matrices

We solve the problem of semiscalar equivalence of polynomial matrices to the Smith canonical form diag(1, (x), ..., (x)) from the condition that the polynomial (x) has simple roots.Translated fromMatematichni Metodi ta Fiziko-Mekhanichni Polya, Vol. 40, No. 3, 1997, pp. 7–12.     

The characteristic polynomial of a random permutation matrix at different points

We consider the logarithm of the characteristic polynomial of random permutation matrices, evaluated on a finite set of different points. The permutations are chosen with respect to the Ewens distribution on the symmetric group. We show that the behavior at different points is independent in the limit and are asymptotically normal. Our methods enable us to study also the wreath product of permutation matrices and diagonal matrices with i.i.d. entries and more general class functions on the symmetric group with a multiplicative structure.     

The multiplicativity of the smith normal form

The problem of multiplicativity of the Smith normal form of nonsingular matrices over a principal ideal rings is investigated.     

Strongly regular graphs and spin models for the Kauffman polynomial

We study spin models for invariants of links as defined by Jones [22]. We consider the two algebras generated by the weight matrices of such models under ordinary or Hadamard product and establish an isomorphism between them. When these algebras coincide they form the Bose-Mesner algebra of a formally self-dual association scheme. We study the special case of strongly regular graphs, which is associated to a particularly interesting link invariant, the Kauffman polynomial [27]. This leads to a classification of spin models for the Kauffman polynomial in terms of formally self-dual strongly regular graphs with strongly regular subconstituents [7]. In particular we obtain a new model based on the Higman-Sims graph [17].     

Inversion of polynomial and rational matrices

The inversion of polynomial and rational matrices is considered. For regular matrices, three algorithms for computing the inverse matrix in a factored form are proposed. For singular matrices, algorithms of constructing pseudoinverse matrices are considered. The algorithms of inversion of rational matrices are based on the minimal factorization which reduces the problem to the inversion of polynomial matrices. A class of special polynomial matrices is regarded whose inverse matrices are also polynomial matrices. Inversion algorithms are applied to the solution of systems with polynomial and rational matrices. Bibliography: 3 titles. Translated by V. N. Kublanovskaya. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 202, 1992, pp. 97–109.     

分块友矩阵的相似类

定义了与n次矩阵多项式A(λ)友矩阵CA相似的矩阵为A(λ)的(广义)友矩阵,通过将此友矩阵分解成一组特殊的分块矩阵乘积的方法得到了一类(广义)友矩阵.     

Effective partitioning method for computing generalized inverses and their gradients

We extend the algorithm for computing {1}, {1, 3}, {1, 4} inverses and their gradients from [11] to the set of multiple-variable rational and polynomial matrices. An improvement of this extension, appropriate to sparse polynomial matrices with relatively small number of nonzero coefficient matrices as well as in the case when the nonzero coefficient matrices are sparse, is introduced. For that purpose, we exploit two effective structures form [6], which make use of only nonzero addends in polynomial matrices, and define their partial derivatives. Symbolic computational package MATHEMATICA is used in the implementation. Several randomly generated test matrices are tested and the CPU times required by two used effective structures are compared and discussed.     

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.     

广义对角多项式指数和的估计

利用高斯和与次数矩阵Smith标准形的不变因子,给出了有限域上广义对角多项式指数和的估计,从而改进了Deligne-Weil型估计这类多项式指数和的结果.     

A compound matrix algorithm for the computation of the Smith form of a polynomial matrix

In the present paper is presented a numerical method for the exact reduction of a singlevariable polynomial matrix to its Smith form without finding roots and without applying unimodular transformations. Using the notion of compound matrices, the Smith canonical form of a polynomial matrixM(s)^nxn[s] is calculated directly from its definition, requiring only the construction of all thep-compound matricesC _p (M(s)) ofM(s), 1<pn. This technique produces a stable and accurate numerical algorithm working satisfactorily for any polynomial matrix of any degree.