## 2 Some Remarks on Circulant and \(\omega\)-Circulant Matrices  
In this introductory section, we lay the groundwork for the main part of this paper by recalling the basic definitions and properties of both circulant and \(\omega\)-circulant matrices. More information can be found in Ref. [7]. We recall that circulant and \(\omega\)-circulant matrices have played a major role in the last four decades for the fast solution of structured linear systems, mainly of Toeplitz type, but also stemming from approximated PDEs. Classical references are Refs. [2; 9; 10; 11; 12; 13; 14], where preconditioned Krylov methods, local Fourier analysis, and its GLT generalizations are treated with attention to the circulant structure and to the related fast Fourier transform (FFT); see Ref. [15]. More specific references for the numerical treatment of PDEs via \(\omega\)-circulant preconditioning or directly by multigrid solvers or combination of them can be found in Refs. [16; 10; 17; 18]. **Definition 1**. : _Consider \(\mathbf{\alpha}=[\alpha_{0},\alpha_{1},\ldots,\alpha_{n-1}]\) with \(\alpha_{j}\in\mathbb{R}\). A square matrix \(\mathbf{C}\in\mathbb{R}^{n\times n}\) is called circulant and it is denoted with \(\mathbf{C}=\text{circ}(\mathbf{\alpha})\) if we have_  
\[(\mathbf{C})_{s,t}=\alpha_{s-t\pmod{n}}\qquad\forall s,t=0,\ldots,n-1.\]  
_An equivalent and compact representation of \(\mathbf{C}\) is given by_  
\[\mathbf{C}=\sum_{j=0}^{n-1}\Pi_{n}^{j}\mathbf{\alpha}_{j},\]  
_where \(\Pi_{n}\) is the permutation matrix_  
\[\Pi_{n}= \begin{bmatrix}0&0&0&\ldots&0&1\\ 1&0&0&\ldots&0&0\\ 0&1&0&\ldots&0&0\\ 0&0&1&\ldots&0&0\\ \ddots&\ddots&\ddots&\ddots&\ddots&\ddots\\ 0&0&0&\ldots&1&0\end{bmatrix} .\]  
Note that for any fixed \(p,q\in\mathbb{N}\) the matrix \(\mathbf{C}=\sum_{j=-p}^{q}\Pi_{n}^{j}\mathbf{\alpha}_{j}\) is circulant, since this sum can always be traced back to the form in the above definition. Denoting with \(\cdot\)' the conjugate transpose, circulant matrices admit the following spectral decomposition. **Proposition 1**. : \(\mathbf{C}\) _can be diagonalized as_  
\[\mathbf{C}=F_{n}L_{n}F_{n}^{*},\]  
_where_  
\[L_{n}=\operatorname{diag}_{s=0,\ldots,n-1}\left(\sum_{j=0}^{n-1}\exp\left(2 \pi\mathrm{i}\frac{\mathrm{i}j}{n}\right)\mathbf{\alpha}_{j}\right)\]  
_is the diagonal matrix containing the eigenvalues of \(\mathbf{C}\) and_  
\[F_{n}=\frac{1}{\sqrt{n}}\left[\exp\left(-2\pi\mathrm{i}\frac{\mathrm{i}\pi}{n }\right)\right]_{j,k=0}^{n-1},\ \ \mathrm{i}^{2}=-1\]  
_is the unitary Fourier matrix._  
Proof. : By a direct computation of the eigenvalues, it is easy to verify that \(\Pi_{n}\) factorizes as  
\[\Pi_{n}=F_{n}\Omega_{n}F_{n}^{*} \tag{1}\]with  
\[\Omega_{n}=\text{diag}_{s=0,\ldots,n-1}\Big{(}\text{exp}\left(2\pi\text{i}\frac{s }{n}\right)\Big{)}. \tag{2}\]  
The thesis follows. **Remark 1**. : _The eigenvalues of \(\mathbf{C}\), namely the diagonal elements of \(L_{n}\), are given by the Fourier transform of the first column of \(\mathbf{C}\). Alternatively, they can be seen as_  
\[\Lambda(\mathbf{C})=\bigg{\{}f\bigg{(}\frac{2\pi s}{n}\bigg{)},s=0,\ldots,n-1 \bigg{\}},\]  
_where the function \(f(\theta):=\sum_{j=0}^{n-1}\alpha_{j}\exp(\text{i}j\theta)\) is called (spectral) symbol of \(\mathbf{C}\)._  
\(\omega\)-circulant matrices represent an extension of the notion of circulant matrix (see, e.g., Refs. [6; 19; 20] for more details). **Definition 2**. : _Consider \(\boldsymbol{\alpha}=[\alpha_{0},\alpha_{1},\ldots,\alpha_{n-1}]\) with \(\alpha_{j}\in\mathbb{R}\). A square matrix \(\mathbf{C}_{\omega}\in\mathbb{R}^{n\times n}\) is called \(\omega\)-circulant and it is denoted with \(\mathbf{C}_{\omega}=\text{circ}_{\omega}(\boldsymbol{\alpha})\) if it holds_  
\[(\mathbf{C}_{\omega})_{s,t}= \begin{cases}\alpha_{s-t\pmod{n}},&\text{if }s>t, \\ \omega\alpha_{s-t\pmod{n}},&\text{if }s\leq t,\end{cases}