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.     

On the generalizations of circulants

The generalized q-circulant is defined, which is a generalization of circulants. The set of all generalized 1-circulants is a commutative algebra. The determinant and a formula for the Moore-Penrose inverse of a generalized q-circulant are given.     

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.     

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.     

Common circulant homogeneous factorisations of the complete digraph

In this paper we determine the positive integers n and k for which there exists a homogeneous factorisation of a complete digraph on n vertices with k ‘common circulant’ factors. This means a partition of the arc set of the complete digraph K_n into k circulant factor digraphs, such that a cyclic group of order n acts regularly on the vertices of each factor digraph whilst preserving the edges, and in addition, an overgroup of this permutes the factor digraphs transitively amongst themselves. This determination generalises a previous result for self-complementary circulants.     

The Moore-Penrose inverse of a retrocirculant

In a recent paper Chao [2] has determined the eigenvalues of a matrix of the form A=PC where P is a permutation matrix which commutes with a certain unitary matrix and C is a circulant. Here we determine the Moore-Penrose inverse of such a “retrocirculant” and show that the nonzero eigenvalues of the Moore-Penrose inverse are the reciprocals of the nonzero eigenvalues of the retrocirculant.     

Generalized inverses of certain Toeplitz matrices

The spectral inverse A^s of a Toeplitz matrix A whose form is related to that of a circulant matrix is studied by describing the algebraic structure of the semigroup of all matrices commuting with a given matrix with distinct eigenvalues. A computational form for A^s is given and necessary and sufficient conditions are found for A^s to be the Moore-Penrose generalized inverse A⁺.     

The inverse of circulant matrix

A direct method is proposed to get the inverse matrix of circulant matrix that find important application in engineering, the elements of the inverse matrix are functions of zero points of the characteristic polynomial g(z) and g′(z) of circulant matrix, four examples to get the inverse matrix are presented in the paper.     

Diameters of random circulant graphs

The diameter of a graph measures the maximal distance between any pair of vertices. The diameters of many small-world networks, as well as a variety of other random graph models, grow logarithmically in the number of nodes. In contrast, the worst connected networks are cycles whose diameters increase linearly in the number of nodes. In the present study we consider an intermediate class of examples: Cayley graphs of cyclic groups, also known as circulant graphs or multi-loop networks. We show that the diameter of a random circulant 2k-regular graph with n vertices scales as n ^1/k , and establish a limit theorem for the distribution of their diameters. We obtain analogous results for the distribution of the average distance and higher moments.     

Level-m scaled circulant factor matrices over the complex number field and the quaternion division algebra

The level-m scaled circulant factor matrix over the complex number field is introduced. Its diagonalization and spectral decomposition and representation are discussed. An explicit formula for the entries of the inverse of a level-m scaled circulant factor matrix is presented. Finally, an algorithm for finding the inverse of such matrices over the quaternion division algebra is given.     

On an extremal family of circulant networks

The paper addresses the optimization problem for circulant networks of maximizing the number of vertices given the degree and diameter of a graph. For the graphs in the best available extremal family of circulant networks, we improve the estimate for diameter, which together with previous results for multiplicative circulant networks enables us to improve the lower bounds for the attainable number of vertices of circulant networks of all dimensions k ≥ 4.     

Perturbations and expressions for generalized inverses in Banach spaces and Moore-Penrose inverses in Hilbert spaces of closed linear operators

The problems of perturbation and expression for the generalized inverses of closed linear operators in Banach spaces and for the Moore-Penrose inverses of closed linear operators in Hilbert spaces are studied. We first provide some stability characterizations of generalized inverses of closed linear operators under T-bounded perturbation in Banach spaces, which are exactly equivalent to that the generalized inverse of the perturbed operator has the simplest expression T⁺(I+δTT⁺)^-1. Utilizing these results, we investigate the expression for the Moore-Penrose inverse of the perturbed operator in Hilbert spaces and provide a unified approach to deal with the range preserving or null space preserving perturbation. An explicit representation for the Moore-Penrose inverse of the perturbation is also given. Moreover, we give an equivalent condition for the Moore-Penrose inverse to have the simplest expression T^†(I+δTT^†)^-1. The results obtained in this paper extend and improve many recent results in this area.     

A variant of the Johnson-Lindenstrauss lemma for circulant matrices

We continue our study of the Johnson-Lindenstrauss lemma and its connection to circulant matrices started in Hinrichs and Vybíral (in press) [7]. We reduce the bound on k from k=Ω(ε−2log³n) proven there to k=Ω(ε−2log²n). Our technique differs essentially from the one used in Hinrichs and Vybíral (in press) [7]. We employ the discrete Fourier transform and singular value decomposition to deal with the dependency caused by the circulant structure.     

Computational results of duadic double circulant codes

Quadratic residue codes have been one of the most important classes of algebraic codes. They have been generalized into duadic codes and quadratic double circulant codes. In this paper we introduce a new subclass of double circulant codes, called duadic double circulant codes, which is a generalization of quadratic double circulant codes for prime lengths. This class generates optimal self-dual codes, optimal linear codes, and linear codes with the best known parameters in a systematic way. We describe a method to construct duadic double circulant codes using 4-cyclotomic cosets and give certain duadic double circulant codes over $\mathbb{F}_{2}$ , $\mathbb{F}_{3}$ , $\mathbb{F}_{4}$ , $\mathbb{F}_{5}$ , and $\mathbb{F}_{7}$ . In particular, we find a new ternary self-dual [76,38,18] code and easily rediscover optimal binary self-dual codes with parameters [66,33,12], [68,34,12], [86,43,16], and [88,44,16] as well as a formally self-dual binary [82,41,14] code.     

On Hamiltonicity of circulant digraphs of outdegree three

This paper deals with Hamiltonicity of connected loopless circulant digraphs of outdegree three with connection set of the form {a,ka,c}, where k is an integer. In particular, we prove that if k=−1 or k=2 such a circulant digraph is Hamiltonian if and only if it is not isomorphic to the circulant digraph on 12 vertices with connection set {3,6,4}.     

求鳞状因子循环矩阵的逆阵及广义逆阵的快速付氏变换法

借助快速付立叶变换(FFT),本文给出一种求n阶鳞状因子循环矩阵的逆阵、自反g-逆、群逆、Moore-Penrose逆的快速算法,该算法的计算复杂性为O(nlog2n),最后给出的两个数值算例表明了该算法的有效性.     

Codes associated with circulant graphs and permutation decoding

Binary codes that can be obtained from designs associated with circulant graphs G(n, S) are studied. The parameters of the codes and the information sets are obtained. PD-sets for full-error correction are found for certain values of n.     

Integral circulant graphs

In this note we characterize integral graphs among circulant graphs. It is conjectured that there are exactly 2^τ(n)-1 non-isomorphic integral circulant graphs on n vertices, where τ(n) is the number of divisors of n.     

On isomorphisms of circulant digraphs of bounded degree

C.H. Li recently made the following conjecture: Let Γ be a circulant digraph of order n=n₁n₂ and degree m, where gcd(n₁,n₂)=1, n₁ divides 4k, where k is odd and square-free, and every prime divisor of n₂ is greater than m, or, if Γ is a circulant graph, every prime divisor of n₂ is greater than 2m. Then Γ is a CI-digraph of Z_n. In this paper we verify that this conjecture is true.     

The generalized weighted Moore-Penrose inverse

In this paper, we definite a generalized weighted Moore-Penrose inverse A _M,N ⁺ of a given matrixA, and give the necessary and sufficient conditions for its existence. We also prove its uniqueness and give a representation of it. In the end we point out this generalized inverse is also a prescribed rangT and null spaceS of {2}-(or outer) inverse ofA.