On the similarity of matrices of even order

We study invariants of simultaneous similarity of a pair of matrices of even order 2k over the field of complex numbers for the case in which all elementary divisors of the corresponding characteristic polynomial matrix are identical and their number is k.     

On the representability of totally unimodular matrices on bidirected graphs

We present a polynomial time algorithm to construct a bidirected graph for any totally unimodular matrix B by finding node-edge incidence matrices Q and S such that QB=S. Seymour’s famous decomposition theorem for regular matroids states that any totally unimodular (TU) matrix can be constructed through a series of composition operations called k-sums starting from network matrices and their transposes and two compact representation matrices B₁,B₂ of a certain ten element matroid. Given that B₁,B₂ are binet matrices we examine the k-sums of network and binet matrices. It is shown that thek-sum of a network and a binet matrix is a binet matrix, but binet matrices are not closed under this operation for k=2,3. A new class of matrices is introduced, the so-called tour matrices, which generalise network, binet and totally unimodular matrices. For any such matrix there exists a bidirected graph such that the columns represent a collection of closed tours in the graph. It is shown that tour matrices are closed under k-sums, as well as under pivoting and other elementary operations on their rows and columns. Given the constructive proofs of the above results regarding the k-sum operation and existing recognition algorithms for network and binet matrices, an algorithm is presented which constructs a bidirected graph for any TU matrix.     

Fast block diagonalization of k-tridiagonal matrices

In the present paper, we give a fast algorithm for block diagonalization of k-tridiagonal matrices. The block diagonalization provides us with some useful results: e.g., another derivation of a very recent result on generalized k-Fibonacci numbers in [M.E.A. El-Mikkawy, T. Sogabe, A new family of k-Fibonacci numbers, Appl. Math. Comput. 215 (2010) 4456-4461]; efficient (symbolic) algorithm for computing the matrix determinant.     

Algebraic properties of Manin matrices 1

We study a class of matrices with noncommutative entries, which were first considered by Yu.I. Manin in 1988 in relation with quantum group theory. They are defined as “noncommutative endomorphisms” of a polynomial algebra. More explicitly their defining conditions read: (1) elements in the same column commute; (2) commutators of the cross terms are equal: [M_ij,M_kl]=[M_kj,M_il] (e.g. [M₁₁,M₂₂]=[M₂₁,M₁₂]). The basic claim is that despite noncommutativity many theorems of linear algebra hold true for Manin matrices in a form identical to that of the commutative case. Moreover in some examples the converse is also true, that is, Manin matrices are the most general class of matrices such that linear algebra holds true for them. The present paper gives a complete list and detailed proofs of algebraic properties of Manin matrices known up to the moment; many of them are new. In particular we provide complete proofs that an inverse to a Manin matrix is again a Manin matrix and for the Schur formula for the determinant of a block matrix; we generalize the noncommutative Cauchy–Binet formulas discovered recently arXiv:0809.3516, which includes the classical Capelli and related identities. We also discuss many other properties, such as the Cramer formula for the inverse matrix, the Cayley–Hamilton theorem, Newton and MacMahon–Wronski identities, Plücker relations, Sylvester's theorem, the Lagrange–Desnanot–Lewis Carroll formula, the Weinstein–Aronszajn formula, some multiplicativity properties for the determinant, relations with quasideterminants, calculation of the determinant via Gauss decomposition, conjugation to the second normal (Frobenius) form, and so on and so forth. Finally several examples and open question are discussed. We refer to [A. Chervov, G. Falqui, Manin matrices and Talalaev's formula, J. Phys. A 41 (2008) 194006; V. Rubtsov, A. Silantiev, D. Talalaev, Manin matrices, elliptic commuting families and characteristic polynomial of quantum gl_n elliptic Gaudin model, in press] for some applications in the realm of quantum integrable systems.     

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.     

A note on certain matrices with h(x) – Fibonacci quaternion polynomials

In this paper we consider a g – circulant, right circulant, left circulant and a special kind of a tridiagonal matrices whose entries are h(x) – Fibonacci quaternion polynomials. We present the determinant of these matrices and with the tridiagonal matrices we show that the determinant is equal to the nth term of the h(x) – Fibonacci quaternion polynomial sequences.     

Cyclic matrices of weighted digraphs

In this paper, we address several properties of the so-called augmented cyclic matrices of weighted digraphs. These matrices arise in different applications of digraph theory to electrical circuit analysis, and can be seen as an enlargement of basic cyclic matrices of the form BWB^T, where B is a cycle matrix and W is a diagonal matrix of weights. By using certain matrix factorizations and some properties of cycle bases, we characterize the determinant of augmented cyclic matrices, via Cauchy-Binet expansions, in terms of the so-called proper cotrees. In the simpler context defined by basic cyclic matrices, we obtain the dual result of Maxwell’s determinantal expansion for weighted Laplacian (nodal) matrices. Additional relations with nodal matrices are also discussed. We apply this framework to the characterization of the differential-algebraic circuit models arising from loop analysis, and also to the analysis of branch-oriented models of circuits including charge-controlled memristors.     

A recursive algorithm for constructing complicated Dixon matrices

Whether the determinant of the Dixon matrix equals zero or not is used for determining if a system of n + 1 polynomial equations in n variables has a common root, and is a very efficient quantifier elimination approach too. But for a complicated polynomial system, it is not easy to construct the Dixon matrix. In this paper, a recursive algorithm to construct the Dixon matrix is proposed by which some problems that cannot be tackled by other methods can be solved on the same computer platform. A dynamic programming algorithm based on the recursive formula is developed and compared for speed and efficiency to the recursive algorithm.     

The centro-invertible matrix: A new type of matrix arising in pseudo-random number generation

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^(k2) 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).     

包含切比雪夫多项式的循环矩阵行列式的计算

行首加r尾r右循环矩阵和行尾加r首r左循环矩阵是两种特殊类型的矩阵,这篇论文中就是利用多项式因式分解的逆变换这一重要的技巧以及这类循环矩阵漂亮的结构和切比雪夫多项式的特殊的结构,分别讨论了第一类、第二类切比雪夫多项式的关于行首加r尾r右循环矩阵和行尾加r首r左循环矩阵的行列式,从而给出了行首加r尾r右循环矩阵和行尾加r首r左循环矩阵的行列式显式表达式.这些显式表达式与切比雪夫多项式以及参数r有关.这一问题的应用背景主要在循环编码,图像处理等信息理论方面.     

The scrambling index of symmetric primitive matrices

A nonnegative square matrix A is primitive if some power A^k>0 (that is, A^k is entrywise positive). The least such k is called the exponent of A. In [2], Akelbek and Kirkland defined the scrambling index of a primitive matrix A, which is the smallest positive integer k such that any two rows of A^k have at least one positive element in a coincident position. In this paper, we give a relation between the scrambling index and the exponent for symmetric primitive matrices, and determine the scrambling index set for the class of symmetric primitive matrices. We also characterize completely the symmetric primitive matrices in this class such that the scrambling index is equal to the maximum value.     

Subtotally positive and Monge matrices

A real matrix is called k-subtotally positive if the determinants of all its submatrices of order at most k are positive. We show that for an m × n matrix, only mn inequalities determine such class for every k, 1 ? k ? min(m,n). Spectral properties of square k-subtotally positive matrices are studied. Finally, completion problems for 2-subtotally positive matrices and their additive counterpart, the anti-Monge matrices, are investigated. Since totally positive matrices are 2-subtotally positive as well, the presented necessary conditions for this completion problem are also necessary conditions for totally positive matrices.     

Invariant Hyperfunction Solutions to Invariant Differential Equations on the Space of Real Symmetric Matrices

The real special linear group of degree n naturally acts on the vector space of n×n real symmetric matrices. How to determine invariant hyperfunction solutions of invariant linear differential equations with polynomial coefficients on the vector space of n×n real symmetric matrices is discussed in this paper. We prove that every invariant hyperfunction solution is expressed as a linear combination of Laurent expansion coefficients of the complex power of the determinant function with respect to the parameter of the power. Then the problem is reduced to the determination of Laurent expansion coefficients.     

Polynomial Fibonacci–Hessenberg matrices

A Fibonacci–Hessenberg matrix with Fibonacci polynomial determinant is referred to as a polynomial Fibonacci–Hessenberg matrix. Several classes of polynomial Fibonacci–Hessenberg matrices are introduced. The notion of two-dimensional Fibonacci polynomial array is introduced and three classes of polynomial Fibonacci–Hessenberg matrices satisfying this property are given.     

Torsion formulas for signed graphs

Following our recent exposition on the algebraic foundations of signed graphs, we introduce bond (circuit) basis matrices for the tension (flow) lattices of signed graphs, and compute the torsions of such matrices and Laplacians. We present closed formulas for the torsions of the incidence matrix, the Laplacian, bond basis matrices, and circuit basis matrices. These formulas show that the torsions of all such matrices are powers of 2, and so imply that the matroids of signed graphs are representable over any field of characteristic not 2. A notable feature of using torsion is that the Matrix-Tree formula for ordinary graphs and Zaslavsky’s formula for unbalanced signed graphs are unified into one Matrix-Basis formula in terms of the torsion of its Laplacian matrix, rather than in terms of its determinant, which vanishes for an ordinary graph unless one row is deleted from the incidence matrix.     

A Widom like formula for some Toeplitz plus Hankel determinants

A well known Widom formula expresses the determinant of a Toeplitz matrix _Tn$T_n$ with Laurant polynomial symbol f in terms of the zeros of f. We give similar formulae for some even Toeplitz plus Hankel matrices. The formulae are based on an analytic representation of the determinant of such matrices in terms of Chebyshev polynomials.     

On sums of squares of k-nomials

In 2005, Boman et al. introduced the concept of factor width for a real symmetric positive semidefinite matrix. This is the smallest positive integer k for which the matrix A can be written as $A=V{V}^T$ with each column of V containing at most k non-zeros. The cones of matrices of bounded factor width give a hierarchy of inner approximations to the PSD cone. In the polynomial optimization context, a Gram matrix of a polynomial having factor width k corresponds to the polynomial being a sum of squares of polynomials of support at most k. Recently, Ahmadi and Majumdar [1], explored this connection for case $k=2$ and proposed to relax the reliance on polynomials that are sums of squares in semidefinite programming to polynomials that are sums of binomial squares In this paper, we prove some results on the geometry of the cones of matrices with bounded factor widths and their duals, and use them to derive new results on the limitations of certificates of nonnegativity of quadratic forms by sums of k-nomial squares using standard multipliers. In particular we show that they never help for symmetric quadratics, for any quadratic if $k=2$, and any quaternary quadratic if $k=3$. Furthermore we give some evidence that those are a complete list of such cases.     

An inversion formula for a matrix polynomial about a (unit) root

A solution to the problem of a closed-form representation for the inverse of a matrix polynomial about a unit root is provided by resorting to a Laurent expansion in matrix notation, whose principal-part coefficients turn out to depend on the non-null derivatives of the adjoint and the determinant of the matrix polynomial at the root. Some basic relationships between principal-part structure and rank properties of algebraic function of the matrix polynomial at the unit root as well as informative closed-form expressions for the leading coefficient matrices of the matrix-polynomial inverse are established.