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.     

Smith Normal Form and acyclic matrices

An approach, based on the Smith Normal Form, is introduced to study the spectra of symmetric matrices with a given graph. The approach serves well to explain how the path cover number (resp. diameter of a tree T) is related to the maximal multiplicity MaxMult(T) occurring for an eigenvalue of a symmetric matrix whose graph is T (resp. the minimal number q(T) of distinct eigenvalues over the symmetric matrices whose graphs are T). The approach is also applied to a more general class of connected graphs G, not necessarily trees, in order to establish a lower bound on q(G).     

On the divisibility of power LCM matrices by power GCD matrices

Let S = {x ₁, ..., x _n } be a set of n distinct positive integers and e ⩾ 1 an integer. Denote the n × n power GCD (resp. power LCM) matrix on S having the e-th power of the greatest common divisor (x _i , x _j ) (resp. the e-th power of the least common multiple [x _i , x _j ]) as the (i, j)-entry of the matrix by ((x _i , x _j ) ^e ) (resp. ([x _i , x _j ] ^e )). We call the set S an odd gcd closed (resp. odd lcm closed) set if every element in S is an odd number and (x _i , x _j ) ∈ S (resp. [x _i , x _j ] ∈ S) for all 1 ⩽ i, j ⩽ n. In studying the divisibility of the power LCM and power GCD matrices, Hong conjectured in 2004 that for any integer e ⩾ 1, the n × n power GCD matrix ((x _i , x _j ) ^e ) defined on an odd-gcd-closed (resp. odd-lcm-closed) set S divides the n × n power LCM matrix ([x _i , x _j ] ^e ) defined on S in the ring M _n (ℤ) of n × n matrices over integers. In this paper, we use Hong’s method developed in his previous papers [J. Algebra 218 (1999) 216–228; 281 (2004) 1–14, Acta Arith. 111 (2004), 165–177 and J. Number Theory 113 (2005), 1–9] to investigate Hong’s conjectures. We show that the conjectures of Hong are true for n ⩽ 3 but they are both not true for n ⩾ 4. Research is partially supported by Program for New Century Excellent Talents in University, by SRF for ROCS, SEM, China and by the Lady Davis Fellowship at the Technion, Israel Research is partially supported by a UGC (HK) grant 2160210 (2003/05).     

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.     

由Smith标准形求解矩阵方程∑AiXBi=C

By using the Smith normal form of polynomial matrix and algebraic methods, this paper discusses the solvability for the linear matrix equation ∑AiXBi = C over a field, and obtains the explicit formulas of general solution or unique solution.     

Distance matrices for points on a line,on a circle,and at the vertices of ann-dimensional cube

Forn pointsA _i ,i=1, 2, ...,n, in Euclidean space ℝ ^m , the distance matrix is defined as a matrix of the form D=(D _i ,j) _i ,j=1,...,n, where theD _i ,j are the distances between the pointsA _i andA _j . Two configurations of pointsA _i ,i=1, 2,...,n, are considered. These are the configurations of points all lying on a circle or on a line and of points at the vertices of anm-dimensional cube. In the first case, the inverse matrix is obtained in explicit form. In the second case, it is shown that the complete set of eigenvectors is composed of the columns of the Hadamard matrix of appropriate order. Using the fact that distance matrices in Euclidean space are nondegenerate, several inequalities are derived for solving the system of linear equations whose matrix is a given distance matrix. Translated fromMatematicheskie Zametki, Vol. 58, No. 1, pp. 127–138, July, 1995.     

Generalized equivalence of pairs of matrices

Pairs (A ₁ B ₁) and (A ₂ B ₂) of matrices over a principal ideal domain R are called the generalized equivalent pairs if A ₂=UA ₁ V ₁ B ₂=UB ₁ V ₂ for some invertible matrices U V ₁ V ₂ over R. A special form is established to which a pair of matrices can be reduced by means of generalized equivalent transformations. Besides necessary and sufficient conditions are found, under which a pair of matrices is generalized equivalent to a pair of diagonal matrices. Applications are made to study the divisibility of matrices and multiplicative property of the Smith normal form.     

Divisibility among power GCD matrices and among power LCM matrices on three coprime divisor chains

Let h be a positive integer and S?=?{x ₁,?…?,?x _h } be a set of h distinct positive integers. We say that the set S is a divisor chain if x _σ(1) ∣?…?∣ x _σ(h) for a permutation σ of {1,?…?,?h}. If the set S can be partitioned as S?=?S ₁?∪?S ₂?∪?S ₃, where S ₁, S ₂ and S ₃ are divisor chains and each element of S _i is coprime to each element of S _j for all 1?≤?i?<?j?≤?3, then we say that the set S consists of three coprime divisor chains. The matrix having the ath power (x _i , x _j ) ^a of the greatest common divisor of x _i and x _j as its i, j-entry is called the ath power greatest common divison (GCD) matrix on S, denoted by (S ^?a ). The ath power least common multiple (LCM) matrix [S ^?a ] can be defined similarly. In this article, let a and b be positive integers and let S consist of three coprime divisor chains with 1?∈?S. We show that if a?∣?b, then the ath power GCD matrix (S ^?a ) (resp., the ath power LCM matrix [S ^?a ]) divides the bth power GCD matrix (S ^?b ) (resp., the bth power LCM matrix [S ^?b ]) in the ring M _h (Z) of h?×?h matrices over integers. We also show that the ath power GCD matrix (S ^?a ) divides the bth power LCM matrix [S ^?b ] in the ring M _h (Z) if a?∣?b. However, if a???b, then such factorizations are not true. Our results extend Hong's and Tan's theorems and also provide further evidences to the conjectures of Hong raised in 2008.     

Properties of Some Character Tables Related to the Symmetric Groups

We determine invariants like the Smith normal form and the determinant for certain integral matrices which arise from the character tables of the symmetric groups S_n and their double covers. In particular, we give a simple computation, based on the theory of Hall-Littlewood symmetric functions, of the determinant of the regular character table _RC of S_n with respect to an integer r 2. This result had earlier been proved by Olsson in a longer and more indirect manner. As a consequence, we obtain a new proof of the Mathas Conjecture on the determinant of the Cartan matrix of the Iwahori-Hecke algebra. When r is prime we determine the Smith normal form of _RC. Taking r large yields the Smith normal form of the full character table of S_n. Analogous results are then given for spin characters.Partially supported by The Danish National Research Council.Partially supported by NSF grant #DMS-9988459.     

Matrices associated with arithmetical functions

Let f be an arithmetical function and S={x ₁,x ₂,…,x_n } a set of distinct positive integers. Denote by [f(x_i ,x_j }] the n×n matrix having f evaluated at the greatest common divisor (x_i ,x_j ) of x_i , and x_j as its i j-entry. We will determine conditions on f that will guarantee the matrix [f(x_i ,x_j )] is positive definite and, in fact, has properties similar to the greatest common divisor (GCD) matrix

[(x_i ,x_j )] where f is the identity function. The set S is gcd-closed if (x_i ,x_j )∈S for 1≤ i j ≤ n. If S is gcd-closed, we calculate the determinant and (if it is invertible) the inverse of the matrix [f(x_i ,x_j )]. Among the examples of determinants of this kind are H. J. S. Smith's determinant det[(i,j)].     

SMITH NORMAL FORMAL OF DISTANCE MATRIX OF BLOCK GRAPHS

A connected graph, whose blocks are all cliques (of possibly varying sizes), is called a { block graph.} Let D(G) be its distance matrix. In this note, we prove that the Smith normal form of D(G) is independent of the interconnection way of blocks and give an explicit expression for the Smith normal form in the case that all cliques have the same size, which generalize the results on determinants.     

Pfaffians and representations of the symmetric group

Pfaffians of matrices with entries z[i, j]/（xi ＋ xj）, or determinants of matrices with entries z[i, j]/（xi - xj）, where the antisymmetrical indeterminates z[i, j] satisfy the Pliicker relations, can be identified with a trace in an irreducible representation of a product of two symmetric groups. Using Young＇s orthogonal bases, one can write explicit expressions of such Pfaffians and determinants, and recover in particular the evaluation of Pfaffians which appeared in the recent literature.     

Differential Posets and Smith Normal Forms

We conjecture a strong property for the up and down maps U and D in an r-differential poset: DU + tI and UD + tI have Smith normal forms over . In particular, this would determine the integral structure of the maps U, D, UD, DU, including their ranks in any characteristic. As evidence, we prove the conjecture for the Young-Fibonacci lattice Y F studied by Okada and its r-differential generalizations Z(r), as well as verifying many of its consequences for Young’s lattice Y and the r-differential Cartesian products Y ^r .     

Skew-Hadamard Matrices and the Smith Normal Form

We show that the Smith normal form of every skew-Hadamard matrix of order 4m is diag[1,2,...,2, 2m,...,2m,4m]     

On the spectral norms of Cauchy–Toeplitz and Cauchy–Hankel matrices

In this study, we have found upper and lower bounds for the spectral norm of Cauchy–Toeplitz and Cauchy–Hankel matrices in the forms T_n=[1/(a+(i−j)b)]ⁿ_i,j=1, H_n=[1/(a+(i+j)b)]ⁿ_i,j=1.     

Properties of (0, 1)-matrices with no triangles

We study (0, 1)-matrices which contain no triangles (submatrices of order 3 with row and column sums 2) previously studied by Ryser. Let the row intersection of row i and row j of some matrix, when regarded as a vector, have a 1 in a given column if both row i and row j do and a zero otherwise. For matrices with no triangles, columns sums ?2, we find that the number of linearly independent row intersections is equal to the number of distinct columns. We then study the extremal (0, 1)-matrices with no triangles, column sums ?2, distinct columns, i.e., those of size mx(^m₂). The number of columns of column sum l is m ? l + 1 and they form a (l ? 1)-tree. The ((^m₂)) columns have a unique SDR of pairs of rows with 1's. Also, these matrices have a fascinating inductive buildup. We finish with an algorithm for constructing these matrices.     

A topological approach to divisibility of arithmetical functions and GCD matrices

Considering lower closed sets as closed sets on a preposet (P, ≤), we obtain an Alexandroff topology on P. Then order preserving functions are continuous functions. In this article we investigate order preserving properties (and thus continuity properties) of integer-valued arithmetical functions under the usual divisibility relation of integers and power GCD matrices under the divisibility relation of integer matrices.     

六元gcd封闭集上Smith矩阵的整除性

我们给出了关于六元gcd封闭集S的充分必要条件,使得在整数矩阵环M_6(Z)中,定义在S上的e次幂GCD矩阵(S~e)整除e次幂LCM矩阵[S~e].这部分解决了Hong在2002年提出的一个公开问题.     

On simultaneous reduction of families of matrices to triangular or diagonal form by unitary congruences

Let {A_i }and {B_i } be two given families of n-by-n matrices. We give conditions under which there is a unitary U such that every matrix UA_iU ¹ is upper triangular. We give conditions, weaker than the classical conditions of commutativity of the whole family, under which there is a unitary U such that every matrix UA_jU ^? is upper triangular. We also give conditions under which there is one single unitary U such that every UA_iU ¹ and every UB_jU ^? is upper triangular. We give necessary and sufficient conditions for simultaneous unitary reduction to diagonal form in this way when all the A_j's are complex symmetric and all theB_j 's are Hermitian.