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.     

INFINITE CIRCULANTS AND THEIR PROPERTIES

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

Generalized circulants and class functions of finite groups

The regular representation of the ring of class functions of a finite group is used to construct families of matrices that enjoy many of the properties of circulant matrices. For different choices of finite groups one gets different families of matrices: the circulants, block circulants, block circulants with circulant blocks of all levels, and many others. The properties of these families are simple consequences of the character theory of finite groups. Many known properties of circulants and some of their generalizations are obtained as special cases of the properties of the families constructed. Some applications to character theory are also mentioned.     

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.     

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.     

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.     

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.     

Circulant digraphs determined by their spectra

Inspired by Ádám's conjecture the isomorphism problem of circulant digraphs is widely investigated. In the literature, the spectrum method was to solve the isomorphism problem for the circulants of prime-power order by some people. In this paper, we develop the spectrum method to characterize the circulant digraphs of orders p^a and p^aq^b, where p and q are distinct primes.     

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.     

The chromatic number of 5-valent circulants

A circulant C(n;S) with connection set S={a₁,a₂,…,a_m} is the graph with vertex set Z_n, the cyclic group of order n, and edge set E={{i,j}:|i−j|∈S}. The chromatic number of connected circulants of degree at most four has been previously determined completely by Heuberger [C. Heuberger, On planarity and colorability of circulant graphs, Discrete Math. 268 (2003) 153-169]. In this paper, we determine completely the chromatic number of connected circulants C(n;a,b,n/2) of degree 5. The methods used are essentially extensions of Heuberger’s method but the formulae developed are much more complex.     

Minimum Cycle of Row Vector of a Generalized Circulant Fuzzy Matrix

51.IntroductionLetF=[O,1],foranya,beF,definea b=max{a,b},a*b=min{a,b}.Mn(F)standsforthesetofa1lthenthordermatrixesinF,matrixAinMn(F)iscalledFuzzymatrixA.Letrbeanynon-negativeinteger.lnannthordermatrix,exclusiveofthefirstrow,theelementsofeveryotherrowarethee1ementsoftheprecedingrowthatcirculaterightwardr-co1umns.Thisnthordermatrixisannthorderr-circulantFuzzymatrix(alsocalledgenearLizedcirculantFuzzymatrix)-Wecallrthecircu1antindexofr-circulantFuzzymatrix.Inthebooklistedin[1j,thisisgiven:…     

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.     

Normal cirulant graphs with noncyclic regular subroups

We prove that any circulant graph of order n with connection set S such that n and the order of ?(S), the subgroup of ? that fixes S set‐wise, are relatively prime, is also a Cayley graph on some noncyclic group, and shows that the converse does not hold in general. In the special case of normal circulants whose order is not divisible by 4, we classify all such graphs that are also Cayley graphs of a noncyclic group, and show that the noncyclic group must be metacyclic, generated by two cyclic groups whose orders are relatively prime. We construct an infinite family of normal circulants whose order is divisible by 4 that are also normal Cayley graphs on dihedral and noncyclic abelian groups. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Remarks concerning possible connections between Fermat's last theorem and integral p×p circulants

Let p be a prime and x, y integers. Then x^p+y^p occurs as the determinant of an integral p×p circulant. Some problems concerning the set of values assumed by det C as C runs through the set of integral p×p circulants are given. The problem of finding sufficient conditions on an integral p×p circulant C which ensure that C can be factored in the form C₁C'₁ (where ' denotes transpose) with C₁ an integral circulant is referred to, and it is conjectured that such a factorization is possible if C is unimodular and positive definite symmetric and $\text{1}\text{2}$(p–1) is also a prime.     

Classifying Arc-Transitive Circulants of Square-Free Order

A circulant is a Cayley graph of a cyclic group. Arc-transitive circulants of square-free order are classified. It is shown that an arc-transitive circulant of square-free order n is one of the following: the lexicographic product , or the deleted lexicographic , where n = bm and is an arc-transitive circulant, or is a normal circulant, that is, Aut has a normal regular cyclic subgroup.     

求置换因子循环矩阵的逆阵及广义逆阵的快速算法

1 引 言 循环矩阵由于其应用非常广泛而成为一类重要的特殊矩阵,如在图象处理、编码理论、自回归滤波器设计等领域中经常会遇到以这类矩阵为系数的线性系统的求解问题.而对称循环组合系统也具有广泛的实际背景,例如造纸机的横向控制系统,具有平行结     

Pancyclicity of connected circulant graphs

The circulant G_n(a₁, ⋖, a_k), where 0 < a₁ < ··· < a_k < (n + 1)/2, is defined as the vertex-transitive graph that has vertices i ± a₁, ···, i ± a_k(mod n) adjacent to each vertex i. In this work we show that the connected circulants of degree at least three contain all even cycles. In addition, we prove that the connected circulants of girth three contain cycles of all lengths. © 1997 John Wiley & Sons, Inc. J Graph Theory 26: 17–25, 1997     

Circulants and their connectivities

There is diverse literature on various properties of a class of graphs known as circulants. We present a new result which answers the previously unsolved question of characterizing the connection sequence of circulants having point connectivity equal to point degree. We also develop some theorems regarding a new generalization of connectivity known as super-connectivity. In addition, we give a survey of published results pertinent to the study of connectivity of circulants.