# Circulant Matrices and Their Application to Vibration Analysis

Brian Olson, Steven Shaw, Chengzhi Shi, Christophe Pierre, Robert Parker

► To cite this version:

Brian Olson, Steven Shaw, Chengzhi Shi, Christophe Pierre, Robert Parker. Circulant Matrices and Their Application to Vibration Analysis. Applied Mechanics Reviews, 2014, 66 (4), 10.1115/1.4027722. [PDF] [Full Text]

HAL Id: hal-01378829

https://hal.science/hal-01378829v1

Submitted on 10 Oct 2016

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Circulant Matrices and Their Application to Vibration Analysis

**Brian J. Olson**

Applied Physics Laboratory,
Air and Missile Defense Department,
The Johns Hopkins University,
Laurel, MD 20723-6099
e-mail: brian.olson@jhuapl.edu

**Steven W. Shaw**

University Distinguished Professor
Department of Mechanical Engineering,
Michigan State University,
East Lansing, MI 48824-1226
e-mail: shawsw@egr.msu.edu

**Chengzhi Shi**

Department of Mechanical Engineering,
University of California, Berkeley,
Berkeley, CA 94720
e-mail: chengzhi.shi@berkeley.edu

**Christophe Pierre**

Professor and Vice President
for Academic Affairs
Department of Mechanical Science
and Engineering,
University of Illinois at Urbana-Champaign,
Urbana, IL 61801
e-mail: chpierre@uillinois.edu

**Robert G. Parker**

L.S. Randolph Professor and Department Head
Department of Mechanical Engineering,
Virginia Polytechnic Institute
and State University,
Blacksburg, VA 24061
e-mail: r.parker@vt.edu

This paper provides a tutorial and summary of the theory of circulant matrices and their application to the modeling and analysis of the free and forced vibration of mechanical structures with cyclic symmetry. Our presentation of the basic theory is distilled from the classic book of Davis (1979, Circulant Matrices, 2nd ed., Wiley, New York) with results, proofs, and examples geared specifically to vibration applications. Our aim is to collect the most relevant results of the existing theory in a single paper, couch the mathematics in a form that is accessible to the vibrations analyst, and provide examples to highlight key concepts. A nonexhaustive survey of the relevant literature is also included, which can be used for further examples and to point the reader to important extensions, applications, and generalizations of the theory.

## 1 Introduction

"The theory of matrices exhibits much that is visually attractive. Thus, diagonal matrices, symmetric matrices, (0, 1) matrices, and the like are attractive independently of their applications. In the same category are the circulants."

Philip J. Davis

The modeling and analysis of structural vibration is a mature field, especially when vibration amplitudes are small and linear models apply. For such models, the powerful tools of modal analysis and superposition allow one to decompose the system and its response into a set of uncoupled single degree-of-freedom (DOF) systems, each of which captures the motion of the overall system in a given normal mode. For geometrically simple continua, the natural frequencies, vibration modes, and response to known excitations can be analytically determined. When discrete models are developed, matrix methods are readily applied for both natural frequency and response analyses. For general system models with no special properties, which occur in the majority of applications, large-scale computational models must be developed, typically using finite element methods. However, certain classes of

systems possess special properties, such as symmetries, which aid in the analysis by enabling significant reduction of the finite element models (Fig. 1(a)). This is particularly true for systems with cyclic symmetry.

The main goal of this tutorial is to consider the vibrations of structural systems with cyclic symmetry, also known as *rotationally periodic* systems. A useful geometric view of these systems is that of a circular disk (a pie) split into *N* equal sectors (i.e., equally sized pieces of the pie), each of which contains an identical mechanical structure with identical coupling to forward-nearest-neighbors and to ground (Fig. 1(b)).

The theory of circulants also applies to more general forms of coupling with non-nearest-neighbors, for example through a base substructure, as long as the rotational symmetry is preserved. These structural arrangements arise naturally in certain types of rotating machines. Turbomachinery examples include bladed disks, such as fans, compressors, turbines, and impeller stages of aircraft, helicopter engines, power plants, as well as propellers, pumps, and the like. Rotational periodicity also arises in some stationary structures such as satellite antennae. In some systems, such as planetary gears and rotors with pendulum vibration absorbers, the overall system is not necessarily cyclic, but subcomponents of it may be. When perfect cyclic symmetry of a model is assumed, special modal properties exist that significantly facilitate its vibration analysis.
<figure><img src="image_2.png" /><figcaption>Fig. 1 (a) Finite element model of a bladed disk assembly [1] and (b) general cyclic system with *N* identical sectors and nearest-neighbor coupling</figcaption></figure>

The nature of rotationally periodic systems imposes a cyclic structure on their mass and stiffness matrices, which are *block circulant* for systems with many DOFs per sector (Fig. 1(a)) and *circulant* for the special case of a single DOF per sector (Fig. 1(b)). By denoting the stiffness of the internal elements of each sector by $K_0$ and the coupling stiffness between sectors as $-K_1$, the stiffness matrices of rotationally periodic structures with nearest-neighbor coupling have the general form

$$ K = \begin{bmatrix} K_0 & -K_1 & 0 & \dots & 0 & -K_1 \\ -K_1 & K_0 & -K_1 & \dots & 0 & 0 \\ 0 & -K_1 & K_0 & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \dots & K_0 & -K_1 \\ -K_1 & 0 & 0 & \dots & -K_1 & K_0 \end{bmatrix} $$

where $K_0$ and $K_1$ are themselves matrices for the complex model shown in Fig. 1(a) and scalars for the simplest prototypical model shown in Fig. 1(b). A key property of $K$ is that the elements of each row are obtained from the previous row by cyclically permuting its entries. That is, for $j = 2, 3, ..., N$, row $j$ is obtained from row $j-1$ by shifting the elements of row $j-1$ to the right by one position and wrapping the right-end element of row $j-1$ into the first position. This is precisely the form of a circulant matrix, which is formally defined in Sec. 2.2. The mass matrix of a rotationally periodic structure with nearest-neighbor coupling is block

diagonal and also shares this cyclic property. The size of the elements of $K$ is equal to the number of DOFs per sector, and is denoted by $M$. Thus, a system with $N$ sectors and $M$ DOFs per sector has a total of $NM$ DOFs. The most important utility of the theory of circulants in analyzing rotationally periodic systems is that they enable a $NM$-DOF system to be decomposed to a set of $NM$-DOF uncoupled systems using the appropriate coordinate transformation. Admittedly, the same can be accomplished using brute-force methods to uncouple the entire system using modal analysis, but such an approach overlooks fundamental properties that are crucial to understanding the free and forced response of these systems and requires significantly more computational power. This is the central motivation for understanding and utilizing circulants to analyze cyclic systems.

The vibration modes of rotationally periodic systems consist of multiple pairs of repeated natural frequencies (eigenvalues) that lead to pairs of degenerate normal modes (eigenvectors). The number and nature of such pairs depend on whether $N$ is even or odd. Each mode pair is characterized as a pair of standing waves (SWs) with different spatial phases, or a pair of traveling waves, labeled as a forward traveling wave (FTW) and backward traveling wave (BTW) when following the terminology used in applications to rotating machinery. The choice of formulation is based on convenience for a given application, which depends on the nature of the system excitation. For example, the excitation frequency is proportional to the engine speed for many cyclic rotating systems, which leads to the so-called *engine order (e.o.) excitation*, and often the spatial nature of the excitation (in the rotating frame of reference) is in the form of a traveling wave. When such excitation is applied to systems with cyclic symmetry, the response also has special properties that can be easily uncovered by making use of the system traveling wave vibration modes.

The strength of the intersector coupling is an important parameter in rotationally periodic systems. When the intersector coupling is strong, the frequencies of the mode pairs are well separated. In contrast, weak intersector coupling yields closely spaced frequencies, high modal density, and large sensitivity to cyclic-symmetry-breaking imperfections. A wave representation of the response [2] shows that the strength of the coupling determines frequency passband widths, wherein unattenuated propagation of waves takes place. Weak intersector coupling leads to narrow passbands, and the passbands widen as the coupling strength increases. Another important parameter for cyclically symmetric structures is the total number of sectors. The modal density is larger for large $N$, which corresponds to more natural frequencies within each frequency passband. In all cases, the modes are spatially distributed, or extended, for models of cyclic systems. That is, the pattern of displacements in a modal response is uniformly spread around the circumference of the structure.

Systems with cyclic symmetry have been studied in the context of vibration analysis for over 40 yr. Early work considered properties of the vibration modes [3,4] and the steady-state response to harmonic excitation [5-7] of tuned and mistuned turbomachinery rotors. Many of these contributions were motivated by vibration studies of general rotationally periodic systems [8-20], bladed disks [1,3,21-30], planetary gear systems [31-43], rings [44,45], circular plates [46-48], disk spindle systems [49-51], centrifugal pendulum vibration absorbers [52-56], space antennae [57], and microelectromechanical system frequency filters [58]. Implicit in these investigations is the assumption of perfect symmetry which, of course, is an idealization. Perfect symmetry gives rise to well-structured vibration modes [9,31,33-37,39,53,56], which are characterized by certain phase indices that define specific phase relationships between cyclic components in each vibration mode [18]. This vibration mode structure is critical in the investigation of dynamic response of cyclic systems using modal analysis [54]. These special properties of rotationally periodic structures save tremendous calculation effort in the analysis of the system dynamics [59-61]. The properties of cyclic symmetry are not only used in the study of mechanical vibrations, they are also important
to the analysis of elastic stress [62,63] and coupled cell networks [64].

The special properties of systems with cyclic symmetry extend to nonlinear systems, where they are expressed quite naturally in terms of symmetry groups: the cyclic group, in particular [65–68]. The group theoretic formulation can also be applied to the linear vibration problems considered in this paper [69,70], but the approach presented here is more approachable to readers with a standard engineering background in linear algebra.

The extension to systems with small imperfections that perturb the cyclic symmetry has led to important results related to *mode localization*, which arises in systems with high modal density caused by weak intersector coupling or a large number of sectors. In particular parameter regimes, the mode shapes are highly sensitive to small, symmetry-breaking imperfections among the nominally identical sectors, and the spatial nature of the vibration modes can become highly localized. For these cases, the vibration energy is focused in a small number of sectors, and sometimes even a single sector. This behavior, which stems from the seminal work of Anderson on lattices [71], was originally recognized to be relevant to structural vibrations by Hodges and Woodhouse [72,73] and Pierre and Dowell [74], and has been extensively studied from both fundamental [75] and applied [76–78] points of view. The phenomenon of mode localization is also observed in the forced response and has practical implications for the fatigue life of bladed disks in turbomachinery [79,80]. It is interesting to note that localization also arises in nonlinear systems with perfect symmetry, where the dependence of the system natural frequencies on the amplitudes of vibration naturally leads to the possibility of mistuning of frequencies between sectors if their amplitudes are different [81–88].

Another topic central to vibration analysis that relies on the theory of circulants is the discrete Fourier transform (DFT) [89,90]. The DFT was known to Gauss [91], and is the most common tool used to process vibration signals from experimental measurements and numerical simulations. The DFT and inverse DFT (IDFT) provide a computationally convenient means of determining the frequency content of a given signal. Because the mathematics of circulants is at the heart of the computation of the DFT, we include a brief introduction to the relationship between the DFT and IDFT, and its connection to the theory of circulants.

The goal of this paper is to provide a detailed theory of circulant matrices as it applies to the analysis of free and forced structural vibrations. Much of the material was developed as part of the Ph.D. research of the lead author [21,22,92–95]. References to other relevant work are included throughout this paper, but we do not claim to provide an exhaustive survey of the relevant literature. The remainder of the paper is organized as follows. Section 2 gives a quite exhaustive and self-contained treatment of the theory of circulants, which is distilled from the seminal work by Davis [96]. We adopt a presentation style similar to that of Öttarsson [97], one that should be familiar to an analyst in the vibrations engineering community. This section is meant to act simultaneously as a detailed reference and tutorial, including proofs of the main results and simple illustrative examples. Section 3 provides three examples that make use of the theory, including ordinary circulants and the more general block circulant matrices. Particular attention is given to cyclic systems under traveling wave engine order excitation because this type of system forcing appears naturally in many relevant applications of rotating machinery. The apprised reader, or the reader who wishes to learn by example, can skip directly to Sec. 3, depending on their background, and revisit Sec. 2 as warranted. The paper closes with a brief summary in Sec. 4.

## 2 The Theory of Circulants

This section details the theory and mathematics of circulant matrices that are relevant to vibration analysis of mechanical structures with cyclic symmetry. The basic theory is distilled from

the seminal work by Davis [96] and is presented using mathematics and notation that should be familiar to the vibrations engineer. Selected topics from linear algebra are reviewed in Sec. 2.1 to introduce relevant notion and support the theoretical development of circulant matrices in Secs. 2.2–2.8. This material is included for completeness; the apprised reader can skip directly to Secs. 2.2 and 2.3, where circulant and block circulant matrices (also referred to as *circulants and block circulants*) are defined. Representations of circulants are discussed in Sec. 2.4. Diagonalization of circulants and block circulants is discussed at length in Sec. 2.5, which begins with a treatment of the Nth roots of unity in Sec. 2.5.1 and the Fourier matrix in Sec. 2.5.2. It is subsequently shown how to diagonalize the cyclic forward shift matrix in Sec. 2.5.3 a circulant in Sec. 2.5.4, and a block circulant in Sec. 2.5.5. Some generalizations of the theory are discussed in Sec. 2.6, including the diagonalization of block circulants with circulant blocks. Relevant mathematics of the DFT and IDFT are summarized in Sec. 2.7. Finally, the circulant eigenvalue problem (cEVP) is discussed in Sec. 2.8, including the eigenvalues and eigenvectors of circulants and block circulants, their symmetry characteristics, and connection to the DFT process.

### 2.1 Mathematical Preliminaries.
Definitions and relevant properties of special operators and matrices are discussed in Secs. 2.1.1 and 2.1.2, respectively, including the direct (Kronecker) product, and Hermitian, unitary, cyclic forward shift, and flip matrices. This is followed in Sec. 2.1.3 with a treatment of matrix diagonalizability.

#### 2.1.1 Special Operators.
Let $\mathbb{C}$ denote the set of complex numbers and $\mathbb{Z}_+$ be the set of positive integers.

**DEFINITION 1 (Direct Sum).** For each $i = 1, 2, ..., N$ and $p_i \in \mathbb{Z}_+$, let $\mathbf{A}_i \in \mathbb{C}^{p_i \times p_i}$. Then the direct sum of $\mathbf{A}_i$ is denoted by

$$ \oplus_{i=1}^{N} \mathbf{A}_i = \mathbf{A}_1 \oplus \mathbf{A}_2 \oplus \dots \oplus \mathbf{A}_N $$

and results in the block diagonal square matrix

$$ \mathbf{A} = \begin{bmatrix} \mathbf{A}_1 & \mathbf{0} & \dots & \mathbf{0} \\ \mathbf{0} & \mathbf{A}_2 & \dots & \mathbf{0} \\ \vdots & \vdots & \ddots & \vdots \\ \mathbf{0} & \mathbf{0} & \dots & \mathbf{A}_N \end{bmatrix} $$

of order $p_1 + p_2 + \dots + p_N$, where each zero matrix $\mathbf{0}$ has the appropriate dimension. $\triangle$

It is convenient to define the operator $\mathrm{diag}(\cdot)$ that takes as its argument the ordered set of matrices $\mathbf{A}_1, \mathbf{A}_2, ..., \mathbf{A}_N$ and results in the block diagonal matrix given in Definition 1, that is,

$$ \mathbf{A} = \mathrm{diag}(\mathbf{A}_1, \mathbf{A}_2, \dots, \mathbf{A}_N) = \mathrm{diag}_{i=1,...,N}(\mathbf{A}_i) $$

For the case when each $\mathbf{A}_i = a_i$ is a scalar ($1 \times 1$), the direct sum of $a_i$ is denoted by the diagonal matrix

$$ \mathrm{diag}(a_1, a_2, \dots, a_N) = \mathrm{diag}(a_i) $$

**DEFINITION 2 (Direct Product).** Let $\mathbf{a}, \mathbf{b} \in \mathbb{C}^n$. Then the direct product (or Kronecker product) of $\mathbf{a}$ and $\mathbf{b}^T$ is the square matrix

$$ \mathbf{a} \otimes \mathbf{b}^T = \begin{bmatrix} a_1 b_1 & a_1 b_2 & \dots & a_1 b_n \\ a_2 b_1 & a_2 b_2 & \dots & a_2 b_n \\ \vdots & \vdots & \ddots & \vdots \\ a_n b_1 & a_n b_2 & \dots & a_n b_n \end{bmatrix} $$

where $(\cdot)^T$ denotes transposition. If $\mathbf{A} \in \mathbb{C}^{m \times n}$ and $\mathbf{B} \in \mathbb{C}^{p \times q}$ are matrices, then the direct product of $\mathbf{A}$ and $\mathbf{B}$ is the matrix
$$
\mathbf{A} \otimes \mathbf{B} = \begin{bmatrix} a_{11} \mathbf{B} & a_{12} \mathbf{B} & \cdots & a_{1n} \mathbf{B} \\ a_{21} \mathbf{B} & a_{22} \mathbf{B} & \cdots & a_{2n} \mathbf{B} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} \mathbf{B} & a_{m2} \mathbf{B} & \cdots & a_{mn} \mathbf{B} \end{bmatrix}
$$

of dimension mp × nq.

<figure><img src="image_3.png" /></figure>

Example 1. Consider the matrices

$$
\mathbf{A} = \begin{bmatrix} 1 & 2 & 3 \end{bmatrix} \quad \text{and} \quad \mathbf{B} = \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}
$$

Then the direct product of A and B is given by

$$
\begin{align*}
\mathbf{A} \otimes \mathbf{B} &= \begin{bmatrix} 1 & 2 & 3 \end{bmatrix} \otimes \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \\
&= \left( 1 \cdot \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}, 2 \cdot \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}, 3 \cdot \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \right) \\
&= \left( \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix}, \begin{bmatrix} 2 & 4 \\ 6 & 8 \end{bmatrix}, \begin{bmatrix} 3 & 6 \\ 9 & 12 \end{bmatrix} \right) \\
&= \begin{bmatrix} 1 & 2 & 2 & 4 \\ 3 & 4 & 6 & 8 \end{bmatrix} \begin{bmatrix} 3 & 6 \\ 9 & 12 \end{bmatrix}
\end{align*}
$$

Because $\mathbf{A}$ is $1 \times 3$ and $\mathbf{B}$ is $2 \times 2$, the direct product $\mathbf{A} \otimes \mathbf{B}$ has dimension $1 \cdot 2 \times 3 \cdot 2$, or $2 \times 6$.

<figure><img src="image_4.png" /></figure>

Some important properties of the direct product are as follows:

(1) The direct product is a bilinear operator. If A and B are square matrices and $\alpha$ is a scalar, then

$$
\alpha(\mathbf{A} \otimes \mathbf{B}) = (\alpha\mathbf{A}) \otimes \mathbf{B} = \mathbf{A} \otimes (\alpha\mathbf{B}) \quad (1)
$$

(2) The direct product distributes over addition. If A, B, and C are square matrices with the same dimension, then

$$
(\mathbf{A} + \mathbf{B}) \otimes \mathbf{C} = \mathbf{A} \otimes \mathbf{C} + \mathbf{B} \otimes \mathbf{C} \quad (2a)
$$

$$
\mathbf{A} \otimes (\mathbf{B} + \mathbf{C}) = \mathbf{A} \otimes \mathbf{B} + \mathbf{A} \otimes \mathbf{C} \quad (2b)
$$

(3) The direct product is associative. If A, B, and C are square matrices, then

$$
\mathbf{A} \otimes (\mathbf{B} \otimes \mathbf{C}) = (\mathbf{A} \otimes \mathbf{B}) \otimes \mathbf{C} \quad (3)
$$

(4) The product of two direct products yields another direct product. If A, B, C, and D are square matrices such that AC and BD exist, then

$$
(\mathbf{A} \otimes \mathbf{B})(\mathbf{C} \otimes \mathbf{D}) = (\mathbf{A}\mathbf{C}) \otimes (\mathbf{B}\mathbf{D}) \quad (4)
$$

(5) The inverse of a direct product yields the direct product of two matrix inverses. If A and B are invertible matrices, then

$$
(\mathbf{A} \otimes \mathbf{B})^{-1} = \mathbf{A}^{-1} \otimes \mathbf{B}^{-1} \quad (5)
$$

where $(\cdot)^{-1}$ denotes the matrix inverse.

<table><caption>**Table 1 Selected special matrices**</caption>
  <thead>
    <tr>
      <th>Type</th>
      <th>Condition</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>Symmetric</td>
      <td>A = A<sup>T</sup></td>
    </tr>
    <tr>
      <td>Hermitian</td>
      <td>A = A<sup>H</sup></td>
    </tr>
    <tr>
      <td>Orthogonal</td>
      <td>A<sup>T</sup>A = I (or) A<sup>T</sup> = A<sup>-1</sup></td>
    </tr>
    <tr>
      <td>Unitary</td>
      <td>A<sup>H</sup>A = I (or) A<sup>H</sup> = A<sup>-1</sup></td>
    </tr>
  </tbody>
</table>

(6) The transpose or conjugate transpose of a direct product yields the direct product of two transposes or conjugate transposes. If A and B are square matrices, then

$$
(\mathbf{A} \otimes \mathbf{B})^{\mathrm{T}} = \mathbf{A}^{\mathrm{T}} \otimes \mathbf{B}^{\mathrm{T}} \quad (6a)
$$

$$
(\mathbf{A} \otimes \mathbf{B})^{\mathcal{H}} = \mathbf{A}^{\mathcal{H}} \otimes \mathbf{B}^{\mathcal{H}} \quad (6b)
$$

where $(\cdot)^{\mathcal{H}} = (\bar{\cdot})^{\mathrm{T}}$ is the conjugate transpose and $\bar{\cdot}$ denotes complex conjugation.

(7) If A and B are square matrices with dimensions n and m, respectively, then

$$
\det(\mathbf{A} \otimes \mathbf{B}) = (\det \mathbf{A})^m (\det \mathbf{B})^n \quad (7a)
$$

$$
\mathrm{tr}(\mathbf{A} \otimes \mathbf{B}) = \mathrm{tr}(\mathbf{A}) \mathrm{tr}(\mathbf{B}) \quad (7b)
$$

where $\det(\cdot)$ and $\mathrm{tr}(\cdot)$ denote the matrix determinant and trace.

2.1.2 Special Matrices. The definitions and relevant proper-
ties of selected special matrices are summarized. Hermitian and
unitary matrices are defined first (see Table 1), followed by a brief
treatment of two important permutation matrices: the cyclic for-
ward shift matrix and the flip matrix. The details of circulant mat-
rices and the Fourier matrix, which are employed extensively
throughout this work, are deferred to Secs. 2.2, 2.3, and 2.5.2.

**Definition 3 (Hermitian Matrix).** A matrix $\mathbf{H} \in \mathbb{C}^{N \times N}$ is Hermitian if $\mathbf{H} = \mathbf{H}^{\mathrm{T}}$. $\triangleq$

The elements of a Hermitian matrix $\mathbf{H}$ satisfy $h_{ik} = \bar{h}_{ki}$ for all $i, k = 1, 2, \dots, N$. Thus, the diagonal elements $h_{ii}$ of a Hermitian matrix must be real, while the off-diagonal elements may be complex. If $\mathbf{H} = \mathbf{H}^{\mathrm{T}}$ then $\mathbf{H}$ is said to be symmetric.

**Definition 4 (Unitary Matrix).** A matrix $\mathbf{U} \in \mathbb{C}^{N \times N}$ is unitary if $\mathbf{U}^{\mathrm{T}}\mathbf{U} = \mathbf{I}$, where $\mathbf{I}$ is the $N \times N$ identity matrix. $\triangleq$

Real unitary matrices are orthogonal matrices. If a matrix $\mathbf{U}$ is unitary, then so too is $\mathbf{U}^{\mathcal{H}}$. To see this, consider $(\mathbf{U}^{\mathcal{H}})^{\mathcal{H}}(\mathbf{U}^{\mathcal{H}}) = \mathbf{U}\mathbf{U}^{\mathcal{H}} = \mathbf{I}$, from which it follows that

$$
\mathbf{U}^{\mathcal{H}} \mathbf{U} = \mathbf{U} \mathbf{U}^{\mathcal{H}} = \mathbf{I} \quad (8)
$$

Finally, if $\mathbf{U}$ is unitary and nonsingular, then $\mathbf{U}^{\mathcal{H}} = \mathbf{U}^{-1}$.

A general permutation matrix is formed from the identity matrix by reordering its columns or rows. Here, we introduce two such matrices: the cyclic forward shift matrix and the flip matrix.

**Definition 5 (Cyclic Forward Shift Matrix).** The $N \times N$ cyclic forward shift matrix is given by

$$
\boldsymbol{\sigma}_N = \begin{bmatrix} 0 & 1 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 1 & 0 \\ 0 & 0 & 0 & \cdots & 0 & 1 \\ 1 & 0 & 0 & \cdots & 0 & 0 \end{bmatrix}_{N \times N}
$$

which is populated with ones along the superdiagonal and in the
(N, 1) position, and zeros otherwise.
$\triangleq$

The cyclic forward shift matrix plays a key role in the represen-
tation and diagonalization of circulant matrices, which are dis-
cussed in Secs. 2.4 and 2.5.

*Example 2.* Let $\mathbf{a}=(a, b, c)$ be a three-vector. Then the operation

$$
\begin{align*}
\mathbf{a}\sigma_3 &= [a \ b \ c] \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} \\
&= (c, a, b)
\end{align*}
$$
<table><caption>**Table 2** Selected types of linear transformations</caption><thead><tr><th>Type</th><th>Condition</th><th>Transformation</th></tr></thead><tbody><tr><td>Equivalence</td><td><b>P</b> and <b>Q</b> are nonsingular</td><td><b>B</b> = <b>P</b> <b>A</b> <b>Q</b></td></tr><tr><td>Congruence</td><td><b>Q</b> is nonsingular</td><td><b>B</b> = <b>Q</b><sup><b>T</b></sup> <b>A</b> <b>Q</b></td></tr><tr><td>Similarity</td><td><b>Q</b> is nonsingular</td><td><b>B</b> = <b>Q</b><sup>-1</sup> <b>A</b> <b>Q</b></td></tr><tr><td>Orthogonal</td><td><b>Q</b> is nonsingular and orthogonal</td><td><b>B</b> = <b>Q</b><sup><b>T</b></sup> <b>A</b> <b>Q</b> = <b>Q</b><sup>-1</sup> <b>A</b> <b>Q</b></td></tr><tr><td>Unitary</td><td><b>Q</b> is nonsingular and unitary</td><td><b>B</b> = <b>Q</b><sup><b>H</b></sup> <b>A</b> <b>Q</b> = <b>Q</b><sup>-1</sup> <b>A</b> <b>Q</b></td></tr></tbody></table>

cyclically shifts the entries of **a** by one entry to the right. That is, the ith entry of **a** is shifted to entry i + 1, except for entry N = 3, which is placed in position 1 of **a**.

**DEFINITION 6 (Flip Matrix).** The $N \times N$ flip matrix is given by

<figure><img src="image_5.png" /></figure>

$$ \mathbf{\kappa}_N = \begin{bmatrix} 1 & 0 & 0 & \cdots & 0 & 0 \\ 0 & 0 & 0 & \cdots & 0 & 1 \\ 0 & 0 & 0 & \cdots & 1 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 1 & \cdots & 0 & 0 \\ 0 & 1 & 0 & \cdots & 0 & 0 \end{bmatrix}_{N \times N} $$

which is populated with ones in the (1, 1) position and along the subantidiagonal, and zeros otherwise.

<figure><img src="image_6.png" /></figure>

**COROLLARY 1.** Let $\mathbf{\kappa}_N$ be the flip matrix. Then

$$ \left. \begin{array}{l} \mathbf{\kappa}_N^2 = \mathbf{I}_N \\ \mathbf{\kappa}_N^H = \mathbf{\kappa}_N^T = \mathbf{\kappa}_N = \mathbf{\kappa}_N^{-1} \end{array} \right\} $$

where $\mathbf{I}_N$ is the $N \times N$ identity matrix.

<figure><img src="image_7.png" /></figure>

2.1.3 *Matrix Diagonalizability.* Matrix diagonalization is the process of taking a square matrix and transforming it into a diagonal matrix that shares the same fundamental properties of the underlying matrix, such as its characteristic polynomial, trace, and determinant. This section defines matrix diagonalizability in terms of similarity, provides necessary conditions for a matrix to be diagonalizable, and summarizes relevant properties of diagonalizable matrices. Diagonalization of circulant matrices is deferred to Sec. 2.5.

**DEFINITION 7 (Similarity Transformation).** Let **Q** be an arbitrary nonsingular matrix. Then **B** = **Q**⁻¹ **A** **Q** is a similarity transformation and **B** is said to be similar to **A**.

<figure><img src="image_8.png" /></figure>

If **B** is similar to **A**, then **A** = (**Q**⁻¹)⁻¹ **B** (**Q**⁻¹) is similar to **B**. It therefore suffices to say that **A** and **B** are similar. A summary of selected additional linear transformations is provided in Table 2. If **B** is orthogonally (resp. unitarily) similar to **A**, then we say that **A** and **B** are orthogonally (resp. unitarily) similar matrices.

**THEOREM 1.** If **A** and **B** are similar matrices, then they have the same characteristic equation and hence the same eigenvalues.

<figure><img src="image_9.png" /></figure>

Theorem 1 guarantees that the eigenvalues of a matrix are preserved under a similarity transformation. A proof can be found in any standard textbook on linear algebra [98,99]. Because $\mathbf{Q}^T = \mathbf{Q}^{-1}$ for orthogonal $\mathbf{Q}$ and $\mathbf{Q}^H = \mathbf{Q}^{-1}$ for unitary $\mathbf{Q}$, the eigenvalues are also preserved under orthogonal and unitary transformations.

**THEOREM 2.** Let the matrices **A** and **B** be similar. Then if

$$ p(t) = \sum_{k=0}^{N} c_k t^k $$

denotes a finite polynomial in $t$ with arbitrary coefficients $c_k$ ($k = 1, 2, ..., N$), the matrix polynomials $p(\mathbf{A})$ and $p(\mathbf{B})$ are similar.

<figure><img src="image_10.png" /></figure>

**Proof.** Let **Q** be an arbitrary nonsingular matrix. Then

$$ \begin{aligned} p(\mathbf{B}) &= p(\mathbf{Q}^{-1} \mathbf{A} \mathbf{Q}) \\ &= \sum_{k=0}^{N} c_k (\mathbf{Q}^{-1} \mathbf{A} \mathbf{Q})^k \\ &= c_0 \mathbf{I} + c_1 \mathbf{Q}^{-1} \mathbf{A} \mathbf{Q} + c_2 \mathbf{Q}^{-1} \mathbf{A} \mathbf{Q} \mathbf{Q}^{-1} \mathbf{A} \mathbf{Q} + \dots \\ &\quad + c_N \mathbf{Q}^{-1} \mathbf{A} \mathbf{Q} \cdots \mathbf{Q}^{-1} \mathbf{A} \mathbf{Q} \\ &= c_0 \mathbf{I} + c_1 \mathbf{Q}^{-1} \mathbf{A} \mathbf{Q} + c_2 \mathbf{Q}^{-1} \mathbf{A}^2 \mathbf{Q} + \dots + c_N \mathbf{Q}^{-1} \mathbf{A}^N \mathbf{Q} \\ &= \mathbf{Q}^{-1} (c_0 \mathbf{I} + c_1 \mathbf{A} + c_2 \mathbf{A}^2 + \dots + c_N \mathbf{A}^N) \mathbf{Q} \\ &= \mathbf{Q}^{-1} p(\mathbf{A}) \mathbf{Q} \end{aligned} $$

which completes the proof.

<figure><img src="image_11.png" /></figure>

If $p(t) = t^k$ with $k > 0$ in Theorem 2, then we have the following result.

**COROLLARY 2.** If $\mathbf{B} = \mathbf{Q}^{-1} \mathbf{A} \mathbf{Q}$, then $\mathbf{B}^k = \mathbf{Q}^{-1} \mathbf{A}^k \mathbf{Q}$ for any $k \in \mathbb{Z}_+$.

**DEFINITION 8 (Diagonalizable Matrix).** A square matrix **A** is diagonalizable if there exists a nonsingular matrix **Q** and a diagonal matrix **D** such that $\mathbf{Q}^{-1} \mathbf{A} \mathbf{Q} = \mathbf{D}$.

Thus, a matrix is diagonalizable if it is similar to a diagonal matrix. If **A** is diagonalizable by **Q**, we say that **Q** diagonalizes **A** and that **Q** is the diagonalizing matrix.

**THEOREM 3.** An $N \times N$ matrix **A** is diagonalizable if it has $N$ linearly independent eigenvectors.

<figure><img src="image_12.png" /></figure>

**Proof.** Suppose **A** has $N$ linearly independent eigenvectors and denote them by $\mathbf{q}_1, \mathbf{q}_2, ..., \mathbf{q}_N$. Let $\lambda_i$ be the eigenvalue of **A** corresponding to $\mathbf{q}_i$ for each $i = 1, ..., N$. Then if **Q** is the matrix that has as its ith column the vector $\mathbf{q}_i$, it follows that

$$ \begin{aligned} \mathbf{A} \mathbf{Q} &= (\mathbf{A} \mathbf{q}_1, \mathbf{A} \mathbf{q}_2, ..., \mathbf{A} \mathbf{q}_N) \\ &= (\mathbf{q}_1 \lambda_1, \mathbf{q}_2 \lambda_2, ..., \mathbf{q}_N \lambda_N) \\ &= (\mathbf{q}_1, \mathbf{q}_2, ..., \mathbf{q}_N) \operatorname{diag} (\lambda_1) \\ &\equiv \mathbf{Q} \mathbf{D} \end{aligned} $$

Because **Q** is nonsingular by hypothesis, $\mathbf{D} = \mathbf{Q}^{-1} \mathbf{A} \mathbf{Q}$.

<figure><img src="image_13.png" /></figure>

## 2.2 Circulant Matrices

**DEFINITION 9 (Circulant Matrix).** A $N \times N$ circulant matrix (or circulant, or ordinary circulant) is generated from the $N$-vector $\{c_1, c_2, ..., c_N\}$ by cyclically permuting its entries, and is of the form

$$ \mathbf{C} = \begin{bmatrix} c_1 & c_2 & \cdots & c_N \\ c_N & c_1 & \cdots & c_{N-1} \\ \vdots & \vdots & \ddots & \vdots \\ c_2 & c_3 & \cdots & c_1 \end{bmatrix} $$

<figure><img src="image_14.png" /></figure>

**DEFINITION 10 (Generating Elements).** Let the $N \times N$ circulant matrix **C** be given by Definition 9. Then the elements of the $N$-vector

$$ \{c_1, c_2, ..., c_N\} $$

are said to be the generating elements of **C**.

<figure><img src="image_15.png" /></figure>

Thus, a circulant matrix is defined completely by the generating elements in its first row, which are cyclically shifted to the right by one position per row to form the subsequent rows. The set of all such matrices of order $N$ is denoted by $\mathcal{C}_N$. A matrix contained in $\mathcal{C}_N$ is said to be a circulant of type $N$.

It is convenient to define the circulant operator $\operatorname{circ}(\cdot)$ that takes as its argument the generating elements $c_1, c_2, ..., c_N$ and results in the array given in Definition 9, that is,
$$
C = \mathrm{circ}(c_1, c_2, \dots, c_N) \tag{9}
$$

An $N \times N$ circulant is also characterized in terms of its $(i, k)$ entry by $(\mathbf{C})_{ik} = c_{k-i+1(\mathrm{mod}N)}$ for $i, k = 1, 2, \dots, N$.

Example 3. The circulant array formed by the generating ele-
ments a, b, c, d can be written as

$$
\mathrm{circ}(a, b, c, d) = \begin{bmatrix} a & b & c & d \\ d & a & b & c \\ c & d & a & b \\ b & c & d & a \end{bmatrix} \in \mathcal{C}_4
$$

which is a circulant matrix of type 4.

<figure><img src="image_16.png" /></figure>

If a matrix is both circulant and symmetric, its generating ele-
ments are

$$
\left\{
\begin{array}{ll}
c_1, \dots, c_N, & N \text{ even} \\
c_1, \dots, c_{\frac{N-1}{2}}, c_{\frac{N+1}{2}}, & N \text{ odd}
\end{array}
\right.
\qquad (10)
$$

which are necessarily repeated. Only (N + 2)/2 generating ele-
ments are distinct if N is even and (N + 1)/2 are distinct if N is
odd. The set of all N × N symmetric circulants is denoted by
*S*C<sub>N</sub>. A matrix contained in *S*C<sub>N</sub> is said to be a symmetric circu-
lant of type N.

Example 4. The 5 × 5 matrix

$$
\mathrm{circ}(a, b, c, c, b) = \begin{bmatrix} a & b & c & c & b \\ b & a & b & c & c \\ c & b & a & b & c \\ c & c & b & a & b \\ b & c & c & b & a \end{bmatrix} \in \mathcal{S}\mathcal{C}_5
$$

(N + 1)/2 = 3 distinct elements.

<figure><img src="image_17.png" /></figure>

The matrix defined in Example 3 is not a symmetric circulant
because its generating elements are distinct. Next, we give a nec-
essary and sufficient condition for a square matrix to be circulant.

THEOREM 4. Let $\boldsymbol{\sigma}_N$ be the cyclic forward shift matrix. Then a $N \times N$ matrix $\mathbf{C}$ is circulant if and only if $\mathbf{C}\boldsymbol{\sigma}_N = \boldsymbol{\sigma}_N\mathbf{C}$. $\square$

<figure><img src="image_18.png" /></figure>

Proof. Let $\mathbf{C}$ be an $N \times N$ matrix with arbitrary elements $c_{ik}$ for $i, k = 1, 2, \dots, N$. Then

$$
\mathbf{C}\boldsymbol{\sigma}_N = \begin{bmatrix} c_{1N} & c_{11} & c_{12} & \cdots & c_{1(N-1)} \\ c_{2N} & c_{21} & c_{22} & \cdots & c_{2(N-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ c_{NN} & c_{N1} & c_{N2} & \cdots & c_{N(N-1)} \end{bmatrix}
$$

and

$$
\boldsymbol{\sigma}_N \mathbf{C} = \begin{bmatrix} c_{21} & c_{22} & c_{23} & \cdots & c_{2N} \\ c_{31} & c_{32} & c_{33} & \cdots & c_{3N} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ c_{11} & c_{12} & c_{13} & \cdots & c_{1N} \end{bmatrix}
$$

These matrices are equal if and only if the equalities

$$
\begin{align*}
c_{1N} &= c_{21}, & c_{11} &= c_{22}, & \cdots & c_{1(N-1)} &= c_{2N} \\
c_{2N} &= c_{31}, & c_{21} &= c_{32}, & \cdots & c_{2(N-1)} &= c_{3N} \\
&\vdots    & \vdots    & \ddots    & \vdots    & \\
c_{NN} &= c_{11}, & c_{N1} &= c_{12}, & \cdots & c_{N(N-1)} &= c_{1N}
\end{align*}
$$

are satisfied. Then **C** can be written as

$$
\mathbf{C} = \begin{bmatrix} c_{11} & c_{12} & \cdots & c_{1N} \\ c_{21} & c_{22} & \cdots & c_{2N} \\ \vdots & \vdots & \ddots & \vdots \\ c_{N1} & c_{N2} & \cdots & c_{NN} \end{bmatrix} = \begin{bmatrix} c_{11} & c_{12} & \cdots & c_{1N} \\ c_{1N} & c_{11} & \cdots & c_{1(N-1)} \\ \vdots & \vdots & \ddots & \vdots \\ c_{12} & c_{13} & \cdots & c_{11} \end{bmatrix}
$$

which is a $N \times N$ circulant matrix with generating elements $c_{11}, c_{12}, \dots, c_{1N}$.

Any matrix that commutes with the cyclic forward shift matrix
is, therefore, a circulant. Theorem 4 also says that circulant
matrices are invariant under similarity transformations involving
the cyclic forward shift matrix. That is, $\mathbf{C}$ is similar to itself for a
similarity transformation using $\boldsymbol{\sigma}_N$.

Example 5. Consider the 3 × 3 matrix

$$
\mathbf{A} = \begin{bmatrix} a & b & c \\ c & a & b \\ b & c & a \end{bmatrix}
$$

Then

$$
\begin{bmatrix} a & b & c \\ c & a & b \\ b & c & a \end{bmatrix} \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} = \begin{bmatrix} c & a & b \\ b & c & a \\ a & b & c \end{bmatrix} \\
= \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} a & b & c \\ c & a & b \\ b & c & a \end{bmatrix}
$$

which implies that $\mathbf{A}\boldsymbol{\sigma}_3 = \boldsymbol{\sigma}_3\mathbf{A}$. Thus, $\mathbf{A} = \mathrm{circ}(a, b, c) \in \mathcal{C}_3$ is a circulant matrix of type $N=3$.

<figure><img src="image_19.png" /></figure>

Next we introduce block circulant matrices, which are natural generalizations of ordinary circulants.

**2.3 Block Circulant Matrices.** A block circulant matrix is obtained from a circulant matrix by replacing each entry $c_k$ in Definition 9 by the $M \times M$ matrix $\mathbf{C}_i$ for $i = 1, 2, \dots, N$.

DEFINITION 11 (Block Circulant Matrix). Let $\mathbf{C}_i$ be a $M \times M$ matrix for each $i = 1, 2, \dots, N$. Then a $NM \times NM$ block circulant matrix (or block circulant) is generated from the ordered set $\{\mathbf{C}_1, \mathbf{C}_2, \dots, \mathbf{C}_N\}$, and is of the form

$$
\mathbf{C} = \begin{bmatrix} \mathbf{C}_1 & \mathbf{C}_2 & \cdots & \mathbf{C}_N \\ \mathbf{C}_N & \mathbf{C}_1 & \cdots & \mathbf{C}_{N-1} \\ \vdots & \vdots & \ddots & \vdots \\ \mathbf{C}_2 & \mathbf{C}_3 & \cdots & \mathbf{C}_1 \end{bmatrix} \quad \Delta
$$

DEFINITION 12 (Generating Matrices). Let the NM × NM block circulant C be given by Definition 11. Then the elements of the ordered set

$$
\{\mathbf{C}_1, \mathbf{C}_2, \dots, \mathbf{C}_N\}
$$

are said to be the generating matrices of $\mathbf{C}$. $\triangle$

A block circulant is therefore defined completely by its generat-
ing matrices. The matrix array given by Definition 11 is said to be
a block circulant of type (M, N). The set of all such matrices is
denoted by $\mathcal{B}\mathcal{C}_{M,N}$. A matrix $\mathbf{C} \in \mathcal{B}\mathcal{C}_{M,N}$ is not necessarily a cir-
culant, as the following example demonstrates.

Example 6. Let

$$
\mathbf{A} = \begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix} \quad \text{and} \quad \mathbf{B} = \begin{bmatrix} -1 & 0 \\ 0 & -1 \end{bmatrix}
$$

Then
$$
C = \begin{bmatrix} A & B & 0 & B \\ B & A & B & 0 \\ 0 & B & A & B \\ B & 0 & B & A \end{bmatrix}
= \begin{bmatrix} 2 & -1 & |-1 & 0 & 0 & 0 & |-1 & 0 \\ -1 & 2 & 0 & -1 & 0 & 0 & 0 & -1 \\ -1 & 0 & 2 & -1 & -1 & 0 & 0 & 0 \\ 0 & -1 & -1 & 2 & 0 & -1 & 0 & 0 \\ 0 & 0 & -1 & 0 & 2 & -1 & -1 & 0 \\ 0 & 0 & 0 & -1 & -1 & 2 & 0 & -1 \\ |-1 & 0 & 0 & 0 & -1 & 0 & 2 & -1 \\ 0 & -1 & 0 & 0 & 0 & -1 & -1 & 2 \end{bmatrix}
$$

is a block circulant of type (2, 4), but it is not a circulant.

<figure><img src="image_20.png" /></figure>

Next we give a necessary and sufficient condition for a matrix
to be block circulant.

THEOREM 5. Let $\boldsymbol{\sigma}_N$ be the cyclic forward shift matrix of dimension $N$ and $\mathbf{I}_M$ be the identity matrix of dimension $M$. Then a $NM \times NM$ matrix $\mathbf{C}$ is a block circulant of type $(M, N)$ if and only if $\mathbf{C}(\boldsymbol{\sigma}_N \otimes \mathbf{I}_M) = (\boldsymbol{\sigma}_N \otimes \mathbf{I}_M)\mathbf{C}$. $\square$

<figure><img src="image_21.png" /></figure>

The proof of Theorem 5 follows similarly to that of Theorem 4 by replacing the scalar elements $c_{ik}$ with $M \times M$ matrices $C_{ik}$ for $i, k = 1, 2, \dots, N$. The reader can verify that the matrix $\mathbf{C}$ in Example 6 satisfies the condition in Theorem 5, but not that in Theorem 4.

A block circulant, block symmetric matrix of type (M, N) has generating matrices of the same form as Eq. (10), and is obtained by replacing each entry $c_k$ by the $M \times M$ matrix $\mathbf{C}_k$ for $k = 1, 2, \dots, N$. The set of all such matrices is denoted by $\mathcal{BCB}_{M,N}$. The matrix $\mathbf{C}$ in Example 6 is recognized to be a block symmetric, block circulant matrix of type (2, 4), that is, it is contained in $\mathcal{BCB}_{2,4}$, which is a subset of $\mathcal{BC}_{2,4}$.

**2.4 Representations of Circulants.** It is clear from Definition 5 that the $N \times N$ cyclic forward shift matrix is a circulant with $N$ generating elements $0, 1, 0, \dots, 0, 0$. The integer powers of $\boldsymbol{\sigma}_N$ can be written as

$$
\left.
\begin{aligned}
\boldsymbol{\sigma}_N^0 &= \operatorname{circ}(1, 0, 0, 0, 0, \dots, 0, 0) = \mathbf{I}_N \\
\boldsymbol{\sigma}_N^1 &= \boldsymbol{\sigma}_N = \operatorname{circ}(0, 1, 0, 0, 0, \dots, 0, 0) \\
\boldsymbol{\sigma}_N^2 &= \operatorname{circ}(0, 0, 1, 0, 0, \dots, 0, 0) \\
&\vdots \\
\boldsymbol{\sigma}_N^{N-1} &= \operatorname{circ}(0, 0, 0, 0, 0, \dots, 0, 1) \\
\boldsymbol{\sigma}_N^N &= \operatorname{circ}(1, 0, 0, 0, 0, \dots, 0, 0) = \boldsymbol{\sigma}_N^0 = \mathbf{I}_N
\end{aligned}
\right\} \qquad (11)
$$

where each successive power cyclically permutes the generating
elements. This enables the representation of a general circulant in
terms of a finite matrix polynomial involving the cyclic forward
shift matrix and its powers.

COROLLARY 3. Let $\mathbf{C} \in \mathcal{C}_N$ be a circulant matrix of type $N$ with generating elements $c_1, c_2, \dots, c_N$. Then $\mathbf{C}$ can be represented by the matrix sum

$$
\mathbf{C} = c_1 \boldsymbol{\sigma}_N^0 + c_2 \boldsymbol{\sigma}_N^1 + c_3 \boldsymbol{\sigma}_N^2 + \cdots + c_N \boldsymbol{\sigma}_N^{N-1}
$$

where $\boldsymbol{\sigma}_N$ is the $N \times N$ cyclic forward shift matrix.

<figure><img src="image_22.png" /></figure>

Example 7. The matrix **A** = circ(a, b, c) from Example 5 can be represented by the matrix sum

$$
\begin{align*}
\mathbf{A} &= a\boldsymbol{\sigma}_3^0 + b\boldsymbol{\sigma}_3^1 + c\boldsymbol{\sigma}_3^2 \\
&= a\mathbf{I}_3 + b\boldsymbol{\sigma}_3 + c\boldsymbol{\sigma}_3^2 \\
&= a\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} + b\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{bmatrix} + c\begin{bmatrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{bmatrix} \\
&= \begin{bmatrix} a & b & c \\ c & a & b \\ b & c & a \end{bmatrix}
\end{align*}
$$

where $\mathbf{I}_3$ and $\boldsymbol{\sigma}_3$ are the $3 \times 3$ identity and cyclic forward shift matrices.

<figure><img src="image_23.png" /></figure>

Corollary 3 is exploited in Sec. 2.5.4 to diagonalize a general circulant matrix, and can be generalized to represent a general block circulant matrix in terms of the cyclic forward shift matrix and its powers.

COROLLARY 4. Let $\mathbf{C} \in \mathcal{CB}_{M,N}$ be a block circulant matrix of type $(M, N)$ with generating matrices $\mathbf{C}_1, \mathbf{C}_2, \dots, \mathbf{C}_N$. Then $\mathbf{C}$ can be represented by the matrix sum

$$
\mathbf{C} = \boldsymbol{\sigma}_N^0 \otimes \mathbf{C}_1 + \boldsymbol{\sigma}_N^1 \otimes \mathbf{C}_2 + \dots + \boldsymbol{\sigma}_N^{N-1} \otimes \mathbf{C}_N
$$

where $\boldsymbol{\sigma}_N$ is the cyclic forward shift matrix.

<figure><img src="image_24.png" /></figure>

Corollaries 3 and 4 motivate the following result, which cap-
tures the representation of circulant and block circulant matrices
in terms of the cyclic forward shift matrix, and facilitates their
diagonalization in Secs. 2.5.4 and 2.5.5.

DEFINITION 13. Let **t** and **τ** be arbitrary square matrices. Then the function

$$
\rho(\mathbf{t}, \boldsymbol{\tau}) = \sum_{k=1}^{N} \mathbf{t}^{k-1} \otimes \boldsymbol{\tau}
$$

is a finite sum of direct products.

<figure><img src="image_25.png" /></figure>

COROLLARY 5. Let $\boldsymbol{\sigma}_N$ be the $N \times N$ cyclic forward shift matrix. Then a circulant matrix with generating elements $c_1, c_2, \dots, c_N$ and a block circulant matrix with generating elements $\mathbf{C}_1, \mathbf{C}_2, \dots, \mathbf{C}_N$ can be represented by the matrix sums

$$
\rho(\boldsymbol{\sigma}_N, c_k) = \sum_{k=1}^{N} \boldsymbol{\sigma}_N^{k-1} c_k = \operatorname{circ}(c_1, c_2, \dots, c_N)
$$

$$
\rho(\boldsymbol{\sigma}_N, \mathbf{C}_k) = \sum_{k=1}^{N} \boldsymbol{\sigma}_N^{k-1} \otimes \mathbf{C}_k = \operatorname{circ}(\mathbf{C}_1, \mathbf{C}_2, \dots, \mathbf{C}_N)
$$

where the function $\rho(\cdot)$ is given by Definition 13.

<figure><img src="image_26.png" /></figure>

What is meant by the notation $\rho(\boldsymbol{\sigma}_N, c_k)$, for example, is to sub-
stitute $\mathbf{t}$ with $\boldsymbol{\sigma}_N$ and $\boldsymbol{\tau}$ with $c_k$ in Definition 13 and then perform
the summation observing any indices $k$ introduced by the
substitution.

**2.5 Diagonalization of Circulants.** Any circulant or block circulant matrix can be represented in terms of the cyclic forward shift matrix according to Corollary 5. The diagonalization of a general circulant begins, therefore, by finding a matrix that diagonalizes $\boldsymbol{\sigma}_N$. Together with some basic results from linear algebra (these are summarized in Sec. 2.1), this leads naturally to the diagonalization of an arbitrary circulant. Regarding a suitable diagonalizing matrix, there are a number of candidates [10–12,16,17,100], but all feature powers of the Nth roots of unity or their real/imaginary parts. In this work, we employ an array composed of the distinct Nth roots of unity (Sec. 2.5.1) and their integer powers in the form of the complex Fourier matrix (Sec. 2.5.2). A unitary transformation involving the Fourier matrix is used to diagonalize the cyclic forward shift matrix (Sec. 2.5.3),
general circulant matrices (Sec. 2.5.4), and general block circulant matrices (Sec. 2.5.5).

### 2.5.1 Nth Roots of Unity.
A root of unity is any complex number that results in 1 when raised to some integer $N \in \mathbb{Z}_+$ [101]. More generally, the Nth roots of a complex number $z_o = r_o e^{i\theta_o}$ are given by a nonzero number $z = r e^{i\theta}$ such that

$$z^N = z_o \quad \text{or} \quad r^N e^{iN\theta} = r_o e^{i\theta_o} \qquad (12)$$

where $j = \sqrt{-1}$. Equation (12) holds if and only if $r^N = r_o$ and $N\theta = \theta_o + 2\pi k$ with $k \in \mathbb{Z}$. Therefore,

$$\left. \begin{aligned} r &= \sqrt[N]{r_o} \\ \theta &= \frac{\theta_o + 2\pi k}{N} \end{aligned} \right\} , \quad k \in \mathbb{Z} \qquad (13)$$

and the Nth roots are

$$z = \sqrt[N]{r_o} \exp \left( j \frac{\theta_o + 2\pi k}{N} \right), \quad k \in \mathbb{Z} \qquad (14)$$

Equation (14) shows that the roots all lie on a circle of radius $\sqrt[N]{r_o}$ centered at the origin in the complex plane, and that they are equally distributed every $2\pi/N$ radians. Thus, all of the distinct roots correspond to $k = 0, 1, 2, \dots, N-1$.

**DEFINITION 14 (Distinct Nth Roots of Unity).** The distinct Nth roots of unity follow from Eq. (14) by setting $r_o = 1$ and $\theta_o = 0$ and are denoted by

$$w_N^{(k)} = e^{j \frac{2\pi k}{N}}$$

for integers $k = 0, 1, 2, \dots, N-1$. △

**DEFINITION 15 (Primitive Nth Root of Unity).** The primitive Nth root of unity is denoted by

$$w_N = e^{j \frac{2\pi k}{N}}$$

which corresponds to $k = 1$ in Definition 14. △

**COROLLARY 6.** The integer powers $w_N^k$ of the primitive Nth root of unity are equivalent to the distinct Nth roots of unity $w_N^{(k)}$ for $k = 1, 2, \dots, N$. □

*Proof.* Consider $w_N^k = (e^{j\frac{2\pi k}{N}})^k = e^{j\frac{2\pi k}{N}} = w_N^{(k)}$, which follows from Definition 14. Thus, the powers

$$1, w_N^1, w_N^2, \dots, w_N^{N-1}$$

are equivalent to the distinct Nth roots of unity

$$1, w_N^{(1)}, w_N^{(2)}, \dots, w_N^{(N-1)}$$

where $w_N^0 = w_N^{(0)} = 1$. ■

Example plots of the distinct Nth roots of unity are shown in Fig. 2, where $w_N^{(k)}$ are arranged on the unit circle in the complex plane (centered at the origin) for $N = 1, 2, \dots, 9$. Note that $w_N^{(0)} = 1$ is real, as is $w_N^{(N/2)} = -1$ if N is even. The remaining roots appear in complex conjugate pairs. Thus, the distinct Nth roots of unity are symmetric about the real axis in the complex plane.

**Example 8.** Let $N = 4$. Then the distinct Nth roots of unity are given by the set

$$\begin{aligned} \{w_4^0, w_4^1, w_4^2, w_4^3\} &= \{e^{j\frac{2\pi}{4}} - 0, e^{j\frac{2\pi}{4}} - 1, e^{j\frac{2\pi}{4}} - 2, e^{j\frac{2\pi}{4}} - 3\} \\ &= \{e^0, e^{j\frac{\pi}{2}}, e^{j\pi}, e^{j\frac{3\pi}{2}}\} \\ &= \{1, j, -1, -j\} \end{aligned}$$

These four distinct roots of unity can be visualized in Fig. 2 for the case of $N = 4$. ☰

**DEFINITION 16.** Let $w_N$ be the primitive Nth root of unity. Then

$$\begin{aligned} \mathbf{\Omega}_N &= \begin{bmatrix} 1 & & & & 0 \\ & w_N & & & \\ & & w_N^2 & & \\ & & & \ddots & \\ & & & & w_N^{N-1} \end{bmatrix}_{N \times N} \\ &= \operatorname{diag}(1, w_N, w_N^2, \dots, w_N^{N-1}) \end{aligned}$$

is the $N \times N$ diagonal matrix formed by placing the distinct Nth roots of unity 1, $w_N$, $w_N^2, \dots, w_N^{N-1}$ along its diagonal. △

The matrix $\mathbf{\Omega}_N$ appears naturally in the diagonalization of circulants, which is discussed in Secs. 2.5.3–2.5.5.

### 2.5.2 The Fourier Matrix.
This section introduces the complex Fourier matrix and its relevant properties, including the symmetric structure of the N-vectors that compose its columns. A key result is that the Fourier matrix is unitary, which is systematically developed and proved.

**DEFINITION 17 (Fourier Matrix).** The $N \times N$ Fourier matrix is defined as

$$\mathbf{E}_N = \frac{1}{\sqrt{N}} \begin{bmatrix} 1 & 1 & 1 & \cdots & 1 \\ 1 & w_N & w_N^2 & \cdots & w_N^{N-1} \\ 1 & w_N^2 & w_N^4 & \cdots & w_N^{2(N-1)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & w_N^{N-1} & w_N^{2(N-1)} & \cdots & w_N^{(N-1)(N-1)} \end{bmatrix}_{N \times N}$$

where $w_N$ is the primitive Nth root of unity and $N \in \mathbb{Z}_+$. △

LABELING KEY

<figure><img src="image_27.png" /></figure>

<figure><img src="image_28.png" /><figcaption>**Fig. 2** Example plots of the distinct Nth roots of unity</figcaption></figure>
**Example 9.** For the special case of $N=4$, the Fourier matrix is given by

$$ \mathbf{E}_4 = \frac{1}{\sqrt{4}} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & j & -1 & -j \\ 1 & -1 & 1 & -1 \\ 1 & -j & -1 & j \end{bmatrix} \quad \square $$

Clearly the Fourier matrix is symmetric, but generally it is not Hermitian. It can be written element wise as

$$ \begin{aligned} (\mathbf{E}_N)_{ik} &= \frac{1}{\sqrt{N}} w_N^{(i-1)(k-1)} \\ &= \frac{1}{\sqrt{N}} e^{i(j-1)\phi_k} \\ &= \frac{1}{\sqrt{N}} e^{i(k-1)\phi_i}, \quad i, k = 1, 2, \dots, N \end{aligned} \quad (15) $$

where

$$ \phi_i = \frac{2\pi}{N} (i - 1) \quad (16) $$

is the angle subtended from the positive real axis in the complex plane to the $i$th power of $w_N$, which is also the $(i+1)$th of the $N$ roots of unity according to Definition 14 and the numbering scheme in Fig. 2.

**COROLLARY 7.** The matrix $\mathbf{E}_N^H$ is obtained from $\mathbf{E}_N$ by changing the signs of the powers of each element. □

**Proof.** The Fourier matrix is unaffected by transposition because it is symmetric. Thus, the $(i, k)$ element of $\mathbf{E}_N^H$ is

$$ (\mathbf{E}_N^H)_{ik} = (\overline{\mathbf{E}_N})_{ik} = \frac{1}{\sqrt{N}} w_N^{(i-1)(k-1)} = \frac{1}{\sqrt{N}} w_N^{-(i-1)(k-1)} $$

where the identity

$$ \overline{w_N^k} = \overline{e^{j \frac{2\pi k}{N}}} = e^{-j \frac{2\pi k}{N}} = (e^{j \frac{2\pi}{N}})^{-k} = w_N^{-k}, \quad k \in \mathbb{Z} $$

is employed. It follows that $\mathbf{E}_N^H$ can be obtained from $\mathbf{E}_N$ by changing the sign of the powers of the $N$th roots of unity. ■

It is shown in Sec. 2.8 that all circulant matrices contained in $\mathcal{C}_N$ share the same linearly independent eigenvectors, the elements of which compose the $N$ columns (or rows) of $\mathbf{E}_N$.

**DEFINITION 18.** Let $w_N$ be the primitive $N$th root of unity. Then for $i=1, 2, \dots, N$ the columns of the Fourier matrix $\mathbf{E}_N$ are defined by

$$ \begin{aligned} \mathbf{e}_i &= \frac{1}{\sqrt{N}} \left( 1, w_N^{(i-1)}, w_N^{2(i-1)}, \dots, w_N^{(N-1)(i-1)} \right)^T \\ &= \frac{1}{\sqrt{N}} \left( 1, e^{j\phi_i}, e^{j2\phi_i}, \dots, e^{j(N-1)\phi_i} \right)^T \end{aligned} $$

where $\phi_i$ is given by Eq. (16). △

**Example 10.** The third column of the Fourier matrix $\mathbf{E}_4$ is given by

$$ \begin{aligned} \mathbf{e}_3 &= \frac{1}{\sqrt{4}} \left( 1, w_4^{(3-1)}, w_4^{2(3-1)}, w_4^{3(3-1)} \right)^T \\ &= \frac{1}{2} \left( 1, w_4^2, w_4^4, w_4^6 \right)^T \\ &= \frac{1}{2} \left( 1, e^{j\frac{2\pi}{4}}, e^{j\frac{2\pi}{4}}, e^{j\frac{2\pi}{4}} \right)^T \\ &= \frac{1}{2} \left( 1, e^{j\pi}, e^{j2\pi}, e^{j3\pi} \right)^T \\ &= \frac{1}{2} \left( 1, -1, 1, -1 \right)^T \end{aligned} $$

for the special case of $N=4$.

The columns $\mathbf{e}_i$ of the Fourier matrix $\mathbf{E}_N = (\mathbf{e}_1, \dots, \mathbf{e}_N)$ exhibit a symmetric structure with respect to the index $i=(N+2)/2$ for even $N$. In Example 9, for instance, the vectors $\mathbf{e}_1$ and $\mathbf{e}_{(N+2)/2} = \mathbf{e}_3$ are real and distinct, and the vectors $\mathbf{e}_2$ and $\mathbf{e}_4$ appear in complex conjugate pairs. This same structure generally holds for any $\mathbf{E}_N$ with even $N$. To see this, consider

$$ \begin{aligned} \mathbf{e}_{\frac{N}{2} \pm \frac{1}{2} + q} &= \frac{1}{\sqrt{N}} \left( 1, (w_N^{\frac{\zeta}{2} \pm q})^1, \dots, (w_N^{\frac{\zeta}{2} \pm q})^{N-1} \right)^T \\ &= \frac{1}{\sqrt{N}} \left( 1, (-w_N^{\pm q})^1, \dots, (-w_N^{\pm q})^{N-1} \right)^T \end{aligned} \quad (17) $$

where the integers $\pm q$ correspond to vector pairs relative to the index $i = (N + 2)/2$ and the identity

$$ w_N^{\frac{N}{2} \pm q} = w_N^{\frac{N}{2}} w_N^{\pm q} = -w_N^{\pm q} $$

is employed. The case of $q=0$ corresponds to $i = (N + 2)/2$ and yields the real vector

$$ \mathbf{e}_{\frac{N}{2} \pm} = \frac{1}{\sqrt{N}} (1, -1, 1, \dots, -1, 1)^T \quad (18) $$

which has the same value for each element with alternating signs from element to element. For $q \neq 0$ the terms $w_N^{\pm q}$ are complex conjugates according to the proof of Corollary 7 such that $\mathbf{e}_{((N+2)/2)+q}$ and $\mathbf{e}_{((N+2)/2)-q}$ are complex conjugate pairs. There are $(N-2)/2$ such pairs corresponding to $q = \{1, 2, \dots, (N-2)/2\}$ in Eq. (17). Finally, the case of $i=1$ always yields the real vector

$$ \mathbf{e}_1 = \frac{1}{\sqrt{N}} (1, 1, 1, \dots, 1, 1)^T \quad (19) $$

for even and odd $N$. A similar formulation for odd $N$ shows that $\mathbf{e}_1$ is real and distinct and the remaining $(N-1)/2$ vectors appear in complex conjugate pairs. This is shown by example in Sec. 3.3 in the context of vibration modes for a cyclic structure with a single DOF per sector.

A key feature of the Fourier matrix is that it is unitary. This is essentially a statement of orthogonality of each column of $\mathbf{E}_N$ and is captured by the following lemmas.

**LEMMA 1** (Finite Geometric Series Identity). Let $N \in \mathbb{Z}_+$ and $q \in \mathbb{C}$. Then

$$ \sum_{r=s}^{s+N-1} q^r = \frac{q^s(1-q^N)}{1-q} $$

for any $s \in \mathbb{Z}$ and $q \neq 1$. □

**Proof.** Consider the finite geometric series

$$ \begin{aligned} \sum_{r=s}^{s+N-1} q^r &= q^s + q^{s+1} + q^{s+2} + \dots + q^{s+N-1} \\ &= q^s(1 + q + q^2 + \dots + q^{N-1}) \end{aligned} $$

Multiplying from the left by $q$ yields

$$ q \sum_{r=s}^{s+N-1} q^r = q^s (q + q^2 + q^3 + \dots + q^N) $$

Subtraction of the second equation from the first results in

$$ (1-q) \sum_{r=s}^{s+N-1} q^r = q^s (1-q^N) $$
from which the proof is established by division of the term $(1-q)$ because $q \neq 1$ by restriction. ■

Lemma 1 is used to establish the following result, which is required to show that the Fourier matrix is unitary. The orthogonality condition is fundamental to the diagonalization of circulants in Secs. 2.5.3–2.5.5, and the relationship between the DFT and IDFT in Sec. 2.7.

**LEMMA 2.** Let $w_N$ be the primitive $N$th root of unity with $N \in \mathbb{Z}_+$. Then

$$ \sum_{r=s}^{s+N-1} w_N^{r(i-k)} = \begin{cases} N, & i-k=mN \\ 0, & \text{otherwise} \end{cases} $$

for $i, k \in \mathbb{Z}$ and any $s, m \in \mathbb{Z}$. □

*Proof.* Let $q = w_N^{(i-k)} = e^{j2\pi(i-k)/N}$ and note that $q^N = 1$. If $i-k=mN$, then $q = e^{j2\pi m} = 1$ for any integer $m$, and it follows that

$$ \begin{aligned} \sum_{r=s}^{s+N-1} w_N^{r(i-k)} &= \sum_{r=s}^{s+N-1} q^r \\ &= \underbrace{(1)^s + (1)^{s+1} + \dots + (1)^{s+N-1}}_{N \text{ terms}} \\ &= N \end{aligned} $$

For the case of $i-k \neq mN$ it follows from Lemma 1 that

$$ \begin{aligned} \sum_{r=0}^{N-1} w_N^{r(i-k)} &= \sum_{r=0}^{N-1} q^r \\ &= \frac{1-q^N}{1-q} \tag{Lem. 1} \\ &= \frac{1-1}{1-q} \\ &= 0 \end{aligned} $$

which completes the proof. ■

*Example 11.* Consider the orthogonality condition given by Lemma 2 for $s=0$. Then if $i-k=N=5$,

$$ \begin{aligned} \sum_{r=0}^{5-1} w_5^{r \cdot 5} &= \sum_{r=0}^{4} (e^{j \frac{2\pi}{2} r})^{5r} \\ &= \sum_{r=0}^{4} e^{j \frac{2\pi}{5} 5r} \\ &= e^0 + e^{j2\pi} + e^{j4\pi} + e^{j6\pi} + e^{j8\pi} \\ &= 1+1+1+1+1 \\ &= 5 \end{aligned} $$

which is numerically equal to N, as expected. If instead we set $i-k=5$ but $N=4$, then

$$ \begin{aligned} \sum_{r=0}^{4-1} w_4^{r \cdot 5} &= \sum_{r=0}^{3} \left(e^{j \frac{2\pi}{4} r}\right)^{5r} \\ &= \sum_{r=0}^{3} e^{j \frac{2\pi}{4} 5r} \\ &= \sum_{r=0}^{3} e^{j \frac{5\pi}{2} r} \\ &= e^{\frac{5\pi}{2} 0} + e^{\frac{5\pi}{2} 1} + e^{\frac{5\pi}{2} 2} + e^{\frac{5\pi}{2} 3} \\ &= e^0 + e^{\frac{5\pi}{2}} + e^{5\pi} + e^{\frac{15\pi}{2}} \\ &= 1 + j - 1 - j \\ &= 0 \end{aligned} $$

sums to zero.

Lemma 2 allows for representations of the $N \times N$ identity, flip, and cyclic forward shift matrices in terms of certain conditions on their indices relative to N.

**COROLLARY 8.** For $i, k = 1, \dots, N$ and any integer $m$, the $(i, k)$ elements of the $N \times N$ identity, flip, and cyclic forward shift matrices can be represented by the summations

$$ \begin{aligned} \delta_{ik} &= (\mathbf{I}_N)_{ik} = \frac{1}{N} \sum_{r=0}^{N-1} w_N^{r(i-k)} = \begin{cases} 1, & i-k=mN \\ 0, & \text{otherwise} \end{cases} \\ (\mathbf{\kappa}_N)_{ik} &= \frac{1}{N} \sum_{r=0}^{N-1} w_N^{r(i+k-2)} = \begin{cases} 1, & i+k-2=mN \\ 0, & \text{otherwise} \end{cases} \\ (\mathbf{\sigma}_N)_{ik} &= \frac{1}{N} \sum_{r=0}^{N-1} w_N^{r(i-k+1)} = \begin{cases} 1, & i-k+1=mN \\ 0, & \text{otherwise} \end{cases} \end{aligned} $$

where $\delta_{ik}$ is the Kronecker delta. □

The reader can verify Corollary 8 for the special case of $N=3$ by inspection of the arrays in Fig. 3.

We are now ready to state the key result required to diagonalize a general circulant matrix. Corollaries 7 and 8 are used to show that the Fourier matrix is unitary.

**THEOREM 6 (Unitary Fourier Matrix).** The Fourier matrix $\mathbf{E}_N$ is unitary. □

*Proof.* For $1 \le i, k \le N$, the $(i, k)$ entry of $\mathbf{E}_N^H \mathbf{E}_N$ is given by

$$ \begin{aligned} (\mathbf{E}_N^H \mathbf{E}_N)_{ik} &= \sum_{r=1}^{N} (\mathbf{E}_N^H)_{ir} (\mathbf{E}_N)_{rk} \\ &= \sum_{r=1}^{N} \frac{1}{\sqrt{N}} w_N^{-(i-1)(r-1)} \\ &\quad \times \frac{1}{\sqrt{N}} w_N^{(r-1)(k-1)} \tag{Eq. 15 and Cor. 7} \\ &= \frac{1}{N} \sum_{r=1}^{N} w_N^{(r-1)(i-k)} \\ &= \frac{1}{N} \sum_{r=0}^{N-1} w_N^{r(i-k)} \\ &= (\mathbf{I}_N)_{ik} \tag{Cor. 8} \end{aligned} $$

from which it follows that $\mathbf{E}_N^H \mathbf{E}_N = \mathbf{I}_N$. ■

*Example 12.* Consider the matrix $\mathbf{E}_4$ from Example 9. Because the Fourier matrix is unitary, it follows that

<figure><img src="image_29.png" /><figcaption>**Fig. 3** Arrays showing the $(i, k)$ elements of the (a) identity, (b) flip, and (c) cyclic forward shift matrices of dimension $N=3$ for $i, k=1, 2, 3$</figcaption></figure>

<figure><img src="image_30.png" /></figure>
$$
\begin{align*}
\mathbf{E}_4^H \mathbf{E}_4 &= \frac{1}{\sqrt{4}} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \end{bmatrix} \frac{1}{\sqrt{4}} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & j & -1 & -j \\ 1 & -1 & 1 & -1 \\ 1 & -j & -1 & j \end{bmatrix} \\
&= \frac{1}{4} \begin{bmatrix} 4 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 \\ 0 & 0 & 4 & 0 \\ 0 & 0 & 0 & 4 \end{bmatrix} \\
&= \mathbf{I}_4
\end{align*}
$$

where $\mathbf{I}_4$ is the $4 \times 4$ identity matrix.

The following corollaries follow from Theorem 6.

COROLLARY 9. If $\mathbf{E}_N$ is the unitary Fourier matrix, then $\bar{\mathbf{E}}_N$ is also unitary. $\square$

*Proof.* Note that $\mathbf{E}_N^H = \mathbf{E}_N^T = \mathbf{E}_N$ because $\mathbf{E}_N = \mathbf{E}_N^T$ is symmetric. It follows that

$$
\begin{align*}
\bar{\mathbf{E}}_N^H \bar{\mathbf{E}}_N &= \mathbf{E}_N^T \bar{\mathbf{E}}_N \\
&= \mathbf{E}_N \bar{\mathbf{E}}_N \\
&= \mathbf{E}_N \mathbf{E}_N^H \\
&= \mathbf{E}_N^H \mathbf{E}_N \tag{Eq. 8} \\
&= \mathbf{I}_N \tag{Thm. 6}
\end{align*}
$$

which implies that $\bar{\mathbf{E}}_N$ is unitary.

Example 13. Consider the unitary matrix $\mathbf{E}_4$ from Example 12. Corollary 9 guarantees that $\bar{\mathbf{E}}_4$ is also unitary. Thus,

$$
\begin{align*}
\bar{\mathbf{E}}_4^H \bar{\mathbf{E}}_4 &= \frac{1}{\sqrt{4}} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \end{bmatrix} \frac{1}{\sqrt{4}} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & j & -1 & -j \\ 1 & -1 & 1 & -1 \\ 1 & -j & -1 & j \end{bmatrix} \\
&= \frac{1}{4} \begin{bmatrix} 4 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 \\ 0 & 0 & 4 & 0 \\ 0 & 0 & 0 & 4 \end{bmatrix} \\
&= \mathbf{I}_4
\end{align*}
$$

as expected.

COROLLARY 10. Let $\mathbf{e}_i$ denote the $i$-th column of the Fourier matrix $\mathbf{E}_N$ and $\delta_{ik}$ be the Kronecker delta. Then

$$
\mathbf{e}_i^H \mathbf{e}_k = \delta_{ik}
$$

for $i, k = 1, 2, \dots, N$.

*Proof.* For $i, k = 1, 2, \dots, N$, the $(i, k)$ entry of $\mathbf{E}_N^H \mathbf{E}_N$ can be written as

$$
\begin{align*}
(\mathbf{e}_i^H \mathbf{e}_k)_{ik} &= (\mathbf{E}_N^H \mathbf{E}_N)_{ik} \\
&= (\mathbf{I}_N)_{ik} \tag{Thm. 6}
\end{align*}
$$

where $\mathbf{I}_N$ is the $N \times N$ identity matrix. Thus, $\mathbf{e}_i^H \mathbf{e}_k = \delta_{ik}$.

Corollary 10 shows that the columns (and rows) of the Fourier matrix are mutually orthogonal. The result can also be proved by

expanding the product $\mathbf{e}_i^H \mathbf{e}_k$ according to Eq. (15) and invoking Lemma 2, as is done in the proof of Theorem 6. The same result also follows by expanding

$$
\begin{align}
\mathbf{E}_N^H \mathbf{E}_N &= \begin{bmatrix} \mathbf{e}_1^H \\ \vdots \\ \mathbf{e}_i^H \\ \vdots \\ \mathbf{e}_N^H \end{bmatrix} [\mathbf{e}_1 \ \cdots \ \mathbf{e}_k \ \cdots \ \mathbf{e}_N] \nonumber \\
&= \begin{bmatrix} \mathbf{e}_1^H \mathbf{e}_1 & \cdots & \mathbf{e}_1^H \mathbf{e}_k & \cdots & \mathbf{e}_1^H \mathbf{e}_N \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ \mathbf{e}_i^H \mathbf{e}_1 & \cdots & \mathbf{e}_i^H \mathbf{e}_k & \cdots & \mathbf{e}_i^H \mathbf{e}_N \\ \vdots & \ddots & \vdots & \ddots & \vdots \\ \mathbf{e}_N^H \mathbf{e}_1 & \cdots & \mathbf{e}_N^H \mathbf{e}_k & \cdots & \mathbf{e}_N^H \mathbf{e}_N \end{bmatrix} \tag{20} \\
&= \mathbf{I}_N \nonumber
\end{align}
$$

which is a statement of unitary $\mathbf{E}_N$. The matrix equality holds only if each $\mathbf{e}_i^H \mathbf{e}_k = \delta_{ik}$ for $i, k = 1, 2, \dots, N$.

Example 14. Consider the vector $\mathbf{e}_3 = \frac{1}{2}(1, -1, 1, -1)^T$ from Example 10. Then the product

$$
\begin{align*}
\mathbf{e}_3^H \mathbf{e}_3 &= \frac{1}{2} [\begin{smallmatrix} 1 & -1 & 1 & -1 \end{smallmatrix}] \frac{1}{2} \begin{bmatrix} 1 \\ -1 \\ 1 \\ -1 \end{bmatrix} \\
&= \frac{1}{4} (1 + 1 + 1 + 1) \\
&= 1
\end{align*}
$$

corresponds to $\delta_{33} = 1$ in Corollary 10. However, the product

$$
\begin{align*}
\mathbf{e}_3^H \mathbf{e}_2 &= \frac{1}{2} [\begin{smallmatrix} 1 & -1 & 1 & -1 \end{smallmatrix}] \frac{1}{2} \begin{bmatrix} 1 \\ j \\ -1 \\ -j \end{bmatrix} \\
&= \frac{1}{4} (1 - j - 1 + j) \\
&= 0
\end{align*}
$$

vanishes because $\mathbf{e}_2$ and $\mathbf{e}_3$ are mutually orthogonal.

COROLLARY 11. If $\mathbf{E}_N$ is the $N \times N$ Fourier matrix and $\mathbf{I}_M$ is the identity matrix of dimension $M$, then the $NM \times NM$ matrix $\mathbf{E}_N \otimes \mathbf{I}_M$ is unitary. $\square$

*Proof.* Consider the matrix product

$$
\begin{align*}
(\mathbf{E}_N \otimes \mathbf{I}_M)^H (\mathbf{E}_N \otimes \mathbf{I}_M) \\
&= (\mathbf{E}_N^H \otimes \mathbf{I}_M^H) (\mathbf{E}_N \otimes \mathbf{I}_M) \tag{Eq. 6b} \\
&= (\mathbf{E}_N^H \mathbf{E}_N) \otimes (\mathbf{I}_M^H \mathbf{I}_M) \tag{Eq. 4}
\end{align*}
$$
$$ \begin{aligned} \mathbf{I}_N \otimes \mathbf{I}_M \\ = \mathbf{I}_{NM} \end{aligned} \qquad (\text{Thm. 6}) $$

where $\mathbf{I}_N$ and $\mathbf{I}_{NM}$ are identity matrices of dimension $N$ and $NM$, respectively.

COROLLARY 12. If $\mathbf{e}_i$ denotes the $i$th column of the Fourier matrix $\mathbf{E}_N$, $\mathbf{I}_M$ is the identity matrix of dimension $M$, and $\delta_{ik}$ is the Kronecker delta, then the $NM \times M$ matrices $\mathbf{e}_i \otimes \mathbf{I}_M$ are such that

$$ (\mathbf{e}_i \otimes \mathbf{I}_M)^H (\mathbf{e}_k \otimes \mathbf{I}_M) = \delta_{ik} \mathbf{I}_M $$

$$ \text{for } i, k = 1, 2, \dots, N. \qquad \square $$

*Proof.* Consider the matrix product

$$ (\mathbf{e}_i \otimes \mathbf{I}_M)^H (\mathbf{e}_k \otimes \mathbf{I}_M) = (\mathbf{e}_i^H \otimes \mathbf{I}_M^H)(\mathbf{e}_k \otimes \mathbf{I}_M) \qquad (\text{Eq. 6b}) $$

$$ = (\mathbf{e}_i^H \mathbf{e}_k) \otimes (\mathbf{I}_M^H \mathbf{I}_M) \qquad (\text{Eq. 4}) $$

$$ = \delta_{ik} \otimes \mathbf{I}_M \qquad (\text{Cor. 10}) $$

$$ = \delta_{ik} \mathbf{I}_M $$

which completes the proof. ■

Corollary 12 can also be obtained directly from Corollary 11 by writing

$$ \mathbf{E}_N^H \otimes \mathbf{I}_M = \begin{bmatrix} \mathbf{e}_1^H \\ \mathbf{e}_2^H \\ \vdots \\ \mathbf{e}_N^H \end{bmatrix} \otimes \mathbf{I}_M = \begin{bmatrix} \mathbf{e}_1^H \otimes \mathbf{I}_M \\ \mathbf{e}_2^H \otimes \mathbf{I}_M \\ \vdots \\ \mathbf{e}_N^H \otimes \mathbf{I}_M \end{bmatrix} $$

and

$$ \begin{aligned} \mathbf{E}_N \otimes \mathbf{I}_M &= (\mathbf{e}_1, \mathbf{e}_2, \dots, \mathbf{e}_N) \otimes \mathbf{I}_M \\ &= (\mathbf{e}_1 \otimes \mathbf{I}_M, \mathbf{e}_2 \otimes \mathbf{I}_M, \dots, \mathbf{e}_N \otimes \mathbf{I}_M) \end{aligned} $$

expanding these matrices similarly to Eq. (20), and setting the result equal to $\mathbf{I}_{NM} = \text{diag}(\mathbf{I}_M, \mathbf{I}_M, \dots, \mathbf{I}_M)$.

Next we derive a relationship between the Fourier and flip matrices.

THEOREM 7. Let $\mathbf{E}_N$ and $\mathbf{\kappa}_N$ denote the $N \times N$ Fourier and flip matrices, respectively. Then

$$ \mathbf{E}_N^2 = \mathbf{\kappa}_N = (\mathbf{E}_N^H)^2. \qquad \square $$

*Proof.* We first shown that $\mathbf{E}_N^2 = \mathbf{E}_N \mathbf{E}_N = \mathbf{\kappa}_N$. For any integer $m$ and $i, k = 1, 2, \dots, N$, the $(i, k)$ entry of $\mathbf{E}_N \mathbf{E}_N$ is given by

$$ \begin{aligned} (\mathbf{E}_N \mathbf{E}_N)_{ik} &= \sum_{r=1}^{N} (\mathbf{E}_N)_{ir} (\mathbf{E}_N)_{rk} \\ &= \sum_{r=1}^{N} \frac{1}{\sqrt{N}} w_N^{(i-1)(r-1)} \frac{1}{\sqrt{N}} w_N^{(r-1)(k-1)} \qquad (\text{Eq. 15}) \\ &= \frac{1}{N} \sum_{r=0}^{N-1} w_N^{r(i+k-2)} \\ &= (\mathbf{\kappa}_N)_{ik} \qquad (\text{Cor. 8}) \end{aligned} $$

from which it follows that $\mathbf{E}_N^2 = \mathbf{\kappa}_N$. The result $\mathbf{\kappa}_N = (\mathbf{E}_N^H)^2$ follows from complex conjugation and transposition of $\mathbf{\kappa}_N = \mathbf{E}_N \mathbf{E}_N$, and by invoking the properties $\mathbf{\kappa}_N^H = \mathbf{\kappa}_N$ and $(\mathbf{E}_N^2)^H = (\mathbf{E}_N^H)^2$. ■

A number of properties follow directly from Theorem 7.

COROLLARY 13. Let $\mathbf{E}_N$ and $\mathbf{\kappa}_N$ be the $N \times N$ Fourier and flip matrices. Then

(a) $\mathbf{E}_N \mathbf{\kappa}_N = \mathbf{\kappa}_N \mathbf{E}_N$;

(b) $\mathbf{\kappa}_N^2 = \mathbf{I}_N$ or $\mathbf{\kappa}_N = \sqrt{\mathbf{I}_N}$; and

(c) $\mathbf{E}_N^2 = \mathbf{I}_N$ or $\mathbf{E}_N = \sqrt{\mathbf{I}_N}$

where $\mathbf{I}_N$ is the $N \times N$ identity matrix. □

Property (a) of Corollary 13 says that the flip and Fourier matrices commute or, since $\mathbf{E}_N$ is unitary, that $\mathbf{\kappa}_N$ is invariant under a unitary transformation with respect to $\mathbf{E}_N$. Thus, $\mathbf{\kappa}_N$ is not diagonalizable by $\mathbf{E}_N$. Properties (b) and (c) give alternative definitions of the flip and Fourier matrices. Moreover, because the power of a diagonal matrix is obtained by raising each diagonal element to the power in question, it follows that the eigenvalues of $\mathbf{\kappa}_N$ are $\pm 1$ and those of $\mathbf{E}_N$ are $\pm 1$ and $\pm j$, each with the appropriate multiplicities.

### 2.5.3 Diagonalization of the Cyclic Forward Shift Matrix.
In light of Corollary 5, diagonalization of a general circulant or block circulant matrix begins by diagonalizing the cyclic forward shift matrix.

THEOREM 8. Let $\mathbf{E}_N$ be the $N \times N$ Fourier matrix and $\mathbf{\sigma}_N$ be the $N \times N$ cyclic forward shift matrix. Then

$$ \mathbf{E}_N^H \mathbf{\sigma}_N \mathbf{E}_N = \mathbf{\Omega}_N $$

is a diagonal matrix, where $\mathbf{\Omega}_N$ is given by Definition 16. □

*Proof.* For $i, k = 1, 2, \dots, N$, the $(i, k)$ entry of $\mathbf{E}_N \mathbf{\Omega}_N \mathbf{E}_N^H$ is given by

$$ \begin{aligned} (\mathbf{E}_N \mathbf{\Omega}_N \mathbf{E}_N^H)_{ik} &= \sum_{r=1}^{N} \sum_{p=1}^{N} (\mathbf{E}_N)_{ip} (\mathbf{\Omega}_N)_{pr} (\mathbf{E}_N^H)_{rk} \\ &= \sum_{r=1}^{N} \sum_{p=1}^{N} \frac{1}{\sqrt{N}} w_N^{(i-1)(p-1)} \delta_{pr} w_N^{(r-1)} \\ & \qquad \times \frac{1}{\sqrt{N}} w_N^{-(r-1)(k-1)} \qquad (\text{Eq. 15}) \\ &= \frac{1}{N} \sum_{r=1}^{N} w_N^{(i-1)(r-1)} w_N^{(r-1)} w^{-(r-1)(k-1)} \\ &= \frac{1}{N} \sum_{r=1}^{N} w_N^{(r-1)(i-k+1)} \\ &= \frac{1}{N} \sum_{r=0}^{N-1} w_N^{r(i-k+1)} \\ &= (\mathbf{\sigma}_N)_{ik} \qquad (\text{Cor. 8}) \end{aligned} $$

from which it follows that $\mathbf{E}_N \mathbf{\Omega}_N \mathbf{E}_N^H = \mathbf{\sigma}_N$. The desired result follows by multiplying from the left by $\mathbf{E}_N^H$, multiplying from the right by $\mathbf{E}_N$, and invoking Theorem 6. ■

Theorem 8 implies that $\mathbf{\sigma}_N$ is unitarily similar to a diagonal matrix whose diagonal elements are the distinct $N$th root of unity (i.e., Definition 16). Because the eigenvalues of a matrix are preserved under such a transformation (this is guaranteed by Theorem 1), it follows that

$$ \alpha(\mathbf{\sigma}_N) = \alpha(\mathbf{\Omega}_N) = \{1, w_N, w_N^2, \dots, w_N^{N-1}\} $$

where $\alpha(\cdot)$ denotes the matrix spectrum. The eigenvectors of the circulant matrix $\mathbf{\sigma}_N$ are the linearly independent columns of $\mathbf{E}_N = (\mathbf{e}_1, \mathbf{e}_2, \dots, \mathbf{e}_N)$, which are given by Definition 18. In fact, all circulant matrices contained in $\mathcal{C}_N$ share the same eigenvectors
$e_i$, which is shown in Sec. 2.8. In light of Corollary 2, we have the following results.

**COROLLARY 14.** Let $\mathbf{E}_N$ and $\boldsymbol{\sigma}_N$ be the $N \times N$ Fourier and cyclic forward shift matrices. Then for any $n \in \mathbb{Z}_+$,

$$ \mathbf{E}_N^H \boldsymbol{\sigma}_N^n \mathbf{E}_N = \boldsymbol{\Omega}_N^n $$

where $\boldsymbol{\Omega}_N$ given by Definition 16. $\square$

**COROLLARY 15.** Let $\mathbf{e}_i$ be the ith column of the Fourier matrix $\mathbf{E}_N$ and $\boldsymbol{\sigma}_N$ be cyclic forward shift matrix. Then for any $n \in \mathbb{Z}_+$ and $i, k = 1, 2, \dots, N$,

$$ \begin{aligned} \mathbf{e}_i^H \boldsymbol{\sigma}_N^n \mathbf{e}_k &= (w_N^{j-1})^n \delta_{ik} \\ &= w_N^{n(i-1)} \delta_{ik} \end{aligned} $$

where $\delta_{ik}$ is the Kronecker delta. $\square$

Corollary 15 shows that the columns of the Fourier matrix are orthogonal with respect to the cyclic forward shift matrix and its powers. It is shown in Sec. 2.5.4 that they are in fact orthogonal with respect to any circulant matrix.

### 2.5.4 Diagonalization of a Circulant.

**Corollary 16.** Let the matrix $\boldsymbol{\Omega}_N$ be populated with the distinct Nth roots of unity according to Definition 16 and $\boldsymbol{\tau}$ be an arbitrary square matrix. Then

$$ \rho(\boldsymbol{\Omega}_N, \boldsymbol{\tau}) = \operatorname{diag} (\rho(w_N^{j-1}, \boldsymbol{\tau})) $$

where $\rho(\cdot)$ is given by Definition 13. $\square$

**Proof.** Consider the representation

$$ \begin{aligned} \rho(\boldsymbol{\Omega}_N, \boldsymbol{\tau}) &= \rho(\operatorname{diag}(1, w_N, w_N^2, \dots, w_N^{N-1}), \boldsymbol{\tau}) \\ &= \sum_{k=1}^{N} \operatorname{diag}(w_N^{0-(k-1)}, w_N^{1-(k-1)}, \dots, w_N^{(N-1)(k-1)}) \otimes \boldsymbol{\tau} \\ &= \sum_{k=1}^{N} \operatorname{diag}(\boldsymbol{\tau} w_N^{0-(k-1)}, \boldsymbol{\tau} w_N^{1-(k-1)}, \dots, \boldsymbol{\tau} w_N^{(N-1)(k-1)}) \\ &= \operatorname{diag} \sum_{i=1, \dots, N}^{N} \boldsymbol{\tau} w_N^{(i-1)(k-1)} \\ &= \operatorname{diag} (\rho(w_N^{j-1}, \boldsymbol{\tau})) \end{aligned} $$

which is diagonal when $\boldsymbol{\tau}$ is a scalar and block diagonal when $\boldsymbol{\tau}$ is a matrix. $\blacksquare$

**THEOREM 9 (Diagonalization of a Circulant).** Let $\mathbf{C} \in \mathcal{C}_N$ have generating elements $c_1, c_2, \dots, c_N$. Then if $\mathbf{E}_N$ is the $N \times N$ Fourier matrix,

$$ \mathbf{E}_N^H \mathbf{C} \mathbf{E}_N = \begin{bmatrix} \lambda_1 & & & 0 \\ & \lambda_2 & & \\ & & \ddots & \\ 0 & & & \lambda_N \end{bmatrix} $$

is a diagonal matrix. For $i = 1, 2, \dots, N$, the diagonal elements are

$$ \lambda_i = \rho(w_N^{j-1}, c_k) = \sum_{k=1}^{N} c_k w_N^{(k-1)(i-1)} \quad (21) $$

where $w_N$ is the primitive Nth root of unity and the function $\rho(\cdot)$ is given by Definition 13. $\square$

**Proof.** Consider the representation

$$ \mathbf{C} = \rho(\boldsymbol{\sigma}_N, c_k) \quad (\text{Cor. 5}) $$

$$ = \rho(\mathbf{E}_N \boldsymbol{\Omega}_N \mathbf{E}_N^H, c_k) \quad (\text{Thm. 8}) $$

$$ = \mathbf{E}_N \rho(\boldsymbol{\Omega}_N, c_k) \mathbf{E}_N^H \quad (\text{Thms. 2 and 6}) $$

where the last step follows directly from the proof of Theorem 2 and the polynomial term

$$ \begin{aligned} \rho(\boldsymbol{\Omega}_N, c_k) &= \operatorname{diag} \left( \sum_{i=1, \dots, N}^{N} c_k w_N^{(k-1)(i-1)} \right) \\ &= \operatorname{diag} (\rho w_N^{j-1}, c_k) \end{aligned} $$

follows from Corollary 16 and Definition 13. The desired result is obtained by multiplying from the left by $\mathbf{E}_N^H$, multiplying from the right by $\mathbf{E}_N$, and invoking Theorem 6. $\blacksquare$

Theorem 9 shows that the Fourier matrix $\mathbf{E}_N$ diagonalizes any $N \times N$ circulant matrix. As discussed in Sec. 2.8, the columns $\mathbf{e}_1, \mathbf{e}_2, \dots, \mathbf{e}_N$ of $\mathbf{E}_N$ are the eigenvectors of $\mathbf{C}$. The scalars $\lambda_i$ in Theorem 9 are the eigenvalues of $\mathbf{C}$. Unlike the eigenvectors, they depend on the elements (i.e., generating elements) of $\mathbf{C}$. In fact, Eq. (21) has the same form as the DFT of a discrete time series, which is clear by comparing it to Definition 20 of Sec. 2.7. In this case, $c_k$ ($k = 1, 2, \dots, N$) and $\lambda_i$ ($i = 1, 2, \dots, N$) are analogous to a discrete signal and its DFT, and are related by

$$ \begin{bmatrix} \lambda_1 \\ \lambda_2 \\ \vdots \\ \lambda_N \end{bmatrix} = \sqrt{N} \mathbf{E}_N \begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_N \end{bmatrix} \quad (22) $$

which has the same form as the matrix-vector representation of the DFT defined by Eq. (27) of Sec. 2.7. Thus, the eigenvalues $\lambda_i$ can be calculated directly using Eq. (21) or Eq. (22), which are equivalent.

If the circulant matrix in Theorem 9 is also symmetric, the eigenvalues are real-valued and certain ones are repeated, as shown in Corollary 17.

**COROLLARY 17.** If $\mathbf{C} \in \mathcal{C}_N$ is a symmetric circulant, Eq. (21) reduces to

$$ \lambda_i = \begin{cases} c_1 + 2 \sum_{k=2}^{N/2} c_k \cos \left( \frac{2\pi(k-1)(i-1)}{N} \right) & N \text{ even} \\ +(-1)^{i-1} c_{\frac{N+2}{2}} & N \text{ odd} \end{cases} $$

where the generating elements are given by Eq. (10). $\square$

**Proof.** If $N$ is even, the generating elements of $\mathbf{C}$ are given by

$$ c_1, c_2, \dots, c_{\frac{N}{2}}, c_{\frac{N+2}{2}}, c_{\frac{N}{2}}, \dots, c_3, c_2 $$

and Eq. (21) reduces to
$$
\begin{align*}
\lambda_i &= \sum_{k=1}^{N} c_k w_N^{(k-1)(i-1)} \\
&= c_1 w_N^{0(i-1)} + c_2 w_N^{1(i-1)} + c_3 w_N^{2(i-1)} + \dots \\
&\quad + c_{\frac{N}{2}} w_N^{(\frac{N}{2}-1)(i-1)} + c_{\frac{N+2}{2}} w_N^{(\frac{N+2}{2}-1)(i-1)} \\
&\quad + c_{\frac{N}{2}} w_N^{(\frac{N+4}{2}-1)(i-1)} + \dots \\
&\quad + c_3 w_N^{(N-1)(i-1)} + c_2 w_N^{(N-1)(i-1)} \\
&= c_1 + c_2 (w_N^{(i-1)} + w_N^{(N-1)(i-1)}) \\
&\quad + c_3 (w_N^{2(i-1)} + w_N^{(N-2)(i-1)}) + \dots \\
&\quad + c_{\frac{N}{2}} (w_N^{\frac{N-2}{2}(i-1)} + w_N^{(N-\frac{N-2}{2})(i-1)}) + c_{\frac{N+2}{2}} w_N^{\frac{N}{2}(i-1)} \\
&= c_1 + 2 \sum_{k=2}^{N/2} c_k \cos \left( \frac{2\pi(k-1)(i-1)}{N} \right) + c_{\frac{N+2}{2}} (-1)^{i-1}
\end{align*}
$$

where the identity

$$
w_N^{k(i-1)} + w_N^{(N-k)(i-1)} = 2 \cos \left( \frac{2\pi k}{N} (i-1) \right)
$$

is employed. If N is odd, the generating elements of C are given by

$$
c_1, c_2, \dots, c_{\frac{N-1}{2}}, c_{\frac{N+1}{2}}, c_{\frac{N+2}{2}}, c_{\frac{N-1}{2}}, \dots, c_3, c_2
$$

and Eq. (21) reduces similarly to the case for even N, which is left
as an exercise for the reader.
■

The cosinusoidal nature of $\lambda_i$ in Corollary 17 implies that $\lambda_1$ is
distinct for a symmetric circulant matrix $\mathbf{C} \in \mathcal{S}\mathcal{C}_N$, but the
remaining elements $\lambda_i = \lambda_{N+2-i}$ appear in repeated pairs. How-
ever, $\lambda_{(N+2/2)}$ is also distinct if $N$ is even.

*Example 15.* Let $\mathbf{C} = \text{circ}(4, -1, 0, -1) \in \mathcal{S}\mathcal{C}_4$ be a symmetric circulant matrix. Then the product

$$
\begin{align*}
\mathbf{E}_4^H \mathbf{C} \mathbf{E}_4 &= \frac{1}{\sqrt{4}} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \end{bmatrix} \begin{bmatrix} 4 & -1 & 0 & -1 \\ -1 & 4 & -1 & 0 \\ 0 & -1 & 4 & -1 \\ -1 & 0 & -1 & 4 \end{bmatrix} \\
&\quad \times \frac{1}{\sqrt{4}} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & j & -1 & -j \\ 1 & -1 & 1 & -1 \\ 1 & -j & -1 & j \end{bmatrix} \\
&= \frac{1}{4} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \end{bmatrix} \begin{bmatrix} 2 & 4 & 6 & 4 \\ 2 & 4j & -6 & -4j \\ 2 & -4 & 6 & -4 \\ 2 & -4j & -6 & 4j \end{bmatrix} \\
&= \begin{bmatrix} 2 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 \\ 0 & 0 & 6 & 0 \\ 0 & 0 & 0 & 4 \end{bmatrix} \\
&= \operatorname{diag}(2, 4, 6, 4)
\end{align*}
$$

is a diagonal matrix. The diagonal elements can be computed
directly using Eq. (21) for N = 4. For example,

$$
\begin{align*}
\lambda_3 &= \sum_{k=1}^{4} c_k w_4^{(k-1)(3-1)} \\
&= 4w_4^{(1-1)(3-1)} + (-1)w_4^{(2-1)(3-1)} \\
&\quad + 0 \cdot w_4^{(3-1)(3-1)} + (-1)w_4^{(4-1)(3-1)} \\
&= 4(1) - e^{j\frac{2\pi}{4}\cdot 2} + 0 - e^{j\frac{2\pi}{4}\cdot 6} \\
&= 4 - e^{j\pi} + 0 - e^{j\cdot 3\pi} \\
&= 4 - (-1) + 0 - (-1) = 6
\end{align*}
$$

which is recognized to be the third diagonal element of the matrix
product $\mathbf{E}_4^H \mathbf{C} \mathbf{E}_4$. Because $\mathbf{C}$ is a symmetric circulant matrix, Corol-
lary 17 can also be used. Observing that $N=4$ is even, it follows that

$$
\begin{align*}
\lambda_3 &= c_1 + 2 \sum_{k=2}^{4/2} c_k \cos \left( \frac{2\pi(k-1)(3-1)}{4} \right) + (-1)^{(3-1)} c_{\frac{4+2}{2}} \\
&= 4 + 2 \cdot (-1) \cos \left( \frac{2\pi(2-1)(3-1)}{4} \right) + (-1)^2 \cdot 0 \\
&= 4 - 2 \cos \pi + 0 \\
&= 4 - 2(-1) + 0 = 6
\end{align*}
$$

as before. The eigenvalues and eigenvectors of C are discussed in
Example 24 of Sec. 2.8.

<figure><img src="image_31.png" /></figure>

*Example 16.* Let $\mathbf{C} = \text{circ}(4, -1, 0, 1) \in \mathcal{C}_4$ be a nonsymmetric circulant matrix. Then the product

$$
\begin{align*}
\mathbf{E}_4^H \mathbf{C} \mathbf{E}_4 &= \frac{1}{\sqrt{4}} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \end{bmatrix} \begin{bmatrix} 4 & -1 & 0 & 1 \\ 1 & 4 & -1 & 0 \\ 0 & 1 & 4 & -1 \\ -1 & 0 & 1 & 4 \end{bmatrix} \\
&\quad \times \frac{1}{\sqrt{4}} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & j & -1 & -j \\ 1 & -1 & 1 & -1 \\ 1 & -j & -1 & j \end{bmatrix} \\
&= \frac{1}{4} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \end{bmatrix} \begin{bmatrix} 4 & 4-2j & 4 & 4+2j \\ 4 & 2+4j & -4 & 2-4j \\ 4 & -4+2j & 4 & -4-2j \\ 4 & -2-4j & -4 & -2+4j \end{bmatrix} \\
&= \begin{bmatrix} 4 & 0 & 0 & 0 \\ 0 & 4-2j & 0 & 0 \\ 0 & 0 & 4 & 0 \\ 0 & 0 & 0 & 4+2j \end{bmatrix}
\end{align*}
$$

is a diagonal matrix. The diagonal elements are the eigenvalues of C,
which is stated explicitly for general C in the following corollary. They
may be computed directly using Eq. (21), as it is done in Example 15,
but Corollary 17 cannot be used because C is not symmetric.
$\square$

<figure><img src="image_32.png" /></figure>

The eigenvalue magnitudes of the nonsymmetric matrix $\mathbf{C}$ in Example 16 are observed to exhibit the same multiplicity (and symmetry) as the eigenvalues in Example 15 for a symmetric circulant. It is shown in Sec. 2.8.3 that the eigenvalues of any circulant matrix $\mathbf{C} \in \mathcal{C}_N$ with real-valued generating elements exhibit
a certain symmetry about the so-called “Nyquist” component, which is analogous to the DFT of a real-valued sequence. This is because Eq. (22) represents the DFT of the generating elements $c_1, c_2, \dots, c_N$.

**COROLLARY 18.** Let $\mathbf{e}_i$ be the $i$-th column of the Fourier matrix $\mathbf{E}_N$ and $\mathbf{C}$ be a $N \times N$ circulant matrix. Then for $i, k = 1, 2, \dots, N$,

$$ \mathbf{e}_i^H \mathbf{C} \mathbf{e}_k = \lambda_i \delta_{ik} $$

where $\delta_{ik}$ is the Kronecker delta and $\lambda_i$ is defined by Eq. (21) for $\mathbf{C} \in \mathcal{C}_N$ or Corollary 17 if $\mathbf{C} \in \mathcal{C}'\mathcal{C}_N$.

Thus, the columns of the Fourier matrix are mutually orthogonal (Corollary 10) and orthogonal with respect to any circulant matrix (Corollary 18), not just the cyclic forward shift matrix and its integer powers (Corollary 15).

**Example 17.** Consider the circulant $\mathbf{C} = \text{circ}(4, -1, 0, -1)$ from Example 15. Then

$$ \begin{aligned} \mathbf{e}_3^H \mathbf{C} \mathbf{e}_3 &= \frac{1}{\sqrt{4}} [\begin{matrix} 1 & -1 & 1 & -1 \end{matrix}] \begin{bmatrix} 4 & -1 & 0 & -1 \\ -1 & 4 & -1 & 0 \\ 0 & -1 & 4 & -1 \\ -1 & 0 & -1 & 4 \end{bmatrix} \frac{1}{\sqrt{4}} \begin{bmatrix} 1 \\ -1 \\ 1 \\ -1 \end{bmatrix} \\ &= \frac{1}{4} [\begin{matrix} 1 & -1 & 1 & -1 \end{matrix}] \begin{bmatrix} 6 \\ -6 \\ 6 \\ -6 \end{bmatrix} \\ &= \frac{1}{4} \cdot 24 = 6 \end{aligned} $$

which is recognized to be the third diagonal element $\lambda_3$ of the matrix $\mathbf{E}_4^H \mathbf{C} \mathbf{e}_4$ in Example 15. However, the scalar

$$ \begin{aligned} \mathbf{e}_3^H \mathbf{C} \mathbf{e}_1 &= \frac{1}{\sqrt{4}} [\begin{matrix} 1 & -1 & 1 & -1 \end{matrix}] \begin{bmatrix} 4 & -1 & 0 & -1 \\ -1 & 4 & -1 & 0 \\ 0 & -1 & 4 & -1 \\ -1 & 0 & -1 & 4 \end{bmatrix} \frac{1}{\sqrt{4}} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \\ &= \frac{1}{4} [\begin{matrix} 1 & -1 & 1 & -1 \end{matrix}] \begin{bmatrix} 2 \\ 2 \\ 2 \\ 2 \end{bmatrix} \\ &= \frac{1}{4} \cdot 0 = 0 \end{aligned} $$

vanishes, as expected, because $i \neq k$ in Corollary 18 such that $\delta_{ik} = 0$.

<figure><img src="image_33.png" /></figure>

**2.5.5** *Block Diagonalization of a Block Circulant.* Theorem 9 is generalized to handle block circulants using the Fourier and identity matrices together with the Kronecker product. The choice of diagonalizing matrix $\mathbf{E}_N^H \otimes \mathbf{I}_M$ is discussed in Sec. 2.6, where generalizations of Theorem 10 are considered.

**THEOREM 10 (Block Diagonalization of a Block Circulant).** Let $\mathbf{C} \in \mathcal{C}'\mathcal{C}_{M,N}$ and denote its $M \times M$ generating matrices by $\mathbf{C}_1, \mathbf{C}_2, \dots, \mathbf{C}_N$. Then if $\mathbf{E}_N$ is the $N \times N$ Fourier matrix and $\mathbf{I}_M$ is the identity matrix of dimension $M$,

$$ (\mathbf{E}_N^H \otimes \mathbf{I}_M) \mathbf{C} (\mathbf{E}_N \otimes \mathbf{I}_M) = \begin{bmatrix} \mathbf{\Lambda}_1 & & & \mathbf{0} \\ & \mathbf{\Lambda}_2 & & \\ & & \ddots & \\ \mathbf{0} & & & \mathbf{\Lambda}_N \end{bmatrix} $$

is a $NM \times NM$ block diagonal matrix. For $i = 1, 2, \dots, N$, the $M \times M$ diagonal blocks are

$$ \mathbf{\Lambda}_i = \rho(\mathbf{w}_N^{i-1}, \mathbf{C}_k) = \sum_{k=1}^{N} \mathbf{C}_k \mathbf{w}_N^{(k-1)(i-1)} \quad (23) $$

where $\mathbf{w}_N$ is the primitive $N$th root of unity and the function $\rho(\cdot)$ is given by Definition 13.

<figure><img src="image_34.png" /></figure>

**Proof.** Consider the representation

$$ \mathbf{C} = \sum_{k=1}^{N} \boldsymbol{\sigma}_{N}^{k-1} \otimes \mathbf{C}_k \quad (\text{Cor. 5}) $$

$$ = \sum_{k=1}^{N} (\mathbf{E}_N \mathbf{\Omega}_N^{k-1} \mathbf{E}_N^H) \otimes \mathbf{C}_k \quad (\text{Cor. 14}) $$

$$ = \sum_{k=1}^{N} (\mathbf{E}_N \otimes \mathbf{I}_M) (\mathbf{\Omega}_N^{k-1} \otimes \mathbf{C}_k) (\mathbf{E}_N^H \otimes \mathbf{I}_M) \quad (\text{Eq. 4}) $$

$$ = (\mathbf{E}_N \otimes \mathbf{I}_M) \rho(\mathbf{\Omega}_N, \mathbf{C}_k) (\mathbf{E}_N^H \otimes \mathbf{I}_M) \quad (\text{Def. 13}) $$

where

$$ \begin{aligned} \rho(\mathbf{\Omega}_N, \mathbf{C}_k) &= \operatorname{diag} \left( \sum_{i=1, \dots, N} \mathbf{C}_k \mathbf{w}_N^{(k-1)(i-1)} \right) \\ &= \operatorname{diag} \left( \rho(\mathbf{w}_N^{i-1}, \mathbf{C}_k) \right) \end{aligned} $$

follows from Corollary 16 and Definition 13. The desired result follows by multiplying from the left by

$$ (\mathbf{E}_N^H \otimes \mathbf{I}_M) = (\mathbf{E}_N \otimes \mathbf{I}_M)^H $$

multiplying from the right by $(\mathbf{E}_N \otimes \mathbf{I}_M)$, and invoking Corollary 11.

<figure><img src="image_35.png" /></figure>

Thus, the unitary matrix $\mathbf{E}_N \otimes \mathbf{I}_M$ reduces any $NM \times NM$ block circulant matrix with $M \times M$ blocks to a block diagonal matrix with $M \times M$ diagonal blocks.

**Example 18.** Consider $\mathbf{C} = \text{circ}(\mathbf{A}, \mathbf{B}, \mathbf{0}, \mathbf{B}) \in \mathcal{C}'\mathcal{C}_{2,4}$ from Example 6. It can be block diagonalized via the transformation $(\mathbf{E}_4^H \otimes \mathbf{I}_2) \mathbf{C} (\mathbf{E}_4 \otimes \mathbf{I}_2)$. That is,

$$ \frac{1}{\sqrt{4}} \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & -j & 0 & -1 & 0 & j & 0 \\ 0 & 1 & 0 & -j & 0 & -1 & 0 & j \\ 1 & 0 & -1 & 0 & 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 & 0 & 1 & 0 & -1 \\ 1 & 0 & j & 0 & -1 & 0 & -j & 0 \\ 0 & 1 & 0 & j & 0 & -1 & 0 & -j \end{bmatrix} \mathbf{C} $$

$$ \times \frac{1}{\sqrt{4}} \begin{bmatrix} 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & j & 0 & -1 & 0 & -j & 0 \\ 0 & 1 & 0 & j & 0 & -1 & 0 & -j \\ 1 & 0 & -1 & 0 & 1 & 0 & -1 & 0 \\ 0 & 1 & 0 & -1 & 0 & 1 & 0 & -1 \\ 1 & 0 & -j & 0 & -1 & 0 & j & 0 \\ 0 & 1 & 0 & -j & 0 & -1 & 0 & j \end{bmatrix} $$

$$ = \operatorname{diag} \begin{bmatrix} 0 & -1 \\ -1 & 0 \end{bmatrix}, \begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix}, \begin{bmatrix} 4 & -1 \\ -1 & 4 \end{bmatrix}, \begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix} $$
which is a block diagonal matrix with 2 × 2 diagonal blocks. The eigenvalues and eigenvectors of C are discussed in Example 25 of Sec. 2.8.

COROLLARY 19. Let $\mathbf{C} \in \mathcal{B}\mathcal{C}_{M,N}$ have $M \times M$ generating matrices $C_1, C_2, \dots, C_N$ and $\mathbf{\Lambda}_i$ be defined by Eq. (23). Then if each $C_i$ is symmetric, it follows that $\mathbf{\Lambda}_i$ is symmetric for $i = 1, 2, \dots, N$. $\square$

Proof. If each $C_k$ is symmetric for $k = 1, 2, \dots, N$, then so too are the matrices $C_k w_N^{(k-1)(i-1)}$ for each $i$ because $w_N^{(k-1)(i-1)}$ is a scalar. Moreover, the sum and difference of two symmetric matrices is again symmetric. If follows that

$$ \mathbf{\Lambda}_i = \sum_{k=1}^{N} C_k w_N^{(k-1)(i-1)} $$

is symmetric for $i = 1, 2, \dots, N$.

COROLLARY 20. Let $\mathbf{C} \in \mathcal{B}\mathcal{C}_{M,N}$ be a $NM \times NM$ block circulant matrix. Then for $i, k = 1, 2, \dots, N$,

$$ (\mathbf{e}_i^H \otimes \mathbf{I}_M) \mathbf{C} (\mathbf{e}_k \otimes \mathbf{I}_M) = \mathbf{\Lambda}_i \delta_{ik} $$

where $\mathbf{\Lambda}_i$ is defined by Eq. (23).

Example 19. Consider $\mathbf{C} = \text{circ}(\mathbf{A}, \mathbf{B}, \mathbf{0}, \mathbf{B}) \in \mathcal{B}\mathcal{C}_{2,4}$ from Examples 6 and 18. Then

$$ \begin{aligned} (\mathbf{e}_3^H \otimes \mathbf{I}_2) \mathbf{C} (\mathbf{e}_3 \otimes \mathbf{I}_2) &= \left( \frac{1}{\sqrt{4}} \begin{bmatrix} 1 & -1 & 1 & -1 \end{bmatrix} \otimes \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \right) \mathbf{C} \\ & \quad \times \left( \frac{1}{\sqrt{4}} \begin{bmatrix} 1 \\ -1 \\ 1 \\ -1 \end{bmatrix} \otimes \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \right) \\ &= \begin{bmatrix} 4 & -1 \\ -1 & 4 \end{bmatrix} \end{aligned} $$

is the third 2 × 2 block of the block diagonal matrix obtained in Example 18.

**2.6 Generalizations.** Let $(\cdot)^*$ denote an arbitrary operation that takes a square matrix as its argument and returns another square matrix with the same dimension. For example, the operation could denote a matrix inverse such that $(\cdot)^* = (\cdot)^{-1}$. Let $(\cdot)^#$ be another arbitrary matrix operation with the same restrictions (i.e., returns another square matrix with the same dimension). Then if $\mathbf{C} \in \mathcal{B}\mathcal{C}_{M,N}$ has generating matrices $C_1, C_2, \dots, C_N$, it follows that

$$ \begin{aligned} & (\mathbf{A}^* \otimes \mathbf{B}^\#) \mathbf{C}(\mathbf{A} \otimes \mathbf{B}) \\ &= (\mathbf{A}^* \otimes \mathbf{B}^\#) \sum_{k=1}^{N} \sigma_N^{k-1} \otimes C_k) (\mathbf{A} \otimes \mathbf{B}) \quad (\text{Cor. 5}) \\ &= \sum_{k=1}^{N} ((\mathbf{A}^* \sigma_N^{k-1}) \otimes (\mathbf{B}^\# C_k))(\mathbf{A} \otimes \mathbf{B}) \quad (\text{Eq. 4}) \\ &= \sum_{k=1}^{N} (\mathbf{A}^* \sigma_N^{k-1} \mathbf{A}) \otimes (\mathbf{B}^\# C_k \mathbf{B}) \quad (\text{Eq. 4}) \end{aligned} $$

for any matrices $\mathbf{A} \in \mathbb{C}^{N \times N}$ and $\mathbf{B} \in \mathbb{C}^{M \times M}$. The importance of this result is that $\mathbf{C}$ can be decomposed into a summation of direct products of two separate equivalence transformations, one that operates on the cyclic forward shift matrix and the other on the generating matrices of $\mathbf{C}$. This decomposition justifies the diagonalizing matrix used in Sec. 2.5, motivates some generalizations

of Theorem 10, and aids in proving orthogonality relationships for the cyclic eigenvalue problems described in Sec. 2.8.

In light of Corollary 14, it is clear that the choice of $\mathbf{A} = \mathbf{E}_N$ and $(\cdot)^* = (\cdot)^H$ accomplishes block diagonalization of a matrix $\mathbf{C} \in \mathcal{B}\mathcal{C}_{M,N}$. Then if $\mathbf{B} = \mathbf{I}_M$, the appropriate diagonalizing matrix to block decouple $\mathbf{C}$ without operating on its generating matrices is $\mathbf{E}_N \otimes \mathbf{I}_M$ (see Theorem 10). However, if $\mathbf{B}$ and $(\cdot)^\#$ are kept general, we have the following result.

THEOREM 11. Let $\mathbf{C} \in \mathcal{B}\mathcal{C}_{M,N}$ have $M \times M$ generating matrices $C_1, C_2, \dots, C_N$ and $\mathbf{E}_N$ be the $N \times N$ Fourier matrix. Then for an arbitrary matrix $\mathbf{B} \in \mathbb{C}^{M \times M}$ and operator $(\cdot)^\#,$

$$ (\mathbf{E}_N^H \otimes \mathbf{B}^\#) \mathbf{C}(\mathbf{E}_N \otimes \mathbf{B}) = \begin{bmatrix} \mathbf{\Psi}_1 & & & \\ & \mathbf{\Psi}_2 & & \\ & & \ddots & \\ & & & \mathbf{\Psi}_N \end{bmatrix} $$

is a block diagonal matrix, where

$$ \mathbf{\Psi}_i = \rho(w_N^{i-1}, \mathbf{B}^\# C_k \mathbf{B}) = \sum_{k=1}^{N} \mathbf{B}^\# C_k \mathbf{B} w_N^{(k-1)(i-1)} \quad (24) $$

is the $i$th $M \times M$ diagonal block for $i = 1, 2, \dots, N$. $\square$

COROLLARY 21. Let $\mathbf{C} \in \mathcal{B}\mathcal{C}_{M,N}$ be a $NM \times NM$ block circulant matrix, $\mathbf{B} \in \mathbb{C}^{M \times M}$ be an arbitrary square matrix, and $(\cdot)^\#$ denote an arbitrary operation that takes a square matrix as its argument and returns another square matrix with the same dimension. Then for $i, k = 1, 2, \dots, N$,

$$ (\mathbf{e}_i^H \otimes \mathbf{B}^\#) \mathbf{C}(\mathbf{e}_k \otimes \mathbf{B}) = \mathbf{\Psi}_i \delta_{ik} $$

where $\mathbf{\Psi}_i$ is defined by Eq. (24).

Theorem 11 is useful if there exists an equivalence transformation $\mathbf{B}^\# C_k \mathbf{B}$ that simplifies each of the generating matrices. For example, if each $C_k$ is a circulant of type $M$, then the additional choice of $\mathbf{B} = \mathbf{E}_M$ and $(\cdot)^\# = (\cdot)^H$ fully diagonalizes a block circulant matrix $\mathbf{C} \in \mathcal{B}\mathcal{C}_{N,M}$ with circulant blocks.

COROLLARY 22. Let $\mathbf{C} \in \mathcal{B}\mathcal{C}_{M,N}$ have generating matrices $C_1, C_2, \dots, C_N \in \mathcal{C}_M$ and denote the generating elements of each $C_i$ by $c_i^{(1)}, c_i^{(2)}, \dots, c_i^{(M)}$. Then

$$ (\mathbf{E}_N^H \otimes \mathbf{E}_M^H) \mathbf{C}(\mathbf{E}_N \otimes \mathbf{E}_M) = \text{diag}_{i=1,...,N} \begin{bmatrix} \lambda_i^{(1)} & & & 0 \\ & \lambda_i^{(2)} & & \\ & & \ddots & \\ 0 & & & \lambda_i^{(M)} \end{bmatrix} $$

is a $NM \times NM$ diagonal matrix, where

$$ \lambda_i^{(p)} = \sum_{k=1}^{N} \sum_{l=1}^{M} c_k^{(l)} w_M^{(l-1)(p-1)} w_N^{(k-1)(i-1)} \quad (25) $$

is the $p$th diagonal element of the $i$th $M \times M$ block for $i = 1, 2, \dots, N$ and $p = 1, 2, \dots, M$. $\square$

Corollary 22 shows that the $NM$-dimensional eigenvectors $\mathbf{q}_i^{(p)}$ of $\mathbf{C}$ are the columns of $\mathbf{E}_N \otimes \mathbf{E}_M$. This is in contrast to rotationally periodic structures, where $\mathbf{q}$ is partitioned into $N$ $M$-vectors corresponding to each sector and decomposed into a set of $N$ reduced-order eigenvalue problems described in Sec. 2.8.

Example 20. Consider $\mathbf{C} = \text{circ}(\mathbf{A}, \mathbf{B}, \mathbf{0}, \mathbf{B}) \in \mathcal{B}\mathcal{C}_{2,4}$ from Examples 6, 18, and 19. Because each of its generating matrices is a circulant, that is, $(\mathbf{A}, \mathbf{B}, \mathbf{0}) \in \mathcal{C}_2$, the block circulant $\mathbf{C}$ is diagonalized via the transformation
$$
\begin{align*}
(\mathbf{E}_4^H \otimes \mathbf{E}_2^H) \mathbf{C}(\mathbf{E}_4 \otimes \mathbf{E}_2) &= \left( \frac{1}{\sqrt{4}} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \end{bmatrix} \otimes \begin{bmatrix} 1 & 1 \\ 1 & j \end{bmatrix} \right) \mathbf{C} \\
&\quad \times \left( \frac{1}{\sqrt{4}} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & j & -1 & -j \\ 1 & -1 & 1 & -1 \\ 1 & -j & -1 & j \end{bmatrix} \otimes \begin{bmatrix} 1 & 1 \\ 1 & -j \end{bmatrix} \right) \\
&= \begin{bmatrix} -1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 3 \end{bmatrix}
\end{align*}
$$

from which is follows that $\alpha(\mathbf{C}) = \{-1, 1, 1, 3, 3, 5, 1, 3\}$. Observing that

$$
\left.
\begin{aligned}
c_1^{(1)} &= 2, & c_2^{(1)} &= -1, & c_3^{(1)} &= 0, & c_4^{(1)} &= -1 \\
c_1^{(2)} &= -1, & c_2^{(2)} &= 0, & c_3^{(2)} &= 0, & c_4^{(2)} &= 0
\end{aligned}
\right\}
$$

are the generating elements of $\mathbf{C}$, the $NM = 4 \cdot 2 = 8$ diagonal elements can be calculated directly using Eq. (25). For example, the second diagonal element ($p=2$) of the third $4 \times 4$ diagonal block ($i=3$) is given by

$$
\begin{align*}
\lambda_3^{(2)} &= c_1^{(1)} w_2^{(1-1)(2-1)} w_4^{(1-1)(3-1)} + c_1^{(2)} w_2^{(2-1)(2-1)} w_4^{(1-1)(3-1)} \\
&\quad + c_2^{(1)} w_2^{(1-1)(2-1)} w_4^{(2-1)(3-1)} + c_2^{(2)} w_2^{(2-1)(2-1)} w_4^{(2-1)(3-1)} \\
&\quad + c_3^{(1)} w_2^{(1-1)(2-1)} w_4^{(3-1)(3-1)} + c_3^{(2)} w_2^{(2-1)(2-1)} w_4^{(3-1)(3-1)} \\
&\quad + c_4^{(1)} w_2^{(1-1)(2-1)} w_4^{(4-1)(3-1)} + c_4^{(2)} w_2^{(2-1)(2-1)} w_4^{(4-1)(3-1)} \\
&= (2)(1)(1) & & + (-1)(-1)(1) \\
& & & + (-1)(1)(-1) & + (0)(-1)(-1) \\
& & & + (0)(1)(1) & + (0)(-1)(1) \\
& & & + (-1)(1)(-1) & + (0)(-1)(-1) \\
&= 5
\end{align*}
$$

The reader can compare this matrix decomposition to the results in Example 25 of Sec. 2.8.1. Finally, the eigenvectors $\mathbf{q}_i^{(p)}$ are the columns of $\mathbf{E}_4 \otimes \mathbf{E}_2$ and are stated explicitly in Example 25. ■

**2.7 Relationship to the Discrete Fourier Transform.**
Before turning to the circulant eigenvalue problem, we consider a somewhat tangential but relevant subject on the DFT and its inverse, which are central to the analysis of experimental data in a wide range of fields, including mechanical vibrations. In this detour we show that computation of the DFT is, in fact, a multiplication of an $N$-vector of discrete signal samples by the Fourier matrix and a constant $c_f$. The IDFT is similarly defined using the Hermitian of the Fourier matrix and a constant $c_i$, where $c_f c_i = 1/N$. More importantly, it is shown that the DFT

computation is exactly analogous to the determination of the eigenvalues of a circulant matrix given its generating elements. We begin by defining the DFT sinusoids, which provide a convenient means of representing the DFT of a discretized signal, and then develop the relationships of interest for the DFT and the IDFT. We present only the basic results as they relate to the theory and mathematics of circulants. The reader can find a vast literature on related topics [89–91,102–110].

**DEFINITION 19 (DFT Sinusoids).** Let $w_N^k$ denote the distinct $N$th roots of unity, where $w_N = e^{j\frac{2\pi k}{N}}$ is the primitive root. Then the DFT sinusoids are

$$
S_k(r) = (w_N^k)^r = w_N^{kr} = e^{j\frac{2\pi kr}{N}}
$$

for $k, r = 0, 1, \dots, N-1$.

COROLLARY 23. The DFT sinusoids are orthogonal.

*Proof.* Consider the DFT sinusoids

$$
\left.
\begin{aligned}
S_i(r) &= e^{j \frac{2\pi i r}{N}} \\
S_k(r) &= e^{j \frac{2\pi kr}{N}}
\end{aligned}
\right\} , \quad i, k, r = 0, 1, \dots, N-1
$$

The inner product of $S_i(r)$ and $S_k(r)$ is given by

$$
\begin{align*}
\langle S_i(r), S_k(r) \rangle &= \sum_{r=0}^{N-1} S_i(r) \bar{S}_k(r) \\
&= \sum_{r=0}^{N-1} w_N^{ir} \bar{w}_N^{kr} \tag{Def. 19} \\
&= \sum_{r=0}^{N-1} w_N^{ir} w_N^{-kr} \tag{Cor. 7} \\
&= \sum_{r=0}^{N-1} w_N^{r(i-k)} \\
&= \begin{cases} N, & i=k \\ 0, & \text{otherwise} \end{cases} \tag{Lem. 2}
\end{align*}
$$

which shows that the DFT sinusoids are orthogonal.

The Fourier matrix in Definition 17 can be written element wise as

$$
\begin{align*}
(\mathbf{E}_N)_{ik} &= \frac{1}{\sqrt{N}} w_N^{(k-1)(i-1)} \\
&= \frac{1}{\sqrt{N}} e^{j \frac{2\pi k}{N} (k-1)(i-1)} \\
&= \frac{1}{\sqrt{N}} S_{i-1}(k-1) = \frac{1}{\sqrt{N}} S_{k-1}(i-1)
\end{align*}
$$

for each $i, k = 1, 2, \dots, N$. It follows that

$$
\begin{align}
\mathbf{E}_N &= \frac{1}{\sqrt{N}} \begin{bmatrix} S_0(0) & S_0(1) & \dots & S_0(N-1) \\ S_1(0) & S_1(1) & \dots & S_1(N-1) \\ S_2(0) & S_2(1) & \dots & S_2(N-1) \\ \vdots & \vdots & \ddots & \vdots \\ S_{N-1}(0) & S_{N-1}(1) & \dots & S_{N-1}(N-1) \end{bmatrix} \nonumber \\
&= \frac{1}{\sqrt{N}} \mathbf{W}_N \tag{26}
\end{align}
$$

is a representation of the Fourier matrix in terms of the DFT sinusoids, where $\mathbf{W}_N$ is the DFT sinusoid matrix. The DFT is formally
defined next and subsequently reformulated in terms of a matrix multiplication involving $\mathbf{W}_N$.

**DEFINITION 20 (DFT).** Let $x(i)$ denote a finite sequence with indices $i = 1, 2, ..., N$. Then for $k = 1, 2, ..., N$, the DFT of $x(i)$ is the sequence

$$ 
\begin{aligned}
X(k) &= \sum_{i=1}^{N} x(i) e^{j \frac{2\pi i}{N} (i-1)(k-1)} \\
&= \sum_{i=1}^{N} x(i) w_{N}^{(i-1)(k-1)} \\
&= \sum_{i=1}^{N} x(i) S_{i-1}(k-1)
\end{aligned}
$$

where $w_N$ is the primitive Nth root of unity and $S_i(k) = w_N^{ik}$ is a DFT sinusoid. $\triangle$

The DFT preserves the units of $x(i)$. That is, if $x(i)$ has engineering units EU, then the units of $X(k)$ are also EU. This is clear from Definition 20, where the exponential function is dimensionless.

Expanding each $X(k)$ in Definition 20 yields

$$ 
\left. 
\begin{aligned}
X(1) &= x(1)S_0(0) + \cdots + x(N)S_0(N-1) \\
X(2) &= x(1)S_1(0) + \cdots + x(N)S_1(N-1) \\
\vdots \\
X(k) &= x(1)S_{i-1}(0) + \cdots + x(N)S_{i-1}(N-1) \\
\vdots \\
X(N) &= x(1)S_{N-1}(0) + \cdots + x(N)S_{N-1}(N-1)
\end{aligned}
\right\} 
$$

If the discrete samples $x(i)$ and corresponding sequence of DFTs $X(k)$ are assembled into the configuration vectors

$$ 
\left. 
\begin{aligned}
\mathbf{x}_N &= (x(1), x(2), \dots, x(N))^T \\
\mathbf{X}_N &= (X(1), X(2), \dots, X(N))^T
\end{aligned}
\right\} 
$$

then the DFT of $\mathbf{x}_N$ can be represented in the matrix-vector form

$$ \mathbf{X}_N = \mathbf{W}_N \mathbf{x}_N \quad (27) $$

where $\mathbf{W}_N = \sqrt{N}\mathbf{E}_N$ follows from Eq. (26). Thus, the DFT computation is simply a multiplication of the configuration vector $\mathbf{x}_N$ with the DFT sinusoid matrix $\mathbf{W}_N$ and constant $c_f = 1$. Equation (27) has exactly the same form as Eq. (22), where the generating elements of a circulant matrix are analogous to the sequence of signals $x(i)$ and the resulting eigenvalues are analogous to the sequence of DFTs $X(k)$.

**Example 21.** Consider the configuration vector of samples $\mathbf{x}_4 = (0, 1, 2, 3)^T$. The DFT of $\mathbf{x}_4$ follows from Eq. (27) with $N=4$ and is given by

$$ 
\begin{aligned}
\mathbf{X}_4 &= \mathbf{W}_4 \mathbf{x}_4 \\
&= \begin{bmatrix} S_0(0) & S_0(1) & S_0(2) & S_0(3) \\ S_1(0) & S_1(1) & S_1(2) & S_1(3) \\ S_2(0) & S_2(1) & S_2(2) & S_2(3) \\ S_3(0) & S_3(1) & S_3(2) & S_3(3) \end{bmatrix} \begin{bmatrix} x(1) \\ x(2) \\ x(3) \\ x(4) \end{bmatrix} \\
&= \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & -j & -1 & j \\ 1 & -1 & 1 & -1 \\ 1 & j & -1 & -j \end{bmatrix} \begin{bmatrix} 0 \\ 1 \\ 2 \\ 3 \end{bmatrix} \\
&= (6, -2 + 2j, -2, -2 - 2j)^T
\end{aligned}
$$

where $\mathbf{W}_4 = \sqrt{4}\mathbf{E}_4$ follows from Example 9 or by elementwise direct computation according to Definition 19. Alternatively, each element $X(k)$ of $\mathbf{X}_4$ can be computed using the summation given in Definition 20. If $k=3$, for example,

$$ 
\begin{aligned}
X(3) &= \sum_{i=1}^{4} x(i) e^{j \frac{2\pi i}{4} (i-1)(3-i)} \\
&= \sum_{i=1}^{4} x(i) e^{j\pi(i-1)} \\
&= x(1)e^{j\pi\cdot0} + x(2)e^{j\pi\cdot1} + x(3)e^{j\pi\cdot2} + x(4)e^{j\pi\cdot3} \\
&= (0)(1) + (1)(-1) + (2)(1) + (3)(-1) \\
&= 0 - 1 + 2 - 3 \\
&= -2
\end{aligned}
$$

which is the third element of $\mathbf{X}_4$, as expected. Results for $k=1, 2, 4$ follow similarly.

<figure><img src="image_36.png" /></figure>

If $\mathbf{X}_N$ is known, the N-vector $\mathbf{x}_N$ is recovered from Eq. (27) by multiplying from the left by $\mathbf{E}_N^H$ and invoking Theorem 6. Then

$$ \mathbf{E}_N^H \mathbf{X}_N = \mathbf{E}_N^H \mathbf{W}_N \mathbf{x}_N \quad (\text{Eq. 27}) $$

$$ = \mathbf{E}_N^H \left( \sqrt{N} \mathbf{E}_N \right) \mathbf{x}_N \quad (\text{Eq. 26}) $$

$$ = \sqrt{N} \mathbf{E}_N^H \mathbf{E}_N \mathbf{x}_N \\
= \sqrt{N} \mathbf{I}_N \mathbf{x}_N \quad (\text{Thm. 6}) $$

$$ = \sqrt{N} \mathbf{x}_N $$

and it follows that

$$ \mathbf{x}_N = \frac{1}{\sqrt{N}} \mathbf{E}_N^H \mathbf{X}_N = \frac{1}{N} \mathbf{W}_N^H \mathbf{X}_N \quad (28) $$

is a matrix-vector representation of the IDFT of $\mathbf{X}_N$. That is, the IDFT computation is simply a matrix multiplication of $\mathbf{X}_N$ with the Hermitian of $\mathbf{W}_N$ and constant $c_i = 1/N$ such that $c_f c_i = 1/N$. In light of Corollary 7, Eq. (28) can be written as

$$ 
\left[ 
\begin{array}{c}
x(1) \\
x(2) \\
\vdots \\
x(N)
\end{array}
\right] = \frac{1}{N} \left[ 
\begin{array}{cccc}
\overline{S_0(0)} & \overline{S_0(1)} & \cdots & \overline{S_0(N-1)} \\
\overline{S_1(0)} & \overline{S_1(1)} & \cdots & \overline{S_1(N-1)} \\
\vdots & \vdots & \ddots & \vdots \\
\overline{S_{N-1}(0)} & \overline{S_{N-1}(1)} & \cdots & \overline{S_{N-1}(N-1)}
\end{array}
\right] \left[ 
\begin{array}{c}
X(1) \\
X(2) \\
\vdots \\
X(N)
\end{array}
\right] 
$$

Expanding each row yields

$$ 
\left. 
\begin{aligned}
x(1) &= \frac{1}{N} (X(1) \overline{S_0(0)} + \cdots + X(N) \overline{S_0(N-1)}) \\
x(2) &= \frac{1}{N} (X(1) \overline{S_1(0)} + \cdots + X(N) \overline{S_1(N-1)}) \\
\vdots \\
x(i) &= \frac{1}{N} (X(1) \overline{S_{i-1}(0)} + \cdots + X(N) \overline{S_{i-1}(N-1)}) \\
\vdots \\
x(N) &= \frac{1}{N} (X(1) \overline{S_{N-1}(0)} + \cdots + X(N) \overline{S_{N-1}(N-1)})
\end{aligned}
\right\} 
$$

which provides an alternative representation of the IDFT.
**DEFINITION 21 (IDFT).** Let the sequence $X(k)$ be defined according to Definition 20. Then for each $i = 1, 2, ..., N$, the IDFT of $X(k)$ is the sequence

$$ 
\begin{aligned}
x(i) &= \frac{1}{N} \sum_{k=1}^{N} X(k) \overline{S_{k-1}(i-1)} \\
&= \frac{1}{N} \sum_{k=1}^{N} X(k) w_{N}^{-(i-1)(k-1)} \\
&= \frac{1}{N} \sum_{k=1}^{N} X(k) e^{-j \frac{2\pi}{N}(i-1)(k-1)}
\end{aligned}
$$

where $w_N$ is the primitive Nth root of unity and $S_i(k) = w_N^{ik}$ is a DFT sinusoid. $\Delta$

The IDFT preserves the units of $X(k)$. If $X(k)$ has engineering units EU, then the units of $x(i)$ are also EU. This is clear from Definition 21, where the exponential function is dimensionless, as is the number $N$.

**Example 22.** Reconsider Example 21, where it is shown that the DFT of $\mathbf{x}_4 = (0, 1, 2, 3)^T$ is the four-vector $\mathbf{X}_4 = (6, -2 + 2j, -2, -2 - 2j)^T$. The IDFT of $\mathbf{X}_4$ follows from Eq. (28) with $N=4$ and is given by

$$ 
\begin{aligned}
\mathbf{x}_4 &= \frac{1}{N} \mathbf{W}_4^H \mathbf{X}_4 \\
&= \frac{1}{N} \begin{bmatrix} \overline{S_0(0)} & \overline{S_0(1)} & \overline{S_0(2)} & \overline{S_0(3)} \\ \overline{S_1(0)} & \overline{S_1(1)} & \overline{S_1(2)} & \overline{S_1(3)} \\ \overline{S_2(0)} & \overline{S_2(1)} & \overline{S_2(2)} & \overline{S_2(3)} \\ \overline{S_3(0)} & \overline{S_3(1)} & \overline{S_3(2)} & \overline{S_3(3)} \end{bmatrix} \begin{bmatrix} X(1) \\ X(2) \\ X(3) \\ X(4) \end{bmatrix} \\
&= \frac{1}{4} \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & j & -1 & -j \\ 1 & -1 & 1 & -1 \\ 1 & -j & -1 & j \end{bmatrix} \begin{bmatrix} 6 \\ -2 + 2j \\ -2 \\ -2 - 2j \end{bmatrix} \\
&= \frac{1}{4} (0, 4, 8, 12)^T \\
&= (0, 1, 2, 3)^T
\end{aligned}
$$

which is the same four-vector from Example 21. Alternatively, each element $x(i)$ of $\mathbf{x}_4$ can be computed using the summation given in Definition 21. If $i=3$, for example,

$$ 
\begin{aligned}
x(3) &= \frac{1}{4} \sum_{k=1}^{4} X(k) e^{-j \frac{2\pi}{N}(3-k)(k-1)} \\
&= \frac{1}{4} (X(1)e^{-j\pi\cdot0} + X(2)e^{-j\pi\cdot1} + X(3)e^{-j\pi\cdot2} + X(4)e^{-j\pi\cdot3}) \\
&= \frac{1}{4} ((6)(1) + (-2-2j)(-1) + (-2)(1) + (-2+2j)(-1)) \\
&= 2
\end{aligned}
$$

which is the third element of $\mathbf{x}_4$, as expected. Results for $k=1, 2, 4$ follow similarly.

There are other suitable definitions of the DFT/IDFT pair. For example, the signs of the exponents are irrelevant as long as they are opposite in the DFT and IDFT. To see this, suppose that the sign of the exponential in Definition 20 is negative instead of

positive. Then each entry $S_k(r)$ in $\mathbf{W}_N$ is replaced with $\bar{S}_k(r)$ to produce $\bar{\mathbf{W}}_N$ (see Corollary 7), and the DFT is instead given by

$$ \mathbf{X}_N = \bar{\mathbf{W}}_N \mathbf{x}_N \quad (29) $$

The corresponding IDFT takes the form

$$ \mathbf{x}_N = \frac{1}{N} \bar{\mathbf{W}}_N^H \mathbf{x}_N \quad (30) $$

which follows in the same way as Eq. (28) by replacing $\mathbf{E}_N$ with $\bar{\mathbf{E}}_N$ and invoking Corollary 9. Similarly, the multiplicative constants that define the DFT/IDFT pair are arbitrary as long as the product of the constants is equal to $1/N$. This is important for applications involving a transformation of data to the frequency domain for analysis and then back to the time domain for results. However, the multiplicative constant is irrelevant if the analysis goal is only to identify periodicities in a data set (e.g., frequencies that correspond to amplification of a structural response).

Thus, Definitions 20 and 21 form a representation of the DFT/IDFT pair, where Eqs. (27) and (28) are the corresponding matrix-vector forms. The DFT and IDFT pair can be written in the general form

$$ X(k) = c_f \sum_{i=1}^{N} x(i) e^{\pm j \frac{2\pi}{N}(i-1)(k-1)} \quad (31a) $$

$$ x(i) = c_i \sum_{k=1}^{N} X(k) e^{\mp j \frac{2\pi}{N}(i-1)(k-1)} \quad (31b) $$

where $c_i$ and $c_f$ are such that $c_f c_i = 1/N$ but are otherwise arbitrary. Common choices are $\{c_f, c_i\} = \{1/\sqrt{N}, 1/\sqrt{N}\}$ or $\{c_f, c_i\} = \{1, 1/N\}$, where the multiplicative constants in the matrix-vector formulation (i.e., Eqs. (27) and (28) or Eqs. (29) and (30)) are adjusted accordingly.

If the generally complex sequences $x(i)$ and $X(k)$ are dissected into their real and imaginary parts, the DFT/IDFT pair is represented by

$$ x(i) = x_R(i) + jx_I(i) \quad (32a) $$

$$ X(k) = X_R(k) + jX_I(k) \quad (32b) $$

where the subscripts $R$ and $I$ denote the real and imaginary parts and each sequence pair $(x_R(i), x_I(i))$ and $(X_R(k), X_I(k))$ is real for $i, k = 1, 2, ..., N$. An alternative representation of the DFT and IDFT is obtained by substituting Eq. (32) in Definition 20, writing the complex exponential in terms of sines and cosines, and collecting the real and imaginary terms. The result is

$$ X_R(k) = \sum_{i=1}^{N} \left( x_R(i) \cos\left(\frac{2\pi(i-1)(k-1)}{N}\right) - x_I(i) \sin\left(\frac{2\pi(i-1)(k-1)}{N}\right) \right) \quad (33a) $$

$$ X_I(k) = \sum_{i=1}^{N} \left( x_R(i) \sin\left(\frac{2\pi(i-1)(k-1)}{N}\right) + x_I(i) \cos\left(\frac{2\pi(i-1)(k-1)}{N}\right) \right) \quad (33b) $$

which together form the DFT of $x(i)$ according to Eq. (32b). A similar relationship for the IDFT is obtained by substituting Eq. (32) into Definition 21 and collecting the real and imaginary terms. Then
$$x_R(i) = + \frac{1}{N} \sum_{i=1}^{N} \left( X_R(k) \cos \left( \frac{2\pi(i-1)(k-1)}{N} \right) + X_I(k) \sin \left( \frac{2\pi(i-1)(k-1)}{N} \right) \right) \quad (34a)$$

$$x_I(i) = -\frac{1}{N} \sum_{i=1}^{N} \left( X_R(k) \sin \left( \frac{2\pi(i-1)(k-1)}{N} \right) - X_I(k) \cos \left( \frac{2\pi(i-1)(k-1)}{N} \right) \right) \quad (34b)$$

together form the IDFT of $X(k)$ according to Eq. (32a). The DFT/ IDFT pair defined by Eqs. (32)–(34) are equivalent to Definitions 20 and 21.

**Example 23.** Reconsider Example 21, where it is shown that the DFT of $\mathbf{x}_4 = (0, 1, 2, 3)^T$ is the four-vector $\mathbf{X}_4 = (6, -2-2j, -2, -2+2j)^T$. Because $\mathbf{x}_4$ is real, Eq. (33) can be used to compute each $X(k) = X_R(k) + jX_I(k)$ for $k = 1, 2, 3, 4$. If $k=2$, for example, the real and imaginary DFT components are given by

$$\begin{aligned}
X_R(2) &= \sum_{i=1}^{4} x_R(i) \cos\left(\frac{2\pi(i-1)(2-1)}{4}\right) \\
&= 0 \cdot \cos\left(\frac{2\pi(1-1)(1)}{4}\right) + 1 \cdot \cos\left(\frac{2\pi(2-1)(1)}{4}\right) \\
&\quad + 2 \cdot \cos\left(\frac{2\pi(3-1)(1)}{4}\right) + 3 \cdot \cos\left(\frac{2\pi(4-1)(1)}{4}\right) \\
&= 0 \cdot \cos\left(\frac{0\pi}{2}\right) + 1 \cdot \cos\left(\frac{1\pi}{2}\right) + 2 \cdot \cos\left(\frac{2\pi}{2}\right) + 3 \cdot \cos\left(\frac{3\pi}{2}\right) \\
&= (0)(1) + (1)(0) + (2)(-1) + (3)(0) \\
&= -2
\end{aligned}$$

$$\begin{aligned}
X_I(2) &= \sum_{i=1}^{4} x_R(i) \sin\left(\frac{2\pi(i-1)(2-1)}{4}\right) \\
&= 0 \cdot \sin\left(\frac{0\pi}{2}\right) + 1 \cdot \sin\left(\frac{1\pi}{2}\right) + 2 \cdot \sin\left(\frac{2\pi}{2}\right) + 3 \cdot \sin\left(\frac{3\pi}{2}\right) \\
&= (0)(0) + (1)(1) + (2)(0) + (3)(-1) \\
&= -2
\end{aligned}$$

such that $X(2) = -2 - 2j$, as expected. Results for $k = 1, 3, 4$ follow similarly.

**2.8 The Circulant Eigenvalue Problem.** The eigenvalues and eigenvectors of circulants and block circulants with circulant blocks have thus far been inferred from Theorem 9 (circulant matrix) and Corollary 22 (block circulant matrix with circulant blocks), where these matrices are fully diagonalized. Determination of the eigenvalues and eigenvectors of a block circulant matrix with generally noncirculant and nonsymmetric blocks is systematically described here, which reinforces the results already obtained for the special cases of $\mathbf{C} \in \mathcal{C}_N$ and $\mathbf{C} \in \mathcal{B}\mathcal{C}_{M,N}$ with circulant generating matrices. The standard cEVP is discussed in Sec. 2.8.1, where an eigensolution is obtained for a general matrix $\mathbf{C} \in \mathcal{B}\mathcal{C}_{M,N}$. Section 2.8.2 generalizes these results to handle $(\mathbf{M}, \mathbf{K})$ systems with system matrices contained in $\mathcal{B}\mathcal{C}_{M,N}$, which arise naturally in vibration studies of rotationally periodic structures. The structure of the eigenvalues and eigenvectors is discussed in Sec. 2.8.3, which builds upon the relationship to the DFT described in Sec. 2.7. Section 2.8.4 introduces fundamental orthogonality conditions for the special case of block circulants with symmetric generating matrices.

**2.8.1 Standard Circulant Eigenvalue Problem.** Consider the block circulant matrix $\mathbf{C} \in \mathcal{B}\mathcal{C}_{M,N}$ with arbitrary generating matrices $\mathbf{C}_1, \mathbf{C}_2, \dots, \mathbf{C}_N$. The standard cEVP involves determination

of the scalar eigenvalues $\lambda$ and $NM \times 1$ eigenvectors $\mathbf{q}$ of $\mathbf{C}$ such that

$$\mathbf{0}_{NM} = (\mathbf{C} - \lambda \mathbf{I}_{NM})\mathbf{q} \quad (35)$$

where $\mathbf{0}_{NM}$ is a $NM \times 1$ vector of zeros and $\mathbf{I}_{NM}$ is the identity matrix of dimension $NM$. The problem can be simplified considerably by exploiting the block circulant nature of $\mathbf{C}$. To this end, partition $\mathbf{q} = (\mathbf{q}_1, \mathbf{q}_2, \dots, \mathbf{q}_N)^T$ into $M \times 1$ vectors $\mathbf{q}_i$ ($i = 1, \dots, N$) and introduce the change of coordinates

$$\mathbf{q} = (\mathbf{E}_N \otimes \mathbf{I}_M)\mathbf{u} \quad (36)$$

where $\mathbf{I}_M$ is the $M \times M$ identity matrix (same dimension as the generating matrices of $\mathbf{C}$) and $\mathbf{u} = (\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_N)^T$ is composed of $N$ M-vectors $\mathbf{u}_i$. Substituting Eq. (36) into Eq. (35) and multiplying from the left by the unitary matrix $(\mathbf{E}_N \otimes \mathbf{I}_M)^H = (\mathbf{E}_N^H \otimes \mathbf{I}_M)$ yields

$$\begin{aligned}
\mathbf{0}_{NM} &= (\mathbf{E}_N^H \otimes \mathbf{I}_M)(\mathbf{C} - \lambda \mathbf{I}_{NM})(\mathbf{E}_N \otimes \mathbf{I}_M)\mathbf{u} \\
&= ((\mathbf{E}_N^H \otimes \mathbf{I}_M)\mathbf{C}(\mathbf{E}_N \otimes \mathbf{I}_M) \\
&\quad - \lambda(\mathbf{E}_N^H \otimes \mathbf{I}_M)\mathbf{I}_{NM}(\mathbf{E}_N \otimes \mathbf{I}_M))\mathbf{u} \\
&= \begin{bmatrix} \mathbf{\Lambda}_1 & \mathbf{0} \\ \mathbf{\Lambda}_2 & \mathbf{0} \\ \vdots & \vdots \\ \mathbf{0} & \mathbf{\Lambda}_N \end{bmatrix} - \lambda \begin{bmatrix} \mathbf{I}_M & \mathbf{0} \\ \mathbf{0} & \mathbf{I}_M \\ \vdots & \vdots \\ \mathbf{0} & \mathbf{I}_M \end{bmatrix} \begin{bmatrix} \mathbf{u}_1 \\ \mathbf{u}_2 \\ \vdots \\ \mathbf{u}_N \end{bmatrix}
\end{aligned}$$

which follows from Theorem 10, and from

$$\begin{aligned}
(\mathbf{E}_N^H \otimes \mathbf{I}_M)\mathbf{I}_{NM}(\mathbf{E}_N \otimes \mathbf{I}_M) &= (\mathbf{E}_N \otimes \mathbf{I}_M)^H (\mathbf{E}_N \otimes \mathbf{I}_M) \\
&= \mathbf{I}_{NM} \\
&= \operatorname{diag} \underbrace{(\mathbf{I}_M, \mathbf{I}_M, \dots, \mathbf{I}_M)}_{N \text{ terms}}
\end{aligned}$$

in light of Corollary 11. Thus, the single eigenvalue problem defined by Eq. (35) is decomposed into the $N$ reduced-order standard EVPs

$$\mathbf{0}_M = (\mathbf{\Lambda}_i - \lambda \mathbf{I}_M)\mathbf{u}_i, \quad i = 1, 2, \dots, N \quad (37)$$

where $\mathbf{0}_M$ is a $M \times 1$ vector of zeros and each $\mathbf{\Lambda}_i$ is defined by Eq. (23) in terms of the generating matrices of $\mathbf{C}$. Because the transformation defined by Eq. (36) is unitary, it preserves the eigenvalues of $\mathbf{C}$. Thus, the $NM$ eigenvalues of $\mathbf{C}$ are the eigenvalues of the $NM \times M$ matrices $\mathbf{\Lambda}_i$, which follow from the characteristic polynomials

$$\det(\mathbf{\Lambda}_i - \lambda \mathbf{I}_M) = 0, \quad i = 1, 2, \dots, N \quad (38)$$

If $\lambda = \lambda_i^{(p)}$ denotes the $p$th eigenvalue of the $i$th matrix $\mathbf{\Lambda}_i$ for $p = 1, 2, \dots, M$, then the attendant $M \times 1$ eigenvector $\mathbf{u}_i^{(p)}$ is obtained from Eq. (37). The corresponding $NM \times 1$ eigenvector of $\mathbf{C}$ follows from Eq. (36) and is given by

$$\begin{aligned}
\mathbf{q}_i^{(p)} &= (\mathbf{E}_N \otimes \mathbf{I}_M) (\mathbf{0}_M, \dots, \mathbf{u}_i^{(p)}, \dots, \mathbf{0}_M)^T \\
&= ((\mathbf{e}_1, \dots, \mathbf{e}_i, \dots, \mathbf{e}_N) \otimes \mathbf{I}_M) (\mathbf{0}_M, \dots, \mathbf{u}_i^{(p)}, \dots, \mathbf{0}_M)^T \\
&= (\mathbf{e}_1 \otimes \mathbf{I}_M, \dots, \mathbf{e}_i \otimes \mathbf{I}_M, \dots, \mathbf{e}_N \otimes \mathbf{I}_M) \\
&\quad \times (\mathbf{0}_M, \dots, \mathbf{u}_i^{(p)}, \dots, \mathbf{0}_M)^T \\
&= (\mathbf{e}_i \otimes \mathbf{I}_M) \mathbf{u}_i^{(p)} \\
&= \mathbf{e}_i \otimes \mathbf{u}_i^{(p)}
\end{aligned} \quad (39)$$
for $i = 1, 2, ..., N$ and $p = 1, 2, ..., M$. If the scalars $\alpha_i^{(p)}$ are such that each

$$ \tilde{\mathbf{u}}_i^{(p)} = \alpha_i^{(p)} \mathbf{u}_i^{(p)} \quad (40) $$

is orthonormal with respect to $\Lambda_i$, then the corresponding orthonormal eigenvectors of $\mathbf{C}$ are given by

$$ \begin{aligned} \tilde{\mathbf{q}}_i^{(p)} &= \mathbf{e}_i \otimes \tilde{\mathbf{u}}_i^{(p)} \\ &= \mathbf{e}_i \otimes (\alpha_i^{(p)} \mathbf{u}_i^{(p)}) \\ &= \alpha_i^{(p)} (\mathbf{e}_i \otimes \mathbf{u}_i^{(p)}) \\ &= \alpha_i^{(p)} \mathbf{q}_i^{(p)} \end{aligned} \quad (41) $$

for $i = 1, 2, ..., N$ and $p = 1, 2, ..., M$.

If $\mathbf{C}$ is an ordinary (not block) circulant with $M=1$, Eq. (41) reduces to

$$ \tilde{\mathbf{q}}_i^{(1)} = \mathbf{q}_i^{(1)} = \mathbf{e}_i \otimes 1 = \mathbf{e}_i, \quad (M=1) \quad (42) $$

which confirms that all circulants contained in $\mathscr{C}_N$ share the same $N \times 1$ eigenvectors $\mathbf{e}_1, \mathbf{e}_2, ..., \mathbf{e}_N$, and each $\mathbf{e}_i$ is orthonormal with respect to $\mathbf{C}$. The eigenvalues of a matrix $\mathbf{C} \in \mathscr{C}_N$ with generating elements $c_1, c_2, ..., c_N$ are given by Eq. (21), or equivalently by Eq. (22). If $\mathbf{C} \in \mathscr{C}_N$, the eigenvalues follow from Corollary 17.

**Example 24.** Consider $\mathbf{C} = \text{circ}(4, -1, 0, -1) \in \mathscr{C}_4$ from Examples 15 and 17, where it is shown that

$$ \mathbf{E}_4^H \mathbf{C} \mathbf{E}_4 = \text{diag}(2, 4, 6, 4) $$

Thus, the eigenvalues of $\mathbf{C}$ are 2, 4, 6, and 4. Because $N=4$ is even, $\lambda_1 = 2$ and $\lambda_{(N+2)/2} = \lambda_3 = 6$ are distinct and $\lambda_2 = \lambda_4 = 4$ are repeated. The reason for this eigenvalue symmetry is discussed in Sec. 2.8.3. The eigenvalues can be verified using

$$ \lambda_i = 4 - 2 \cos \frac{\pi}{2} (i - 1), \quad i = 1, 2, 3, 4 $$

which follows from Corollary 17 for the case of even $N$ because $\mathbf{C}$ is also contained in $\mathscr{C}_4$. Because $\mathbf{C}$ is an ordinary circulant, its orthonormal eigenvectors are simply the columns of the Fourier matrix $\mathbf{E}_4$, and are given by Definition 18 according to Eq. (42). For example,

$$ \begin{aligned} \mathbf{e}_2 &= \frac{1}{\sqrt{4}} (1, w_4^1, w_4^2, w_4^3)^\mathrm{T} \\ &= \frac{1}{2} (1, e^{j\frac{2\pi}{4}-1}, e^{j\frac{2\pi}{4}-2}, e^{j\frac{2\pi}{4}-3})^\mathrm{T} \\ &= \frac{1}{2} (1, e^{j\frac{2\pi}{4}}, e^{j\pi}, e^{j\frac{3\pi}{2}})^\mathrm{T} \\ &= \frac{1}{2} (1, j, -1, -j)^\mathrm{T} \end{aligned} $$

which can be visualized in Fig. 2 for the case of $N=4$. The complete set of eigenvectors is given by

$$ \mathbf{e}_1 = \frac{1}{2} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, \quad \mathbf{e}_2 = \frac{1}{2} \begin{bmatrix} 1 \\ j \\ -1 \\ -j \end{bmatrix}, \quad \mathbf{e}_3 = \frac{1}{2} \begin{bmatrix} 1 \\ -1 \\ 1 \\ -1 \end{bmatrix}, \quad \mathbf{e}_4 = \frac{1}{2} \begin{bmatrix} 1 \\ -j \\ -1 \\ j \end{bmatrix} $$

The eigenvectors $\mathbf{e}_1$ and $\mathbf{e}_3$ are real and correspond to the distinct eigenvalues $\lambda_1 = 2$ and $\lambda_3 = 6$. The eigenvectors $\mathbf{e}_2$ and $\mathbf{e}_4$ are complex conjugates according to Eq. (17) and correspond to the repeated eigenvalue $\lambda_2 = \lambda_4 = 4$. Example 29 of Sec. 2.8.4 discusses orthogonality of the orthonormal eigenvectors $(1/2)\mathbf{e}_i$ with respect to the matrix $\mathbf{C}$.

The same basic results also hold for the nonsymmetric circulant $\mathbf{C} = \text{circ}(4, -1, 0, 1) \in \mathscr{C}_4$ in Example 16, where it is shown that $\mathbf{E}_4^H \mathbf{C} \mathbf{E}_4 = \text{diag}(4, 4 - 2j, 4, 4 + 2j)$. In this case, the eigenvalues are given by

$$ \alpha(\mathbf{C}) = \{4, 4 - 2j, 4, 4 + 2j\} $$

and the corresponding eigenvectors are the same as those in Example 24 because all circulants contained in $\mathscr{C}_N$ share the same linearly independent eigenvectors.

**Example 25.** Consider $\mathbf{C} = \text{circ}(\mathbf{A}, \mathbf{B}, \mathbf{0}, \mathbf{B}) \in \mathscr{BC}_{2,4}$ from Examples 6, 18, 19, and 20, where it is shown that

$$ \begin{aligned} (\mathbf{E}_4^H \otimes \mathbf{I}_2) \mathbf{C} (\mathbf{E}_4 \otimes \mathbf{I}_2) \\ &= \text{diag} \begin{bmatrix} \begin{bmatrix} 0 & -1 \\ -1 & 0 \end{bmatrix}, \begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix}, \begin{bmatrix} 4 & -1 \\ -1 & 4 \end{bmatrix}, \begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix} \end{bmatrix} \\ &= \text{diag}(\mathbf{\Lambda}_1, \mathbf{\Lambda}_2, \mathbf{\Lambda}_3, \mathbf{\Lambda}_4) \end{aligned} $$

The eigenvalues of $\mathbf{C}$ are obtained from the reduced-order matrices $\mathbf{\Lambda}_i$ ($i = 1, 2, 3, 4$). For example, the eigenvalues of $\mathbf{\Lambda}_3$ follow from the characteristic polynomial

$$ \begin{aligned} \det(\mathbf{\Lambda}_3 - \lambda \mathbf{I}_2) &= \begin{vmatrix} \begin{bmatrix} 4 & -1 \\ -1 & 4 \end{bmatrix} & - \lambda \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} \end{vmatrix} \\ &= \lambda^2 - 8\lambda + 15 \\ &= (\lambda - 3)(\lambda - 5) = 0 \end{aligned} $$

and are given by $\alpha(\mathbf{\Lambda}_3) = \{3, 5\}$. Similarly, $\alpha(\mathbf{\Lambda}_1) = \{-1, 1\}$ and $\alpha(\mathbf{\Lambda}_2) = \alpha(\mathbf{\Lambda}_4) = \{1, 3\}$. Because $N=4$ is even, $\alpha(\mathbf{\Lambda}_1)$ and $\alpha(\mathbf{\Lambda}_3)$ are distinct sets of eigenvalues and $\alpha(\mathbf{\Lambda}_2) = \alpha(\mathbf{\Lambda}_4)$ are repeated sets. Section 2.8.3 discusses the symmetry characteristics and multiplicities of these groups of eigenvalues. The eigenvectors of $\mathbf{C}$ follow from the eigenvectors of each $\mathbf{\Lambda}_i$ according to Eq. (39). For example, for the eigenvector $\mathbf{u}_3^{(1)} = (1, 1)^\mathrm{T}$ of $\mathbf{\Lambda}_3$ with eigenvalue $\lambda_3^{(1)} = 3$, the corresponding eigenvector of $\mathbf{C}$ is

$$ \begin{aligned} \mathbf{q}_3^{(1)} &= \mathbf{e}_3 \otimes \mathbf{u}_3^{(1)} \\ &= \frac{1}{\sqrt{N}} (1, w_4^2, w_4^4, w_4^6)^\mathrm{T} \otimes \begin{bmatrix} 1 \\ 1 \end{bmatrix} \\ &= \frac{1}{\sqrt{4}} (1, -1, 1, -1)^\mathrm{T} \otimes \begin{bmatrix} 1 \\ 1 \end{bmatrix} \\ &= \frac{1}{2} \begin{bmatrix} \begin{bmatrix} 1 \\ 1 \end{bmatrix}, \begin{bmatrix} -1 \\ -1 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \end{bmatrix}, \begin{bmatrix} -1 \\ -1 \end{bmatrix} \end{bmatrix}^\mathrm{T} \\ &= \frac{1}{2} (1, 1, -1, -1, 1, 1, -1, -1)^\mathrm{T} \end{aligned} $$

The entire set of $NM=8$ reduced-order eigenvectors and eigenvalues is given by

$$ \left. \begin{aligned} \mathbf{u}_1^{(1)} &= (1, 1)^\mathrm{T}, & \lambda_1^{(1)} &= -1 \\ \mathbf{u}_1^{(2)} &= (-1, 1)^\mathrm{T}, & \lambda_1^{(2)} &= 1 \\ \mathbf{u}_2^{(1)} &= (1, 1)^\mathrm{T}, & \lambda_2^{(1)} &= 1 \\ \mathbf{u}_2^{(2)} &= (-1, 1)^\mathrm{T}, & \lambda_2^{(2)} &= 3 \\ \mathbf{u}_3^{(1)} &= (1, 1)^\mathrm{T}, & \lambda_3^{(1)} &= 3 \\ \mathbf{u}_3^{(2)} &= (-1, 1)^\mathrm{T}, & \lambda_3^{(2)} &= 5 \\ \mathbf{u}_4^{(1)} &= (1, 1)^\mathrm{T}, & \lambda_4^{(1)} &= 1 \\ \mathbf{u}_4^{(2)} &= (-1, 1)^\mathrm{T}, & \lambda_4^{(2)} &= 3 \end{aligned} \right\} $$
where each pair satisfies Eq. (37). The corresponding eigenvectors of C are

$$
\left.
\begin{aligned}
\mathbf{q}_1^{(1)} &= \frac{1}{2} (1, 1, 1, 1, 1, 1, 1)^T \\
\mathbf{q}_1^{(2)} &= \frac{1}{2} (-1, 1, -1, 1, -1, 1, -1)^T \\
\mathbf{q}_2^{(1)} &= \frac{1}{2} (-1, -1, -j, -j, 1, 1, j)^T \\
\mathbf{q}_2^{(2)} &= \frac{1}{2} (-1, 1, -j, j, 1, -1, -j)^T \\
\mathbf{q}_3^{(1)} &= \frac{1}{2} (-1, -1, 1, 1, -1, 1, 1)^T \\
\mathbf{q}_3^{(2)} &= \frac{1}{2} (-1, 1, 1, -1, -1, 1, -1)^T \\
\mathbf{q}_4^{(1)} &= \frac{1}{2} (-1, -1, j, j, 1, 1, -j)^T \\
\mathbf{q}_4^{(2)} &= \frac{1}{2} (-1, 1, j, -j, 1, -1, -j)^T
\end{aligned}
\right\}
$$

The eigenvectors are made orthonormal according to Eqs. (40) and (41) by setting each $\alpha_i^{(p)} = 1/\sqrt{2}$ for $i = 1, 2, ..., N$ and $p = 1, 2, ..., M$. Orthogonality of the eigenvectors $\tilde{q}_i^{(p)}$ with respect to C is discussed in Example 30 of Sec. 2.8.4. ⊥

The determinant of any matrix is the product of its eigenvalues, which yields the following result.

COROLLARY 24. Let $\mathbf{C} \in \mathcal{B}\mathcal{C}_{M,N}$ be a block circulant matrix. Then the determinant of $\mathbf{C}$ is given by

$$
\det \mathbf{C} = \prod_{i=1}^{NM} \lambda_i
$$

where $\lambda_i$ is the ith eigenvalue of C.

<figure><img src="image_37.png" /></figure>

The determinant of $\mathbf{C} \in \mathcal{C}_N$ follows from Corollary 24 by setting $M=1$. In light of Eq. (21),

$$
\det \mathbf{C} = \prod_{i=1}^{N} \sum_{k=1}^{N} c_k w_N^{(k-1)(i-1)} \quad (C \in \mathcal{C}_N) \quad (43)
$$

for an ordinary circulant matrix with generating elements $c_1, c_2, ..., c_N$. For the special case of $\mathbf{C} \in \mathcal{C} \mathcal{N}$, the ith eigenvalue $\lambda_i$ in Corollary 24 can be replaced by the result given in Corollary 17. Similarly, $\lambda_i$ can be replaced with Eq. (25) if $\mathbf{C} \in \mathcal{B} \mathcal{C}_{M,N}$ has circulant generating matrices.

Example 26. Consider $\mathbf{C} = \text{circ}(\mathbf{A}, \mathbf{B}, \mathbf{0}, \mathbf{B}) \in \mathcal{B}\mathcal{C}_{2,4}$ from Example 25, where it is shown that the eigenvalues are given by the set $\alpha(\mathbf{C}) = \{-1, 1, 1, 3, 3, 5, 1, 3\}$. The determinant of $\mathbf{C}$ follows from Corollary (24) and is given by

$$
\det \mathbf{C} = -1 \times 1 \times 1 \times 3 \times 3 \times 5 \times 1 \times 3 = -135
$$

which is simply the product of the eigenvalues of C.

<figure><img src="image_38.png" /></figure>

2.8.2 Generalized Circulant Eigenvalue Problem. The generalized cEVP involves determination of the scalar eigenvalues $\lambda$ and $NM \times 1$ eigenvectors $\mathbf{q}$ of a cyclic system $(\mathbf{M},\mathbf{K})$ such that

$$
\mathbf{0}_{NM} = (\mathbf{K} - \lambda \mathbf{M}) \mathbf{q} \quad (44)
$$

where

$$
\left.
\begin{aligned}
\mathbf{M} &= \text{circ}(\mathbf{M}_1, \mathbf{M}_2, \dots, \mathbf{M}_N) \\
\mathbf{K} &= \text{circ}(\mathbf{K}_1, \mathbf{K}_2, \dots, \mathbf{K}_N)
\end{aligned}
\right\}
$$

are block circulant matrices contained in $\mathcal{B}\mathcal{C}_{M,N}$. This type of problem arises in the study of cyclic vibratory mechanical systems

composed of $N$ sectors with $M$ DOFs per sector, where $\mathbf{M}$ and $\mathbf{K}$ are $NM \times NM$ block circulant mass and stiffness matrices. Several examples are discussed in Sec. 3, where the eigenvectors $\mathbf{q}$ are the system mode shapes and the eigenvalues $\lambda$ correspond to the system natural frequencies. The generalized cEVP defined by Eq. (44) is handled in the same way as the standard cEVP of Sec. 2.8.1. To this end, partition $\mathbf{q} = (\mathbf{q}_1, \mathbf{q}_2, \dots, \mathbf{q}_N)^\mathrm{T}$ into $M \times 1$ vectors $\mathbf{q}_i$ ($i = 1, 2, \dots, N$), transform to a new set of coordinates $\mathbf{u} = (\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_N)^\mathrm{T}$ by substituting Eq. (36) into Eq. (44), and left-multiply the result by the unitary matrix $\mathbf{E}_N^\mathrm{H} \otimes \mathbf{I}_M$. It follows that

$$
\begin{align}
\mathbf{0}_{NM} &= (\mathbf{E}_N^\mathrm{H} \otimes \mathbf{I}_M)(\mathbf{K} - \lambda \mathbf{M})(\mathbf{E}_N \otimes \mathbf{I}_M)\mathbf{u} \nonumber \\
&= ((\mathbf{E}_N^\mathrm{H} \otimes \mathbf{I}_M)\mathbf{K}(\mathbf{E}_N \otimes \mathbf{I}_M) - \lambda(\mathbf{E}_N^\mathrm{H} \otimes \mathbf{I}_M)\mathbf{M}(\mathbf{E}_N \otimes \mathbf{I}_M))\mathbf{u} \nonumber \\
&= \left( \begin{bmatrix} \tilde{\mathbf{K}}_1 & & & & & & \\ & \ddots & & & & & \\ & & \tilde{\mathbf{K}}_2 & & & & \\ & & & \ddots & & & \\ & & & & \tilde{\mathbf{M}}_1 & & \\ & & & & & \ddots & \\ & & & & & & \tilde{\mathbf{M}}_N \end{bmatrix} - \lambda \begin{bmatrix} \mathbf{0} & & & & & & \\ & \ddots & & & & & \\ & & \mathbf{0} & & & & \\ & & & \ddots & & & \\ & & & & \mathbf{0} & & \\ & & & & & \ddots & \\ & & & & & & \mathbf{0} \end{bmatrix} \right) \nonumber \\
&\quad \times \begin{bmatrix} \mathbf{u}_1 \\ \mathbf{u}_2 \\ \vdots \\ \mathbf{u}_N \end{bmatrix} \tag{45}
\end{align}
$$

where the decomposed $M \times M$ matrices

$$
\left.
\begin{aligned}
\tilde{\mathbf{M}}_i &= \sum_{k=1}^{N} \mathbf{M}_k w_N^{(k-1)(i-1)} \\
\tilde{\mathbf{K}}_i &= \sum_{k=1}^{N} \mathbf{K}_k w_N^{(k-1)(i-1)}
\end{aligned}
\right\}, \quad i = 1, 2, \dots, N \qquad (46)
$$

follow from Theorem 10. Equation (45) represents a set of $N$ reduced-order generalized EVPs

$$
\mathbf{0}_M = (\tilde{\mathbf{K}}_i - \lambda \tilde{\mathbf{M}}_i) \mathbf{u}_i, \quad i = 1, 2, \dots, N \quad (47)
$$

which are analogous to the reduced-order standard EVPs defined by Eq. (37). The eigenvalues are determined from the characteristic polynomials

$$
\det(\tilde{\mathbf{K}}_i - \lambda \tilde{\mathbf{M}}_i) = 0, \quad i = 1, 2, \dots, N \quad (48)
$$

and are denoted by $\lambda = \lambda_i^{(p)}$ for $p = 1, 2, ..., M$. Each $\lambda_i^{(p)}$ also satisfies Eq. (44) because the transformation to new coordinates via Eq. (36) is unitary, and hence preserves the system eigenvalues. The reduced-order eigenvectors $\mathbf{u}_i = \mathbf{u}_i^{(p)}$ are obtained from Eq. (47) for each $\lambda_i^{(p)}$. The eigenvectors of the full system $(\mathbf{M},\mathbf{K})$ are given by $\mathbf{q}_i^{(p)} = \mathbf{e}_i \otimes \mathbf{u}_i^{(p)}$, which is the same as Eq. (39). The relationships defined by Eqs. (40) and (41) also hold for the generalized cEVP to make the eigenvectors orthonormal.

If $\mathbf{M}$ and $\mathbf{K}$ are ordinary circulants (i.e., $M=1$), then the system eigenvectors reduce to $\tilde{\mathbf{q}}_i^{(1)} = \mathbf{q}_i^{(1)} = \mathbf{e}_i \otimes 1 = \mathbf{e}_i$, which is the same as Eq. (42) and shows that $\mathbf{e}_1, \mathbf{e}_2, \dots, \mathbf{e}_N$ are the orthonormal eigenvectors of all generalized eigensystems defined by $\mathbf{M}, \mathbf{K} \in \mathcal{C}_N$. If $M_1, M_2, \dots, M_N$ and $K_1, K_2, \dots, K_N$ are the generating elements of $\mathbf{M}$ and $\mathbf{K}$, respectively, the corresponding eigenvalues are

$$
\lambda_i = \frac{\sum_{k=1}^{N} K_k w_N^{(k-1)(i-1)}}{\sum_{k=1}^{N} M_k w_N^{(k-1)(i-1)}}, \quad i = 1, 2, \dots, N \quad (49)
$$
which follows from Eq. (45) by replacing each $\tilde{\mathbf{M}}_k$ with $M_k$ and $\tilde{\mathbf{K}}_k$ with $K_k$. For the special case of $\mathbf{M} = \mathbf{I}_N$ with generating elements $1, 0, \dots, 0$ (i.e., for the standard cEVP), Eq. (49) reduces to the form shown in Theorem 9, as expected.

It is clear from this formulation that the same basic steps are followed to solve the standard and generalized cEVPs. For the standard cEVP, we say that $\lambda_i^{(p)}$ and $\mathbf{q}_i^{(p)}$ are the eigenvalues and eigenvectors of the matrix $\mathbf{C}$. For the generalized cEVP, the eigenvalues and eigenvectors correspond to the system $(\mathbf{M}, \mathbf{K})$, not the individual matrices $\mathbf{M}$ and $\mathbf{K}$.

**Example 27.** Consider the generalized cEVP defined by Eq. (44). Let the generating elements of $\mathbf{M} \in \mathcal{C}_2$ be $M_1 = 2$ and $M_2 = -1$ and the generating elements of $\mathbf{K} \in \mathcal{C}_2$ be $K_1 = 5$ and $K_2 = -1$ such that

$$ \mathbf{M} = \begin{bmatrix} 2 & -1 \\ -1 & 2 \end{bmatrix} \quad \text{and} \quad \mathbf{K} = \begin{bmatrix} 5 & -1 \\ -1 & 5 \end{bmatrix} $$

Then the eigenvalues of the system $(\mathbf{M}, \mathbf{K})$ follow from Eq. (49) with $N=2$ and are given by

$$ \begin{aligned} \lambda_i &= \frac{\sum_{p=1}^{2} K_p w_N^{(p-1)(i-1)}}{\sum_{p=1}^{2} M_p w_N^{(p-1)(i-1)}} \\ &= \frac{5w_2^0 + (-1)w_2^{i-1}}{2w_2^0 + (-1)w_2^{i-1}} \\ &= \frac{5 - e^{j\pi(i-1)}}{2 - e^{j\pi(i-1)}} \end{aligned} $$

for $i=1, 2$. It follows that $\lambda_1 = 4$ and $\lambda_2 = 2$. The corresponding orthonormal eigenvectors are given by

$$ \begin{aligned} \tilde{\mathbf{q}}_1^{(1)} &= \mathbf{e}_1 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \end{bmatrix} \\ \tilde{\mathbf{q}}_2^{(1)} &= \mathbf{e}_2 = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ w_2 \end{bmatrix} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ -1 \end{bmatrix} \end{aligned} $$

which follow from Definition 18 according to Eq. (42).

<figure><img src="image_39.png" /></figure>

### 2.8.3 Eigenvalue and Eigenvector Structure.
For real-valued generating elements, such as those that arise in models of physical systems with cyclic symmetry, the eigenvalues of a circulant matrix $\mathbf{C} \in \mathcal{C}_N$ are endowed with certain symmetry characteristics, and the same is true for the eigenvalues of systems $\mathbf{M}, \mathbf{K} \in \mathcal{C}_N$. However, we do not require the circulants to be symmetric, as it is assumed in Corollary 17. We begin by systematically describing the eigenvalue structure of an ordinary circulant with real generating elements. The results are generalized by inspection to handle block circulants and $(\mathbf{M}, \mathbf{K})$ systems composed of circulant or block circulant matrices.

The eigenvalues $\lambda_i$ of a circulant matrix $\mathbf{C} \in \mathcal{C}_N$ with generating elements $c_1, c_2, \dots, c_N$ are given by Eq. (21), or the equivalent matrix-vector form in Eq. (22). It is convenient to re-index each $c_k$ and $\lambda_i$ such that

$$ \left. \begin{aligned} y(p)|_{p=0,1,2,\dots,N-1} &= c_k|_{k=1,2,3,\dots,N} \\ Y(r)|_{r=0,1,2,\dots,N-1} &= \lambda_i|_{i=1,2,3,\dots,N} \end{aligned} \right\} \quad (50) $$

which facilitates the results for real generating elements and clarifies their interpretation. If the eigenvalues are dissected according to $Y(r) = Y_R(r) + jY_I(r)$, then the real and imaginary components

$$ Y_R(r) = \sum_{p=0}^{N-1} y(p) \cos\left(\frac{2\pi pr}{N}\right) \quad (51a) $$

$$ Y_I(r) = \sum_{p=0}^{N-1} y(p) \sin\left(\frac{2\pi pr}{N}\right) \quad (51b) $$

follow from the formulation of Eq. (33) in Sec. 2.7 for a real-valued signal where, recall, the eigenvalue expression defined by Eq. (21) has exactly the same form as the DFT in Definition 20. That is, Eq. (51) also represents the real and imaginary parts of the DFT of a real-valued signal, where the sequence of generating elements $y(p)$ is analogous to a real signal and the eigenvalues $Y(r)$ are analogous to its DFT. It is shown that the symmetry of the DFT about the so-called Nyquist component also exists for the eigenvalues of a circulant matrix with real generating elements. As is customary in signal processing, we restrict the formulation to even $N$. The case of odd $N$ also yields symmetric eigenvalues, but with multiplicity of the Nyquist component. This is handled by example in Sec. 3 (for instance, see Fig. 9).

For even $N$, the zeroth eigenvalue $Y(0)$ and “Nyquist” eigenvalue $Y(N/2)$ are always real because

$$ Y_0 \equiv Y_R(0) = \sum_{p=0}^{N-1} y(p) \cos(0) = \sum_{p=0}^{N-1} y(p) \quad (52a) $$

$$ Y_I(0) = \sum_{p=0}^{N-1} y(p) \sin(0) = 0 $$

$$ Y_{N/2} \equiv Y_R\left(\frac{N}{2}\right) = \sum_{p=0}^{N-1} y(p) \cos(p\pi) = \sum_{p=0}^{N-1} y(p) (-1)^p \quad (52b) $$

$$ Y_I\left(\frac{N}{2}\right) = \sum_{p=0}^{N-1} y(p) \sin(p\pi) = 0 $$

are such that the imaginary parts vanish.<fnref n="2" /> The remaining eigenvalues appear in complex conjugate pairs, as the following corollaries show.

**COROLLARY 25.** Let $y(p)$ be the real-valued generating elements of a circulant matrix for $p = 0, 1, 2, \dots, N-1$ and $Y(r)$ denote its eigenvalues according to Eq. (21). Then

$$ Y(N-r) = \bar{Y}(r) = Y(-r) $$

for $r = 0, 1, 2, \dots, N-1$.

<figure><img src="image_40.png" /></figure>

*Proof.* The eigenvalues of $y(p)$ are given by $Y(r) = Y_R(r) + jY_I(r)$, where

$$ \begin{aligned} Y_R(r) &= \sum_{p=0}^{N-1} y(p) \cos\left(\frac{2\pi pr}{N}\right) \\ &= \sum_{p=0}^{N-1} y(p) \cos\left(\frac{2\pi p(-r)}{N}\right) \\ &= Y_R(-r) \end{aligned} \quad (\text{Eq. 51a}) $$

and the property $\cos(-\theta) = \cos(\theta)$ is employed. Similarly,

$$ \begin{aligned} -Y_I(r) &= -\sum_{p=0}^{N-1} y(p) \sin\left(\frac{2\pi pr}{N}\right) \\ &= \sum_{p=0}^{N-1} y(p) \sin\left(\frac{2\pi p(-r)}{N}\right) \\ &= Y_I(-r) \end{aligned} \quad (\text{Eq. 51b}) $$

<footnote n="2">²Equation (52a) also holds if $N$ is odd, but the Nyquist component is repeated with multiplicity of two.</footnote>
where the property $\sin(-\theta) = -\sin(\theta)$ is employed. It follows that

$$ 
\begin{aligned}
\overline{Y(r)} &= Y_R(r) - jY_I(r) \\
&= Y_R(-r) + jY_I(-r) \\
&= Y(-r)
\end{aligned}
 $$

which completes the right-hand side of the proof. To prove the left-hand side, consider

$$ 
\begin{aligned}
Y_R(N - r) &= \sum_{p=0}^{N-1} y(p) \cos\left(\frac{2\pi p(N-r)}{N}\right) \\
&= \sum_{p=0}^{N-1} y(p) \cos\left(2\pi p - \frac{2\pi pr}{N}\right) \\
&= \sum_{p=0}^{N-1} y(p) \left( \cos(2\pi p) \cos\left(-\frac{2\pi pr}{N}\right) \right. \\
&\qquad \left. - \sin(2\pi p) \sin\left(-\frac{2\pi pr}{N}\right) \right) \\
&= \sum_{p=0}^{N-1} y(p) \left( 1 \cdot \cos\left(-\frac{2\pi pr}{N}\right) - 0 \cdot \sin\left(-\frac{2\pi pr}{N}\right) \right) \\
&= \sum_{p=0}^{N-1} y(p) \cos\left(\frac{2\pi p(-r)}{N}\right) \\
&= Y_R(-r)
\end{aligned}
\qquad (\text{Eq. 51a}) $$

and a similar expansion shows that $Y_I(N - r) = -Y_I(r)$. It follows that

$$ 
\begin{aligned}
Y(N - r) &= Y_R(N - r) - jY_I(N - r) \\
&= Y_R(r) - jY_I(r) \\
&= \overline{Y(r)}
\end{aligned}
 $$

which completes the proof.

Corollary 25 establishes the following result.

COROLLARY 26. Let $y(p)$ be the real-valued generating elements of a circulant matrix for $p = 0, 1, 2, ..., N - 1$ and $Y(r)$ denote its eigenvalues according to Eq. (21). Then

$$ 
\begin{aligned}
|Y(N - r)| &= |Y(r)| \\
\angle Y(N - r) &= -\angle Y(r)
\end{aligned}
 $$

for integers $r = 0, 1, 2, ..., N - 1$.

<figure><img src="image_41.png" /></figure>

<figure><img src="image_42.png" /></figure>

The magnitudes $|Y(r)|$ and arguments $\angle Y(r)$ of the eigenvalues $Y(r)$ are listed in Table 3 for the special case of even $N = 8$, where $Y(r) = \overline{Y}(N - r)$ follows from complex conjugation of the left-hand equality given by Corollary 25. The zeroth eigenvalue $Y(0) = Y_0$ is real and generally distinct, as is $Y(N/2) = Y_{N/2}$ for even $N$, but the remaining eigenvalues generally appear in complex conjugate pairs. It follows that the eigenvalue magnitudes

<table><caption>Table 3 Magnitudes and arguments of $Y(r)$ for even $N = 8$</caption>
  <thead>
    <tr>
      <th>Index<br>r</th>
      <th>Eigenvalue<br>Y(r)</th>
      <th>Y&#773;(N - r)</th>
      <th>Magnitude<br>|Y(r)|</th>
      <th>Argument<br>&Delta;Y(r)</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>0</td>
      <td>Y(0) = Y<sub>0</sub></td>
      <td>Y(8)</td>
      <td>|Y(0)| = Y<sub>0</sub></td>
      <td>&Delta;Y(0)</td>
    </tr>
    <tr>
      <td>1</td>
      <td>Y(1)</td>
      <td>Y(7)</td>
      <td>|Y(1)|</td>
      <td>&Delta;Y(1)</td>
    </tr>
    <tr>
      <td>2</td>
      <td>Y(2)</td>
      <td>Y(6)</td>
      <td>|Y(2)|</td>
      <td>&Delta;Y(2)</td>
    </tr>
    <tr>
      <td>3</td>
      <td>Y(3)</td>
      <td>Y(5)</td>
      <td>|Y(3)|</td>
      <td>&Delta;Y(3)</td>
    </tr>
    <tr>
      <td>4 = (N/2)</td>
      <td>Y(4) = Y(4) = Y<sub>N/2</sub></td>
      <td>Y(4)</td>
      <td>|Y(4)| = Y<sub>N/2</sub></td>
      <td>&Delta;Y(4)</td>
    </tr>
    <tr>
      <td>5</td>
      <td>Y(5) = Y(3)</td>
      <td>Y(3)</td>
      <td>|Y(3)|</td>
      <td>-&Delta;Y(3)</td>
    </tr>
    <tr>
      <td>6</td>
      <td>Y(6) = Y(2)</td>
      <td>Y(2)</td>
      <td>|Y(2)|</td>
      <td>-&Delta;Y(2)</td>
    </tr>
    <tr>
      <td>7</td>
      <td>Y(7) = Y(1)</td>
      <td>Y(1)</td>
      <td>|Y(1)|</td>
      <td>-&Delta;Y(1)</td>
    </tr>
  </tbody>
</table>

(frequencies) are symmetric about the Nyquist component $Y_{N/2}$, as are the arguments (phase angles) but with the opposite sign for indices $r > N/2$.

The eigenvalue symmetries can be observed in the examples of Sec. 2.5.4. The eigenvalues of the matrix $C = \text{circ}(4, -1, 0, -1)$ in Example 15 are $\alpha(C) = \{2, 4, 6, 4\}$, where $Y(0) = 2$ and $Y_{N/2} = Y(2) = 6$ are real and distinct and $Y(1) = Y(3) = 4$ are real and repeated. Similarly, for the matrix $C = \text{circ}(4, -1, 0, 1)$ in Example 16, the eigenvalues are $\alpha(C) = \{4, 4 - 2j, 4, 4 + 2j\}$, where $Y(1) = 4 - 2j$ and $Y(3) = 4 + 2j$ are complex conjugates and $Y(0) = Y_{N/2} = Y(2) = 4$ are real-valued. As expected, these same symmetries are also observed in Example 21 for the DFT of a real-valued signal.

A similar formulation shows that the eigenvalues of real-valued $(M, K)$ systems exhibit the same symmetry characteristics because the numerator and denominator of Eq. (49) have exactly the same form as Eq. (21). If the scalars $M_k$ and $K_k$ in Eq. (49) are re-indexed and restricted to be real-valued, then Corollaries 25 and 26 are generalized accordingly.

For signal processing applications, the symmetry characteristics summarized in Table 3 have practical significance because the subset of $(N + 2)/2$ frequency-domain components $0 \le r \le N/2$ is endowed with the same basic “information” contained in all $N$ time-domain signal samples for $0 \le p \le N - 1$. That is, when transformed to the frequency domain by the DFT process, any real-valued signal has a zero-frequency or dc component ($r = 0$), distinct magnitude and phase information for $0 \le r \le N/2$, and repeated magnitude and phase information for $r > N/2$. For circulant matrices that describe physical systems with cyclic symmetry, $Y_0$ and $Y_{N/2}$ correspond to standing wave vibration modes and the remaining eigenvalues are associated with traveling wave modes. This is discussed in Sec. 3.

Equation (42) shows that $e_1, e_2, ..., e_N$ are the eigenvectors of any circulant matrix $C$, and the same is true for $(M, K)$ systems composed of circulant matrices. Each eigenvector $e_i$ is associated with an eigenvalue $Y(r)$ (i.e., $\lambda_i$) according to the indices defined by Eq. (50). For the special case of real generating elements, the eigenvalues summarized in Table 3 have exactly the same symmetry characteristics as the vectors $e_1, e_2, ..., e_N$, which are discussed in Sec. 2.5.2. For example, if $N$ is even, the real eigenvalues $Y_{N/2}$ (i.e., $\lambda_{(N+2)/2}$) and $Y(0)$ (i.e., $\lambda_1$) correspond to the real eigenvectors $e_{(N+2)/2}$ and $e_1$ defined by Eqs. (18) and (19), respectively. The remaining eigenvalues appear in complex conjugate pairs and are associated with the complex conjugate eigenvectors according to Eq. (17).

If the scalar sequences $y(p)$ and $Y(r)$ for a circulant matrix are replaced by a sequence of matrices $y(p)$ and $Y(r)$, it is clear that the formulation given above also holds for Eq. (23), which defines the eigenvalues for block circulant matrices. In this case, the groups of eigenvalues associated with each $\Lambda_i$ are endowed with the symmetry properties given in Table 3. This is confirmed by Example 25 where, using the indexing scheme of that section, $\alpha(\Lambda_1) = \{-1, 1\}$ and $\alpha(\Lambda_3) = \{3, 5\}$ are distinct sets of eigenvalues and $\alpha(\Lambda_2) = \alpha(\Lambda_4) = \{1, 3\}$ are repeated.

### 2.8.4 Eigenvector Orthogonality.
Here, we consider eigenvector orthogonality relationships for block circulant matrices $C$ and systems $(M, K)$ contained in $\mathcal{B}\mathcal{C}_{M,N}$ for the special case of symmetric generating matrices. However, we do not restrict either $C$ or $(M, K)$ to be symmetric or block symmetric. We require only that the generating matrices $C_1, C_2, ..., C_N$ of $C$ are symmetric for the standard cEVP, which guarantees that each $\Lambda_i$ is symmetric according to Corollary 19. Similarly, we require that the generating matrices $M_1, M_2, ..., M_N$ and $K_1, K_2, ..., K_N$ of $(M, K)$ are symmetric for the generalized cEVP, which implies that $(\bar{K}_i, \bar{M}_i)$ are symmetric. Symmetric generating matrices commonly arise in models of rotating flexible structures, including the ones considered in Sec. 3, where the sector models and intersector coupling are described by symmetric matrices. Then the usual orthogonality relationships hold for the reduced-order eigenvectors defined in Secs. 2.8.1 and 2.8.2. It is first shown that each $\bar{u}_i^{(p)}$ is
orthogonal with respect to $\Lambda_i$ for the standard cEVP. Proofs can be found in any standard textbook on linear algebra [98,99]. Together with generic orthogonality conditions on the basic circulant structure of a matrix $C \in \mathcal{B}^{C_{M,N}}$, this gives rise to an orthogonality condition on the eigenvector $\tilde{\mathbf{q}}_i^{(p)} = \mathbf{e}_i \otimes \tilde{\mathbf{u}}_i^{(p)}$ with respect to $C$. Orthogonality of $\tilde{\mathbf{q}}_i^{(p)}$ with respect to the system $\mathbf{M}, \mathbf{K} \in \mathcal{B}^{C_{M,N}}$ is handled similarly.

The results of this section, and the requirement of symmetric generating matrices, are meant to highlight how orthogonality of an eigenvector $\tilde{\mathbf{q}}_i^{(p)} = \mathbf{e}_i \otimes \tilde{\mathbf{u}}_i^{(p)}$ is essentially dissected into the orthogonality of $\mathbf{e}_i$ with respect to the circulant structure of $C \in \mathcal{B}^{C_{M,N}}$ and orthogonality of $\tilde{\mathbf{u}}_i^{(p)}$ with respect to the generating matrices (e.g., $\Lambda_i$), where the latter requires symmetric $C_1, C_2, \dots, C_N$. It should be noted that none of the results in Sec. 2, aside from this section, require symmetric generating matrices. In particular, Theorems 9 and 10, upon which block reduction of the cEVPs in Secs. 2.8.1 and 2.8.2 are based, are valid for arbitrary $\mathbf{M} \times \mathbf{M}$ generating matrices.

**COROLLARY 27.** Suppose each $\Lambda_i$ defined by Eq. (23) is symmetric. Let $\tilde{\mathbf{u}}_i^{(p)}$ be the $p$th orthonormal eigenvector of $\Lambda_i$ and $\lambda_i^{(p)}$ be the corresponding eigenvalue. Then if $\tilde{\mathbf{U}}_i = (\tilde{\mathbf{u}}_i^{(1)}, \tilde{\mathbf{u}}_i^{(2)}, \dots, \tilde{\mathbf{u}}_i^{(M)})$ is the $\mathbf{M} \times \mathbf{M}$ orthonormal modal matrix associated with $\Lambda_i$, it follows that

$$ \tilde{\mathbf{U}}_i^T \Lambda_i \tilde{\mathbf{U}}_i = \begin{bmatrix} \lambda_i^{(1)} & & 0 \\ & \lambda_i^{(2)} & \\ 0 & & \lambda_i^{(M)} \end{bmatrix}, \quad i = 1, 2, \dots, N $$

is a diagonal matrix with eigenvalues $\lambda_i^{(p)}$ along its diagonal for $p = 1, 2, \dots, M$ and

$$ \tilde{\mathbf{u}}_i^{(p)\mathrm{T}} \Lambda_i \tilde{\mathbf{u}}_i^{(q)} = \lambda_i^{(p)} \delta_{pq} $$

where $\delta_{pq}$ is the Kronecker delta.

**Example 28.** Consider the eigensolutions

$$ \left. \begin{aligned} \tilde{\mathbf{u}}_3^{(1)} &= \frac{1}{\sqrt{2}} (1, 1)^{\mathrm{T}}, & \lambda_3^{(1)} &= 3 \\ \tilde{\mathbf{u}}_3^{(2)} &= \frac{1}{\sqrt{2}} (-1, 1)^{\mathrm{T}}, & \lambda_3^{(2)} &= 5 \end{aligned} \right\} $$

corresponding to the symmetric matrix

$$ \Lambda_3 = \begin{bmatrix} 4 & -1 \\ -1 & 4 \end{bmatrix} $$

from Example 25, where the reduced-order eigenvectors are in orthonormal form. The corresponding reduced-order modal matrix is denoted by

$$ \tilde{\mathbf{U}}_3 = (\tilde{\mathbf{u}}_3^{(1)}, \tilde{\mathbf{u}}_3^{(2)}) \\ = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix} $$

It follows from Corollary 27 that the diagonal matrix

$$ \begin{aligned} \tilde{\mathbf{U}}_3^T \Lambda_3 \tilde{\mathbf{U}}_3 &= \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix}^T \begin{bmatrix} 4 & -1 \\ -1 & 4 \end{bmatrix} \frac{1}{\sqrt{2}} \begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix} \\ &= \frac{1}{2} \begin{bmatrix} 1 & 1 \\ -1 & 1 \end{bmatrix} \begin{bmatrix} 3 & -5 \\ 3 & 5 \end{bmatrix} \\ &= \frac{1}{2} \begin{bmatrix} 6 & 0 \\ 0 & 10 \end{bmatrix} \\ &= \begin{bmatrix} 3 & 0 \\ 0 & 5 \end{bmatrix} \end{aligned} $$

has eigenvalues $\lambda_3^{(1)} = 3$ and $\lambda_3^{(2)} = 5$ as its diagonal elements. The reader can verify that $\tilde{\mathbf{u}}_3^{(1)\mathrm{T}} \Lambda_3 \tilde{\mathbf{u}}_3^{(1)} = 3$ and $\tilde{\mathbf{u}}_3^{(2)\mathrm{T}} \Lambda_3 \tilde{\mathbf{u}}_3^{(2)} = 5$ according to Corollary 27.

Orthogonality of an eigenvector $\tilde{\mathbf{q}}_i^{(p)} = \mathbf{e}_i \otimes \tilde{\mathbf{u}}_i^{(p)}$ with respect to $C \in \mathcal{B}^{C_{M,N}}$ is essentially decomposed into orthogonality of $\mathbf{e}_i$ with respect to the circulant structure of $C$ and orthogonality of each $\tilde{\mathbf{u}}_i^{(p)}$ with respect to the symmetric matrices $\Lambda_i$. These individual orthogonality conditions are captured by Corollaries 18 and 27, which lead to the following fundamental result.

**COROLLARY 28.** Let $C \in \mathcal{B}^{C_{M,N}}$ be a block circulant matrix with symmetric generating matrices, $\mathbf{e}_i$ be the $i$th column of the $N \times N$ Fourier matrix $\mathbf{E}_N$, and $\tilde{\mathbf{u}}_i^{(p)}$ be the $p$th reduced-order orthonormal eigenvector corresponding to $\Lambda_i$ defined by Eq. (23). Then

$$ (\mathbf{e}_i^H \otimes (\tilde{\mathbf{u}}_i^{(p)})^\mathrm{T}) \mathbf{C} (\mathbf{e}_k \otimes \tilde{\mathbf{u}}_i^{(q)}) = \lambda_i^{(p)} \delta_{ik} \delta_{pq} $$

for $i, k = 1, 2, \dots, N$ and $p, q = 1, 2, \dots, M$, where $\lambda_i^{(p)}$ is the eigenvalue associated with $\tilde{\mathbf{u}}_i^{(p)}$ and $\delta_{ik}$ is the Kronecker delta.

**Proof.** Let $\tilde{\mathbf{U}}_i = (\tilde{\mathbf{u}}_i^{(1)}, \tilde{\mathbf{u}}_i^{(2)}, \dots, \tilde{\mathbf{u}}_i^{(M)})$ be the orthonormal modal matrix associated with $\Lambda_i$ and $C_1, C_2, \dots, C_N$ be the symmetric generating matrices of $C$. Corollary 19 guarantees that $\Lambda_i$ is symmetric because the generating matrices are symmetric. By setting $\mathbf{B} = \tilde{\mathbf{U}}_i$ and $(\cdot)^\# = (\cdot)^\mathrm{T}$ in Corollary 21, it follows that

$$ \begin{aligned} (\mathbf{e}_i^H \otimes \tilde{\mathbf{U}}_i^\mathrm{T}) \mathbf{C} (\mathbf{e}_k \otimes \tilde{\mathbf{U}}_i) &= \mathbf{\Psi}_i \delta_{ik} \\ &= \begin{cases} \mathbf{\Psi}_i, & i = k \\ \mathbf{0}, & \text{otherwise} \end{cases} \end{aligned} $$

where

$$ \mathbf{\Psi}_i = \sum_{n=1}^{N} \mathbf{B}^\# \mathbf{C}_n \mathbf{B}_N^{(n-1)(i-1)} \quad (\text{Eq. 24}) $$

$$ = \sum_{n=1}^{N} \tilde{\mathbf{U}}_i^T \mathbf{C}_n \tilde{\mathbf{U}}_i w_N^{(n-1)(i-1)} \quad (\text{by substitution}) $$

$$ = \tilde{\mathbf{U}}_i^T \sum_{n=1}^{N} \mathbf{C}_n w_N^{(n-1)(i-1)} \tilde{\mathbf{U}}_i \quad (\text{Eq. 23}) $$

$$ = \tilde{\mathbf{U}}_i^T \Lambda_i \tilde{\mathbf{U}}_i \quad (\text{Cor. 27}) \quad \begin{bmatrix} \lambda_i^{(1)} & & 0 \\ & \lambda_i^{(2)} & \\ 0 & & \lambda_i^{(M)} \end{bmatrix} $$

for $i = 1, 2, \dots, N_c$ Expanding the $\mathbf{M} \times \mathbf{M}$ matrix product $(\mathbf{e}_i^H \otimes \tilde{\mathbf{U}}_i^T) \mathbf{C} (\mathbf{e}_k \otimes \tilde{\mathbf{U}}_i)$ yields

$$ \left( \mathbf{e}_i^H \otimes \begin{bmatrix} (\tilde{\mathbf{u}}_i^{(1)})^\mathrm{T} \\ \vdots \\ (\tilde{\mathbf{u}}_i^{(p)})^\mathrm{T} \\ \vdots \\ (\tilde{\mathbf{u}}_i^{(M)})^\mathrm{T} \end{bmatrix} \right) \mathbf{C} \left( \mathbf{e}_k \otimes (\tilde{\mathbf{u}}_i^{(1)}, \dots, \tilde{\mathbf{u}}_i^{(q)}, \dots, \tilde{\mathbf{u}}_i^{(M)}) \right) \\ = \left[ \begin{bmatrix} \mathbf{e}_i^H \otimes (\tilde{\mathbf{u}}_i^{(1)})^\mathrm{T} \\ \vdots \\ \mathbf{e}_i^H \otimes (\tilde{\mathbf{u}}_i^{(p)})^\mathrm{T} \\ \vdots \\ \mathbf{e}_i^H \otimes (\tilde{\mathbf{u}}_i^{(M)})^\mathrm{T} \end{bmatrix} \right] \mathbf{C} (\mathbf{e}_k \otimes \tilde{\mathbf{u}}_i^{(1)}, \dots, \mathbf{e}_k \otimes \tilde{\mathbf{u}}_i^{(q)}, \dots, \mathbf{e}_k \otimes \tilde{\mathbf{u}}_i^{(M)}) $$

which produces an $\mathbf{M} \times \mathbf{M}$ array with scalar elements
$$ (e_i^H \otimes (\bar{u}_i^{(p)})^T) C (e_k \otimes \bar{u}_i^{(q)}) $$

in the $(p, q)$ position for $p, q = 1, 2, ..., M$. However, in light of the diagonal structure of each $\Psi_i$, only the diagonal elements survive in this expansion. That is,

$$ \begin{aligned} (e_i^H \otimes (\bar{u}_i^{(p)})^T) C (e_k \otimes \bar{u}_i^{(q)}) &= \begin{cases} \lambda_i^{(p)} \delta_{ik}, & p=q \\ 0, & \text{otherwise} \end{cases} \\ &= \lambda_i^{(p)} \delta_{ik} \delta_{pq} \end{aligned} $$

which completes the proof.

<figure><img src="image_43.png" /></figure>

If $i=k$ in Corollary 28, the orthogonality condition can be stated in terms of the eigenvectors $\tilde{\mathbf{q}}_i^{(p)} = \mathbf{e}_i \otimes \bar{\mathbf{u}}_i^{(p)}$. That is,

$$ (\tilde{\mathbf{q}}_i^{(p)})^H \mathbf{C} \tilde{\mathbf{q}}_i^{(q)} = \lambda_i^{(p)} \delta_{pq}, \quad i = 1, 2, \dots, N \quad (53) $$

For an ordinary circulant, each $\tilde{\mathbf{u}}_i^{(p)} = 1$ and Corollary 28 reduces to

$$ \mathbf{e}_i^H \mathbf{C} \mathbf{e}_k = \lambda_i \delta_{ik}, \quad i = 1, 2, \dots, N \quad (54) $$

which is the same result given by Corollary 18.

*Example 29.* Consider $\mathbf{C} = \text{circ}(4, -1, 0, -1) \in \mathcal{C}_4$ from Examples 15, 17, and 24, where it is shown that $\mathbf{e}_2 = \frac{1}{2}(1, j, -1, -j)^T$ is an eigenvector of $\mathbf{C}$ corresponding to the eigenvalue $\lambda_2 = 4$. Thus, the product

$$ \begin{aligned} \mathbf{e}_2^H \mathbf{C} \mathbf{e}_2 &= \frac{1}{2} [1 \ -j \ -1 \ j] \begin{bmatrix} 4 & -1 & 0 & -1 \\ -1 & 4 & -1 & 0 \\ 0 & -1 & 4 & -1 \\ -1 & 0 & -1 & 4 \end{bmatrix} \frac{1}{2} \begin{bmatrix} 1 \\ j \\ -1 \\ -j \end{bmatrix} \\ &= \frac{1}{4} [1 \ -j \ -1 \ j] (4, 4j, -4, -4j)^T \\ &= \frac{1}{4} (4 + 4 + 4 + 4) \\ &= 4 \end{aligned} $$

is numerically equal to $\lambda_2$ according to Eq. (54). However, the product

$$ \begin{aligned} \mathbf{e}_4^H \mathbf{C} \mathbf{e}_2 &= \frac{1}{4} [1 \ j \ -1 \ -j] (4, 4j, -4, -4j)^T \\ &= \frac{1}{4} (4 - 4 + 4 - 4) \\ &= 0 \end{aligned} $$

vanishes because $i \neq k$.

<figure><img src="image_44.png" /></figure>

*Example 30.* Consider $\mathbf{C} = \text{circ}(\mathbf{A}, \mathbf{B}, \mathbf{0}, \mathbf{B}) \in \mathcal{BC}_{2,4}$ from Examples 6, 18, 19, 20, and 25, where it is shown that

$$ \begin{aligned} \tilde{\mathbf{q}}_3^{(2)} &= \frac{1}{\sqrt{2}} \mathbf{q}_3^{(2)} \\ &= \frac{1}{2\sqrt{2}} (-1, 1, 1, -1, -1, 1, 1, -1)^T \end{aligned} $$

is an orthonormal eigenvector of $\mathbf{C}$ corresponding to the eigenvalue $\lambda_3^{(2)} = 5$. Because the generating matrices $\mathbf{A}, \mathbf{B}, \mathbf{0}, \mathbf{B}$ are symmetric (see Example 6), Corollary 28 guarantees that each $\tilde{\mathbf{q}}_i^{(p)} = \mathbf{e}_i \otimes \bar{\mathbf{u}}_i^{(p)}$ is mutually orthogonal with respect to $\mathbf{C}$. For example, it follows from Eq. (53) that

$$ \begin{aligned} \mathbf{q}_3^{(2)H} \mathbf{C} \mathbf{q}_3^{(2)} &= \frac{1}{2\sqrt{2}} \begin{bmatrix} -1 & 1 & 1 & -1 & 1 & 1 & -1 \end{bmatrix} \\ & \quad \times \begin{bmatrix} 2 & -1 & -1 & 0 & 0 & 0 & -1 & 0 \\ -1 & 2 & 0 & -1 & 0 & 0 & 0 & -1 \\ -1 & 0 & 2 & -1 & -1 & 0 & 0 & 0 \\ 0 & -1 & -1 & 2 & 0 & -1 & 0 & 0 \\ 0 & 0 & -1 & 0 & 2 & -1 & -1 & 0 \\ 0 & 0 & 0 & -1 & -1 & 2 & 0 & -1 \\ -1 & 0 & 0 & 0 & -1 & 0 & 2 & -1 \\ 0 & -1 & 0 & 0 & 0 & -1 & -1 & 2 \end{bmatrix} \\ & \quad \times \frac{1}{2\sqrt{2}} \begin{bmatrix} -1 \\ 1 \\ 1 \\ -1 \\ -1 \\ 1 \\ 1 \\ -1 \\ 1 \\ -1 \end{bmatrix} \\ &= \frac{1}{8} \begin{bmatrix} -1 & 1 & 1 & -1 & -1 & 1 & 1 & -1 \end{bmatrix} \\ & \quad \times (-5, 5, 5, -5, -5, 5, 5, -5)^T \\ &= 5 \end{aligned} $$

which is numerically equal to the eigenvalue $\lambda_3^{(2)}$. However, the matrix product

$$ \begin{aligned} (\mathbf{e}_3 \otimes \mathbf{u}_3^{(1)})^H \mathbf{C} (\mathbf{e}_3 \otimes \mathbf{u}_3^{(2)}) &= (\mathbf{e}_3^H \otimes (\mathbf{u}_3^{(1)})^H) \mathbf{C} (\mathbf{e}_3 \otimes \mathbf{u}_3^{(2)}) \\ &= (\mathbf{e}_3^H \otimes (\mathbf{u}_3^{(1)})^T) \mathbf{C} (\mathbf{e}_3 \otimes \mathbf{u}_3^{(2)}) \\ &= \frac{1}{2\sqrt{2}} [1 \ 1 \ -1 \ -1 \ 1 \ 1 \ -1 \ -1] \mathbf{C} \\ & \quad \times \frac{1}{2\sqrt{2}} (-1, 1, 1, -1, -1, 1, 1, -1)^T \\ &= \frac{1}{8} [1 \ 1 \ -1 \ -1 \ 1 \ 1 \ -1 \ -1] \\ & \quad \times (-5, 5, 5, -5, -5, 5, 5, -5)^T \\ &= 0 \end{aligned} $$

vanishes because $\delta_{pq} = 0$ ($p \neq q$) in Corollary 28. Similarly,

$$ \begin{aligned} (\mathbf{e}_2 \otimes \mathbf{u}_3^{(2)})^H \mathbf{C} (\mathbf{e}_3 \otimes \mathbf{u}_3^{(2)}) &= \frac{1}{2\sqrt{2}} \begin{bmatrix} -1 & 1 & -j & j & 1 & -1 & j & -j \end{bmatrix} \mathbf{C} \\ & \quad \times \frac{1}{2\sqrt{2}} (-1, 1, 1, -1, -1, 1, 1, -1)^T \\ &= \frac{1}{8} \begin{bmatrix} -1 & 1 & -j & j & 1 & -1 & j & -j \end{bmatrix} \\ & \quad \times (-5, 5, 5, -5, -5, 5, 5, -5)^T \\ &= 0 \end{aligned} $$

because $\delta_{ik} = 0$ ($i \neq k$).
If instead we set $\mathbf{A}=4$ and $\mathbf{B}=-1$ such that $\mathbf{C} \in \mathcal{C}_4$ is an ordinary circulant, we recover the orthogonality condition in Example 15 for $i=3$.

The orthogonality conditions used in Example 30 for the special case of an ordinary circulant does not require that the circulant structure is symmetric (i.e., $\mathbf{C}$ need not be contained in $\mathcal{C}_N$). The reader can verify that Eq. (54) also holds for nonsymmetric matrices $\mathbf{C} \in \mathcal{C}_N$ by inspection of Example 16.

The fundamental orthogonality relationship given by Corollary 28 also holds for $\mathbf{M}, \mathbf{K} \in \mathcal{C}_{M,N}$ systems with symmetric generating matrices, as the following corollary shows.

Corollary 29. Let $\mathbf{M}, \mathbf{K} \in \mathcal{C}_{M,N}$ be block circulant with symmetric generating matrices, $\mathbf{e}_i$ be the $i$th column of the $N \times N$ Fourier matrix $\mathbf{E}_N$, and $\mathbf{u}_i^{(p)}$ be the $p$th $M \times 1$ reduced-order orthonormal eigenvector corresponding to the $i$th system $(\mathbf{M}_i, \mathbf{K}_i)$ defined by Eq. (46). Then

$$ \left. \begin{aligned} (\mathbf{e}_i^H \otimes (\mathbf{u}_i^{(p)})^T) \mathbf{M} (\mathbf{e}_i \otimes \mathbf{u}_i^{(p)}) &= \delta_{ik} \delta_{pq} \\ (\mathbf{e}_i^H \otimes (\mathbf{u}_i^{(p)})^T) \mathbf{K} (\mathbf{e}_i \otimes \mathbf{u}_i^{(p)}) &= \lambda_i^{(p)} \delta_{ik} \delta_{pq} \end{aligned} \right\} $$

for $i, k = 1, 2, \dots, N$ and $p, q = 1, 2, \dots, M$, where $\lambda_i^{(p)}$ is the eigenvalue associated with $\mathbf{u}_i^{(p)}$ and $\delta_{ik}$ is the Kronecker delta. $\square$

In practice, of course, the $M \times 1$ reduced-order eigenvectors $\mathbf{u}_i^{(p)}$ are not known a priori. Instead, Theorem 10 is used in Sec. 3 to decouple the $NM$-DOF system equations into a set of $N$ reduced-order $M$-DOF standard vibratory problems, from which the system eigenvalues (natural frequencies) and eigenvectors (normal modes) are extracted.

### 3 Example Applications

In this section we apply the results developed in Sec. 2 to vibration models of systems with cyclic symmetry. For each model considered, we begin by formulating the equations of motion (EOM) and then use the theory of circulants to diagonalize or block diagonalize the governing equations. This is achieved by a coordinate transformation that exploits the special relationship between circulant matrices and the Fourier matrix. The process also shows how external forces are projected on the resulting block diagonal EOM. The special case of traveling wave engine order excitation is also presented in some detail because it appears in many relevant applications of rotating machinery.

Three examples are presented. The first example (Sec. 3.1) considers the structure of the EOM for a general cyclic system with $N$ sectors, $M$ DOFs per sector, and arbitrary excitation. It is shown how to block diagonalize the system equations via a modal transformation involving the Fourier matrix, which results in $NM$-DOF reduced-order vibratory systems. If engine order excitation is assumed (Sec. 3.2), it is shown that the steady-state forced response of the $NM$-DOF system can be obtained from a single $M$-DOF harmonically forced, reduced-order system in modal space. The mathematical and physical details of engine order excitation are discussed, including its temporal and spatial duality. The second example (Sec. 3.3) considers a cyclic system with one DOF per sector under engine order excitation. This system is fully diagonalized by the Fourier matrix. The example is presented in detail, showing the nature of the natural modes and frequencies, and the resonant response to excitation of various engine orders. The third example (Sec. 3.4) has two DOFs per sector and demonstrates the block diagonalization process for a perfectly cyclic system with specified sector models, as opposed to the general sector models in the first example. In each sector, one DOF is due to flexure, and thus has a constant frequency, while the other DOF is a centrifugally driven pendulum whose frequency is proportional to the rotor speed. The coupling between these DOFs leads to some interesting behavior in both the free and forced vibration of the system, which is discussed in Refs. [21,22] and [92–95]. More importantly, this example shows the process of handling multiple

DOFs per sector, which easily extends from two to $M$ DOFs per sector using the theory presented in Sec. 2.

#### 3.1 General Cyclic System

3.1.1 Equations of Motion. Consider the general cyclic vibratory system shown schematically in Fig. 4, which consists of $N$ sectors with coupling (elastic and damping) to adjacent neighbors. The topology diagram only indicates nearest-neighbor coupling, but more general coupling is admissible as long as the cyclic symmetry is preserved. If there are $M$ DOFs per sector, each $M \times 1$ vector $\mathbf{q}_i$ describes the dynamics of the $i$th sector for $i \in \{1, 2, \dots, N\} \equiv \mathcal{N}$. Then the linear EOM takes the form

$$ \mathbf{M}\ddot{\mathbf{q}} + \mathbf{C}\dot{\mathbf{q}} + \mathbf{K}\mathbf{q} = \hat{\mathbf{f}} \quad (55) $$

where $\mathbf{q} = (\mathbf{q}_1, \mathbf{q}_2, \dots, \mathbf{q}_N)^T$ is a $NM \times 1$ configuration vector, the system matrices are block circulant with $M \times M$ blocks, and overdots denote differentiation with respect to time. If the $M \times 1$ vector $\mathbf{f}_i$ denotes the component of forcing on the $i$th sector, then $\hat{\mathbf{f}} = (\mathbf{f}_1, \mathbf{f}_2, \dots, \mathbf{f}_N)^T$ is a $NM \times 1$ general forcing vector. The $NM \times NM$ system mass, damping, and stiffness matrices are of the form

$$ \left. \begin{aligned} \mathbf{M} &= \operatorname{circ}(\mathbf{M}_1, \mathbf{M}_2, \dots, \mathbf{M}_N) \in \mathcal{C}_{M,N} \\ \mathbf{C} &= \operatorname{circ}(\mathbf{C}_1, \mathbf{C}_2, \dots, \mathbf{C}_N) \in \mathcal{C}_{M,N} \\ \mathbf{K} &= \operatorname{circ}(\mathbf{K}_1, \mathbf{K}_2, \dots, \mathbf{K}_N) \in \mathcal{C}_{M,N} \end{aligned} \right\} \quad (56) $$

where the generating matrices $\mathbf{M}_i, \mathbf{C}_i$, and $\mathbf{K}_i$ depend on the $M \times M$ sector mass, damping, and stiffness matrices and the intersector coupling (stiffness and damping). Equation (55) is a general model for any linear, lumped-parameter, conservative, nongyroscopic, cyclic vibratory system with $N$ sectors and $M$ DOFs per sector. For example, a linearized lumped-parameter model of a bladed disk assembly under engine order excitation is captured by Eq. (55), where $N$ is the number of blades, $M$ is the number of DOFs per blade, $\mathbf{f}$ has the special properties described in Sec. 3.2, and the system matrices depend on the structural details of each blade (i.e., sector) and its connectivity to adjacent blades and rotating hub.

3.1.2 Modal Transformation. Of course, one can apply standard techniques [99] to investigate the free and forced response of the model given by Eq. (55). However, this requires solving an $NM \times NM$ eigenvalue problem to determine the modal properties, or inversion of an $NM \times NM$ impedance matrix to determine the response to harmonic excitation. Such an approach may be prohibitive or computationally expensive for practical models with

<figure><img src="image_45.png" /><figcaption>Fig. 4 Topology diagram of a general cyclic system</figcaption></figure>
many sectors and many DOFs per sector, nor does it highlight or exploit the underlying features of the cyclic system. It is precisely these special features that are brought to light by the properties of the circulants or block circulants that describe the system.

Solving for the system response is significantly facilitated by a modal transformation that exploits the cyclic symmetry among the N sectors. Specifically, it is straightforward to block decouple the EOM into a set of N systems, each with M DOFs. To this end, we introduce the change of coordinates

$$ \mathbf{q} = (\mathbf{E}_N \otimes \mathbf{I}_M)\mathbf{u} \quad (57) $$

where $\mathbf{u} = (\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_N)^\mathrm{T}$ is a $NM \times 1$ vector of modal coordinates. Each $\mathbf{u}_i$ is $M \times 1$ and describes the sector dynamics in modal space, where the EOM are block decoupled (as described below). In this formulation the physical coordinates $\mathbf{q}$ are expressed in terms of the modal coordinates $\mathbf{u}_i$ and the Fourier elements of length N, which accounts for the overall cyclic nature of the EOM. Substituting Eq. (57) into Eq. (55) and multiplying from the left by $(\mathbf{E}_N \otimes \mathbf{I}_M)^\mathrm{H} = (\mathbf{E}_N^\mathrm{H} \otimes \mathbf{I}_M)$ yields

$$ \begin{aligned} & (\mathbf{E}_N^\mathrm{H} \otimes \mathbf{I}_M)\mathbf{M}(\mathbf{E}_N \otimes \mathbf{I}_M)\ddot{\mathbf{u}} + (\mathbf{E}_N^\mathrm{H} \otimes \mathbf{I}_M)\mathbf{C}(\mathbf{E}_N \otimes \mathbf{I}_M)\dot{\mathbf{u}} \\ & \quad + (\mathbf{E}_N^\mathrm{H} \otimes \mathbf{I}_M)\mathbf{K}(\mathbf{E}_N \otimes \mathbf{I}_M)\mathbf{u} \\ & = (\mathbf{E}_N^\mathrm{H} \otimes \mathbf{I}_M)\hat{\mathbf{f}} \end{aligned} $$

or

$$ \begin{bmatrix} \tilde{\mathbf{M}}_1 & & & & & & \\ & \ddots & & & & & \\ & & \tilde{\mathbf{M}}_N & & & & \\ & & & \tilde{\mathbf{M}}_N & & & \\ & & & & \ddots & & \\ & & & & & \tilde{\mathbf{C}}_1 & \\ & & & & & & \tilde{\mathbf{C}}_2 & \\ & & & & & & & \ddots \\ & & & & & & & & \tilde{\mathbf{C}}_N & \\ & & & & & & & & & \tilde{\mathbf{u}}_1 \\ & & & & & & & & \tilde{\mathbf{u}}_2 \\ & & & & & & & & & \ddots \\ & & & & & & & & & & \tilde{\mathbf{u}}_N \end{bmatrix} + \begin{bmatrix} \tilde{\mathbf{K}}_1 & & & & & & \\ & \ddots & & & & & \\ & & \tilde{\mathbf{K}}_2 & & & & \\ & & & \tilde{\mathbf{K}}_N & & & \\ & & & & \ddots & & \\ & & & & & \tilde{\mathbf{K}}_1 & \\ & & & & & & \tilde{\mathbf{K}}_2 & \\ & & & & & & & \ddots \\ & & & & & & & & \tilde{\mathbf{K}}_N & \end{bmatrix} \begin{bmatrix} \mathbf{u}_1 \\ \mathbf{u}_2 \\ \vdots \\ \mathbf{u}_N \end{bmatrix} = \begin{bmatrix} (\mathbf{e}_1^\mathrm{H} \otimes \mathbf{I}_M)\hat{\mathbf{f}} \\ (\mathbf{e}_2^\mathrm{H} \otimes \mathbf{I}_M)\hat{\mathbf{f}} \\ \vdots \\ (\mathbf{e}_N^\mathrm{H} \otimes \mathbf{I}_M)\hat{\mathbf{f}} \end{bmatrix} \quad (58) $$

The block diagonal structure on the left-hand side of Eq. (58) follows from Theorem 10, where the $M \times M$ modal mass, damping, and stiffness matrices associated with the pth mode follow from Eq. (23) and are given by

$$ \left. \begin{aligned} \tilde{\mathbf{M}}_p &= \sum_{k=1}^{N} \mathbf{M}_k w_N^{(k-1)(p-1)} \\ \tilde{\mathbf{C}}_p &= \sum_{k=1}^{N} \mathbf{C}_k w_N^{(k-1)(p-1)} \\ \tilde{\mathbf{K}}_p &= \sum_{k=1}^{N} \mathbf{K}_k w_N^{(k-1)(p-1)} \end{aligned} \right\} , \quad p \in \mathcal{N} \quad (59) $$

The forcing terms on the right-hand side of Eq. (58) follow from the decomposition

$$ \begin{aligned} (\mathbf{E}_N^\mathrm{H} \otimes \mathbf{I}_M)\hat{\mathbf{f}} &= ((\mathbf{e}_1^\mathrm{H}, \mathbf{e}_2^\mathrm{H}, \dots, \mathbf{e}_N^\mathrm{H})^\mathrm{T} \otimes \mathbf{I}_M)\hat{\mathbf{f}} \\ &= (\mathbf{e}_1^\mathrm{H} \otimes \mathbf{I}_M, \mathbf{e}_2^\mathrm{H} \otimes \mathbf{I}_M, \dots, \mathbf{e}_N^\mathrm{H} \otimes \mathbf{I}_M)^\mathrm{T}\hat{\mathbf{f}} \\ &= \begin{bmatrix} (\mathbf{e}_1^\mathrm{H} \otimes \mathbf{I}_M)\hat{\mathbf{f}} \\ (\mathbf{e}_2^\mathrm{H} \otimes \mathbf{I}_M)\hat{\mathbf{f}} \\ \vdots \\ (\mathbf{e}_N^\mathrm{H} \otimes \mathbf{I}_M)\hat{\mathbf{f}} \end{bmatrix} \end{aligned} \quad (60) $$

and make no assumptions on the nature of the applied forcing. Thus, the solution to the NM-DOF matrix EOM given by Eq. (58) reduces to solving NM-DOF uncoupled systems

$$ \tilde{\mathbf{M}}_p \ddot{\mathbf{u}}_p + \tilde{\mathbf{C}}_p \dot{\mathbf{u}}_p + \tilde{\mathbf{K}}_p \mathbf{u}_p = (\mathbf{e}_p^\mathrm{H} \otimes \mathbf{I}_M)\hat{\mathbf{f}}, \quad p \in \mathcal{N} \quad (61) $$

for the modal solutions $\mathbf{u}_p$. These N reduced-order EOMs of order M offer a substantial computational savings compared to the full NM-DOF system defined by Eq. (55). The reduced equations can be solved directly or with standard modal analysis by solving a set of N generalized eigenvalue problems, each of order M, from which one can form the global eigenvectors of the system. Specifically, solving the N eigenvalue problems associated with Eq. (61) yields a set of normalized $M \times M$ modal matrices $\mathbf{U}_p$, which define a change to reduced modal coordinates via $\mathbf{u}_p = \mathbf{U}_p s_p$. The $s_p$ are modes that define the behavior of the internal sector dynamics and account for the manner in which these are coupled to each other in a given Fourier mode of the overall system. The EOM for the $s_i$ form a set of M uncoupled equations, and these are related to the physical coordinates of the original system by $\mathbf{q} = (\mathbf{E}_N \otimes \mathbf{I}_M)\mathbf{u}$ where $\mathbf{u} = (\mathbf{U}_1 \mathbf{s}_1, \mathbf{U}_2 \mathbf{s}_2, \dots, \mathbf{U}_N \mathbf{s}_N)^\mathrm{T}$. This process is general, and it allows one to decouple the full EOM in two steps, one which accounts for the global cyclic nature of the system, and the other which accounts for the details of the sector model.

Equation (61) can be simplified even further if the system is subjected to the so-called *engine order excitation*. The mathematics and physics of this type of excitation are developed in the next section, which closes with a treatment of the general cyclic system governed by Eq. (61) under engine order excitation.

## 3.2 Engine Order Excitation.
Traveling wave engine order excitation arises in rotating machinery and is a primary source of forced vibration response in bladed disk assemblies [11,111]. A mathematical model of this common form of excitation is developed in Sec. 3.2.1 and its traveling wave characteristics are described in Sec. 3.2.2. While this material is known, the discussion that follows is unique because it provides physical insights and a systematic explanation of the temporal and spatial duality of engine order excitation. The general cyclic system of Sec. 3.1 is reconsidered in Sec. 3.2.3 under engine order excitation, where it is shown that the steady-state forced response of the NM-DOF system reduces to that of a single sector in modal space.

### 3.2.1 Mathematical Model.
Ideally, the steady axial gas pressure in a jet engine might vary with radius but is otherwise uniform in the circumferential direction, thus resulting in an identical force field on each blade in a particular fan, compressor, or turbine within the engine. In practice, however, flow entering an engine inlet invariably meets static obstructions, such as struts, stator vanes, etc., in addition to rotating bladed disk assemblies in its path to the exhaust. Even in steady operation, therefore, the flow slightly upstream of these bladed assemblies is nonuniform in pressure, temperature, and so on. This results in a static pressure (effective force) field on the blades that vary circumferentially, a notional example of which is shown in Fig. 5.

Consider, for example, an engine in steady operation with n evenly spaced struts slightly upstream (or downstream) of a bladed assembly. As explained in Ref. [3], these obstructions produce a circumferential variation upon the mean axial gas pressure that is essentially proportional to $\cos n\theta$, where $\theta$ is an angular position. Thus, a blade rotating through this static pressure field experiences a force proportional to $\cos n\Omega t$, where $\Omega$ is the constant angular speed of the bladed disk assembly and t is time. An adjacent blade experiences the same force, but at a constant fraction of time later. This type of excitation is defined as *engine order* (e.o.) *excitation* and n is said to be the *order* of the excitation.

To be more precise, the axial gas pressure of a steady flow through a jet engine may be described by the function $p(\theta) = p(\theta + 2\pi)$, where $\theta$ is an angular coordinate measured
<figure><img src="image_46.png" /><figcaption>Fig. 5 The axial gas pressure $p(\theta)$: ideal and (notional) actual conditions</figcaption></figure>

relative to a fixed origin on the machine. That is, the pressure field is rotationally periodic and can therefore be expanded in a Fourier series with terms of the form $p_o \cos n\theta$. If the angular position of the ith blade relative to the same origin is defined by

$$ \theta_i(t) = \Omega t + \frac{2\pi}{N}(i - 1), \quad i \in \mathcal{N} $$

where N is the total number of blades and $\mathcal{N} = \{1, 2, ..., N\}$ is the set of blade, or sector numbers, it follows that the total effective force exerted on blade i due to the nth harmonic of the pressure field $p(\theta)$ is captured by

$$ F \cos \left( n\Omega t + 2\pi \frac{n}{N} (i-1) \right), \quad i \in \mathcal{N} \qquad (62) $$

Upon complexifying,

$$ F_i(t) = F e^{j\phi_i} e^{in\Omega t}, \quad i \in \mathcal{N} \qquad (63) $$

is a model for the nth predominant component of the excitation. Eq. (63) has period $T = 2\pi/n\Omega$, strength $F$, and is said to have angular speed $\Omega$. The so-called interblade phase angle is defined by

$$ \phi_i = \phi_i^{(n)} = 2\pi \frac{n}{N} (i-1) = n\phi_i, \quad i \in \mathcal{N} \qquad (64) $$

where $n \in \mathbb{Z}_+$ and $\phi_i$ is the angle subtended from blade 1 to blade i and is defined by Eq. (16). Equation (63) is defined as nth engine order, or traveling wave excitation. The traveling wave characteristics of this type of excitation are considered next.

### 3.2.2 Traveling Wave Characteristics.
The function defined by Eq. (63) is continuous in time and discretized in space via the index i. This gives rise to two interpretations of engine order excitation relative to the rotating hub, one discrete and the other continuous. These can be visualized in Fig. 6, which shows a dissection of the excitation amplitudes along time and sector axes. In the first and usual sense, Eq. (63) is a discrete temporal variation of the dynamic loading applied to individual blades. That is, under an engine order n excitation, each sector is harmonically forced with strength F and frequency $n\Omega$, but with a fixed phase difference relative to its nearest neighbors. Physically, one can think of this as placing N different observers at the discrete sectors and having the ith observer record the excitation strength applied to sector i as a function of time. Their recorded time traces would resemble those shown in Fig. 6(a). In the second and more general sense, Eq. (63) can be viewed as a continuous spatial variation of the excitation strength relative to the rotating hub (along the sector axis) that evolves with increasing time, i.e., it is a propagating

waveform, or traveling wave. If a single observer was placed on the rotating hub and recorded the strength of this traveling wave as a function of i (taken here to be continuous), it would resemble the curve shown in Fig. 6(b). In this context, the instantaneous loading applied to individual blades is obtained by essentially “sampling” the continuous traveling wave at each sector $i \in \mathcal{N}$ and, as time evolves, these sampled points define N time profiles of the force amplitudes, which is equivalent to the discrete temporal interpretation described above. However, the latter interpretation illuminates some important traveling wave characteristics of the engine order excitation that are otherwise difficult to explain, and in what follows these are systematically described.

To explain the traveling wave mathematically, it is convenient to define the function

$$ \Phi_k(\chi) = \cos\left(\frac{2\pi(k-1)}{N}\chi\right) = \cos(\phi_k\chi) \qquad (65) $$

which is a harmonic waveform with wavelength $2\pi/\phi_k$. Then for $i \in \mathcal{N}$ and noting that $\phi_i = \phi_{n+1}(i-1)$, Eq. (63) can be written in real form as

$$ \begin{aligned} F_i(t) &= F \cos(\phi_{n+1}(i-1) + n\Omega t) \\ &= F \cos\left(\phi_{n+1}\left(i - 1 + \frac{n\Omega}{\phi_{n+1}}t\right)\right) \qquad (66) \\ &= F\Phi_{n+1}(i - 1 + Ct) \end{aligned} $$

which is a harmonic function with a wavelength of $2\pi/\phi_{n+1} = N/n$ ($\phi_{n+1}$ is the wave number) and angular frequency $n\Omega$. Equation (66) shows that engine order excitation is a TW in the negative i-direction (descending blade number) with speed $C = n\Omega/\phi_{n+1} = N\Omega/2\pi$, measured in sectors per second. An example plot of this continuous BTW is shown in Fig. 6(b) and, as described above, the applied loads can be obtained from this figure by continuously “sampling” the waveform at the discrete sector numbers as time evolves. Then the engine order excitation applied to the individual blades consists of a wave composed of these N discrete points, examples of which are shown in Figs. 7(a)–7(d). Interestingly, this gives rise to discrete SW or even FTW applied dynamic loads (depending on the value of n relative to N), even though Eq. (66) is strictly a BTW relative to the rotating hub. These additional possibilities arise due to aliasing of the “sampled points” just as it occurs in elementary signal processing theory [112,113]. Before characterizing the traveling and standing waveforms, it is shown that one need only consider engine orders $n \in \mathcal{N}$.

The traveling wave nature of the discrete applied loads (i.e., SW, BTW, or FTW) depends only on the value of n relative to N. To see this, let

$$ \bar{n} = n \mod N \in \mathcal{N}, \quad n \in \mathbb{Z}_+ \qquad (67) $$

and assume $n = \bar{n} + mN$ for some integer m. Then

$$ \Phi_{\bar{n}+mN+1}(\chi) = \Phi_{\bar{n}+1}(\chi) $$

That is, if $n = \bar{n}$ corresponds to a SW, BTW, or FTW, then so does $\bar{n} + mN$ for any $m \in \mathbb{Z}_+$. In this sense, the traveling wave nature of the applied dynamic loads is seen to alias relative to N. These features are characterized for engine orders

$$ n \in \mathcal{N} = \mathcal{N}_{\text{BTW}}^{\text{O.E}} \cup \mathcal{N}_{\text{FTW}}^{\text{O.E}} \cup \mathcal{N}_{\text{SW}}^{\text{O.E}} $$

where it is understood that the results apply to any $n > N$ simply by taking n modulo N, as appropriate. The subsets $\mathcal{N}_{\text{BTW}}^{\text{O.E}}$, $\mathcal{N}_{\text{FTW}}^{\text{O.E}}$, and $\mathcal{N}_{\text{SW}}^{\text{O.E}}$ are defined in Table 4 and discussed below.

For the special case of $n=N$ the rotating blades become entrained with the excitation because $\phi_i^{(N)} = 2\pi n(i-1)$ with
<figure><img src="image_47.png" /><figcaption>Fig. 6 Example illustration of the discrete temporal and continuous spatial variations of the traveling wave excitation defined by Eq. (63) in real form: (a) the discrete dynamic loads with amplitude F and period T = 2π/nΩ applied to each sector; and (b) the continuous BTW excitation with wavelength N/n and speed C = NΩ/2π relative to the rotating hub</figcaption></figure>

i, n ∈ Z+, and hence each is forced with the same strength and phase. As illustrated in Fig. 7(d), this is a SW excitation where each blade is harmonically forced according to $F_i(t) = F \cos n\Omega t$. Entrainment also occurs when $n=N/2$ if N is even, in which case $\phi_i^{(N/2)} = \pi n(i-1)$, where $(i-1)$ is odd (resp. even) for even (resp. odd) sector numbers $i \in N$. Accordingly, all blades with odd sector numbers are driven by $F_i(t) = F \cos n\Omega t$, as are the blades with even sector numbers, but with a 180-deg phase shift. As shown in Fig. 7(b), this amounts to the same standing wave excitation as the $n=N$ case, except for a phase reversal in the excitation among adjacent blades. The engine orders corresponding to SW excitations for odd and even N are denoted by the sets $N_{SW}^{O,E} \subset N$, and all other values of $n \in N$ correspond to traveling waves. Engine orders $n \in N_{BTW}^{O,E}$ (resp. $n \in N_{FTW}^{O,E}$) correspond to BTW (resp. FTW) excitation, an example of which is shown in Fig. 7(a) (resp. Fig. 7(c)), where $N_{BTW}^{O,E}$ and $N_{FTW}^{O,E}$ are also defined in Table 4. These sets can be visualized in Figs. 7(i) and 7(ii) for odd and even N, respectively.

The manner in which cyclic systems respond to this type of excitation is considered in the examples that follow. In Sec. 3.2.3, we prove the most important result related to the forced response of cyclic systems, namely, that in the case of perfect symmetry each engine order excites only a single mode. This is clear mathematically and will be explored with more physical insight in the examples presented in Secs. 3.3 and 3.4.

### 3.2.3 Forced Response of a General Cyclic System Under Engine Order Excitation.
The general cyclic system governed by Eq. (55) is reconsidered here under engine order excitation. Using the notation of Sec. 3.1, a model for the nth engine order excitation is

$$ \mathbf{f}_i = \mathbf{f} e^{in\phi_i} e^{in\Omega t}, \quad i \in \mathcal{N} \qquad (68) $$

where $\mathbf{f}$ is a constant $M \times M$ vector of sector force amplitudes, $t$ is time, $\phi_i$ is the angle subtended from sector 1 to sector i and is defined by Eq. (16), $n$ is the order of the excitation, $n\Omega$ is the angular frequency of the excitation, and $\Omega$ is the angular speed of the system relative to the excitation. Under this type of excitation, the system forcing vector becomes

$$ \hat{\mathbf{f}} = \begin{bmatrix} \mathbf{f}_1 \\ \mathbf{f}_2 \\ \vdots \\ \mathbf{f}_N \end{bmatrix} = \begin{bmatrix} \mathbf{f} e^{in\phi_1} e^{in\Omega t} \\ \mathbf{f} e^{in\phi_2} e^{in\Omega t} \\ \vdots \\ \mathbf{f} e^{in\phi_N} e^{in\Omega t} \end{bmatrix} = \mathbf{f}_0 \otimes \mathbf{f} e^{in\Omega t} $$

where
<figure><img src="image_48.png" /><figcaption>Fig. 7 Engine orders n mod N corresponding to BTW, FTW and SW applied dynamic loading for (i) odd N and (ii) even N (see also Table 4); example plots of applied dynamic loading (represented by the dots) for a model with N = 10 sectors and with (a) n = 1 (BTW), (b) n = 5 (SW), (c) n = 9 (FTW), and (d) n = 10 (SW). The BTW engine order excitation is represented by the solid lines.</figcaption></figure>

<table><caption>Table 4 Sets of engine orders n(mod N) ∈ N corresponding to BTW, FTW, SW dynamics loads applied to the blades for odd and even N. These can be visualized in Figs. 7(i) and 7(ii).</caption><thead><tr><th>N</th><th>Type</th><th>Set</th></tr></thead><tbody><tr><td rowspan="3">Odd</td><td>BTW</td><td>N<sup>O</sup><sub>BTW</sub> = {n ∈ Z<sub>+</sub>: 1 ≤ n ≤ (N − 1)/2}</td></tr><tr><td>FTW</td><td>N<sup>O</sup><sub>FTW</sub> = {n ∈ Z<sub>+</sub>: (N + 1)/2 ≤ n ≤ N − 1}</td></tr><tr><td>SW</td><td>N<sup>O</sup><sub>SW</sub> = {N}</td></tr><tr><td rowspan="3">Even</td><td>BTW</td><td>N<sup>E</sup><sub>BTW</sub> = {n ∈ Z<sub>+</sub>: 1 ≤ n ≤ (N − 2)/2}</td></tr><tr><td>FTW</td><td>N<sup>E</sup><sub>FTW</sub> = {n ∈ Z<sub>+</sub>: (N + 2)/2 ≤ n ≤ N − 1}</td></tr><tr><td>SW</td><td>N<sup>E</sup><sub>SW</sub> = {N/2, N}</td></tr></tbody></table>

$$ 
\begin{aligned}
\mathbf{f}_0 &= (e^{j n \phi_1}, e^{j n \phi_2}, \dots, e^{j n \phi_N})^\mathrm{T} \\
&= (e^{j \phi_1}, e^{j \phi_2}, \dots, e^{j \phi_N})^\mathrm{T}
\end{aligned}
\qquad (69) $$

is a vector of constant intersector phase angles $\phi_i = n\phi_i$. Thus, the pth modal forcing term on the right-hand side of Eq. (61) reduces to

$$ 
\begin{aligned}
(\mathbf{e}_p^H \otimes \mathbf{I}_M) \hat{\mathbf{f}} &= (\mathbf{e}_p^H \otimes \mathbf{I}_M)(\mathbf{f}_0 \otimes \mathbf{f}) e^{j n \Omega t} \\
&= (\mathbf{e}_p^H \mathbf{f}_0) \otimes (\mathbf{I}_M \mathbf{f}) e^{j n \Omega t} \\
&= (\mathbf{e}_p^H \mathbf{f}_0) \otimes \mathbf{f} e^{j n \Omega t}, \quad p \in \mathcal{N}
\end{aligned}
\qquad (70) $$

which is a direct product of the scalar product $\mathbf{e}_p^H \mathbf{f}_0$ with the nth order harmonic excitation $\mathbf{f} e^{j n \Omega t}$ imparted to each sector. This dissection of the modal forcing term highlights an orthogonality condition that is shared by all cyclic systems under engine order excitation. In particular,

$$ 
\begin{aligned}
\mathbf{e}_p^H \mathbf{f}_0 &= \frac{1}{\sqrt{N}} (e^{-j0 \cdot \phi_p}, e^{-j1 \cdot \phi_p}, \dots, e^{-j(N-1) \cdot \phi_p}) \\
&\quad \times (e^{j n \phi_1}, e^{j n \phi_2}, \dots, e^{j n \phi_N})^\mathrm{T} \\
&= \frac{1}{\sqrt{N}} \sum_{k=1}^N e^{-j(k-1) \cdot \phi_p} e^{j n \phi_k} \\
&= \frac{1}{\sqrt{N}} \sum_{k=1}^N e^{-j(k-1) \cdot \phi_p} e^{j n \phi_N} (k-1) \\
&= \frac{1}{\sqrt{N}} \sum_{k=1}^N w_N^{-(k-1)(p-1)} w_N^{n(k-1)} \\
&= \frac{1}{\sqrt{N}} \sum_{k=1}^N w_N^{(k-1)(n+1-p)} \\
&= \begin{cases} \sqrt{N}, & p = n+1 \\ 0, & \text{otherwise} \end{cases}
\end{aligned}
\qquad (71) $$

which follows from Lemma 2 and shows that the force vector $\mathbf{f}_0$ is mutually orthogonal to all but one of the modal vectors $\mathbf{e}_p$. This result is obtained more directly from Corollary 10 by observing that

$$ 
\begin{aligned}
\mathbf{f}_0 &= (e^{j n \phi_1}, e^{j n \phi_2}, \dots, e^{j n \phi_N})^\mathrm{T} \\
&= (e^{j 0 \cdot \phi_{n+1}}, e^{j 1 \cdot \phi_{n+1}}, \dots, e^{j (N-1) \cdot \phi_{n+1}})^\mathrm{T} \\
&= \sqrt{N} \mathbf{e}_{n+1}
\end{aligned}
$$

where $\mathbf{e}_{n+1}$ is the $(n+1)$th column of the Fourier matrix. It follows that

$$ 
\begin{aligned}
\mathbf{e}_p^H \mathbf{f}_0 &= \mathbf{e}_p^H \sqrt{N} \mathbf{e}_{n+1} \\
&= \sqrt{N} \mathbf{e}_p^H \mathbf{e}_{n+1} \\
&= \sqrt{N} \delta_{p(n+1)}
\end{aligned}
\qquad (72) $$

which is the same orthogonality condition given by Eq. (71). Thus, for $p \in \mathcal{N}$, the only excited mode is

$$ p = n \mod N + 1 \qquad (73) $$

for an engine order $n \in Z_+$ excitation. Then Eq. (70) becomes

$$ (\mathbf{e}_p^H \otimes \mathbf{I}_M) \hat{\mathbf{f}} = \begin{cases} \sqrt{N} \mathbf{f} e^{j n \Omega t}, & p = n+1 \\ 0, & \text{otherwise} \end{cases} \qquad (74) $$

and the forced response of the NM-DOF matrix EOM given by Eq. (58) reduces to solving a single, M-DOF system

$$ \tilde{\mathbf{M}}_{n+1} \ddot{\mathbf{u}}_{n+1} + \tilde{\mathbf{C}}_{n+1} \dot{\mathbf{u}}_{n+1} + \tilde{\mathbf{K}}_{n+1} \mathbf{u}_{n+1} = \sqrt{N} \mathbf{f} e^{j n \Omega t} \qquad (75) $$

in modal space. Assuming harmonic motion, the steady-state modal response is given by

$$ \mathbf{u}_{n+1}^{ss}(t) = \sqrt{N} \tilde{\mathbf{Z}}_{n+1} \mathbf{f} e^{j n \Omega t} \qquad (76) $$

where
$$ \tilde{Z}_{n+1} = \tilde{K}_{n+1} + jn\Omega\tilde{C}_{n+1} - (n\Omega)^2\tilde{M}_{n+1} $$

is the $(n+1)$th modal impedance matrix. All other steady-state modal responses are zero because only mode $p=n+1$ is excited. In light of the decomposition shown in Eq. (39), the forced response in physical coordinates follows from Eq. (57) and is given by

$$ \mathbf{q}^{ss}(t) = \mathbf{e}_{n+1} \otimes \mathbf{u}_{n+1}^{ss}(t) \quad (77) $$

where $\mathbf{e}_{n+1}$ is the $(n+1)$th column of the Fourier matrix and $\mathbf{u}_{n+1}^{ss}(t)$ is given by Eq. (76). Expanding Eq. (77) into its sector components yields

$$ \begin{bmatrix} \mathbf{q}_1^{ss}(t) \\ \mathbf{q}_2^{ss}(t) \\ \vdots \\ \mathbf{q}_i^{ss}(t) \\ \vdots \\ \mathbf{q}_N^{ss}(t) \end{bmatrix} = \frac{1}{\sqrt{N}} \begin{bmatrix} e^{j \cdot 0 \cdot \phi_{n+1}} \\ e^{j \cdot 1 \cdot \phi_{n+1}} \\ \vdots \\ e^{j \cdot (i-1) \cdot \phi_{n+1}} \\ \vdots \\ e^{j \cdot (N-1) \cdot \phi_{n+1}} \end{bmatrix} \otimes \sqrt{N} \tilde{Z}_{n+1} \mathbf{f} e^{jn\Omega t} \quad (78) $$

Thus, the steady-state forced response of the $i$th sector in physical coordinates is given by

$$ \begin{aligned} \mathbf{q}_i^{ss}(t) &= \frac{1}{\sqrt{N}} e^{j(i-1)\cdot\phi_{n+1}} \sqrt{N} \tilde{Z}_{n+1} \mathbf{f} e^{jn\Omega t} \\ &= \tilde{Z}_{n+1} \mathbf{f} e^{jn\phi_i} e^{jn\Omega t}, \quad i \in \mathcal{N} \end{aligned} \quad (79) $$

where $\phi_i = 2\pi(n/N)(i-1)$. The response of each sector is identical but simply shifted in time by a constant phase relative to its nearest neighbors.

### 3.3 Cyclic System With One DOF Per Sector.
This example considers the simplest prototypical model for vibrations of a bladed disk with only one DOF per sector, nearest-neighbor coupling, and perfect symmetry. Despite the simplicity of the model, we show that the resonant response can be quite complicated when the system is subjected to engine order excitation with multiple orders. We begin by formulating the EOM, and then consider a direct (traditional) approach to deriving the response to traveling wave excitation. The forced response is then derived using the modal analysis based on the Fourier matrix, which decouples the EOM. The nature of the natural frequencies and modes is considered next, which sets the stage for examining the resonance behavior of the system when subjected to engine order excitation. This provides a quite general view of the forced response of these models.

#### 3.3.1 Equations of Motion.
The undamped cyclic system to be considered is shown in Fig. 8 in dimensionless form. It consists of a cyclic chain of $N$ identical and identically coupled single-DOF oscillators with unit mass, the dynamics of which are captured by the dimensionless transverse displacements $q_i$ for $i \in \mathcal{N}$. The oscillators are uniformly attached around the circumference of a stationary rigid hub via linear elastic elements with unit stiffness and unit effective length. Adjacent masses are elastically coupled via linear springs, each with nondimensional stiffness $\nu$. It is assumed that the elastic elements are unstressed when the oscillators are in a purely radial configuration, that is, when $q_i=0$ for each $i \in \mathcal{N}$. An individual oscillator, together with the forward-nearest-neighbor elastic coupling, forms one fundamental sector and there are $N$ such sectors in the overall system. The oscillator chain has cyclic boundary conditions such that $q_0=q_N$ and $q_{N+1}=q_1$. Finally, the system is subjected to engine order excitation (Sec. 3.2) according to

$$ f_i(t) = f e^{j\phi_i} e^{jn\sigma\tau}, \quad i \in \mathcal{N} \quad (80) $$

<figure><img src="image_49.png" /><figcaption>Fig. 8 Linear cyclic vibratory system with $N$ sectors and one DOF per sector</figcaption></figure>

where $f$ is the strength of the excitation, the interphase blade angle $\phi_i$ is defined by Eq. (64), $n \in \mathbb{Z}_+$ is the excitation order, $\sigma$ is the angular speed, and $\tau$ is time (all dimensionless).

The linear dynamics of the $i$th sector are obtained using Newton's laws and are governed by

$$ \ddot{q}_i + q_i + \nu^2(-q_{i-1} + 2q_i - q_{i+1}) = f e^{j\phi_i} e^{jn\sigma\tau}, \quad i \in \mathcal{N} \quad (81) $$

where overdots denote differentiation with respect to dimensionless time $\tau$. In Eq. (81), the $q_{i\pm 1}$ terms arise from the left-nearest-neighbor ($i-1$) and right-nearest-neighbor ($i+1$) elastic coupling. By stacking the $N$ coordinates $q_i$ into the configuration vector $\mathbf{q} = (q_1, q_2, \dots, q_N)^{\mathrm{T}}$, the governing EOM for the overall $N$-DOF system takes the form

$$ \ddot{\mathbf{q}} + \mathbf{K}_{11}\mathbf{q} = \mathbf{f}_{11}e^{jn\sigma\tau}, \quad i \in \mathcal{N} \quad (82) $$

where $\mathbf{f}_{11} = (f e^{j\phi_1}, f e^{j\phi_2}, \dots, f e^{j\phi_N})^{\mathrm{T}}$ is the system forcing vector, which accounts for the constant phase difference in the dynamic loading from one sector to the next. The $N \times N$ matrix

$$ \mathbf{K}_{11} = \begin{bmatrix} 1 + 2\nu^2 & -\nu^2 & 0 & \dots & 0 & -\nu^2 \\ -\nu^2 & 1 + 2\nu^2 & -\nu^2 & \dots & 0 & 0 \\ 0 & -\nu^2 & 1 + 2\nu^2 & \dots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \dots & 1 + 2\nu^2 & -\nu^2 \\ -\nu^2 & 0 & 0 & \dots & -\nu^2 & 1 + 2\nu^2 \end{bmatrix} \quad (83) $$

captures the nondimensional stiffness of each sector relative to the hub (additive unity along its diagonal) and the intersector coupling ($\nu^2$ along the super-diagonal and subdiagonal). The elements $-\nu^2$ appearing in the $(1, N)$ and $(N, 1)$ positions of $\mathbf{K}_{11}$ are due to the cyclic boundary conditions $q_0=q_N$ and $q_{N+1}=q_1$. In the absence of these cyclic coupling terms, the system represents a finite chain of $N$ oscillators. Thus, in addition to being symmetric, Eq. (83) is also a circulant and can be written as

$$ \mathbf{K}_{11} = \mathrm{circ}(1 + 2\nu^2, -\nu^2, 0, \dots, 0, -\nu^2) \in \mathcal{S}\mathcal{C}_N \quad (84) $$

where $1+2\nu^2, -\nu^2, 0, \dots, 0, -\nu^2$ are the $N$ generating elements. In the absence of coupling (that is, if $\nu=0$) $\mathbf{K}_{11}$ is diagonal and Eq. (82) represents a decoupled set of $N$ harmonically forced, single-DOF oscillators.

The forced response of Eq. (82) is considered next with emphasis on a modal analysis whereby the fully coupled system (that is, one in which $\nu \neq 0$) is reduced to a set of $N$ single-DOF oscillators, only one of which is harmonically excited. The approach taken here, and a generalization in which each sector has multiple DOFs, is applied to the linear system in Sec. 3.4 to block decouple the system matrices as it is done in Sec. 3.1.

#### 3.3.2 Forced Response.
The steady-state forced response of Eq. (82) can be obtained using standard techniques [99] and, for nonresonant forcing, is given by