# Approximate Triangulations of Grassmann Manifolds
## 2 Materials and Methods
### Sampling Procedures  
To build a Vietoris-Rips or witness complex on points in \(G_{k}(\mathbb{R}^{n})\), we need to develop a sampling procedure. The first question to be asked is in which Euclidean space do we embed \(G_{k}(\mathbb{R}^{n})\)? This is highly nontrivial. Even in the case of projective spaces (\(k=1\)), it is not so obvious how to proceed. A whole industry has been devoted to the question of the minimal embedding dimension of \(\mathbb{R}P^{n}\)[13], but the proof of the minimality of any particular embedding rarely comes with an explicit _formula_ for the map. An exception is if one insists on an _isometric_ embedding [14], but the minimal dimension of such an embedding for \(\mathbb{R}P^{n}\) is \(n(n+3)/2\), which grows rather quickly. For arbitrary Grassmannians, one could try to use the Plucker embedding \(G_{k}(\mathbb{R}^{n})\to P(\bigwedge^{k}(\mathbb{R}^{n}))=\mathbb{R}P^{(z)-1}\) defined by  
\[(x_{1},\ldots,x_{k})\mapsto[x_{1}\wedge\cdots\wedge x_{k}]\]  
(where \([v]\) denotes the line spanned by the vector \(v\)) and then embed the target projective space into Euclidean space. Of course, this explodes the dimension further, making this an impractical solution. Aside from some low dimensional projective spaces, we will instead approach this problem via the following result. **Proposition 2**: _The manifold \(G_{k}(\mathbb{R}^{n})\) is diffeomorphic to the smooth manifold consisting of all \(n\times n\) symmetric, idempotent matrices of trace \(k\). The map \(\varphi\) realizing this takes a \(k\)-plane \(X\) to the operator defined by orthogonal projection onto \(X\)._  
If \(X\) is a \(k\)-plane with orthonormal basis \(x_{1},\ldots,x_{k}\), denote by \(A\) the \(n\times k\) matrix having the \(x_{i}\) as columns. Define a map \(\varphi:G_{k}(\mathbb{R}^{n})\to M_{n}(\mathbb{R})\) by \(X\mapsto AA^{T}\). This map is clearly smooth since it consists of polynomials in the entries of the various \(x_{i}\). Moreover, it is well-defined since, if \(y_{1},\ldots,y_{k}\) is another orthonormal basis of \(X\) with associated matrix \(B\), then there is an orthogonal matrix \(O\) such that \(B=AO\). Then, \(BB^{T}=(AO)(AO)^{T}=AOOT^{T}A^{T}=AA^{T}\). The matrix \(AA^{T}\) is symmetric: \((AA^{T})^{T}=(A^{T})^{T}A^{T}=AA^{T}\). It is idempotent: \((AA^{T})^{2}=AA^{T}AA^{T}=AI_{k}A^{T}=AA^{T}\) (note that \(A^{T}A=I_{k}\), the \(k\times k\) identity matrix, since the columns of \(A\) are orthonormal). Finally, the trace of \(AA^{T}\) is \(k\) since its rank is \(k\) and its only eigenvalues are \(0\) and \(1\). Thus, the image of \(\varphi\) lies in the set of symmetric, idempotent matrices of trace \(k\). To see that \(\varphi\) surjects onto this set, note that such a matrix \(B\) is projection onto a \(k\)-dimensional subspace \(X\) and there exists a basis \(x_{1},\ldots,x_{k}\) with \(\varphi(X)=B\). Injectivity of \(\varphi\) follows since the subspace determined by a projection is unique. \(\square\)  
Now, to generate a sample of points on which to build a Vietoris-Rips or witness complex, we will use the embedding \(\varphi\). A crude sampling is then obtained by the following procedure:  
* Select \(k\) random vectors in \(\mathbb{R}^{n}\). * Perform the Gram-Schmidt orthogonalization algorithm to yield an orthornomal set \(x_{1},\ldots,x_{k}\). Let \(A\) be the matrix with \(x_{i}\) as columns. * Compute \(AA^{T}\). One immediate problem with this process is that the \(k\)-plane it constructs lives in the top-dimensional Schubert cell with probability \(1\). However, since we know the space we are interested in, and we know its homology, we can bias our sample to ensure we include points from each Schubert cell. The following procedure implements this idea:  
* Determine the percentage of sample points desired from each Schubert cell. For example, one might choose \(5\%\) from a \(1\)-cell, \(10\%\) from a \(2\)-cell, and so on. * Elements of a given Schubert cell correspond to the column space of a particular matrix form.