THE UNI V E R S I TY O:F MICHIGAN SYSTEMS ENGINEERING LABORATORY Department of Electrical Engineering College of Engineering SEL Technical Report No. 4 SOME PROPERTIES OF CIRCULANTS by Frederick Mo Waltz March 1966 This research was supported in part by contract No. DA-36-039-AMC-03733(E) with the.U. S. Army Electronics Command, Fort Monmouth, New Jersey, and in part by contract No. DA-31-124-ARO-D-245 with the U. S. Army Research Office, Durham, North Carolina.

TABLE OF CONTENTS Page v ABSTRACT I. INTRODUCTION II. GENERAL CIRCULANTS III. REAL CIRCULANTS IV. SYMMETRIC CIRCULANTS V. REAL SYMETRIC CIRCULANTS VI. SOME OTHER SPECIAL CLASSES VII. SIMPLIFIED COMPUTATIONS FOR GENERAL REAL CIRCULANTS VIII. SINGULAR VALUE DECOMPOSITIONS OF CIRCULANTS IX. LEFT CIRCULANTS X. CONCLUSIONS XI. REFERENCES 1 2 13 16 18 25 27 33 54 55 ii

ABSTRACT A circulant is a square matrix which is completely determined by its first row in the following manner: The second row is obtained by shifting (t circulating") the first row one position to the right and placing the last entry of the first row in the first position of the second rowo Each succeeding row is determined from the row above it in like manner. Circulants occur in various practical problemso This paper presents certain properties of circulants (Some already published and some new) which render such operations as matrix inversion, the determination of eigenvalues and eigenvectors, and even matrix multiplication considerably simpler than the corresponding operations with general matriceso Basic to the simplified procedures is the fact that all circulants of a given size (N x N) have the same eigenvector matrix, which is easily determined from the N Nth roots of unity. Further simplifications result when the circulant is real or symmetric. In fact, if the circulant is both real and symmetric, the eigenvector matrix applicable to general circulants can be replaced by a real eigenvector matrix, and all the operations become even simpler. It then becomes possible to invert an arbitrary N x N real symmetric circulant on a digital. computer using at most N+2 variable storage locationso Singular-value decompositions of circulants are also discussed, as are many of the properties of "left-circulants"; i.e., matrices in which each succeeding row is obtained by circulating the row above to the left, rather than to the right. v

I. INTRODUCTION Square matrices A of the form a0 a1... aN-2 aN-I aN-1 a0 ~. aN-3 aN_2 * * * ( A =.... (1) a2 a3.. a0 a1 al a2.. aN_1 a0 are called circulants. Note that each row is equal to the preceding row shifted one place to the right, with the last element moved to the beginning of the row. Circulants have a number of practical applications in diverse fields (see Refs. 1 and 2 and the references listed therein). Computations of eigenvalues, inverses, and singular values of circulants are much simpler than corresponding computations for general matrices of the same size, and for this reason circulants are profitably studied as a special class. The aim of this report is to bring together in one place various useful properties of circulants. The results are presented as a series of lemmas and theorems. Some of these proofs repeat or parallel results given in the references, but are included here for the sake of continuity. The specialized results given here for real symmetric circulants, the simplified computational procedures, the singular value decompositions, and all of the material on left circulants are believed by the author to be original contributions. 1

II. GENERAL CIRCULANTS We first study circulants in which the elements ao, al,...aN_1 of A are allowed to be complex numbers, and begin by making the following definitionso Let a denote the N-component column vector which characterizes the circulant A; that is, let a be the column vector with elements equal to the elements of the first row of A: a0 al aNl a = (2) Let X be the N x N matrix whose columns are the column vectors x-k 1 rk 2 rk N-1 rk k = 01 1) a 0 0 )N-1 (3) where rk is one of the k-th roots of unity, namely rk = exp (jk 2) (4) Thus 2

1 1 1 1 rl r2 1 1 2 rN (5) 1 N-1 rl N-1 rN_ Finally, let'0, r1...r'N-1 denote the eigenvalues of A, and let 0no I1 *N 1 TI0 07 \1 and H = (6) 0 TN-1_ Lemma 1: X is symmetric; i.e., T X = X where the superscripted T denotes transposition. Proof: This follows from the fact that xmk, the element of X in the (m + l)-th row and (k + l)-tti column, satisfies m m Xk rk = [exp (jkG)] Xmk k = exp (jkme) = [exp (jm)] = r = m Xkm for k,m = 0,1,...,N-1 where xkm is the element of X in the (k+l)-th row and (m+l)-th column, and where here, as henceforth, 9 denotes the quantity 2rt/N. Therefore X is symmetric. Q.E.D.

Because of the symmetry of X, no distinction will be made henceforth T between X and Xo A fundamental property of circulants, which underlies all other results given below, can now be stated, as follows: Theorem 1: The eigenvalues of A are given by p~2. N-l k = aO + al rk + a2 rk + *' * + aN-1 k )k = 0)11...,TJ-l (7) The vectors x, xl,.. XN 1 are the corresponding eigenvectors. In vectormatrix notation, these statements can be summarized as = X a AX = XH or A = XHX (8) (9) Proof: For each XKk k = 0,1,...,N-1, A k aNl a al a1 a0 aN1 aN_2 1 rk rN_ k. a2 a _ a0 + a rk + aN-1 + a rk + al + a2 rk + ~. + aN-2. + a N-3 + aN-1 N-2 rk N-2 r k N-2 rk N-l + aN-l rk + a rN-1 N-2 k N-1 + a rN Ok _

a0 + al rk' rk(a0 + a r + rN(ao + al r + N-1-" + aN-1 rk o + N-1 k ) ( + + aN -1 = (a +ar +...+ aNrk ) lk aN-ik 1 rk a Nrk. N The next-to-last step above follows from the fact that rk = 1 or, equivalently, m m+N rk = rk, k, m 0,+1,+2,... From the last step we see that xk is an eigenN-1 vector of A and that the corresponding eigenvalue is (aO + a1 rk +. + aNlrk ), as claimed, Equations 8 and 9 then follow at once from the definition of matrix multiplication, and from the symmetry of X. QoE.Do Next we note certain other properties of the eigenvector matrix X. Lemma 2: The columns XoXl,..xN1 of X are orthogonal to each other and have normTN in terms of the Hermitian inner product* N-1 (-2 I'Xk) = Xmh mk mO (10) and the norm generated by this inner product, of the vector xho Hence where xmh is the (m+l)-th element 1 - N N (11) *A line over a scalar quantity denotes the complex conjugate of that quantityo A line over a vector or matrix quantity signifies that each element of the vector or matrix is to be replaced by its complex conjugate. 5

Proof: Consider any two of the vectors xh and Xk, and form their inner product: N-1 N-1 (xh, x) = Z exp (jmhO) exp (-jmke) = exp [jm(h-k)O ] m=O m=O (Here, as before, the quantity 2- has been denoted by 8o ) We recognize this N as a geometric series with common ratio exp[j(h-k)G] and initial term unityo Therefore, for h i k N (Xh, x k) 1 - [exp j(h-k)e] = 1 - exp j(h-k)NO = 1 - 1 1 - exp j(h-k)e 1 - exp j(h-k)e 1 - exp j(h-k)Q For h k, each term of the summation is equal to unity, so that (xk, xk) = 11l2 = N and llxkll = N From this and from the symmetry of X, it follows that XX = XX = NI or 1 - -l 1X(- ) (1 X)X = I, where I is the identity matrix. Hence X = - X, as N N N claimed~ Q.E.Do Substitution of this result into Eq. 9 shows that every circulant can be decomposed into a product of matrices of the form 1 A = X HX (12) Theorem 1 states that every circulant can be decomposed in a certain formo The following theorem states the converse. Theorem 2: An N x N matrix A is a circulant if it can be decomposed as follows: 6

A =XHX XHX (13) N where X is as defined above and H is a diagonal matrix with the eigenvalues of A as diagonal elements. Proof~ Assume that A can be decomposed in the form -XHX, and let n be the N N-component column vector of eigenvalues of A (i.eo, a_ consists of the diagonal 1entries of H, as always)o Let b = N X, and let B be the circulant characterized T by b (ioeo, the circulant having b as its first row). Then, from Eq. 8 and Lemma 2, the eigenvalues of B are given by Xb = X(-X1 ) = Since B is by definition a circulant, it follows from Eq. 12 that B can be written as B HX N Therefore B = A, and therefore A is a circulant. The equivalence of the two expressions XHX 1 and XHX given for the decomposition of A follows from N Lemma 2, of course. Q,E.D. Involved in the proof of Theorem 2 was the construction of a circulant having given eigenvalues. This is a useful result in its own right, and will therefore be presented as a lemmao Lemma 3: A circulant B having specified eigenvalues* r_ can be constructed T by choosing b as the first row of B, where *Note, of course, that a different circulant B results if the same eigenvalues are arranged in different order in the vector jo 7

b -- -X (14) - N Proof: See proof of Theorem 2. We have shown that every circulant of a given order N (i.e., every N x N circulant) has the same eigenvector matrix X (Theorem 1), and that every matrix having X as its eigenvector matrix is a circulant (Theorem 2). Many simple and convenient properties of circulants follow from these facts. Some of these are given below Lemma 4: Sums and differences of circulants of the same order are circulants, and the eigenvalues of the result are the corresponding sums or differences of the corresponding eigenvalues of the original circulants. -1 Proof: Let A and B be circulants of order No Write A = XHAX and B = XHBX 1 Then A ~ B = [XHAX-1] ~ [XHBX 1] = X[H A+ HB]X1. HA and HB are diagonal matrices, and therefore [HA ~ HB] is also. Therefore A ~ B has the form required by Theorem 2, and consequently is a circulant. The generalization to more than two matrices is obvious QEoDo Lemma 5: Products of circulants of the same order are circulants. The resulting circulant is not affected by the order in which the factors are taken. Proof: Let A and B be circulants of the same order N. Since A and B are circulants, they can be decomposed as A = XHAX-1 and B = XHBX'1. Thus AB - XHAHBX and BA = XHBHAX1 o But since HA and HB are diagonal matrices, they commute, so that AB = BA. Furthermore, HA HB = HB HA is also a diagonal matrix, so that AB = BA is of the form required by Theorem 2, and hence is a circulant. Note ease with which the inverse of a circulant can be obtained: 8

Lemma 6: If a circulant A has an inverse, then the inverse A- is a circulant, and is characterized by -1 b X [X a] (15) -1 where [X a] denotes the vector obtained by replacing each component of the vector X a by its reciprocal. This inverse exists if every component of X a is different from zero. -1 Proof: Since A is a circulant, it can be expressed in the form A = XHX Its inverse, if it exists, is thus given by -1 [XHX]- XH- 1 XH (16) N and is therefore a circulant, by Theorem 2. Also by Theorem 2, the diagonal elements 0 1'.l'**') N-1 of H are given by X a, so that H exists if every component of X a is nonzero. Equation 15 then follows from Eqs. 8 and 14. Q.E.D. + Lemma 7: The pseudo-inverse* A of a circulant A (obtained by replacing all nonzero eigenvalues of A by their reciprocals and leaving zero eigenvalues unchanged in the decomposition A = XHX ) is a circulant. + Proof: By the definition of the pseudo-inverse, A is expressible in the form required by Theorem 2, and hence is a circulant. Q.E.D. On the basis of these lemmas and of various properties of associativity, commutivity, distributivity, etc., inherited from matrix addition and multiplication, it is easily shown that circulants of a given order *This pseudo-inverse is a special case of the Penrose pseudo-inverse applicable to square matrices. See Ref. 5. 9

1) form a commutative group with respect to matrix addition, with the zero matrix (itself a circulant) acting as the unit element; 2) form a commutative semi-group with respect to matrix multiplication having a unit element (the identity matrix, itself a circulant)o Circulants of a given order therefore form a commutative ring having a unit element with respect to multiplication. They fail to form a field because some circulants have no multiplicative inverseo The following two lemmas allow the evaluation of I||111 without actual computation of i, and give an upper bound on the maximum modulus of any component of A, which is also an upper bound* on IIAI. Lemma 8: lll - ETN lal|| (17) where the norm is as defined in Lemma lo Proof: From the definition of the norm and from Eq. 8, 1 1 1 2-W (^) [ - T]2 a X X a] From. Lemmas 1 and 2, xx = xx = X(NX 1) = NI 1 1 Therefore HIl= T - [Na a 2 N[a]2 = N |Ia|| Q.EDo. *IIAII is here defined as max IIAxI It can be shown that for circulants IIAII = _, o Ioxllx max IT i i 10

N-1 Le rmma9 ik < lal k=0 o10,N-l (18) m=O N-1 m Proof~ From Eqo 7, k = rk am, so that m=O N-1 N-1 N-1 N-1 kl I r aml < Irk m = I Irk la I la l iik - m m.=O m=O m m=O since rmi 1 for all k and m. Q.EoDo Other properties of circulants can be derived just as easily. For instance, it can be shown that, if they exist, rational or irrational powers of circulants are circulants; that, if they exist, general functions of circulants are cirk k-l culants; that polynomials of the form Z + Ak_1 Z +... + A Z + AO, where k-i 1 0 Akl-,...,A0 are N x N circulants and Z is an unknown N x N matrix, have easily determined families of zeroes, each member of which is a circulant; etc, Other convenient properties possessed by special classes of circulants are developed in the following sections, In discussing these special classes it will prove enlightening to investigate the number of degrees of freedom of circulants of various types; that is, the number of independent choices that must be made in order to specify the circulant completelyo As a reference point for these later discussions, we note that the circulants so far considered have 2N degrees of freedom-the N real parts and N imaginary parts of the elements aOal, oo aN1 of ao The circulant property then determines the remaining elements of Ao Furthermore, because each choice of a uniquely determines an a (Theorem 1) and vice versa (Lemma 3)., it is not surprising that there are 2N degrees of freedom in volved in the choice of an — the N real parts and the N imaginary parts of the 11

elements qO., r11 ~ *.lN-l There are no additional degrees of freedom, since X must be as specified by Eqo 5. Thus there is a 1:1 correspondence between N x N circulants and points in N-dimensional complex Euclidean space, so that circulants can be regarded as elements of an N-dimensional complex vector space. 12

IIIo REAL CIRCULANTS If the elements ao, al, o.., aN 1 of A are required to be real, as they are in many of the practical applications of circulants, then clearly only N degrees of freedom remain in the choice of A. Similarly, if we wish to choose an i_ so as to generate a real circulant by means by Lemma 3, there can be only N degrees of freedom We now investigate the restrictions on j_ which are implied by the realness of ao Theorem _o The eigenvlaues of real circulants occur in complex conjugate pairs, w:th the exceptions of r0 and, if N is even, N/2, which are not necessarily paired and must be realo Thus,'I' N - k " 1, N-i -1 N odd k=l2,o.., <, — 2 N even _ 2 (19) Proof N-1 m =kL =am rk m=O N-1 m.'NL-k - m N-k m=0 m m But rNk = rk, since N k- rN k = (exp [j(Nk)6] = exp [jm(N-k)O] = [ e p-kN ) [exp(jmrrie)] [exp(-jmk9)] = exp(-jmkO) = exp(jmk~) = r Thus N-l RN-k = Z am rk, which, because of the realness of a, is clearly the complex ff pO JN-1 conjugate of the expression given above for TB k Since 0 = C a, r0 is realo m=O 13

N-1 For N even, rthat T/2 (-1) a, which is also that real. Q.E.D. N/r = mwisa real Q m=0 Lemma 10: The converse of Theorem 3 is true. That is, the circulant which corresponds to any I of the form given by Theorem 3 is real. Proof: Let I have the stated form. Such an a corresponds to a circulant B 1 - characterized by b = -X, from Lemma 3. Assume that N is odd. Then, for k = 0,1,..., N-i, N-1 \ (N-l)/2 1 k k k bk =N ( r m = N o + (rm + rN-m nN-m)] m=0 m=l (N-l)/2 - I1 + E (r + Tm + rm Ti)] m=l which is always real. This last step follows from the assumed form of r and from the fact that k k rNm = exp [jk(N-m)E] = exp(-jkm@) = rm k A similar argument, in which both 10 and (-1) BN/2 are taken outside the summation sign, leads to the stated conclusion for even N. Q.E.D. There are therefore N degrees of freedom associated with T —if N is odd, the real part of 0O and the real and imaginary parts of ril, Q2''. (N1)/2; if N is even, the real parts of q and TN/2, plus the real and imaginary parts of T'1' Ti2''". (N-2)/2' This reduces the amount of computation required to determine N+l N+2 i, since only 2 or 2 eigenvalues need be computed by Eq. 7, the remaining eigenvalues being obtained by taking complex conjugates, as indicated by Eq. 19. 14

The following result has some practical application in determining the maximum or minimum eigenvalue of A, and hence the norm of A, in special cases. Lemma 11: If every element of a is real and has the same sign, i oe, if a) am > 0 m = 01,... N-1 or if b) am 0 m = 0,1,.,N-1 then an eigenvalue of A having maximum absolute value is TO. N-l N-l is Proof: For case a), 1HkI < j lam! = am = 7O1 from Lemma 9 and Eqo N-l m=O N-1 m=O 7o For case b), klI < aml = - T a = - I, by the same argum=O m=O ments QoEDo 15

IV. SYMMETRIC CIRCULANTS In this section we again allow the elements of A to be complex, but require T that A be symmetric, i.e., that A = A, or, equivalently, that -N1 N odd 2 ak =aN-k k=1,2,..., (20) N —2 N even 2 In this case N+l degrees of freedom remain if N is odd-namely, the real and imaginary parts of ao, al, a2,...,a(N )/2. If N is even, there are N + 2 degrees of freedom-the real and imaginary parts of ao, al,...,aN/2. These restrictions on A impose restrictions on X as follows: Theorem 4: The eigenvalues of a symmetric (not necessarily real) circulant occur in pairs, with the exceptions of rO and, if N is even, qN/2' which are not necessarily paired. Thus N-1 N odd N odd 2 TN-k = k' k=1,2,...,< (21) N-2 N even _ 2 N-l Proof: Assume that N is odd. Then for k = 1,2,..., 2 N-1 (N-1)/2 (N-1)/2 = Z am r =ao + am(r + rk ) a + a (r + rk k k km k 0 k k m=O m=l m=l (N-1)/2 _v m m Similarly, rN-k = aO + a(rk+ rNk + r- But since m=l 16

m m N-l r = exp[jm(N-k)8] = exp(-jmkO = rk, it follows that nk = nN-k,k=O,l,..., - N-k 2 as claimed. A similar argument establishes the stated result for N even. Q.E.D. Lemma 12: The converse of Theorem 4 is true. That is, the circulant which corresponds to any 1 of the form given by Theorem 4 is symmetric. Proof: Let n have the stated form. Such an j corresponds to a circulant B 1characterized by b = X T, from Lemma 3. Assume that N is odd. Then, for N-l k = ly..., 2 N-l (N-1)/2 1 k 1 k k bk N r = N [O + (r nm + rN )] = m \ L -m N-m m=O m=l (N-l)/2 i k - I + Timr + k N 0 m N -m m=l Similarly, (N-l)/2 1 rN -k N-k b - [ + E I ( r + rNm )] N-k = N [r0 +, Tm( + m-mN-k m=l N-k k Td.N-k But, as is easily shown, rN-k = r and r = so that b b as m N-N- m kN- = k' as claimed. A similar argument holds for N even. Q.E.D. There are thus the required number of degrees of freedom in j: if N is odd, N+l the N + 1 real and imaginary parts of the 2 eigenvalues Ti0, l'-,.. T(N-1)/2; N if N is even, the N + 2 real and imaginary parts of the 2 + 1 eigenvalues T0' 11' N..' N/2. Therefore, in this special case too the use of circulants simplifies the computation of the eigenvalues of A. 17

V o EAL SYMMETRIC CIRCULANTS A class of circulants having important practical applications (see Refo 2, for example) is the class of real symmetric circulants. The conditions on - which correspond to imposing these conditions on A are easily obtained by cormbining the requirements for real circulants and symmetric circulantso We put this in the form of a theorem. Theorem 5: The eigenvalues of a real symmetric circulant are real and satisfy (N-1)/2 N odd N-k = k k=l,2,..., (N-2)/2 N even Proof: As noted above, the proof follows at once from Theorems 3 and 4, For real symmetric circulants, the procedure for computing the eigenvalues can be even further reduced, for the following reasons: 1) Because both a and I are known to be real, the imaginary part of the matrix X can be discarded in applying Eqo 8, 2) Because of the pairing of the eigenvalues qk and TNk' only N odd r(N-l)/2 N od rO' rl' *' LN/2 N even need be computedo 5) Symmetries in the real parts of the elements of X allow further reduction in the number of computations requiredo 18

To illustrate these points, let us define 1 1 1 cos E 1 cos 2Q 1 cos 28 cos 4e e o ~ 1 o. cos MO.. cos 2MG (22) 2 1 cos MG cos 2MO.. cos M f(N-l)/2 N odd where M /2 (2) IN/2 N even and, as always, 0 = 2A/N. We can then prove the following theorem: Theorem 6: If A is a real symmetric circulant, its eigenvalues are given by ~0 T1 J(N-l) /2 T0 T1 o T'(N-2) TN/2 a - 0 2a1 2a(N-1)/2 a 0 2a o 2a(N-2) /2 aN/2 (24) N odd N even /2 19

The remaining eigenvalues can be evaluated by using the pairing relationships of Theorem 5. Proof: Write X and X = XR + jXI, where XR and XI are real. Then 7 = X a = XR a + jXI a. Because XI and a are real, jXI a is pure imaginary. But, from Theorem 5, j must be real, so that XI a must be zero and r = XR a Therefore, the first M + 1 eigenvalues are given by 710 1 1 1.. 1 a0 1 cos 9 cos 29... cos (N-l)9 == | 1 cos 28 cos 49... cos 2(N-1)9 al TrMj 1 cos MS cos 2MO... cos (N-1)ME _aN-l_ since Re [exp(jkmO)] = cos kme. Now consider the case where N is odd, and rewrite this equation as -o[ 1 1... 1 1... 1 a0 1 cos e.. c os M@ cos(M+l)9... cos(N-l)G Tl1 1 cos 2... cos 2M9 cos 2(M+l)G... cos 2(N-l)9 aM 8M+1 1 cos MO... cos M O cos M(M+1)e... os M(N-1)_ aN1 Note(from the definition of the cosine) that cos k(N-m)G = cos kmO and (from the symmetry assumption) that aN-m = am, for k, m = 1,2,...,M. Thus, the expression for Tk, 20

kk = aO + al cos k + a2 cos 2k +... + aN-l cos k(N-l)O can be rearranged as [k = aO + [al cos kO + aNl cos k(N-l)O] +... + [aM cos kM9 + aM+l cos k(M+l)E] = a0 + 2a1 cos kO +... + 2aM cos kMO. This establishes the validity of Eq. 24 for N odd. The proof for N even is similar, and is omitted here. Q.E.D. The practical significance of this theorem becomes clear when we note that the already greatly simplified problem of finding the eigenvalues of a real circulant A by carrying out the multiplication of an N x N complex matrix and a real N-vector has been reduced to the multiplication of an (M+l)x(M+l) real matrix by a real (M+l) vector-a reduction from approximately 2N multiplications and 2(N-l) additions, for each of N eigenvalues, to M+l multiplications and M additions for each of M+l eigenvalues. This amounts to a reduction of almost 8 to 1 in the number of computations. An even further reduction is possible. It turns out that every cosine appearing anywhere in the matrix Y also appears somewhere in the second row of Y, so that only M cosines must be computed in order to compute Y. The pattern is as follows: Let Yk = cos k9, k=0O,l...,M. Imagine these M+l values arranged in a cyclic pattern of the form YO)Yll * * * -J)'YYMlMYMYM-l * * YYYl* * *'YM-lYM)YMYM-l) * * *Y1YOYl * * for N odd and YO'yly' yM-l'YMYyM- Ml' *',YyYO'yl' *, Y. M-.'.YMl' M-l'*' y.'Yl'YO'lyl'... for N even. 21

The first row of Y is then obtained by starting with y0 and indexing none at a time (i.e., yO,yO,YOYO,y...); the second row is obtained by starting with YO and indexing one at a time (i.e., yO,yl,y2,*.); the third row is obtained by starting with yO and indexing two at a time (i.e., yO,y2,y4,y6,...); and so on. Alternatively, the j-th element of the i-th row of Y is given by Yij = Yp where p =m _< M and where m is computed as the remainder, mod N, of hN-m m > M the expression (i-l).(j-l). Taking advantage of these simplifications and symmetries, one can find the eigenvalues of or invert an N x N real symmetric circulant by using only 1 N od memory locations* for storage of the matrix A, then its LN+2 N evenj eigenvalues, and then its inverse. (Because A and its inverse are symmetric and circulant, we of course need store only part of the vectors which characterize A and its inverse). Some of the results derived for general circulant matrices in the previous sections take on an even simpler form for real symmetric circulants. For instance, Lemma 13: The real symmetric N x N circulant having the eigenvalues Ol *.''."M is characterized by the vector b = [bo,bl,...,bN1], where *Not including the accumulator, two storage locations for indices, one storage location for N, and storage for the program itself. If the information about the original matrix is not to be destroyed in the process, M additional locations are needed. 22

01 2 1 b] 2r 1 = Y ~ (N odd) or = Y (N even) iJ JM mM | M-l NM and the remaining elements of b are obtained by use of the symmetry conditionso Proof: Since for real symmetric circulants a and m possess the same symmetries, the arguments used in the proof of Theorem 6 can be used here to obtain the stated result from Lemma 35 Q.E,D. Also of interest is the fact that Lemmas 4, 5, 6, and 7 can be proven with the word "circulant" replaced by "real symmetric circulant" throughout, and hence that real symmetric circulants of a given order also form a commutative ring having a unit element with respect to multiplicationo One other point is worthy of mention hereo Whereas in the case of general real circulants, the eigenvectors occur in complex conjugate pairs, it is possible to write an eigenvector matrix for real symmetric circulants (call it W) which is realo This results from the fact that for real symmetric circulants the eigenvalues occur in pairs, so that the two (complex conjugate) eigenvectors Xk and XNd k spanning the subspaces corresponding to a given pair of eigenval-ues Tk and TN-k can be replaced by any other orthogonal pair spanning the same subpaceo It turns out that there is a convenient pair of real orthonormal eigenvectors wk and WN-k, spanning each such two-dimensional subspace, namely, k -2 xk 2 -k Re( x) + Im k) and

w +j - = Re(x ) - Im(Xk) -N-k 2 -k 2 -kN-k k The eigenvectors corresponding to rO and, if N is even, fN/2' are real in any case, of course. Then, by using the definition of xk and various trigonometric identities, W can be written as 1 1 o o o 1 1 cos G + sin 9 o o. cos(N-1)9 + sin(N-l)O 1 cos 29 + sin 29.. o cos 2(N-1)9 + sin 2(N-l)G W. 1 cos(N-l)8 + sin(N-1)9 0 G o cos(N-l) 2 + sin(N-l)2 Lemma 14~ If, in all the above theorems and lemmas applicable to the matrix X and/or to general circulants, the word "circulant" is replaced by "real symmetric circulant" and the matrices X and X are replaced by W, and if, in Theorem 2 and Lemma 3 the restriction is added that _ be of the form appropriate to real symmetric circulants (see Theorem 5), then all remain valido Proof~ The proof is omitted hereo It is straightforward, and depends on the fact that the eigenvalues of a real symmetric circulant occur in pairs, so that pairs of x-vectors spanning two-dimensional subspaces can be replaced by pairs of w-vectors spanning the same subspaceso

VI. SOME OTHER SPEICAL CLASSES The main results of the previous three sections are summarized in Table' I. along with the corresponding results for four additional special classes of circulants: "anti-symmetric," Hermitian (self-adjoint), skew-symmetric, and skewHermitian. Proofs of these results either follow from properties of matrices in general (e.g., those for skew-Hermitian circulants) or else are similar to proofs already given, and are omitted here. 25

TABLE I Condition Degrees of Freedom Class Conditions* on a Conditions* on on A N odd N even Real A = A ao..aN_l real l N |' TN/2 real; Tk = qN-k Symmetric A = A | aN-k ak N+l N+2 |k = N-k T A +A = Anti- aN = -ak BN/2 = 90 Symmetric diagonal Nk N+l N matrix aN/2 =0. TN-k = 2rO0 - k a0, aN/2 real Hermitian AA N N | -. N,1 real aN-k ak Skew- A =-AT a aN/ N- N-2 /2 Symmetric aN-k = N = - N-k -k.,N-k - -_k aoj., aN/2 pure A = -A imaginary N N * pure imaginary Hermitian aNk = -ak' Real - T aO'""aNl i real r- | N +' "'N real A =A =A +1 Symmetric aNk = ak 2 2 N-k = *In this table, conditions given for aN/2 andn T/2 apply only when N is even, and the index k always runs from 1 to (N-l)/2 for N odd and from 1 to (N-2)/2 for N even.

VII. SIMPLIFIED COMPUTATIONS FOR GENERAL REAL CIRCULANTS We have seen that the process of computing the eigenvalues of real symmetric circulants can be greatly simplified by taking advantage of the symetries of X and a. A significant reduction (approximately 4 to 1) can also be achieved for general real circulants, based on these results. The key idea here is the breaking up of the circulant into a symmetric part and a skew-symmetric part (a process that can always be carried out uniquely). We begin by making some additional definitions: Let b be the symmetric part of a, and let c be the skew-symmetric part; i.e., b0=a0; bk^ = (k + aN-k) 1 k=1,2,...,N-l (25) c =; ck = (ak - aN) Let B and C denote the circulants characterized by b and.c, respectively. Note that, since a is real, b and c are also. Note also that B is symmetric and C is skew-symmetric (See Table I). Thus A = B+C a = b+c Finally, let O 0 0..-. 0 O sin O sin 2... sin MO Z =... (26) 0 sin MO sin 2MO... sin M e 27

N-l N where, as always, M = -1 for N odd and N for N even. 2 2 We note that jZ is simply the imaginary part of the upper left-hand quarter of X, just as the matrix Y defined above was the real part of this same submatrix We can now state Theorem 7 The eigenvalues T0' 1,'.'lM of the real circulant A are given by q0 TI1 _IM_ ~m bo0 2b1 2b2 2bM 2b1 2b + jz +jZ Co 2c1 2c 2 2CM. M N odd (27) 2bM bM N even The remaining eigenvalues are given by TrN-k lk Also, rj0 and, (N-1)/2 -- ikl,2,...,: iN-2)/2 if N is even, IN/2' are real. N odd N even 28

Proof: Write the equation m = X a (from Theorem 1) as _ = (XR + jXI) (b + c) where, as before, XR is the real part of X and jXI is the imaginary part. From Theorem 5, X b is real, since it is the eigenvalue vector corresponding to the real symmetric circulant B. Hence jXI b = O. Now, note that C is real and skew-symmetric From Table I, this means that the eigenvalues X c of C must satisfy the conditions given there for both cases. This implies that the eigenvalues of C, which are expressible as XRC + jXIc, are pure imaginary, and hence t hat XRC = Thus _ = XRb + JXIc; in other words, the symmetric part of A gives rise to the real part of j_ and the skew-symmetric part of A gives rise to the imaginary part of ro The replacement of the term XIc by the term c c 0. 2c1 2c1 Z O or Z 2cM 2 CM is then easily carried out along the same lines used in replacing XR by Y in the proof of Theorem 6. The rest of this theorem is a repetition of parts of 29

of Theorem 5o QoE.D. One other slight simplification might be noted here: For N even, the constant cN/2 is always zero and hence need not be computed. A simplified procedure for inverting a general real circulant based on these results, is also possible, Theorem 8: Let A be a real circulant and let j be its eigenvalue vector. Let A be invertible (i.e., let a be such that Tk # 0, k = 0,1,...,N-l), and let the inverse be denoted by Do Let 1 k = O,l,... N-l --- = 5k + J~k " k where 5k and 4k are real. Then D is a real circulant characterized by d b + c, where b 6 c 4|r o 0o 0 o b 261 c 2C1 - Y -51 0; 0 N odd'b 25 c1 21 Y, 1 y o21 c1 1 w Z 1. N even N N bM 2M-l CM |2M-l M_ M M _

>(N-l)/2 N odd bN k =k CN-k -c k=l, 2,... (N-2)/2 N even N-1 N and where, as always, M = for N odd and - for N even. 2 2 Proof: Since A is a real circulant, its eigenvalues occur in complex conjugate pairs Tlk and lN-k (except for ro and rN/2' which are unpaired and real). Thus the reciprocals of these r's satisfy the same conditions, so that D, the inverse of A, is also a real circulant, by Lemma 10. By Lemma 6, 1 - -1 1 - d = N X [X ] = X (6 + j_) N (XR jXI) (- +j ) 1 1 -N i(XR + XI) + j N (XR X ) Since d is real (as noted above), the imaginary part of this expression must be zero, so that d = x R5 + X, d- N N I The reduction of this expression to the form given in the statement of the theorem then follows by the same steps used in the proofs of Theorems 6 and 7, since 6 and I have the same symmetries as b and c of Theorem 7, respectively. Q.E.D. The following lemma is needed in the next section. Lemma 15: Let A be a real circulant characterized by a. Then the eigenT T value vector -X[a0, aNl, a_2...,aa1] of A is the complex conjugate of the eigenvalue vector Xa of A. 51

Proof: The vector [aoa,aN_, o.,al] is of course the vector characterizT T ing AT, and AT is a circulant, so that the above product does indeed give the T eigenvalues of A, The symmetric part of A gives rise to the real part of = X a, and the skew-symmetric part of A gives rise to the imaginary part T of _, as noted aboveo The symmetric parts of A and A are the same, and the skew-symmetric parts of A and AT are negatives of each othero Thus the imagiT nary part of the eigenvalue vector of A is the negative of that of A, and the real parts are the same. Q oEoD 52

VIII. SINGULAR VALUE DECOMPOSITIONS OF CIRCULANTS Singular value decompositions (see Ref. 3) play a key role in Naylor's transform technique for time-varying systems (Ref. 3 and 4), and also offer considerable insight into the properties of matrices as transformations (see Ref. 3)~ The computation of the singular value decomposition of a real circulant is much simpler than that for a general matrix, and turns out to be closely related to the eigenvalue decomposition. These points are explored in the lemmas and theorems to follow. Let us first mention two procedures which can be used to obtain singular value decompositions of a general real N x N matrix A: Form the real, symT metric, positive semi-definite matrix A A, and find its eigenvalues and any set of real orthogonal eigenvectors. (Such a set of real orthogonal eigenT vectors always exists because A A is a normal matrix. See Bellman, Ref. 1, T p. 197.) The eigenvalues of A A are real and non-negative, and the singular values of A are the positive square roots of these eigenvalues. Form a diagonal matrix A with the singular values as diagonal elements, and form a matrix U having the above-noted eigenvectors (normalized to TN and taken in the same order as the corresponding singular values in A) as columns. Finally, let V be any orthonormal matrix (with columns having norm fN) for which 1 T -U AV = A (29) N 1 T This expression, U A V, is called a singular value decomposition of A, and always exists under the conditions given here for A (and, in fact, for much more 33

general conditions, also; see Refo 5)o It turns out that the matrix V can be obtained by replacing all the zero columns* of ATUA+ by any set of orthonormal vectors (normfNN) which are also orthogonal to all the nonzero columns of T + + - T + ATUA+ Of course, if A is invertible, so that A = A, then A UA has no zero columns and V is completely determined by ATUA+. Even here, of course, the decomposition is not necessarily unique, since U may not be unique ** T That is, when two or more of the eigenvalues of A A are equal, there is some freedom in choosing the eigenvectors to span the corresponding subspace. An alternative procedure for finding a singular value decomposition for A is to form the diagonal matrix*** A having the positive square roots of the ~~~T~~~~~~~~T eigenvalues of A A as its diagonal elements, and the matrix V having any corresponding set of real orthonormal eigenvectors (norm N) of A A as its columnso Then U is obtained from A V A by a procedure analogous to that given above for V, and the singular value decomposition is again given by Eq. 29. These decompositions may differ from each other in more than order and sign changes on corresponding columns of U and V unless the singular values are distinct, in which case the two decompositions are equivalent. Lemma 16: The singular values XO, o., N-l of a real circulant A can be expressed in terms of the eigenvalues 1.0, l,..,'N_- as follows~ *A is the pseudo-inverse of A, See Lemma 7 and Ref. 5. **This lack of uniqueness may involve more than changes in the order of the singular values and eigenvectors, or changes in the signs of corresponding columns of U and V Such order and sign variations are regarded here as giving rise to equivalent decomposition. ***It will be the same as the A defined above, except for possible differences in the order of the diagonal elements. 34

o = lnol k I N-k k = 1,2,...,N-1 Since, from Theorem 3, the eigenvalues of a real circulant occur in complex conjugate pairs, (i.e., iN-k =, k=l,2,...,N-1), this can be rewritten as N.M-k k k0 = H = H k N-k k= lkl = IN-kl (N-l)/2 N odd -' k=tl,2,..,. (N-2)/2 N even i I|n |N even N/2 = qN/21 ee Proof: The singular values of a real circulant A characterized by a are the positive square roots of the elements of the column vector XA a, since T A a is the vector which characterizes the real symmetric circulant A A, and T XA a is the eigenvalue vector of A A, by Theorem 1. Application of Eq. 12 gives 1 1 2 XA a X X XHX) a - X H (Xa) where, as always, H is the eigenvalue matrix of A; i.e., its diagonal elements are the corresponding elements of Ti = Xa. Now, since a is real, Xa = Xa =, 2 2 2T so that HXa is simply HJ = [1'0, 11'il.. 19T iN ] From Lemma 2 and from the fact that x = x, k=l,2,..,N-l, if follows that -N-k -k 35

1 0 0. o 0 0 1 O O.,, O 0 0 0 0 1 2 0 0 0 1 0 N 0 0 1 0 0 0 1 0,0 0 It then follows that the singular values of A are | T1 I IT ll ll o QoEoD. Lemma 17: Let A be a real N x N circulant, let A be the diagonal matrix with the singular values K\, l o..,' N1 of A (as defined in Lemma 16) as its diagonal elements, and let U and V (not to be identified as yet with the U and V matrices defined above) be defined as + + U = AWA + W(I- AA ) V = A WA + W(I -AA+) where W is the eigenvector matrix for real symmetric circulants, defined in Section Vo Then U and V are orthonormal matrices, and their columns have norm TN, Proof: Consider V firsto V will have been shown to be orthonormal with - T1 T T column norms ~N if it satisfies V V, or V V = NI We now show that N V does indeed satisfy this equation: V VT =ATW A+ A WA + A WA+ (I - A A ) W + W(I - AA )A WA + W(I - A A) (I - AA)W T + 2 +2 = A W(A ) WA + W(I - A A ) W

since A (I - A A+) is always zero for any A. (Since W is symmetric, we have written W instead of WT here)o Now, we note that (A )2 and (I - A A ) + p +2 satisfy the symmetry requirements of Theorem 5, so that W(A )2 and W(I - AA+ W are real symmetric circulants. Hence they can be rewritten as X(A +)2 and + 2- 1 - X(I - AA ) X. Noting also, from Eqo 12 and Lemma 15, that A = - XHX and N T 1 A =- XHX, we have that T 1 2 — +2V V (J XHX) X(A ) X ( XHX) + X(I - ) X + 2 + 2,XH(A) +HX+X(I -AA) X 2- + 2XHH(A) X + X(I-AA) X - X(A ) X + X(I AA+) X where the second line follows from the first by Lemma 2, the third follows from the second because diagonal matrices commute, and the fourth follows from 2 the third because H H = A, by Lemma 16. Now, A A and (I - A A+) are diagonal + A +2 matrices having only ones and zeroes on the main diagonal, so that A A = (AA ) " + 2 and (I - A +) = (I A A ). Hence V V = X(A A+) X + X(I - A X') X = X(I)X = NI The proof for the orthonormality of U follows similar lineso Q oE.D Theorem 9' Let A be a real N x N circulant, let W be the orthonormal matrix defined in Section V, let A be the diagonal matrix with the singular

values Xo,Xl, oooAXN 1 of A (as defined in Lemma 16) as its diagonal elements, and let U and V be as defined in Lemma 170 Then 1 T A =-WAV N and 1 A = U A W N are singular value decompositions of Ao T T Proof: Note that AA and A A are real symmetric circulants (real because A is real; obviously symmetric; circulants by Lemma 5), so that, from Lemma 14, W may be used as the orthonormal eigenvector matrix called for in each of the above-mentioned procedures for finding singular value decompositions. The theorem then follows at once from these procedures and from Lemma 17. QoEoD. Let us now examine the significance of these resultso The singular value decomposition procedures call for replacing the zero columns of A W A and T + A W A by any set of orthonormal column vectors normal to all nonzero column of A W A+ and AT W A+, respectively. Lemma 17 s.hows that the columns of W corresponding to the zero columns of these matrices will always suffice, regardless of the other singular valueso This somewhat surprising result follows from the fact (to be shown below) that the very same partitioning of the whole N-dimensional space into one- and two-dimensional subspaces observed in the eigenvalue decomposition of real symmetric circulants occurs here also. This result is expressed in the following lemmas, which also give simple expressions for finding the nonzero columns of A W A and A W A from W and H without matrix multiplication. 38

Lemma 18: The columns v, l,..,vN 1 of the matrix V appearing in Lemma -0 17 and Theorem 9 can be obtained from the expressions Y0 = sgn o10 0 rw o ~ Re k Imk -k -- - - - -- k | k o _N-k k N-k 1 Re71k I_ I flkl ReT k Imk r(N-1)/2 N odd N-k = w iN-k+ w k1 2,..., -lNkl -lN-kl.., N-2)/2 N even vN/2 = sgn nN/2 N/2 N even, rN/2 # 0 When =0,. Whe and = w When When 0, When k N -k -k -k -N-k -N-k +1, >0 1TN/2 = 0VN/2 = WN/2 Here sgn T = _ Proof~ Let us look at a particular column vk of V (0<k.< N/2). If k = 0, T 4 then the first term of the expression V = A W A + W(I - A A+) makes no contribution to this column, since the corresponding column of A+ is then zero. The second term contributes wk If nk = 0, then the second term contributes nothing and the first term yields T 1 T 1 T - v = AT W[O..,0,...,0] = A w = XHX w -k k ink -k N lkl -k by Lemmas 16 and 15. From the definitions of wk and WNk given in Section V, it follows that - X1-j + N T x_= [o,.oo,, -,,0,.ooO] N 0 T X-k, 2 2 39

where, as in the steps to follow, the two nonzero entries are in the (k + l)-th and (N-k+l)-th positionso Then T HXk = [0, o,O, N.k n,oo,0 N l I,. 0 -o., O] -k 2 2 1 -- Tk 1-j + k l+j v = XHXw x + -- x -k Nj|rk| -k | 1i 2 k I 1 2 -N-k But, by inverting the equations of Section V which define wk and w of 2k and 2-NN-k- we obtain of xk and EN-k' we obtain in terms xk w + 2- N-k and k = k w + - N-k 2 -k 2 N-k 2 2 which, upon substitution into the above expression for Vk, yield the results stated in the lemmao The other results follow in similar fashion QoEoDo Lemma 19: The columns u-U, Ul, o' - 0- of the matrix U appearing in Lemma 17 and Theorem 9 can be obtained from the expressions -0 = sgn TQ0 0 TI A o Re'lk Uk = wk k + ke I-k.N-k — k IN-k I Ikl Imlk n I ]-N-k nk Imk I N k integer, 0 < k 2 2 uN/2 sgn'lN/2 WN/2 N even, TN/2 0 When q = 0, -0 -= o. When Ik = N-k =, k = TN/2 = o, uN/2 = N/2 ~ wk and u-k = WN k When -k'N-k -:~-N-k

Proof: The proof parallels that of Lemma 18 exactly except that the de1 1- T composition - XHX of A is used in place of the decomposition - XHX of A o QoEDo N N input basis or the output basis for a singular value decomposition of a real circulantO It is easily shown that there are special cases where it is both the input basis and the output basis, or where one basis or the other differs from W only in the signs of some of its basis vectors Lemma 20: Let A be a real symmetric circulanto Then the matrices U and 1 T 1 V appearing in the singular value decompositions A = 1 W A V and A - U A W N N (as given by Lemma 17) are equal, and differ from W only in the signs of some of their columns, as follows: U V = W[sgn H] where [sgn H] is by definition a diagonal matrix with diagonal elements sgn n0, sgn 1' ~, o, sgn 1N-1 and where, in this case, sgn T = [ - O Proof: We note from Theorem 5 that for real symmetric circulants the eigenvalues are real, so that Lemmas 18 and 19 reduce to the stated result. Q.E.Do Lemma 21: Let A be a real, symmetric, positive semidefinite circulant. That is, let A be a real symmetric circulant with non-negative eigenvalues. Then the singular value decompositions given by Theorem 9 both reduce to A 1WAW 1 IWHW N N This is, the eigenvalue and singular value decompositions given above are the same o 41

Proof: The first part of the result follows from Lemma 20, since in this case [sgn H] = I. The second part follows from Lemma 16 and from the real nonnegative nature of the eigenvalues nO, l,'.'. N-l The results of this section can easily be generalized to singular value decompositions of complex matrices, by starting from the eigenvalue decomposition. The singular values must still be real and nonnegative, but the input and output basis vectors may be complex. Let us define "phase" functions of the form. n /HI T n # 0o phase = 1 Br =0 and phase 70 0 phase [phase H] = 0 phase TN-1 We can then state Theorem 10: Let A be a general circulant with eigenvalue matrix H. Then 1 T A = X A (X [phase H]) is a singular value decomposition, where the diagonal elements of the diagonal matrix A are I01, |lll,.-J..lTN_-l. 42

T Proof~ The equation is valid, since A[phase H] = H, X = X, and 1 - A = - XHX, by Eq. 12. Also, the columns of (X[phase H]) form a valid (i.e., orthonormal) input basis, since X is orthonormal, and multiplying a column of X by a constant of unit modulus changes neither the norm of the column nor the subspace spanned by it. Finally, A has the required form, so that this is indeed a singular value decomposition. Q.E.D.

IX. LEFT CIRCULANTS The rather extensive results derived above for circulants might lead one to ask if there are other classes of matrices for which comparable results can be obtainedo Bellman (Refo lpo 235, Exercises 1 and 2) suggests that there are other such classes, based on the roots of general N-th order polynomials N (rather than on the roots of the polynomial r = 1, from which the circulant eigenvector matrix X is derived) Another class of matrices which, to the knowledge of this author, has not been investigated in detail, is the class of left circulants; that is, square matrices of the form 1 2 N-2 a al a2 a3 ~ ~ ~ ^.- aO a1 2 a. aN-1 a0 a2 a3 a4 a0 o a al A = aN-l a0 a1 aN 3 aN-2 (29) which can be seen to resemble circulants except that each row is equal to the row above, circulated to the left rather than to the right-thus the nameo The name "circulant,"without modifier, will be reserved for circulants as originally defined, but in the following discussion, to add emphasis and avoid confusion, circulants, as originally defined, will be referred to as "right circulants ot

Like right circulants, left circulants can be profitably studied as a special class because of simplifications that can be made in the procedures for manipulating them-although the author is not aware of there being any applications in which they arise. They are discussed here because the results obtained above for right circulants offer an excellent basis for deriving and evaluating the sometimes similar and sometimes contrasting properties of left circulants. Let us note first that left circulants of a given order (greater than two) do not all have the same set of eigenvectors. In fact, the eigenvectors depend on the elements of the matrix, in general. For example, consider the general T third-order left circulant A characterized by [aO, al, a2]. Its eigenvalues / r2 2 2 1/2 are (a0 + al + a2), = + [a2 + a + a aal - aa2 + ala2], and -r, and the corresponding eigenvectors are [l,l,1]T, [l,f(r), - 1 - f(')], and T [1, f(-l), - 1 - f(-l.)], where f(rl) = (Tla - ao + a1 a2)/(Tla2 - a2 + aoa). These eigenvectors clearly depend on the values of a0, a1, and a2. Thus, the extensive results obtained above for right circulants (which followed from their all having the same eigenvector matrix X) should not be expected to have analogs in the case of left circulants. Surprisingly, however, there is a decomposition for left circulants which, although not an eigenvalue-type decomposition, has many of the same advantages. Many of the results presented here, including eigenvalue and singular value decompositions will be based on or derived from this decomposition. We begin with the following decomposition theorem. Note that here the quantities TO), 1','' TN-1 appearing in this theorem are in general not the 45

eigenvalues of the left circulant A. We reserve these symbols for the eigenvalues of the right circulant characterized by the same vector ao That is, q is as defined by Eq. 7 or 8. In this section we shall often discuss the properties of left circulants in terms of these same r.qs for convenience. Theorem. 11' Let A be an N x N left circulant characterized by the vector.,ao Then A =- XGX N (30) where X is the same matrix defined above (Eq. 5) for G is a matrix of the form.O 0 0 0 0 0 0 0 0 0 0 0 flN-2 0 rN-1 0 0 0 0 O O right circulants, where (51) 0 0 19l and where the components 0O' ql oo'oN-1 are given by Eqo 7 or 8. Proof: Let us operate on any one of the basis vectors xk of X with the matrix -XGXo Because these vectors are orthonormal with normAN (see Lemma 2), N and because of the particular form of G, the result is N X G X N -4 qk XN-k k= 0 k = 12,,..N-1

Now operate on this same xk with the matr A = -k 2 a0 + a1 rk + a2 rk + N-1 a rk + a + a r + N-2 N-1 a0 rk + a rk + a2 + 2 3 a80 rk + al rk + a2 rk + ix A. The result is.. + a rN-1 N-l k N-2... + aNl rk N-3 + aN-1 rk *+ aNN-1 1 r k -2 rk N-1 = (a0 + ark +... + aNrk ) =k -k - N-1 rk. Qo,o Lk XN-k k= 0 k = 1,2,...,N-1 This is true for each of the vectors xk, k = 0,1,...,N-1. Since these vectors 1 - span the whole N-dimensional space, it then follows that A = -XGX over this N whole space. Q.E.D. Thus, as with right circulants, the partitioning of the N-dimensional space into the two-dimensional subspaces spanned by (x1, x.N-l),(x2, xN_2), etc., plus the one-dimensional subspaces spanned by 20 (and, if N is even, XN/2), crops up again. Here, however, a "rotation" is involved, in that an input x colinear with one of the vectors xk spanning a particular subspace produces an output A x 47

colinear with the other vector spanning the subspace. We now note various properties of left circulants, in a series of lemmaso The first lemma follows obviously from the definition of a left circulant, and the rest are easily established by using the decomposition given by Theorem 11. or by following steps similar to those used in establishing the corresponding lemma for right circulantso Lemma 22: All left circulants are symmetric. Lemma 23: Every matrix which can be decomposed in the form given by Theorem 11 is a left circulanto Lemma 240 Sums and differences of left circulants are left circulantso Lemma 25: The product of two left circulants is a right circulanto Lemma 26: Let L be a left circulant and R a right circulanto Then;LR and RL are left circulants, and LR = RL if and only if R is symmetric. T Lemma 27: Let L1 and L2 be left circulants. The L L = [L2L1] A sufficient (but not necessary) condition that L1 L2 = L2 L1 is that the vectors characterizing L1 and L2 both satisfy conditions of the form given by Eq. 20. + Lemma 28: Let L be a left circulant characterized by a. Then L, the pseudo-inverse of L (which becomes the inverse if the inverse exists), is a left circulant characterized by b - X, where the elements of the column N vector V satisfy the conditions *k = 0 whenever'k = 0 48

l/1O k = 0 Jk = lj> for 0k # O L/TNk k = 1,2, N-1 and where, as always, [ = X ao Lemma 29: Let L and R be left and right circulants, respectively, characterized by the same vector a, and let R be symmetric (i.eo, aN k = ak, k = 1, 2, 0o,0 N-l). Then their pseudo-inverses L and R are left and right circulants, respectively, and are characterized by the same vector b, as given by Lemma 280 Lemma 30: Let L and R be left and right circulants, respectively, charac2 T T T terized by the same vector a. Then L = L L = LTL R R R R Lemma 31: The only left circulants which are also right circulants are characterized by vectors of the form T N odd: a= [a, a0, aO,..,aO] T N even: a = [aO, al, a.0, o.,ao, a1] Thus, odd-order right-and-left circulants have at most one nonzero eigenvalue, T0 = N ao, and even-order right-and-left circulants have at most two nonzero eigenvalues, 0 = N(aO + al)/2 and rN/2 = N(a0 -al)/2. Furthermore, for N = 2 every right circulant is also a left circulant, and vice versa, The decomposition given by Theorem 11, along with the definitions of the vectors wk and wN given in Section V, allow the direct verification of the following eigenvalue decomposition theoremo For simplicity, we limit the theorem to real left circulantso

Theorem 12: Let L be a real left circulant characterized by a, let IO, rly... TIlN-1 be the eigenvalues of the right circulant characterized by the same vector a (see Eq. 7), and let the vectors wo0, wl,..., * 1 be as defined in Section V. Then the eigenvalues y, Y1,',***N-1 of L are YO Yk YN-k 7N/2 = 0 =- k - IN/2 (N-l)/2 N odd k = 1,2,...,' (N-2)/2 N even N even and a corresponding (having norma -N) is orthonormal eigenvector matrix P with columns PO2 E1' *'EN -1 ~0 EN-k -N/2 = w0 -= k +_N-k = Wk+-k -,21, = -k + a wN-k -w/2 N even:N/2 for N odd for N even where ca = 1, p = 0 when_ k = 0 and |kl + Im uk Ca =.. 21 Fk I >when rlk f 0 ITlkl - Im rk = -21 TkI Thus, L may be decomposed as 50

1 T L N P Pr N where r is the diagonal matrix of eigenvalues 70, 71Y * ~7YN 1 Proof: This theorem can be verified directly by showing that each of the vectors pk is an eigenvector with the stated eigenvalue, using Theorem 11 to simplify the computations. The proof is omitted here. Note that, in general, the eigenvectors depend on the values of l9 ooo'qN-L1 and hence are not independent of a. However, as an aside we note also that if all the eigenvalues except i0 and TN/2 are pure imaginary, then the eigenvector matrix P differs from W by no more than the interchanging of certain pairs of columns 2k and JPN-ko Thus, for' these cases the eigenvalue decomposition can be written in terms of W simply by interchanging pairs of eigenvalues in F. We can therefore identify, if we wish, a special class of real left circulants which, in common with real symmetric right circulants, has the matrix W as its eigenvector matrix. This class turns out to be easily specified in terms of the elements of the characterizing vector ao Let us discuss this in terms of the right circulant A characterized by the same vector a. From Table I, we see that a real skew-symmetric right circulant has eigenvalues meeting all these requirements, except that q0 and'N/2 are zero for such a circulant. Thus, if we can find a class of right circulants which have all zero eigenvalues except for these two, which are real, we can add any one of these to any real skew-symmetric right circulant and (by Lemma 4) the resulting right circulant will have the desired eigene value pattern. 51

Upon noting that all the real right-and-left circulants discussed in Lemma 31, have zero eigenvalues, except T0 and TN/2' which are real, the following lemma follows at once: Lemma 52: Any real left circulant L for which the corresponding right circulant A has a symmetric part which is a right-and-left circulant-that is, which has a symmetric part characterized by a vector b of the form [bo) b0, b0..*,b0] for N odd or [b0, bl, b0, bl, b0,...,bl] for N evenhas W as an eigenvector matrix. Such real left circulants have (N + l)/2 degrees of freedom for N odd and (N + 2)/2 for N even. If one wishes, one can use Theorem 12 to identify other special classes of left circulants sharing a common eigenvector matrix (other than W). For instance, the class of real left circulants for which Im rk = 0 for all k = 0, 1,..., N-l share a common eigenvector matrix, and left circulants of this class can be identified as those for which the corresponding right circulant is symmetric. And so on. We can also derive simplified procedures for finding singular value decompositions of left circulants. The proofs can be based either on Theorem 11 or Theorem 12, and are omitted here. Theorem 13: 1 T L = -W A V and L = V A W N N are singular value decompositions of the real left circulant L, where A is a diagonal matrix with diagonal entries T1'1 1 l 1,...i'N _11 and V = L WA + W(I AA+) 52

Lemma 330 obtained from r The columns of the matrix V appearing in Lemma 31 can be and W as follows: 0 = sgn r1 0 O0 Im qk = - k w + -.k -k I Ink l N-k = Imk +k -N k k -N-k 1kl 0 Re'k - N-k Ilk Re rk k -lk k 11Qk I t`I (N-1)/2 for N oda k = 1(N-2 for. (N-2)/2 fcr N even -N/2 = gn TN/2 WN/2 for N even, 1N/2 o When When O0 = = 0o When lk = N 0 AN/ O = o 02 N/ 2k =, vk wk and vN k -= Nk The results derived in this section can readily be used in studying many other properties of real left circulants For instance, one can easily show from Theorem 12 and Lemma 31 that there are no positive definite or negative definite left circulants for N > 2, and that a left circulant can be positive emdef e or negative semidefinite only if it is a right-and-left circulanto Extentions of the eigenvalue and singular value decomposition to complex-valued left circulants is also straightforward, and the results exhibit many more parallels to the corresponding results for right circulants. 553

X. CONCLUSIONS This report has derived and tabulated many properties of circulants. When circulants do arise in practical applications, the results presented here have allowed a.nd will allow great simplifications in certain matrix operations such as inversion. Although it ha.s no known practical applications, the material on left circula.nts has been included both for its own sake and so that it will be available should such practical applications arise 54

XI. REFERENCES 1. R. Bellman, Introduction to Matrix Analysis, Princeton, 1960. 2. F, No Bailey and M, J. Damborg, The Recovery of Clocked Signal Inputs to Linear Dynamic Systems, Cooley Electronics Laboratory Technical Report No 166, The University of Michigan, Ann Arbor, Michigan. 3. Ao Wo Naylor, "Generalized Frequency Response Concepts for TimeVarying, Discrete-Time, Linear Systems," IEEE Transactions on Circuit Theory, Vol. CT-10, No. 3, September 1963. 4. Ao W. Naylor, "A Transform Technique for Multivariable, Time-Varying, Discrete-Time, Linear Systems," Automatica, Vol. 2, pp. 211-2349 1965. 5. R. Penrose, "A Generalized Inverse for Matrices," Proc. Cambridge Philos., Vol. 51, Part 3, pp. 406-413, 1955. 55

DISTRIBUTION LIST. _... _ No. of Copies 2 Commanding Officer, U. S. Army Electronics Command, U. S. Army Electronics Laboratories, Fort Monmouth, New Jersey, Attn: Senior Scientist, Electronic Warfare Division 1 Commanding General, U. S. Army Electronics Proving Ground, Fort Huachuca, Arizona, Attn: Director, Electronic Warfare Department 1 Commanding General, Uo S. Army Materiel Command, Bldg. T-7, Washington 25, D. Co, Attn: AMCRD-DE-E-R 1 Commanding Officer, Signal Corps Electronics Research Unit, 9560th USASRU, P. 0. Box 205, Mountain View, California 1 U. So Atomic Energy Commission, 1901 Constitution Avenue, No W., Washington 25, D. C, Attn: Chief Librarian 1 Director Central Intelligence Agency, 2430 E Street, No W., Washington 25, Do Co, Attn: OCD 1 Uo So Army Research Liaison Officer, MIT-Lincoln Laboratory, Lexington 73, Massachusetts 1 Commander, Air Force Systems Command, Andrews Air Force Base, Washington 25, Do Co, Attn: SCSE 1 Headquarters, USAF, Washington 25, D. C., Attn: AFRDR 1 Commander, Aeronautical Systems Division, WrightPatterson Air Force Base, Ohio, Attn: ASRNCC-1 56

DISTRIBUTION LIST (Cont.) No. of Copies 1 Commander, Aeronautical Systems Division, WrightPatterson Air Force Base, Ohio, Attn: ASAPRD 1 Commander, Aeronautical Systems Division, WrightPatterson Air Force Base, Ohio, Attn: ASRN-CS 1 Commander, Aeronautical Systems Division, WrightPatterson Air Force Base, Ohio, Attn: ASNP 1 Commander, Electronic Systems Division, L. G. Hanscom Field, Bedford, Massachusetts 1 Commander, Rome Air Development Center, Griffiss Air Force Base, New York, Attn: RAYLD 1 Commander, Air Proving Ground Center, Eglin Air Force Base, Florida, Attn: ADJ/Technical Report Branch 1 Chief of Naval Operations, EW Systems Branch, OP-35, Department of the Navy, Washington 25, D. C. 1 Chief, Bureau of Ships, Code 691C, Department of the Navy, Washington 25, D. C. 1 Commander, Bu Naval Weapons, Code RRRE-20, Department of the Navy, Washington 25, D. C. 1 Commander, Naval Ordnance Test Station, Inyokern, China Lake, California, Attn: Test Director - Code 30 1 Commander, Naval Air Missile Test Center, Point Mugu, California 1 Director, Naval Research Laboratory, Countermeasures Branch, Code 5430, Washington 25, D. Co 1 Director, Naval Research Laboratory, Washington 25, D. C., Attn: Code 2021 57

DISTRIBUTION LIST (Cont.) No. of Copies 1 Director, Air University Library, Maxwell Air Force Base, Alabama, Attn: CR-4987 1 Commanding Officer-Director, U. S. Navy Electronic Laboratory, San Diego 52, California 1 Commanding Officer, U. S. Naval Ordnance Laboratory, Silver Spring 19, Maryland 3 Chief, U. SO Army Security Agency, Arlington Hall Station, Arlington 12, Virginia, 222 12 Attn: 2 Cpys - IADEV 1 Copy - EW Div. IATOP 1 President, U. S. Army Defense Board, Headquarters, Fort Bliss, Texas 1 President, U. S. Army Airborne and Electronics Board, Fort Bragg, North Carolina 1 U, S. Army Anti-Aircraft Artillery and Guided Missile School, Fort Bliss, Texas, Attn: ORL 1 Commander, USAF Security Service, San Antonia, Texas, Attn: CLR 1 Chief of Naval Research, Department of the Navy, Washington 25, D, C., Attn: Code 427 1 Commanding Officer, 52d U. S. Army Security Agency, Special Operations Command, Fort Huachuca, Arizona 1 President, Uo S. Army Security Agency Board, Arlington Hall Station, Arlington 12, Virginia 58

DISTRIBUTION LIST (Cont.) No. of Copies 1 10 1 The Research Analysis Corporation, McLean, Virginia, 22101, Attn: Document Control Officer Headquarters, Defense Documentation Center, Cameron Station, Alexandria, Virginia Commanding Officer, U. S. Army Electronics Research and Development Laboratory, Fort Monmouth, New Jersey Attn: U. S. Marine Corps Liaison Office, Code: SIGRA/SL-LNR Director, Fort Monmouth Office, CommunicationsElectronics Combat Developments Agency, Building 410, Fort Monmouth, New Jersey Command Officer, U. S. Army Electronics Command, U. S. Army Electronics Laboratories, Fort Monmouth, New Jersey Attn: 1 7 1 Copy - Director of Research 1 Copy - Technical Documents Center - ADT/E 1 Copy - Chief, Special Devices Branch, Electronic Warfare Division 1 Copy - Chief, Advanced Techiques Branch, Electronic Warfare Division 1 Copy - Chief, Jamming and Deception Branch, Electronic Warfare Division 1 Copy - File Unit No. 2, Mail and Records, Electronic Warfare Division 1 Copy - Chief, Vulnerability Br., Electromagnetic Environment Division 1 Commanding Officer, U. S. Army Signal Missile Support Agency, White Sands Missile Range, New Mexico, Attn: SIGWS-MEW 59

DISTRIBUTION LIST (Cont.) No. of Copies 1 Commanding Officer, U. S. Naval Air Development Center, Johnsville, Pennsylvania, Attn: Naval Air Development Center Library 1 Headquarters, Aeronautical Systems Division, WrightPatterson Air Force Base, Ohio, Attn: ASRNCC-10 1 U. S. A. F. Project Rand, The Rand Corporation, 1700 Main Street, Santa Monica, California 1 Stanford Electronic Laboratories, Stanford University, Stanford, California 1 Director, National Security Agence, Fort George G. Meade, Maryland, Attn: RADE-1 1 Bureau of Naval Weapons Representative, Lockheed Missiles and Space Company, Po O. Box 504, Sunnyvale, California 1 Dr. H. L. Garner, Chairman, Systems Engineering Laboratory, The University of Michigan 55 Systems Engineering Laboratory, The University of Michigan, Ann Arbor, Michigan Above distribution is effected by Electronic Warfare Division, Surveillance Department, USAEL, Evans Area, Belmar, New Jersey. For further information contact Mr. I. 0, Myers. Senior Scientist, Telephone 59-61252. 60

DISTRIBUTION LIST (Cont.) No. of Copies 86 U. S. Army Research Office-Durham, Box CM, Duke Station, Durham, North Carolina, Attn: Mr. James J. Murray, Director Engineering Sciences Division 2 Flight Simulation Branch, Headquarters, White Sands Missile Range, New Mexico, Attn: William S. Agee Above distribution is effected by U. S. Army Research Office-Durham, Box CM, Duke Station, Durham, North Carolina. 61

UNCLASSIFIED Security Classification I 7 DOCUMENT CONTROL DATA- R&D (Security classification of title, body of abstract and indexing annotation must be entered when the overall report is clissified) 1. ORIGINATIN G ACTIVITY (Corporate author) 2a. REPORT SECURITY C LASSIFICATION University of Michigan Unclassified 2b GROUP 3. REPORT TITLE Some Properties of Circulants 4. DESCRIPTIVE NOTES (Type of report and inclusive dates) Technical Report No. 4 5. AUTHOR(S) (Last name, first name, initial) Waltz, Frederick M. 6. REPORT DATE 7a. TOTAL NO. OF PAGES 7b. NO. OF REFS March 1966 53 5 8a. CONTRACT OR GRANT NO. DA 36-039 AMC- 9a. ORIGINATOR'S REPORT NUMBER(S) 03733(E), DA 31-124-ARO-D-245 b. PROJECT NO. 07706-1-T 1PO 21101 A 042 01 c. 9b. OTHER REPORT NO(S) (Any other numbers that may be assigned this report) d. 10. AVA IL ABILITY/LIMITATION NOTICES Qualified requestors may obtain copies of this report from DDC. Foreign announcement and dissemination of this report by DDC is limited. 11. SUPPLEMENTARY NOTES 12. SPONSORING MILITARY ACTIVITY U.S. Army Electronics Command, Fort Monmouth, New Jersey U.S. Army Research Office, Durham, N.C. 13. ABSTRACT A circulant is a square matrix which is completely determined by its first row in the following manner: The second row is obtained by shifting (' circulating' the first row one position to the right and placing the last entry of the first row in the first position of the second row. Each succeeding row is determined from the row above it in like manner. Circulants occur in various practical problems. This paper presents certain properties of circulants (Some already published and some new) which render such operations as matrix inversion, the determination of eigenvalues and eigenvectors, and even matrix multiplication considerably simpler than the corresponding operations with general matrices. ) DD, JAN 64 1473 UNCLASSIFIED Security Classification

Unclassified Security Classification 14. LINK A LINK B LINK C KEY WORDS. ROLE WT ROLE WT ROLE WT Linear Algebra Matrices Circulants Computational Methods I NS 1 KUT I IO NS 1. ORIGINATING ACTIVITY: Enter the name and address of the contractor, subcontractor, grantee, Department of Defense activity or other organization (corporate author) issuing the report. 2a. REPORT SECURITY CLASSIFICATION: Enter the overall security classification of the report. Indicate whether "Restricted Data" is included. Marking is to be in accordance with appropriate security regulations. 2b. GROUP: Automatic downgrading is specified in DoD Directive 5200. 10 and Armed.Forces Industrial Manual. Enterthe group number. Also, when applicable, show that optional markings have been used for Group 3 and'Group 4 as authorized. 3. REPORT TITLE: Enter the complete report title in all capital letters. Titles in all cases should be unclassified. If a meaningful title cannot be selected without classification, show title classification in all capitals in parenthesis immediately following the title. 4. DESCRIPTIVE NOTES: If appropriate, enter the type of report, e.g., interim, progress, summary, annual, or final. Give the inclusive dates when a specific reporting period is covered. 5. AUTHOR(S): Enter the name(s) of authoi(s) as shown on or in the report. Enter last name, first name, middle initial. If military, show rank and branch of service. The name of the principal author is an absolute minimum requirement. 6. REPORT DATE: Enter the date of the report as day, month; year; or month, year. If more than one date appears on the report, use date of publication. 7a. TOTAL NUMBER OF PAGES: The total page count should follow normal pagination procedures, i.e., enter the number of pages containing information. 7b. NUMBER OF REFERENCES: Enter the total number of references cited in the report. 8a. CONTRACT OR GRANT NUMBER: If appropriate, enter the applicable number of the contract or grant under which the report was written. 8b, 8c, & 8d. PROJECT NUMBER: Enter the appropriate military department identification, such as project number, subproject number, system numbers, task number, etc. 9a. ORIGINATOR'S REPORT NUMBER(S): Enter the official report number by which the document will be identified and controlled by the originating activity. This number must be unique to this report. 9b. OTHER REPORT NUMBER(S): If the report has been assigned any other report numbers (either by the originator or by the sponsor), also enter this number(s). 10. AVAILABILITY/LIMITATION NOTICES: Enter any limitations on further dissemination of the report, other than those imposed by security classification, using standard statements such as: (1) "Qualified requesters may obtain copies of this report from DDC." (2) "Foreign announcement and dissemination of this report by DDC is not authorized." (3) "U. S. Governmeht agencies may obtain copies of this report directly from DDC. Other qualified DDC users shall request through,. (4) "U. S. military agencies may obtain copies of this report directly from DDC Other qualified users shall request through,, (5) "All distribution of this report is controlled. Qualified DDC users shall request through,, If the report has been furnished to the Office of Technical Services, Department of Commerce, for sale to the public, indicate this fact and enter the price, if known. 11. SUPPLEMENTARY NOTES: Use for additional explanatory no'tes. 1-2. SPONSORING MILITARY ACTIVITY: Enter the name of the departmental project office or laboratory sponsoring (paying for) the research and development. Include address. 13. ABSTRACT: Enter an abstract giving a brief and factual summary of the document indicative of the report, even though it may also appear elsewhere in the body of the technical report.' If additional space is required, a continuation sheet shall be attached. It is highly desirable that the abstract of classified reports be unclassified. Each paragraph of the abstract shall end with an indication of the military security classification of the information in the paragraph, represented as (TS), (S). (C), or (U). There is no limitation on the length of the abstract. However, the suggested length is from 150 to 225 words. 14. KEY WORDS: Key words are technically meaningful terms or short phrases that characterize a report and may be used as index entries for cataloging the report. Key words must be selected so that no security classification is required. Idenfiers, such as equipment model designation, trade name, military project code name, geographic location, may be used as key words but will be followed by an indication of technical context. The assignment of links, rules, and weights is optional. I "I - _ ~ _~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ li Unclassified Security Classification

UNIVERSITY OF MICHIGAN 0IIl Il.111111111111 1 111111111111011111111 3 9015 03627 7500