Search

In this paper we introduce a new Jacobi–Davidson type eigenvalue solver for a set of commuting matrices, called JDCOMM, used for the global optimization of so-called Minkowski-norm dominated polynomials in several variables. The Stetter–Möller matrix method yields such a set of real non-symmetric commuting matrices since it reformulates the optimization problem as an eigenvalue problem. A drawback of this approach is that the matrix most relevant for computing the global optimum of the polynomial under investigation is usually large and only moderately sparse. However, the other matrices are generally much sparser and have the same eigenvectors because of the commutativity. This fact is used to design the JDCOMM method for this problem: the most relevant matrix is used only in the outer loop and the sparser matrices are exploited in the solution of the correction equation in the inner loop to greatly improve the efficiency of the method. Some numerical examples demonstrate that the method proposed in this paper is more efficient than approaches that work on the main matrix (standard Jacobi–Davidson and implicitly restarted Arnoldi), as well as conventional solvers for computing the global optimum, i.e., SOSTOOLS, GloptiPoly, and PHCpack. Keywords: Multivariate polynomial optimization; Global optimization; Solving systems of polynomial equations; Stetter–Möller matrix method; Commuting matrices; Jacobi–Davidson; Correction equation; Arnoldi method

Let T be a tree with n vertices and let D be the distance matrix of T. According to a classical result due to Graham and Pollack, the determinant of D is a function of n, but does not depend on T. We allow the edges of T to carry weights, which are square matrices of a fixed order. The distance matrix D of T is then defined in a natural way. We obtain a formula for the determinant of D, which involves only the determinants of the sum and the product of the weight matrices.

Let A ( R , S ) denote the class of all (0, 1)-matrices with row sum vector R and column sum vector S. Continuing an earlier investigation of the Bruhat order and secondary Bruhat order (both of which extend the classical Bruhat order on permutations of {1, 2, … , n}) on A ( R , S ) , we provide a counterexample to a conjecture of Brualdi and Hwang which shows that these two orders are not in general the same. We characterize the cover relation for the secondary Bruhat order. We also study in more detail certain classes A ( R , S ) where R = S = (k, k, … , k), a constant vector. We show that for k = 2 the Bruhat order and secondary Bruhat order are the same, but this is not always so when k = 3.

In this paper, we discuss the complete positivity of n × n , n ⩾ 5 , house matrices, i.e., doubly nonnegative matrices whose graph is a cycle 1 , 2 , … , n with a chord between vertices 1 and 3. We describe the set of all possible supports of the columns of a nonnegative matrix B,such that A = BB T ; show that the cp-rank of a completely positive house matrix is at least n - 1 ; give a complete characterization of the singular completely positive house matrices; show that their cp-rank is n - 1 or n and characterize each case.

We prove a result concerning the evaluation of determinant of a matrix, whose entries are given by certain linear inhomogeneous recurrence relations. This result generalizes previous determinants evaluations due to Krattenthaler, Neuwirth and the authors in [C. Krattenthaler, Evaluations of some determinants of matrices related to the Pascal triangle, Sem. Lothar. Combin. 47 (2002), 19, Article B47g; E. Neuwirth, Treeway Galton arrays and generalized Pascal-like determinants, Technical Report, University of Vienna, 2004, pp. 1–16; A.R. Moghaddamfar, S.M.H. Pooya, S. Navid Salehy, S. Nima Salehy, Evaluating and generalizing certain determinants, submitted for publication]. The main tool for proving our result is LU-factorization of the recursive arrays introduced in [C. Krattenthaler, Advanced determinant calculus: a complement, Linear Algebra Appl. 411 (2005) 68–166].

A large part of statistics is devoted to the estimation of models from the sample covariance matrix. The development of the statistical theory and estimators has been greatly facilitated by the introduction of special matrices, such as the commutation matrix and the duplication matrix, and the corresponding matrix algebra. Some more extensive models require, however, estimation based on higher order moments, typically third- and fourth-order moments. An example is the popular Kenny-Judd model that includes interactions between latent variables. This paper introduces some special matrices that can be used to simplify the model expressions for third-, fourth-, and higher order moments, gives some relationships between these matrices and related matrices, and gives some formulas for Kronecker products of three and four matrices. The theory is applied to derive convenient expressions for third- and fourth-order moments of some structural equation models. (c) 2005 Elsevier Inc. All rights reserved.

We consider matrices containing two diagonal bands of positive entries. We show that all eigenvalues of such matrices are of the form r ζ , where r is a nonnegative real number and ζ is a p th root of unity, where p is the period of the matrix, which is computed from the distance between the bands. We also present a problem in the asymptotics of spectra in which such double band matrices are perturbed by banded matrices.

Let H be a subgroup of the symmetric group S n and χ an irreducible character of H . In this paper we give conditions that characterize matrices that leave invariant the value of a given generalized matrix function on the set of upper triangular matrices. In some cases we describe completely these matrices.

The convex cone of n × n completely positive (CP) matrices and its dual cone of copositive matrices arise in several areas of applied mathematics, including optimization. Every CP matrix is doubly nonnegative (DNN), i.e., positive semidefinite and component-wise nonnegative, and it is known that, for n ⩽ 4 only, every DNN matrix is CP. In this paper, we investigate the difference between 5 × 5 DNN and CP matrices. Defining a bad matrix to be one which is DNN but not CP, we: (i) design a finite procedure to decompose any n × n DNN matrix into the sum of a CP matrix and a bad matrix, which itself cannot be further decomposed; (ii) show that every bad 5 × 5 DNN matrix is the sum of a CP matrix and a single bad extreme matrix; and (iii) demonstrate how to separate bad extreme matrices from the cone of 5 × 5 CP matrices.

We study the irregularity of hypergeometric D-modules $\mathcal{M}_A (\beta )$ via the explicit construction of Gevrey series solutions along coordinate subspaces in $X =\mathbb{C}^n$. As a consequence, we prove that along coordinate hyperplanes the combinatorial characterization of the slopes of $\mathcal{M}_A (\beta)$ given by M. Schulze and U. Walther in [21] still holds without any assumption on the matrix A. We also provide a lower bound for the dimensions of the spaces of Gevrey solutions along coordinate subspaces in terms of volumes of polytopes and prove the equality for very generic parameters. Holomorphic solutions outside the singular locus of $\mathcal{M}_A (\beta)$ can be understood as Gevrey solutions of order one along X at generic points and so they are included as a particular case., Comment: 41 pages; references, Remark 7.2. and 4 figures added; some comments changed; corrected typos

In this paper we investigate the L"2-solutions of vector refinement equations with exponentially decaying masks and a general dilation matrix. A vector refinement equation with a general dilation matrix and exponentially decaying masks is of the [email protected](x)[email protected][email protected]@?Z^sa(@a)@f([email protected]),[email protected]?R^s,where the vector of functions @f=(@f"1,...,@f"r)^T is in (L"2(R^s))^r,[email protected]?(a(@a))"@a"@?"Z"^"s is an exponentially decaying sequence of rxr matrices called refinement mask and M is an sxs integer matrix such that lim"n"->"~M^-^n=0. Associated with the mask a and dilation matrix M is a linear operator Q"a on (L"2(R^s))^r given byQ"af(x)@[email protected][email protected]@?Z^sa(@a)f([email protected]),[email protected]?R^s,f=(f"1,...,f"r)^[email protected]?(L"2(R^s))^r.The iterative scheme (Q"a^nf)"n"="1","2","...", is called vector subdivision scheme or vector cascade algorithm. The purpose of this paper is to provide a necessary and sufficient condition to guarantee the sequence (Q"a^nf)"n"="1","2","... to converge in L"2-norm. As an application, we also characterize biorthogonal multiple refinable functions, which extends some main results in [B. Han, R.Q. Jia, Characterization of Riesz bases of wavelets generated from multiresolution analysis, Appl. Comput. Harmon. Anal., to appear] and [R.Q. Jia, Convergence of vector subdivision schemes and construction of biorthogonal multiple wavelets, Advances in Wavelet (Hong Kong, 1997), Springer, Singapore, 1998, pp. 199-227] to the general setting.

In this paper, it is shown that the necessary and sufficient conditions on the Jordan form of a seminonnegative matrix, identified by Zaslavsky and McDonald, are in fact necessary and sufficient conditions on the Jordan form of every eventually nonnegative matrix. Thus every eventually nonnegative matrix is similar to a seminonnegative matrix. In [Linear Algebra Appl. 372 (2003) 253], they show that several of the combinatorial properties of reducible nonnegative matrices carry over to reducible seminonnegative matrices. In this paper it is shown that a property on the index of cyclicity of an irreducible nonnegative matrix carries over to the seminonnegative matrices.

For a class X of real matrices, a list of positions in an n×n matrix (a pattern) is said to have X-completion if every partial X-matrix that specifies exactly these positions can be completed to an X-matrix. If X and X0 are classes that satisfy the conditions any partial X-matrix is a partial X0-matrix, for any X0-matrix A and e>0, A+eI is a X-matrix, and for any partial X-matrix A, there exists δ>0 such that A−δ I is a partial X-matrix (where Ĩ is the partial identity matrix specifying the same pattern as A) then any pattern that has X0-completion must also have X-completion. However, there are usually patterns that have X-completion that fail to have X0-completion. This result applies to many pairs of subclasses of P- and P0-matrices defined by the same restriction on entries, including the classes P/P0-matrices, (weakly) sign-symmetric P/P0-matrices, and non-negative P/P0-matrices. It also applies to other related pairs of subclasses of P0-matrices, such as the pairs classes of P/P0,1-matrices, (weakly) sign-symmetric P/P0,1-matrices and non-negative P/P0,1-matrices. Furthermore, any pattern that has (weakly sign-symmetric, sign-symmetric, non-negative) P0-completion must also have (weakly sign-symmetric, sign-symmetric, non-negative) P0,1-completion, although these pairs of classes do not satisfy condition (3). Similarly, the class of inverse M-matrices and its topological closure do not satisfy condition (3), but the conclusion remains true, and the matrix completion problem for the topological closure of the class of inverse M-matrices is solved for patterns containing the diagonal.

An integer matrix A∈Md(Z) induces a covering σA of Td and an endomorphism αA:f↦f∘σA of C(Td) for which there is a natural transfer operator L. In this paper, we compute the KMS states on the Exel crossed product C(Td)⋊αA,LN and its Toeplitz extension. We find that C(Td)⋊αA,LN has a unique KMS state, which has inverse temperature β=log|detA|. Its Toeplitz extension, on the other hand, exhibits a phase transition at β=log|detA|, and for larger β the simplex of KMSβ states is isomorphic to the simplex of probability measures on Td.

For a given nonderogatory matrix A, formulas are given for functions of A in terms of Krylov matrices of A. Relations between the coefficients of a polynomial of A and the generating vector of a Krylov matrix of A are provided. With the formulas, linear transformations between Krylov matrices and functions of A are introduced, and associated algebraic properties are derived. Hessenberg reduction forms are revisited equipped with appropriate inner products and related properties and matrix factorizations are given.

Fiedler proved in [Linear Algebra Appl. 2 (1969) 191–197] that the set of real n-by-n symmetric matrices A such that rank(A + D) ⩾ n − 1 for every real diagonal matrix D is the set of matrices PTPT where P is a permutation matrix and T an irreducible tridiagonal matrix. We show that this result remains valid for arbitrary fields with some exceptions for 5-by-5 matrices over Z 3 .

Let T be an unweighted rooted tree of k levels such that in each level the vertices have equal degree. Let dk−j+1 denotes the degree of the vertices in the level j. We find the eigenvalues of the adjacency matrix and of the Laplacian matrix of T . They are the eigenvalues of principal submatrices of two nonnegative symmetric tridiagonal matrices of order k × k. The codiagonal entries for both matrices are d j - 1 , 2 ⩽ j ⩽ k - 1 , and d k , while the diagonal entries are zeros, in the case of the adjacency matrix, and dj, 1 ⩽ j ⩽k, in the case of the Laplacian matrix. Moreover, we give some results concerning to the multiplicity of the above mentioned eigenvalues.

A square complex matrix A is said to be EP if A and its conjugate transpose A ∗ have the same range. In this paper, we first collect a group of known characterizations of EP matrix, and give some new characterizations of EP matrices. Then, we define weighted-EP matrix, and present a wealth of characterizations for weighted-EP matrix through various rank formulas for matrices and their generalized inverses.

We introduce in this paper a method to calculate the Hessenberg matrix of a sum of measures from the Hessenberg matrices of the component measures. Our method extends the spectral techniques used by G. Mantica to calculate the Jacobi matrix associated with a sum of measures from the Jacobi matrices of each of the measures. We apply this method to approximate the Hessenberg matrix associated with a self-similar measure and compare it with the result obtained by a former method for self-similar measures which uses a fixed point theorem for moment matrices. Results are given for a series of classical examples of self-similar measures. Finally, we also apply the method introduced in this paper to some examples of sums of (not self-similar) measures obtaining the exact value of the sections of the Hessenberg matrix.

Let D(m,n) be the set of all the integer points in the m-dilate of the Birkhoff polytope of doubly-stochastic n by n matrices. In this paper we find the sharp upper bound on the tropical determinant over the set D(m,n). We define a version of the tropical determinant where the maximum over all the transversals in a matrix is replaced with the minimum and then find the sharp lower bound on thus defined tropical determinant over D(m,n)., Comment: 18 pages

Let A : R d → R d , d ⩾ 1 , be an expansive linear map. The notion of A -approximate continuity was recently used to give a characterization of scaling functions in a multiresolution analysis (MRA). The definition of A -approximate continuity at a point x – or, equivalently, the definition of the family of sets having x as point of A -density – depend on the expansive linear map A . The aim of the present paper is to characterize those self-adjoint expansive linear maps A 1 , A 2 : R d → R d for which the respective concepts of A μ -approximate continuity ( μ = 1 , 2 ) coincide. These we apply to analyze the equivalence among dilation matrices for a construction of systems of MRA. In particular, we give a full description for the equivalence class of the dyadic dilation matrix among all self-adjoint expansive maps. If the so-called “four exponentials conjecture” of algebraic number theory holds true, then a similar full description follows even for general self-adjoint expansive linear maps, too.

It is shown that an arbitrary m × n positive matrix can be written as a sum of at most min { m , n } totally positive matrices, and that this is in general the best possible value for the number of summands. Sufficient conditions are given under which fewer than min { m , n } totally positive summands are needed.

The self-affine measure μM,D corresponding to an expanding integer matrixM=[abcd]andD={(00),(10),(01)} is supported on the attractor (or invariant set) of the iterated function system {ϕd(x)=M−1(x+d)}d∈D. In the present paper we show that if (a+d)2=4(ad−bc) and ad−bc is not a multiple of 3, then there exist at most 3 mutually orthogonal exponential functions in L2(μM,D), and the number 3 is the best. This extends several known results on the non-spectral self-affine measure problem. The proof of such result depends on the characterization of the zero set of the Fourier transform μˆM,D, and provides a way of dealing with the non-spectral problem.

We study recently meet matrices on meet-semilattices as an abstract generalization of greatest common divisor (GCD) matrices. Analogously, in this paper we consider join matrices on lattices as an abstract generalization of least common multiple (LCM) matrices. A formula for the determinant of join matrices on join-closed sets, bounds for the determinant of join matrices on all sets and a formula for the inverse of join matrices on join-closed sets are given. The concept of a semi-multiplicative function gives us formulae for meet matrices on join-closed sets and join matrices on meet-closed sets. Finally, we show what new the study of meet and join matrices contributes to the usual GCD and LCM matrices.

An oriented hypergraph is a hypergraph where each vertex-edge incidence is given a label of + 1 or - 1 . We define the adjacency, incidence and Laplacian matrices of an oriented hypergraph and study each of them. We extend several matrix results known for graphs and signed graphs to oriented hypergraphs. New matrix results that are not direct generalizations are also presented. Finally, we study a new family of matrices that contains walk information.

We present a new approach to study inversion and factorization properties of confluent Cauchy matrices. We consider a class of generalized Vandermonde matrices, called Lagrange matrices, that are connected in a simple way with the Cauchy matrices. We apply the methods introduced in [Adv. Appl. Math. 10 (1989) 348] to obtain inversion and factorization theorems for Lagrange matrices and their confluent forms, and then derive corresponding results for Cauchy matrices.A Lagrange matrix V is associated with a pair of vectors (x0,x1,…,xn) and (y0,y1,…,yn). V is the matrix representation of the substitution operator that sends the vector (p(x0),p(x1),…,p(xn))T to the vector (p(y0),p(y1),…,p(yn))T, for any polynomial p of degree at most n.

D. Gale, in 1957 and H.J. Ryser, in 1963, independently proved the famous Gale–Ryser theorem on the existence of (0, 1)–matrices with prescribed row and column sums. Around the same time, in 1968, Mirsky solved the more general problem of finding conditions for the existence of a nonnegative integral matrix with entries less than or equal to p and prescribed row and column sums. Using the results of Mirsky, Brualdi shows that a modified version of the domination condition of Gale–Ryser is still necessary and sufficient for the existence of a matrix under the same constraints. In this article we prove another extension of Gale–Ryser’s domination condition. Furthermore we present a method to build nonnegative integral matrices with entries less than or equal to p and prescribed row and column sums.

The self-affine measure μ M , D associated with an affine iterated function system { ϕ d ( x ) = M − 1 ( x + d ) } d ∈ D is uniquely determined. The problems of determining the spectrality or non-spectrality of a measure μ M , D have been received much attention in recent years. One of the non-spectral problem on μ M , D is to estimate the number of orthogonal exponentials in L 2 ( μ M , D ) and to find them. In the present paper we show that for an expanding integer matrix M ∈ M 2 ( Z ) and the three-elements digit set D given by M = [ a b d c ] and D = { ( 0 0 ) , ( 1 0 ) , ( 0 1 ) } , if a c − b d ∉ 3 Z , then there exist at most 3 mutually orthogonal exponentials in L 2 ( μ M , D ) , and the number 3 is the best. This confirms the three-elements digit set conjecture on the non-spectrality of self-affine measures in the plane

We consider distance matrices of certain graphs and of points chosen in a rectangular grid. Formulae for the inverse and the determinant of the distance matrix of a weighted tree are obtained. Results concerning the inertia and the determinant of the distance matrix of an unweighted unicyclic graph are proved. If D is the distance matrix of a tree, then we obtain certain results for a perturbation of D−1. As an example, it is shown that if L∼ is the Laplacian matrix of an arbitrary connected graph, then D-1-L∼-1 is an entrywise positive matrix. We consider the distance matrix of a subset of a rectangular grid of points in the plane. If we choose m+k−1 points, not containing a closed path, in an m×k grid, then a formula for the determinant of the distance matrix of such points is obtained.

We obtain the singular value decomposition of multi-companion matrices. We completely characterise the columns of the matrix U and give a simple formula for obtaining the columns of the other unitary matrix, V, from the columns of U. We also obtain necessary and sufficient conditions for the related matrix polynomial to be hyperbolic.

We consider the set of m × n nonnegative real matrices and define the nonnegative rank of a matrix A to be the minimum k such that A = BC where B is m × k and C is k × n . Given that the real rank of A is j for some j , we give bounds on the nonnegative rank of A and A 2 .

In this paper, we study some unitary-equivalence properties of the companion matrices. We obtain a criterion for a companion matrix to be reducible and show that the numerical range of a companion matrix is a circular disc centered at the origin if and only if the matrix equals the (nilpotent) Jordan block. However, the more general assertion that a companion matrix is determined by its numerical range turns out to be false. We also determine, for an n × n matrix A with eigenvalues in the open unit disc, the defect index of a contraction to which A is similar.

In this paper, we give the eigenvalue decomposition for odd order tridiagonal 2-Toeplitz matrix and derive the explicit expression for integer powers of such matrix.

The shifted number system is presented: a method for detecting and avoiding error producing carries during approximate computations with truncated expansions of rational numbers. Using the shifted number system the high-order lifting and integrality certification techniques of Storjohann 2003 for polynomial matrices are extended to the integer case. Las Vegas reductions to integer matrix multiplication are given for some problems involving integer matrices: the determinant and a solution of a linear system can be computed with about the same number of bit operations as required to multiply together two matrices having the same dimension and size of entries as the input matrix. The algorithms are space efficient.

This paper defines a new type of matrix (which will be called a centro-invertible matrix) with the property that the inverse can be found by simply rotating all the elements of the matrix through 180 degrees about the mid-point of the matrix. Centro-invertible matrices have been demonstrated in a previous paper to arise in the analysis of a particular algorithm used for the generation of uniformly-distributed pseudo-random numbers. An involutory matrix is one for which the square of the matrix is equal to the identity. It is shown that there is a one-to-one correspondence between the centro-invertible matrices and the involutory matrices. When working in modular arithmetic this result allows all possible k by k centro-invertible matrices with integer entries modulo M to be enumerated by drawing on existing theoretical results for involutory matrices. Consider the k by k matrices over the integers modulo M. If M takes any specified finite integer value greater than or equal to two then there are only a finite number of such matrices and it is valid to consider the likelihood of such a matrix arising by chance. It is possible to derive both exact expressions and order-of-magnitude estimates for the number of k by k centro-invertible matrices that exist over the integers modulo M. It is shown that order ( √ N ) of the N = M ( k 2 ) different k by k matrices modulo M are centro-invertible, so that the proportion of these matrices that are centro-invertible is order ( 1 / √ N ) .

Given a square complex matrix A and two complex numbers z1 and z2, we find the distance from A to the set of matrices that have z1, z2 as some of their eigenvalues. We use the distance between two matrices associated with the spectral norm.

A sign pattern is a matrix whose entries are from the set { + , - , 0 } . For a real matrix B, sgn ( B ) is the sign pattern obtained by replacing each positive (respectively, negative, zero) entry of B by + (respectively, - , 0). For a sign pattern A, the sign pattern class of A, denoted Q ( A ) , is defined as { B : sgn ( B ) = A } . The purpose of this note is to prove the following theorem: Let A, B, and C be real matrices such that AB = C . Suppose that the zero bipartite graph of C (this is the same as the complement of the bipartite graph of C) is a forest. Then there exist rational perturbations A ∼ , B ∼ and C ∼ of A , B , and C, respectively, in the same corresponding sign pattern classes, such that A ∼ B ∼ = C ∼ .

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, A = G i 1 G i 2 ⋯ G i n - 1 , where ( i 1 , i 2 , … , i n - 1 ) is a permutation of ( 1 , 2 , … , n - 1 ) , and the matrices G k , k = 1 , … , n - 1 have the form G k = I k - 1 C k I n - k - 1 for some 2 × 2 matrices C k . It was observed that (1) independently of the permutation, all such matrices with given C i ’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 (M. Fiedler, A note on companion matrices, Linear Algebra Appl. 372 (2003) 325–331, [9] ), (3) the multiplication of the G i ’s is intrinsic. We explore connections between the 2 × 2 matrices C k and the resulting CB-matrix Π G k ; in particular, which properties are inherited from the C k to the ∏ G k . We consider two situations, for the ordinary real CB-matrices and for the corresponding sign pattern matrices.

We study the 0–1 matrices whose squares are still 0–1 matrices and determine the maximal number of ones in such a matrix. The maximizing matrices are also specified. This solves a special case of a problem posed by Zhan.