Grassmann and Flag Varieties in Linear Algebra, Optimization, and Statistics: An Algebraic Perspective
Hannah Friedman and Serkan Hoşten · 2025
Read Grassmann and Flag Varieties in Linear Algebra, Optimization, and Statistics: An Algebraic Perspective by Hannah Friedman and Serkan Hoşten (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-15969.txt.
Introduction
Hannah Friedman and Serkan Hosten survey in 2025 the hidden algebra behind spaces used in data work. These spaces, Grassmann and flag varieties, collect all the flat slices of a given size inside a larger space. They show up in linear algebra, tuning problems, and statistics. The authors ask how hard such problems are in algebraic terms.
Their measure counts the complex critical points of a tuning problem set on these spaces. The survey first lays out the many ways these spaces can be written as algebraic sets. It then works through sample problems and computes their counts. The results give a yardstick for how complex a problem is before anyone tries to solve it.
Catalog record
| CREATOR | Hannah Friedman and Serkan Hoşten |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 63 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-15969
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Grassmann and Flag Varieties in Linear Algebra, Optimization, and Statistics: An Algebraic Perspective Hannah Friedman and Serkan Hoşten Abstract Grassmann and flag varieties lead many lives in pure and applied mathematics. Here we focus on the algebraic complexity of solving various problems in linear algebra and statistics as optimization problems over these varieties. The measure of the algebraic complexity is the amount of complex critical points of the corresponding optimization problem. After an exposition of different realizations of these manifolds as algebraic varieties we present a sample of optimization problems over them and we compute their algebraic complexity. 1 Introduction A flag manifold or flag variety parametrizes nested sequences of subspaces of fixed dimension, known as flags, of a finite dimensional vector space V . In this article, we take this vector space to be V=\mathbb{R}^{n} or V=\mathbb{C}^{n} . We fix r positive integers 1\leq k_{1}<k_{2}<\cdots<k_{r}\leq n and consider {\rm Fl}({\bf k};n)={\rm Fl}(k_{1},\ldots,k_{r};n)=\{W_{1}\subset W_{2}\subset\cdots\subset W_{r}:W_{i}\subseteq V,\,\dim(W_{i})=k_{i},\,1\leq i\leq r\}. The set of flags {\rm Fl}({\bf k};n) is both a (real or complex) manifold and a (real or complex) algebraic variety. As an algebraic variety, it lives in some affine space \mathbb{A}^{N} or projective space \mathbb{P}^{N} . In this case, we would like to know the defining equations, i.e., the polynomials whose common zero set is {\rm Fl}({\bf k};n) . We also ask to know algebraic invariants of {\rm Fl}({\bf k};n) such as the dimension and the degree where the latter depends on the particular embedding. In Section 2 , we introduce and discuss several realizations of flag varieties, namely, the Stiefel coordinates, Plücker embedding, projection embedding, and isospectral model. The Grassmannian {\rm Gr}(k,n) of k -dimensional subspaces of V is a flag variety with r=1 . It also appears with different realizations such as its Plücker and projection embeddings [ 5 , 7 ] . For each realization of the flag variety, we prove that the natural equations defining these varieties generate prime ideals. We discuss the relationships between these different embeddings. All of these realizations have appeared in the literature; see [ 5 , 7 , 11 , 19 ] . We collect them in one place to help anyone, especially those from the applied and computational algebraic geometry and algebraic statistics communities, to get a foot in the door. Our theme is optimization on Grassmann and flag varieties. As a starting point, consider the eigenvalue problem for symmetric matrices. Let A be an n\times n real symmetric matrix and consider the problem of minimizing or maximizing the Rayleigh quotient: \displaystyle\mathop{{\rm min/max}}_{z\neq 0} \displaystyle\,\,\,\frac{z^{T}Az}{z^{T}z}. (1) It is known that the optimal value for this eigenvalue problem is the minimum (respectively, maximum) eigenvalue of A . A formulation which avoids the fraction in the objective function is the quadratic optimization problem over S^{n-1} , the sphere of dimension n-1 : \displaystyle\mathop{{\rm min/max}}_{z\in S^{n-1}} \displaystyle\,\,\,z^{T}Az. (2) The optimal solution to the above eigenvalue problem ( 1 ) and ( 2 ) is a unit eigenvector corresponding to the minimum/maximum eigenvalue. The critical points of this constrained optimization problem are precisely the unit eigenvectors of A . The choice of sign for each eigenvector gives us 2n critical points. The eigenvalue problem has the following generalization to compute multiple eigenvectors at once where we replace the vector z in ( 2 ) with an n\times k matrix Z consisting of orthonormal columns. We solve a quadratic optimization problem over the Stiefel manifold called the multi-eigenvector problem : \displaystyle\mathop{{\rm min/max}}_{Z^{T}Z={\rm Id}_{k}} \displaystyle\,\,\,{\rm trace}(Z^{T}AZ). (3) The critical points of this problem are the sets of orthogonal k -frames consisting of unit eigenvectors of A , up to the action of the orthogonal group {\rm O}(k) over the complex numbers. Theorem 1.1 . Let A be a generic real symmetric n\times n matrix and let Z be an n\times k variable matrix. The algebraic set of complex critical points of the multi-eigenvector problem ( 3 ) is \bigsqcup_{\{i_{1},\ldots,i_{k}\}\in\binom{[n]}{k}}\{[u_{i_{1}}\,u_{i_{2}}\,\cdots\,u_{i_{k}}]Q\,:\,Q\in{\rm O}(k)\} where u_{1},\ldots,u_{n} is an orthonormal eigenbasis of A . This algebraic set is a disjoint union of \binom{n}{k} varieties isomorphic to {\rm O}(k) ; it has dimension \dim({\rm O}(k))=\binom{n}{k} and degree \deg({\rm O}(k))\binom{n}{k} . The degree of the special orthogonal group was computed in [ 1 , Theorem 1.1] . Because the multi-eigenvector problem is {\rm O}(k) -invariant, it is more naturally considered over the Grassmannian. In Section 3 , we will restate this problem over the Grassmannian in projection coordinates [ 5 ] , where it has \binom{n}{k} critical points (Theorem 3.3 ). To formulate this problem over the flag variety, one can use isospectral coordinates [ 11 ] . In the isospectral formulation, the set of critical points is a disjoint union of products of smaller orthogonal groups (Theorem 3.5 ). In both Theorems 3.3 and 3.5 , we give explicit descriptions of the critical points. When the set of critical points is finite, its size, the algebraic degree , provides a measure for the complexity of the problem. In particular, any optimal solution is an algebraic function of the input data of this degree; see [ 14 , 15 , 18 ] . In Section 4 , we study the heterogeneous quadratics minimization problem, which is used as a benchmark for testing numerical methods for Riemannian optimization [ 17 ] . Given symmetric n\times n matrices A_{1},\ldots,A_{k} , we seek to find Z=[Z_{1}\cdots Z_{k}] such that \displaystyle\mathop{{\rm min/max}}_{Z^{T}Z={\rm Id}_{k}} \displaystyle\,\,\,\sum_{i=1}^{k}Z_{i}^{T}A_{i}Z_{i}. (4) If A_{1}=\cdots=A_{k} , one recovers the multi-eigenvector problem ( 3 ). However, for a generic choice of A_{1},\ldots,A_{k} , this problem is not an optimization problem over the Grassmannian, but rather over the flag variety {\rm Fl}(1,\ldots,k;n) . We formulate the problem in projection coordinates and observe that in this formulation the heteregoneous quadratics minimization problem is a generic linear optimization problem over the flag variety. We use numerical methods to compute the critical point counts for small values of k (Table 1 ). We also report our observation based on our computational experiments that taking A_{1},\ldots,A_{k} to be generic diagonal matrices does not change the number of critical points. For n=3 and k=2 , we show that this number is 40 (Proposition 4.2 ). The code for these computations is available at https://github.com/hannahfriedman/flag_optimization_algebraic_perspective . In Section 5 , we examine two problems from statistics [ 19 ] : canonical correlation analysis and correspondence analysis. In these problems, we consider a rectangular matrix A instead of a symmetric matrix and the critical points of the problems are given by the singular value decomposition of A . In the first case, we give a formula for the finite number of critical points which correspond to pairs of left and right singular vectors of A (Theorem 5.1 ). The second problem can be naturally formulated over a product of Grassmannians, and we give a complete description of the critical points in this case as well (Theorem 5.2 ). 2 The Many Lives of the Flag Variety We start with the observation that the set of partial flags 0=W_{0}\subset W_{1}\subset W_{2}\subset\cdots\subset W_{r}\subset V with \dim(W_{i})=k_{i} are in bijection with the sequence of subspaces (W_{1}/W_{0},W_{2}/W_{1},W_{3}/W_{2},\ldots,W_{r}/W_{r-1}) where W_{i}/W_{i-1} is viewed as a subspace in V/W_{i-1} for i=1,\ldots,r . This gives a formula for the dimension of {\rm Fl}({\bf