# A Note on the Square Roots of a Class of Circulant Matrices

Authors: Ying Zhang; Huisheng Zhang; Guoyan Chen
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

We prove that anyk-circulant matrix and any even order skew k-circulant matrix are diagonalizable for any k∈ℂ. Then, we propose two algorithms for computing the square roots of the k-circulant matrix and the skew k-circulant matrix, respectively. In particular, we show that the square roots of the k-circulant matrix are still k-circulant matrices. Both the theoretical analysis and the numerical experiments show that our algorithms are faster than the standard Schur method.


---

## Body

## 1. Introduction

Given a matrixA, a matrix X is called a square root of A if X2=A. Matrix square roots appear in a variety of branches of mathematics, such as Markov models of finance, the solution of differential equations, the computation of the polar decomposition, and the matrix sign function [1]. A number of methods have been proposed for computing the square roots of a matrix [2–9]. Among them, the Schur method [7] is the most popular and becomes the standard method for computing the matrix square roots. However, Schur method is not so efficient when the matrix order is relatively high. Thus, it is very desirable to design fast computing methods which can make full use of the particular properties of the matrices when the matrices possess special structures.Circulant matrices and their generalizations have a wide range of applications in signal processing, coding theory, digital image disposal, self-regress design, Toeplitz systems, and so on [10–14]. A relatively comprehensive survey about circulant matrices can be found in [15]. Recently, Lu and Gu [16] presented two efficient algorithms to compute the square roots of circulant matrices and quasi-skew circulant matrices, respectively. As they are based on LL iteration [17] and the modified Schulz iterative method, the two algorithms are faster than the standard Schur method. Subsequently, Mei generalized those methods and presented algorithms to compute the square roots of k-circulant matrices and skew k-circulant matrices [18]. These algorithms are also faster than the standard Schur algorithm, but the work is restricted to the case in which the matrix is of even order and k∈ℝ and can not be directly extended to compute the pth root.In this paper, we first show thatk-circulant matrices of any order for any complex number k are diagonalizable and develop an algorithm to compute their principal square roots. Then, we show that skew k-circulant matrices of even order for any complex number k are diagonalizable, and develop an algorithm to compute their principle square roots. Both of our algorithms are theoretically and experimentally proved to be faster than the standard Schur method. Compared with the work in [18], our methods are more general in that they are valid for any k-circulant matrix and any even order skew k-circulant matrix, where k can be any complex number. The remainder of this paper is organized as follows. In Section 2, we compute the square roots of k-circulant matrices. In Section 3, we compute the square roots of skew k-circulant matrices. In Section 4, we present two numerical experiments to exhibit the efficiency of the proposed algorithms in terms of the CPU time.


## 2. Square Roots ofk-Circulant Matrices

Ann×n complex matrix
(1)Circk(a):=[a0a1a2⋯an-1kan-1a0a1…an-2kan-2kan-1a0⋯an-3⋮⋮⋮⋱⋮ka1ka2ka3⋯a0]
is called a k-circulant matrix, where a=(a0,a1,…,an-1)∈ℂn and k∈ℂ. In particular, 1-circulant matrices are circulant matrices, and -1-circulant matrices are skew circulant matrices [19].Another equivalent definition of ak-circulant matrix is as follows [18]: let ℂn×n be the set of all n×n complex matrices, and then, A∈ℂn×n is a k-circulant matrix if and only if A=G-1AG, where G=Circk([0,1,0,…,0]). In this section, we show that k-circulant matrices are diagonalizable.Lemma 1 (see [20]).
IfA and B are two k-circulant matrices of the same order, then A+B is also a k-circulant matrix.Lemma 2 (see [20]).
IfA is a k-circulant matrix, then for any l∈ℂ, lA is also a k-circulant matrix.Lemma 3 (see [20]).
LetG=Circk([0,1,0,…,0]); then,
(2)Gi=[0⋯010⋯00⋯001⋯0⋮⋱⋮⋮⋮⋱⋮0⋯000⋯1k⋯000⋯0⋮⋱⋮⋮⋮⋱⋮0⋯k00⋯0]
is also a k-circulant matrix. In particular, Gn=kE, where E is the identity matrix.Lemma 4 (see [20]).
LetG=Circk([0,1,0,…,0]) and let k=reiθ (r≥0, 0≤θ≤2π); then, the eigenvalues of G are
(3)θj=r1/nei(θ+2π(j-1)/n),(j=1,…,n),
where i is the imaginary unit.Theorem 5 (see [20]).
The matrixC=Circk(a) is a k-circulant matrix of the form (1) if and only if C can be represented by
(4)C=∑j=0n-1ajGj,
where a=(a0,…,an-1), G=Circk([0,1,0,…,0]), and G0=E.Theorem 6 (see [20]).
LetC=Circk(a) be a k-circulant matrix; then, the eigenvalues of C are λj=ϕ(θj) (j=1,…,n), where a=(a0,…,an-1),  ϕ(x)=a0+a1x+a2x2+⋯+an-1xn-1, and θj is defined by (3).Theorem 7 (see [20]).
Anyk-circulant matrix Circk(a) can be diagonalized as follows:
(5)V-1·Circk(a)·V=diag[ϕ(θ1),ϕ(θ2),…,ϕ(θn)]
with the matrix
(6)V=[111⋯1θ1θ2θ3⋯θnθ12θ22θ32⋯θn2⋮⋮⋮⋱⋮θ1n-1θ2n-1θ3n-1⋯θnn-1],
where θj (j=1,…,n) is defined as (3).By (5), we can easily obtain the following result.Corollary 8.
The square roots ofk-circulant matrix Circk(a) are as follows:
(7)Vdiag[ϕ(θ1)1/2,ϕ(θ2)1/2,…,ϕ(θn)1/2]V-1.Remark 9.
We mention that the diagonalization methods [19–22] were used to compute the square roots of k-circulant matrices, where k is restricted to 1 or -1. However, our diagonalization method is valid for any k∈ℂ.Next, we show that the square roots of ak-circulant matrix are still k-circulant matrices.Theorem 10.
Letk=reiθ (r≥0, 0≤θ≤2π), let θj=r1/nei(θ+2π(j-1)/n) (j=1,…,n), and let V be defined as (6). For any diagonal matrix Λ=diag(λ1,…,λn)∈ℂn×n, VΛV-1 is a k-circulant matrix Circk([b0,…,bn-1]), where (b0,…,bn-1)=(λ1,…,λn)V-1.Proof.
By Theorem7, whether VΛV-1 is a k-circulant matrix depends on whether the following system of linear equations with unknown vector (b0,…,bn-1)(8)b0+b1θ1+b2θ12+⋯+bn-1θ1n-1=λ1,b0+b1θ2+b2θ22+⋯+bn-1θ2n-1=λ2⋮b0+b1θn+b2θn2+⋯+bn-1θnn-1=λn
is consistent. Obviously the coefficient matrix of (8) is invertible. Thus, we have
(9)(b0,…,bn-1)=(λ1,…,λn)V-1.
That is to say, VΛV-1 is a k-circulant matrix with the form of Circk([b0,…,bn-1]).Remark 11.
Theorem10 provides a method to construct k-circulant matrix with given eigenvalues. Obviously, the square roots with the form of (7) are k-circulant matrices Circk(b), where b=(ϕ(θ1)1/2,…,ϕ(θn)1/2)V-1.Based on Theorem7 and Corollary 8, we give the following algorithm for computing the principal square root of a k-circulant matrix.Algorithm 12.
Compute a principal square root of ak-circulant matrix A∈ℂn×n.Step
1. Compute the eigenvalues ϕ(θj)=∑s=0n-1as(θj)s (j=1,…,n) of A.Step
2. Compute ϕ(θj)1/2 (j=1,…,n) such that arg(ϕ(θj)1/2)  (j=1,…,n)∈(-π/2,π/2).Step
3. Compute the inverse of V.Step
4. Compute diag[ϕ(θ1)1/2,ϕ(θ2)1/2,…,ϕ(θn)1/2]V-1.Step
5. Compute the square root Vdiag[ϕ(θ1)1/2,ϕ(θ2)1/2,…,ϕ(θn)1/2]V-1 of A.Then, we obtainB=A=Circk([b0,…,bn-1]).The cost of Step 1 is aboutO(nlogn) flops by discrete Fourier transform [18]. The cost of Step 2 is O(n) flops. The cost of Step 3 is about O(nlog2n) flops [23]. The cost of Step 4 is about O(n2) flops. The cost of Step 5 is about O(n2log2n) flops [24]. So, it needs about O(n2log2n) flops in total. The algorithm has the same complexity as the diagonalization methods in [19–21]. But the methods therein are only concerned with the case that k=1 and k=-1. If we use the Schur method, it needs about O(n3) flops in total [7]. We also mention a related work in [18], which only needs about O(nlogn) flops to compute the primary square root of a k-circulant matrix. However, that work restricts the matrix to be of even order and k to be of real number. Those restrictions are not needed in our algorithm.


## 3. Square Roots of Skewk-Circulant Matrices

Letn be an even number; then, A∈ℂn×n is a skew k-circulant matrix if A=-G-1AG, where G=Circk([0,1,0,…,0]) (see [18]). Let k=reiθ (r≥0, 0≤θ≤2π) and let
(10)J=[1000⋯000-100⋯000010⋯00000-1⋯00⋮⋮⋮⋮⋱⋮⋮0000⋯100000⋯0-1].Lemma 13.
LetG=Circk([0,1,0,…,0]). Then,(i)
JGJ=-G;(ii)
JGj=-GjJ for odd number j; JGj=GjJ for even number j.Lemma 14.
Let(11)V=[v1,v2,…,v2m]=[11⋯1θ1θ2⋯θ2mθ12θ22⋯θ2m2⋮⋮⋱⋮θ12m-1θ22m-1⋯θ2m2m-1],
where θj=r1/2mei(θ+2π(j-1)/2m) (j=1,…,2m); then, Jvt=vm+t(t=1,…,m).Proof.
The proof is obvious by paying attention to the fact thatθm+t=θteiπ.Lemma 15.
A skewk-circulant matrix A of order 2m can be written in the form of
(12)JCirck([a0,a1,…,a2m-1]).Proof.
Writen=2m and A=(aij)n×n. Since A=-G-1AG we have GA=-AG; that is,
(13)[a21a22a23⋯a2na31a32a33⋯a3n⋮⋮⋮⋱⋮an1an2an3⋯annka11ka12ka13⋯ka1n]=[-ka1n-a11-a12⋯-a1(n-1)-ka2n-a21-a22⋯-a2(n-1)⋮⋮⋮⋱⋮-ka(n-1)n-a(n-1)1-a(n-1)2⋯-a(n-1)(n-1)-kann-an1-an2⋯-an(n-1)].
Then,
(14)A=[a11a12a13⋯a1n-ka1n-a11-a12⋯-a1(n-1)-ka2n-a21-a22⋯-a2(n-1)⋮⋮⋮⋱⋮-ka(n-1)n-a(n-1)1-a(n-1)2⋯-a(n-1)(n-1)](ka11,ka12,ka13,…,ka1n)=(-kann,-an1,-an2,…,-an(n-1)).
Thus, we have that
(15)A=[a11a12a13⋯a1n-ka1n-a11-a12⋯-a1(n-1)ka1(n-1)ka1na11⋯a1(n-2)⋮⋮⋮⋱⋮-ka12-ka13-ka14⋯-a11]=JCirck([a11,a12,…,a1n]).Theorem 16.
A skewk-circulant matrix JCirck([a0,…,a2m-1]) of order n=2m is diagonalizable.Proof.
WriteC=Circk([a0,…,a2m-1]); then C=a0G0+a1G+a2G2+⋯+a2m-1G2m-1. By Lemma 13,
(16)JC=(a0G0-a1G+a2G2-⋯-a2m-1G2m-1)J.
Thus, we have
(17)C=J(a0G0-a1G+a2G2-⋯-a2m-1G2m-1)J.
By Theorem 7, there exists an invertible matrix V defined in Lemma 14 such that
(18)V-1J(a0G0-a1G+a2G2-⋯-a2m-1G2m-1)JV=diag[ϕ(θ1),ϕ(θ2),…,ϕ(θ2m)],
where ϕ(x)=a0+a1x+a2x2+⋯+a2m-1x2m-1. Then,
(19)(a0G0-a1G+a2G2-⋯-a2m-1G2m-1)JV=JVdiag[ϕ(θ1),ϕ(θ2),…,ϕ(θ2m)].
By (16), we have
(20)JC[v1,v2,…,v2m]=[Jv1,Jv2,…,Jv2m]diag[ϕ(θ1),ϕ(θ2),…,ϕ(θ2m)].
In order to obtain the eigenvalues and eigenvectors of JC, for t=1,…,m, we assume that there exist kt, km+t, and l∈ℂ, such that
(21)JC(ktvt+km+tvm+t)=l(ktvt+km+tvm+t).
Combining this with (20) gives
(22)ktϕ(θt)Jvt+km+tϕ(θm+t)Jvm+t=lktvt+lkm+tvm+t.
Now, we use Lemma 14 to get
(23)ktϕ(θt)vm+t+km+tϕ(θm+t)vt=lkm+tvm+t+lktvt.
Since vt and vm+t are linearly independent, we have
(24)ktϕ(θt)=lkm+t,km+tϕ(θm+t)=lkt.
So, l=±ϕ(θt)ϕ(θm+t), km+t/kt=±ϕ(θt)/ϕ(θm+t). Namely,
(25)JC(ϕ(θm+t)vt+ϕ(θt)vm+t)=ϕ(θt)ϕ(θm+t)(ϕ(θm+t)vt+ϕ(θt)vm+t),JC(ϕ(θm+t)vt-ϕ(θt)vm+t)=-ϕ(θt)ϕ(θm+t)(ϕ(θm+t)vt-ϕ(θt)vm+t).
Let
(26)W=[ϕ(θm+1)v1+ϕ(θ1)vm+1,ϕ(θm+1)v1-ϕ(θ1)vm+1,…,ϕ(θ2m)vm+ϕ(θm)v2m,ϕ(θ2m)vm-ϕ(θm)v2m].
Then(27)JCW=W[ϕ(θ1)ϕ(θm+1)-ϕ(θ1)ϕ(θm+1)⋱ϕ(θm)ϕ(θ2m)-ϕ(θm)ϕ(θ2m)].So,(28)W-1JCW=[ϕ(θ1)ϕ(θm+1)-ϕ(θ1)ϕ(θm+1)⋱ϕ(θm)ϕ(θ2m)-ϕ(θm)ϕ(θ2m)].Corollary 17.
The square roots of an even order skewk-circulant matrix JCirck(a) are as follows:(29)W[ϕ(θ1)ϕ(θm+1)-ϕ(θ1)ϕ(θm+1)⋱ϕ(θm)ϕ(θ2m)-ϕ(θm)ϕ(θ2m)]1/2W-1.Proof.
This is a direct result from (28).Based on Theorem16 and Corollary 17, we give the following algorithm for computing the principal square root of a skew k-circulant matrix.Algorithm 18.
Compute a principal square root of a skewk-circulant matrix A∈ℂ2m×2m.Step
1. Compute ϕ(θj)=∑s=02m-1as(θj)s (j=1,…,2m).Step
2. Compute the eigenvalues of A: ϕ(θ1)ϕ(θm+1),-ϕ(θ1)ϕ(θm+1),…,ϕ(θm)ϕ(θ2m),-ϕ(θm)ϕ(θ2m).Step
3. Compute the square roots of ϕ(θ1)ϕ(θm+1),-ϕ(θ1)ϕ(θm+1),…,ϕ(θm)ϕ(θ2m),-ϕ(θm)ϕ(θ2m) whose arguments should be in (-π/2,π/2).Step
4. Compute (29).Letn=2m. The cost of Step 1 is about O(nlogn) flops by discrete Fourier transform [18]. The cost of Step 2 is O(n). The cost of Step 3 is O(n). Since the matrix multiplication and inversion are equivalent in computational complexity [25], the cost of Step 4 is about O(n2.4) [26]. So, it needs about O(n2.4) flops in total. If we use the Schur method [7] or the method in [18], it needs about O(n3) flops in total. Moreover, our method allows k to be a complex number, whereas the method in [18] only permits k to be a real number.


## 4. Numerical Experiments

We present numerical experiments to compare the algorithms presented in this paper and the standard Schur method with respect to the execution time. The code was implemented in MATLAB 7.0 and run on a Windows-based machine with 2 GB of RAM and Intel Pentium Core Duo CPU running at 2.8 GHz.We gradually increase the order of the matrix by 100 from 100 to 1100 and record the corresponding CPU time. Figure1 shows the execution time for Algorithm 12 and the standard Schur method. Figure 2 compares the execution time for Algorithm 18 and the standard Schur method. From those results, we can confirm that our algorithms are clearly faster than the standard Schur method for computing the square roots of k-circulant matrices and skew k-circulant matrices.Figure 1
Comparison of the CPU time for Algorithm12 and the standard Schur method in logarithmic scale.Figure 2
Comparison of the CPU time for Algorithm18 and the standard Schur method in logarithmic scale.



---

*Source: 601243-2013-11-20.xml*