## 2 Materials and Methods
### Identifying Graph Topologies from Observations of Stationary Graph Signals
#### 2.1.2 Size of the Feasible Set  
Here, we examine the feasibility set and the degrees of freedom of the GSO \(\mathbf{S}\) under the assumption that the perfect output covariance \(\mathbf{C}_{\mathbf{y}}\) is available and \(\mathbf{S}\in\mathcal{S}\) (cf. (7)). This would shed light on the dependency of the feasibility set's structure and dimensionality (hence the difficulty of recovering \(\mathbf{S}\)) on the number \(|\Omega|\) of observed edges. This dependency can serve as a guideline to the number of edges we may seek to observe prior to graph inference. As we show next, the feasibility set may potentially reduce to a singleton (the graph \(\mathbf{S}\in\mathcal{S}\) is completely specified by \(\mathbf{C}_{\mathbf{y}}\)), or more generally to a low-dimensional subspace. In the latter (more interesting) case, or more pragmatically when we approximate \(\hat{\mathbf{C}}_{\mathbf{y}}\) with the observations' sample covariance, we solve the convex optimization problem as in (6) to search for a sparse and structurally admissible GSO. Given the (ensemble) output covariance \(\mathbf{C}_{\mathbf{y}}\), consider the mapping \(\mathbf{SC}_{\mathbf{y}}=\mathbf{C}_{\mathbf{y}}\mathbf{S}\) which stems from the stationarity of \(\mathbf{y}\) (cf. the opening discussion in Section 2.1.1). This identity implies that \(\mathbf{C}_{\mathbf{y}}\) and \(\mathbf{S}\) are simultaneously diagonalizable. Thus, the eigenvectors \(\mathbf{V}\) of \(\mathbf{S}\) are known and coincide with those of \(\mathbf{C}_{\mathbf{y}}\). Given the GSO eigenvectors \(\mathbf{V}\), consider the mapping \(\mathbf{S}=\mathbf{V}\boldsymbol{\Lambda}\mathbf{V}^{T}\) between \(\mathbf{S}\) and \(\boldsymbol{\Lambda}\). This can precisely be rewritten as \(\operatorname{vec}(\mathbf{S})=(\mathbf{V}\circ\mathbf{V})\boldsymbol{\lambda}= \mathbf{W}\boldsymbol{\lambda}\), where \(\odot\) denotes the Khatri-Rao (column-wise Kronecker) product, \(\boldsymbol{\lambda}\in\mathbb{R}^{N}\) collects the diagonal entries of \(\boldsymbol{\Lambda}\), and \(\mathbf{W}:=\mathbf{V}\circ\mathbf{V}\in\mathbb{R}^{N^{2}\times N}\). Recall that \(\mathbf{S}\in\mathcal{S}\) and accordingly the entries of \(\operatorname{vec}(\mathbf{S})\) corresponding to the diagonal of \(\mathbf{S}\) are zero. Upon defining the set \(\mathcal{D}:=\left\{N(i-1)+i\mid i\in\{1,\ldots,N\}\right\}\), we have the mapping \(\mathbf{W}_{\mathcal{D}}\boldsymbol{\lambda}=\mathbf{0}\) to the null diagonal entries of \(\mathbf{S}\), where \(\mathbf{W}_{\mathcal{D}}\in\mathbb{R}^{N\times N}\) is a submatrix of \(\mathbf{W}\) that contains rows indexed by the set \(\mathcal{D}\). Thus, it follows that \(\mathbf{W}_{\mathcal{D}}\) is rank-deficient and \(\boldsymbol{\lambda}\in\operatorname{ker}(\mathbf{W}_{\mathcal{D}})\), where \(\operatorname{ker}(. )\) denotes the null-space of its matrix argument. In particular, assume that \(\operatorname{rank}(\mathbf{W}_{\mathcal{D}})=N-k\), \(1\leq k<N\), which implies \(\boldsymbol{\lambda}\) lives in a \(k\)-dimensional subspace. As some of the entries in \(\mathbf{S}\) are known according to \(\mathcal{S}\), intuitively we expect that by observing \(k=|\Omega|\) \"sufficiently different\" edges, the feasible set may boil down to a singleton resulting in a unique feasible \(\mathbf{S}\in\mathcal{S}\). To quantify the effect of the partial connectivity constraints on the size of the feasible set, let \(\mathcal{M}:=\left\{N(j-1)+i\mid(i,j)\in\Omega\right\}\) correspond to the known entries of \(\operatorname{vec}(\mathbf{S})\). Then upon defining \(\mathbf{U}\in\mathbb{R}^{N\times k}\) comprising the basis vectors of \(\operatorname{ker}(\mathbf{W}_{\mathcal{D}})\), the condition \(\operatorname{rank}(\mathbf{W}_{\mathcal{M}}\mathbf{U})=k\) would be sufficient to determine \(\mathbf{S}\) uniquely in the \(k\)-dimensional null space of \(\mathbf{W}_{\mathcal{D}}\) as stated in the following proposition. Proposition: Suppose the GSO eigenvectors \(\mathbf{V}\) are given.