# A Graduated Non-Convexity Technique for Dealing Large Point Spread Functions
## 4 E-CATILED Technique
### Structural Characterizations of \(\beta\)-Matrices  
In this subsection, we show that \(\mathcal{V}_{n}\) coincides with the direct sum of the sets of all real circulant matrices and of all reverse circulant matrices. We consider the set of families  
\[\mathcal{L}_{n,k} = \{A\in\mathbb{R}^{n\times n}:\text{there is }\mathbf{a}=(a_{0}\, \ldots\,a_{n-1})^{T}\in\mathbb{R}^{n}\text{ with }a_{l,j}=a_{(j+kl)\bmod n}\},\] \[\mathcal{K}_{n,k} = \{A\in\mathbb{R}^{n\times n}:\text{there is a symmetric }\mathbf{a}=(a_{0}\, \ldots\,a_{n-1})^{T}\in\mathbb{R}^{n}\] \[\text{ with }a_{l,j}=a_{(j+kl)\bmod n}\},\] \[\mathcal{J}_{n,k} = \Big{\{}A\in\mathbb{R}^{n\times n}:\text{ there is a symmetric }\mathbf{a}=(a_{0}\, \ldots\,a_{n-1})^{T}\in\mathbb{R}^{n}\] \[\text{ with }\sum_{t=0}^{n-1}a_{t}=0,\sum_{t=0}^{n-1}(-1)^{t}a_{t} \,=\,0\text{ when }n\text{ is even, and }a_{l,j}=a_{(j+kl)\bmod n}\Big{\}},\]  
where \(k\in\{1,2,\ldots,n-1\}\). When \(k=n-1\), \(\mathcal{L}_{n,n-1}\) is the class of all _real circulant matrices_, that is, the family of those matrices \(\mathcal{C}\in\mathbb{R}^{n\times n}\) such that every row, after the first, has the elements of the previous one shifted cyclically one place right (see, e.g., [46]). Given a vector \(\mathbf{c}\in\mathbb{R}^{n}\), \(\mathbf{c}=(c_{0}\,c_{1}\cdots c_{n-1})^{T}\), let us define  
\[\text{circ}(\mathbf{c})=C=\left( \begin{matrix}c_{0}&c_{1}&c_{2}&\ldots&c_{n-2 }&c_{n-1}\\ c_{n-1}&c_{0}&c_{1}&\ldots&c_{n-3}&c_{n-2}\\ c_{n-2}&c_{n-1}&c_{0}&\ddots&c_{n-4}&c_{n-3}\\ \vdots&\vdots&\ddots&\ddots&\ddots&\vdots\\ c_{2}&c_{3}&c_{4}&\ddots&c_{0}&c_{1}\\ c_{1}&c_{2}&c_{3}&\ldots&c_{n-1}&c_{0}\end{matrix} \right),\]  
where \(C\in\mathcal{L}_{n,n-1}\). **Theorem 1** (Theorems 3.2.2 and 3.2.3 in [46]). : _The following result holds:_  
\[\mathcal{W}_{n}=\mathcal{L}_{n,n-1}.\]  
As a consequence of this theorem, we obtain that the \(n\) eigenvectors of every circulant matrix \(C\in\mathbb{R}^{n\times n}\) are given by  
\[\mathbf{w}^{(j)}=(1\,\,\omega_{n}^{j}\,\,\omega_{n}^{2j}\,\,\,\cdots\,\, \omega_{n}^{(n-1)j})^{T},\]  
and the eigenvalues of a matrix \(C=\)circ\((\mathbf{c})\in\mathcal{F}_{n}\) are expressed by  
\[\lambda_{j}=\mathbf{c}^{T}\mathbf{w}^{(j)}=\sum_{k=0}^{n-1}c_{k}\omega_{n}^{jk },\qquad j=0,1,\ldots,n-1.\]  
Now, we present some results about symmetric circulant real matrices. Observe that if \(C=\)circ\((\mathbf{c})\), with \(\mathbf{c}\in\mathbb{R}^{n}\), then \(C\) is symmetric if and only if \(\mathbf{c}\) is symmetric. Thus, the class of all real symmetric circulant matrices coincides with \(\mathcal{K}_{n,n-1}\) and has dimension \(\lfloor\frac{n}{2}\rfloor+1\) over \(\mathbb{R}\). **Theorem 2** (see, e.g., (SS4 in [27]), (Lemma 3 in [44])). : _Let \(C\in\mathcal{K}_{n,n-1}\). Then, the set of all eigenvectors of \(C\) can be expressed as \(\{\mathbf{q}^{(0)},\,\mathbf{q}^{(1)},\ldots,\,\mathbf{q}^{(n-1)}\}\), where \(\mathbf{q}^{(j)},\,j=0,\,1,\ldots,n-1,\) is as in (6)-(8)._  
Note that from Theorem 2 it follows that the set of all real symmetric circulant matrices is contained in \(\mathcal{G}_{n}\). The next result holds. **Theorem 3** (see, e.g., (SS1.2 in [47]), (SS4 in [27]), (Theorem 1 in [48])). : _Let \(C=\text{circ}(\mathbf{c})\in\mathcal{K}_{n,n-1}\). Then, the eigenvalues \(\lambda_{j}\) of \(C\) are given by_  
\[\lambda_{j}=\mathbf{c}^{T}\mathbf{u}^{(j)},\quad j=0,1,\ldots,\lfloor\frac{n}{ 2}\rfloor, \tag{11}\]  
_where the \(\mathbf{u}^{(j)}\)'s are as in (7). Moreover, for \(j=1,\,2,\ldots,\lfloor\frac{n-1}{2}\rfloor\) it is_  
\[\lambda_{j}=\lambda_{n-j}.\]  
From Theorem 3, it follows that, if \(C\) is a real symmetric circulant matrix and \(\lambda^{(C)}\) is the set of its eigenvalues, then \(\lambda^{(C)}\) is symmetric, thanks to (11). Hence, \(\mathcal{K}_{n,n-1}\subset\mathcal{C}_{n}\). Thus, \(\mathcal{C}_{n}\) coincides with the class of symmetric circulant matrices \(\mathcal{K}_{n,n-1}\) since these two vector spaces have the same dimension.