Generalized inverses of circulant and generalized circulant matrices

An expression for the Moore-Penrose inverse of certain singular circulants by S.R. Searle is generalized to include all circulants. Similar expressions are given for the Moore-Penrose inverse of block circulants with circulant blocks, level-q circulants, k-circulants where |k|=1, and certain other matrices which are the product of a permutation matrix and a circulant. Expressions for other generalized inverses are given.     

Well-covered circulant graphs

A graph is well-covered if every independent set can be extended to a maximum independent set. We show that it is co-NP-complete to determine whether an arbitrary graph is well-covered, even when restricted to the family of circulant graphs. Despite the intractability of characterizing the complete set of well-covered circulant graphs, we apply the theory of independence polynomials to show that several families of circulants are indeed well-covered. Since the lexicographic product of two well-covered circulants is also a well-covered circulant, our partial characterization theorems enable us to generate infinitely many families of well-covered circulants previously unknown in the literature.     

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.     

INFINITE CIRCULANTS AND THEIR PROPERTIES

ＩＮＦＩＮＩＴＥＣＩＲＣＵＬＡＮＴＳＡＮＤＴＨＥＩＲＰＲＯＰＥＲＴＩＥＳＺＨＡＮＧＦＵＪＩ（张福基）ＨＵＡＮＧＱＩＯＮＧＸＩＡＮＧ（黄琼湘）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＸｉｎｊｉａｎｇＵｎｉｖｅｒｓｉｔｙ，Ｕｒｕｍｃｈｉ８３００...     

Moore–Penrose inverses of block circulant and block k-circulant matrices

The Moore–Penrose inverse A⁺ of a block circulant matrix whose blocks are arbitrary square matrices is obtained. An explicit form is given for A⁺ in terms of the blocks of A. The eigenvalues of A are determined in terms of the eigenvalues of the blocks where the blocks themselves are circulants.     

Finiteness of circulant weighing matrices of fixed weight

Let n be a fixed positive integer. Every circulant weighing matrix of weight n arises from what we call an irreducible orthogonal family of weight n. We show that the number of irreducible orthogonal families of weight n is finite and thus obtain a finite algorithm for classifying all circulant weighing matrices of weight n. We also show that, for every odd prime power q, there are at most finitely many proper circulant weighing matrices of weight q.     

对角因子分块循环矩阵的对角化和谱分解

导出了对角因子分块循环矩阵的概念，把循环矩阵的对角化和谱分解推广到具有对角因子循环结构的分块矩阵中去．     

On inverting circulant matrices

The elements of the inverse of a circulant matrix having only three non-zero elements in each row (located in cyclically adjacent columns) are derived analytically from the solution of a recurrence equation. Expressing any circulant as a product containing these three-element-type circulants then provides an algorithm for inverting circulants in general. Extension is also made to deriving generalized inverses of certain singular circulants.     

2n Bordered constructions of self-dual codes from group rings

Self-dual codes, which are codes that are equal to their orthogonal, are a widely studied family of codes. Various techniques involving circulant matrices and matrices from group rings have been used to construct such codes. Moreover, families of rings have been used, together with a Gray map, to construct binary self-dual codes. In this paper, we introduce a new bordered construction over group rings for self-dual codes by combining many of the previously used techniques. The purpose of this is to construct self-dual codes that were missed using classical construction techniques by constructing self-dual codes with different automorphism groups. We apply the technique to codes over finite commutative Frobenius rings of characteristic 2 and several group rings and use these to construct interesting binary self-dual codes. In particular, we construct some extremal self-dual codes of length 64 and 68, constructing 30 new extremal self-dual codes of length 68.     

A characterization of the Toeplitz and Hankel circulants

A number of assertions of the following type are proved: A Toeplitz matrix T is a circulant if and only if T has an eigenvector e with unit components. These assertions characterize the circulants (and, more generally, the ϕ circulants), as well as their Hankel counterparts, in the sets of all Toeplitz and all Hankel matrices, respectively. Bibliography: 2 titles.     

Right division in groups, dedekind-frobenius group matrices, and ward quasigroups

The variety of quasigroups satisfying the identity (xy)(zy) = xz mirrors the variety of groups, and offers a new look at groups and their multiplication tables. Such quasigroups are constructed from a group using right division instead of multiplication. Their multiplication tables consist of circulant blocks which have additional symmetries and have a concise presentation. These tables are a reincarnation of the group matrices which Frobenius used to give the first account of group representation theory. Our results imply that every group matrix may be written as a block circulant matrix and that this result leads to partial diagonalization of group matrices, which are present in modern applied mathematics. We also discuss right division in loops with the antiautomorphic inverse property.     

PRODUCTS OF CIRCULANT GRAPHS

ABSTRACT

Graph products of circulants are studied. It is shown that if G and H are circulants and gcd(v(G), v(H)) = 1, then every B-product of G and H is again a circulant. We prove that if m ≠ 2, then the generalised prism K₂ ^mxC_n is a circulant iff n is odd. A similar result is deduced for the conjunction. We also prove that C_p x C_q is a circulant iff p and q are relatively prime. We close by showing that the composition of two circulants is again a circulant and explicitly describe the resultant circulant's jump sequence in terms of the constituent circulants' jump sequences.     

一类特殊的分块反循环矩阵的特征值问题(英文)

利用r-循环矩阵的基本性质,探讨了一类特殊的分块反循环矩阵的特征值问题.     

Some Identities for Enumerators of Circulant Graphs

We establish analytically several new identities connecting enumerators of different types of circulant graphs mainly of prime, twice prime and prime-squared orders. In particular, it is shown that the half-sum of the number of undirected circulants and the number of undirected self-complementary circulants of prime order is equal to the number of directed self-complementary circulants of the same order. Several identities hold only for prime orders p such that (p + 1)/2 is also prime. Some conjectured generalizations and interpretations are discussed.     

Applications of the Generalized Fourier Transform in Numerical Linear Algebra

Equivariant matrices, commuting with a group of permutation matrices, are considered. Such matrices typically arise from PDEs and other computational problems where the computational domain exhibits discrete geometrical symmetries. In these cases, group representation theory provides a powerful tool for block diagonalizing the matrix via the Generalized Fourier Transform (GFT). This technique yields substantial computational savings in problems such as solving linear systems, computing eigenvalues and computing analytic matrix functions such as the matrix exponential. The paper is presenting a comprehensive self contained introduction to this field. Building upon the familiar special (finite commutative) case of circulant matrices being diagonalized with the Discrete Fourier Transform, we generalize the classical convolution theorem and diagonalization results to the noncommutative case of block diagonalizing equivariant matrices. Applications of the GFT in problems with domain symmetries have been developed by several authors in a series of papers. In this paper we elaborate upon the results in these papers by emphasizing the connection between equivariant matrices, block group algebras and noncommutative convolutions. Furthermore, we describe the algebraic structure of projections related to non-free group actions. This approach highlights the role of the underlying mathematical structures, and provides insight useful both for software construction and numerical analysis. The theory is illustrated with a selection of numerical examples. AMS subject classification (2000) 43A30, 65T99, 20B25     

Circulant Wavelet Preconditioners for Solving Elliptic Differential Equations and Boundary Integral Equations

In this paper is discussed solving an elliptic equation and a boundary integral equation of the second kind by representation of compactly supported wavelets. By using wavelet bases and the Galerkin method for these equations, we obtain a stiff sparse matrix that can be ill-conditioned. Therefore, we have to introduce an operator which maps every sparse matrix to a circulant sparse matrix. This class of circulant matrices is a class of preconditioners in a Banach space. Based on having some properties in the spectral theory for this class of matrices, we conclude that the circulant matrices are a good class of preconditioners for solving these equations. We called them circulant wavelet preconditioners (CWP). Therefore, a class of algorithms is introduced for rapid numerical application.     

Circulant preconditioners for Toeplitz-block matrices

We propose two block preconditioners for Toeplitz-block matrices (i.e. each block is Toeplitz), intended to be used in conjunction with conjugate gradient methods. These preconditioners employ and extend existing circulant preconditioners for point Toeplitz matrices. The two preconditioners differ in whether the point circulant approximation is used once or twice, and also in the cost per step. We discuss efficient implementation of these two preconditioners, as well as some basic theoretical properties (such as preservation of symmetry and positive definiteness). We report results of numerical experiments, including an example from active noise control, to compare their performance.Research supported by SRI International and by the Army Research Office under contract DAAL03-91-G-0150 and by the Office of Naval Research under contract N00014-90-J-1695.     

The computation of the square roots of circulant matrices

In the first part of this paper, we investigate the reduced forms of circulant matrices and quasi-skew circulant matrices. By using their properties we present two efficient algorithms to compute the square roots of circulant matrices and quasi-skew circulant matrices, respectively. Those methods are faster than the traditional algorithm which is based on the Schur decomposition. In the second part, we further consider circulant H-matrices with positive diagonal entries and develop two algorithms for computing their principal square roots. Those two algorithms have the common advantage that is they only need matrix-matrix multiplications in their iterative sequences, an operation which can be done very efficiently on modern high performance computers.     

The Semigroup of Primitive Circulant Matrices over a Distributive Lattice

In this paper, the concepts of primitive matrices over a distributive lattice L are introduced, and some algebraic properties of primitive circulant matrices over the lattice L are obtained. Also, some characterizations of the set of all primitive circulant matrices over the lattice L of order n as a semigroup are given.