{'fraction_non_alphanumeric': 0.06281698747326611, 'fraction_numerical': 0.012618392911701803, 'mean_word_length': 3.2796809623430963, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 6, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 27, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
The Euclidean Distance Degree of Orthogonally Invariant Matrix Varieties

We show that the Euclidean distance degree of a real orthogonally invariant matrix variety equals the Euclidean distance degree of its restriction to diagonal matrices. We illustrate how this result can greatly simplify calculations in concrete circumstances.


Introduction
The problem of minimizing the Euclidean distance (ED) of an observed data point y ∈ R n to a real algebraic variety V ⊆ R n arises frequently in applications, and amounts to solving the polynomial optimization problem The algebraic complexity of this problem is closely related to the number of complex regular critical points of y on the Zariski closure V C of V. We will call such points the ED critical points of y with respect to V; see Definition 4.1. The authors of [11] showed that the number of ED critical points of a general data point y ∈ C n is a constant, and hence is an invariant of V. This number is called the Euclidean distance degree (ED degree) of V. As noted in [11], the computation of EDdegree(V) can be subtle, since it may change considerably under a linear transformation of V.
In this work, we explore the ED degree of orthogonally invariant matrix varieties M ⊆ R n×t , meaning those varieties M satisfying Date: January 28, 2016. Drusvyatskiy was partially supported by the AFOSR YIP award FA9550-15-1-0237. Lee and Thomas were partially supported by the NSF grant DMS-1418728.
In most interesting situations, the diagonal restriction S ⊆ R n has simple geometry, as opposed to the matrix variety M, and hence our main result (⋆) provides elementary and transparent means to compute the ED degree of M by working with the simpler object S. Interesting consequences flow from there. For example, consider the r-th rank variety R n×t r := {X ∈ R n×t : rank X ≤ r}, and the essential variety E := {X ∈ R 3×3 : σ 1 (X) = σ 2 (X), σ 3 (X) = 0} from computer vision [1,17,21]; both R n×t r and E are orthogonally invariant. The diagonal restrictions of R n×t and E are finite unions of linear subspaces and their ED degrees are immediate to compute. Moreover, our results readily imply that all ED critical points of a general real data matrix Y on R n×t r and on E are real. This result has been previously shown for R n×t r in [11] -a generalization of the Eckart-Young theorem -and is entirely new for the essential variety E. A related further investigation of the essential variety appears in [15].
Our investigation of orthogonally invariant matrix varieties fits in a broader scope. The idea of studying orthogonally invariant matrix sets M via their diagonal restrictions S -the theme of our paper -is not new, and goes back at least to von Neumann's theorem on unitarily invariant matrix norms [28]. In recent years, it has become clear that various analytic properties of M and S are in one-to-one correspondence, and this philosophy is sometimes called the "transfer principle"; see for instance, [7]. For example, M is C p -smooth around a matrix X if and only if S is C p -smooth around σ(X) [5,12,20,25,27]. Other properties, such as convexity [8], positive reach [6], partial smoothness [5], and Whitney conditions [13] follow the same paradigm. In this sense, our paper explores the transfer principle for the ED degree of algebraic varieties. To the best of our knowledge, this is the first result in this body of work that is rooted in algebraic geometry.
Though our main result (⋆) is easy to state, the proof is subtle; moreover, the result itself is surprising in light of the discussion in [14,Section 5]. The outline of the paper is as follows. In Section 2 we investigate invariance properties of the Zariski closure M C ⊆ C n×t of an orthogonally invariant matrix variety M ⊆ R n×t , as well as the correspondence between irreducible components of S and those of M. In Section 3, we discuss "algebraic singular value decompositions" for general matrices Y ∈ C n×t , leading to Section 4 containing our main results. When S is a subspace arrangement, our results yield particularly nice consequences generalizing several classical facts in matrix theory -the content of Section 5.

Zariski closure, irreducibility, and dimension of matrix varieties
Setting the stage, we begin with some standard notation. For the fields F = R or F = C, the symbol F[x] = F[x 1 , . . . , x n ] will denote the ring of polynomials in x 1 , . . . , x n with coefficients in F. Given polynomials f 1 , . . . , f s ∈ F[x] the set V := {x ∈ F n : f 1 (x) = · · · = f s (x) = 0} is called an (algebraic) variety over F. The Zariski closure of an arbitrary set T in C n , denoted T , is the smallest variety over C containing T . Unless otherwise specified, the topology on C n is fixed to be the Zariski topology, obtained by defining the closed sets to be the varieties over C. The topology on any subset of C n will then always be the one induced by the Zariski topology.
Consider a real algebraic variety V ⊆ R n . The vanishing ideal of V is defined to be I(V) := {f ∈ R[x] : f (x) = 0 for all x ∈ V}. Viewing V as a subset of C n , the Zariski closure of V, denoted V C , can be written as {x ∈ C n : f (x) = 0 for all f ∈ I(V)}; see e.g. [29]. Note this notation is slightly redundant since by definition we have V = V C . Nonetheless, we prefer to keep both symbols to ease notation when appropriate.
2.1. Invariance under closure. Consider a group G acting linearly on C n . Then G also acts on We begin with the following elementary result.
Proof. Fixing g ∈ G, the map µ g : C n → C n given by µ g (x) = g · x is a linear isomorphism. Hence, assuming T is G-invariant, we deduce µ g (T ) = µ g (T ) = T , as claimed.
We now specialize the discussion to the main setting of the paper. For a positive integer s, the symbol O(s) will denote the set of all s × s real orthogonal matrices. This is both a group and a real variety and its Zariski closure O C (s) is the set of all s×s complex orthogonal matrices -those satisfying Q ⊤ Q = QQ ⊤ = I. Henceforth, we fix two positive integers n and t with n ≤ t, and consider the groups O(n) × O(t) and O C (n)×O C (t), along with the group Π ± n of all signed permutations of {1, . . . , n}. Recall that we always consider the action of O(n) × O(t) on R n×t and the action of We now prove the stronger statement: M C is invariant under the larger group O C (n)×O C (t).
Since the proofs are similar, we only prove the first claim. The backward implication is trivial.
. This completes the proof.

Irreducible components of orthogonally invariant varieties.
For the rest of the section, fix a Π ± n -invariant (absolutely symmetric) variety S in R n . Then the O(n) × O(t)-invariant matrix set M := σ −1 (S) is a real variety in R n×t ; see [14,Theorem 3.4] or [7, Proposition 1.1]. Moreover, the diagonal restriction {x ∈ R n : Diag (x) ∈ M} coincides with S. Here, we call a n × t matrix D diagonal if and only if D ij = 0 whenever i = j, and for any vector x ∈ R n the symbol Diag (x) denotes the diagonal matrix with D ii = x i for each i = 1, . . . , n.
In this section, we highlight the correspondence between the irreducible components of S and those of M. Recall that a real or complex variety V is irreducible if it cannot be written as a union V = V 1 ∪ V 2 of two proper subvarieties V 1 and V 2 . Any variety V can be written as a union of finitely many irreducible subvarieties V i satisfying V i V j for distinct indices i and j. The varieties V i are called the irreducible components of V, and are uniquely defined up to indexing.
Coming back to the aim of this section, let {S i } k i=1 be the irreducible components of S. The varieties S i are typically not absolutely symmetric. Hence we define their symmetrizations S π i := π∈Π ± n πS i and the real varieties M i := σ −1 (S π i ). It is standard that a signed permutation maps an irreducible component of S to another irreducible component of S.
We record the following elementary observation for ease of reference.
Lemma 2.3. For any pair of indices i, j, the following implications hold: . Hence for some π ∈ Π ± n , the inclusion S i ⊆ πS j holds. Since both S i and πS j are irreducible components of S, it must be that S i = πS j and hence, S π i = S π j , as claimed. The second implication follows immediately. Observe that Z is an orthogonally invariant variety. Hence the two absolutely symmetric varieties {x : Diag (x) ∈ Γ} and {x : Diag (x) ∈ Z} cover S π i . Since S i is irreducible, either Γ or Z coincides with all of M i . Since the latter is impossible by construction, we conclude that Γ = M i , as claimed.
We end with the following theorem, which will play a key role in the proof of Lemma 4.10, leading to the main result of the paper. Proof. Let {C l } be the set of irreducible components of M. Then for any index l, C l = j (C l ∩ M j ) which implies that C l is contained in M j for some index j(l).
Fix an M i and let H be an irreducible component of M i . From the equality H = l (C l ∩H) we conclude that the inclusion H ⊆ C l holds for some index l. This implies that H ⊆ C l ⊆ M j(l) , and hence by Lemma 2.4, M i ⊆ M j(l) . Lemma 2.3 then implies the equality M i = M j(l) , yielding H ⊆ C l ⊆ M i . Taking the union of this inclusion over all the irreducible components H of M i and the corresponding C l , we deduce that M i is a union of some irreducible components of M.
Since closures of irreducible components of a real variety V are the irreducible components of V C , Theorem 2.5 immediately implies that M i is a union of some irreducible components of M C .
2.3. Dimension of orthogonally invariant varieties. We next show how to read off the dimension of M C from the absolutely symmetric variety S ⊆ R n . To this end, note first that since the equality dim(M C ) = dim(M) holds (see [29,Lemma 8]), it suffices to compute the dimension of the real variety M from S. We will assume that Π ± n acts transitively on the irreducible components of S, that is in the notation of Section 2.2 we have S π i = S for all indices i. If this is not the case, we can treat each set S π i separately. With this simplification, both varieties S and M are equidimensional (Lemma 2.4).
The following recipe follows that in [5, Section 2.3] and [7] and hence we skip some of the explanations. The basic idea is to understand the dimension of the fiber σ −1 (x * ) where x * ∈ S is (carefully) chosen so that the sum of the dimension of the fiber and the dimension of S equals dim(M).
Fixing notation, consider the convex cone Observe that R n +,≥ is exactly the range of σ on R n×t . Along with a point x ∈ R n +,≥ , we associate the partition P x = {P 1 , . . . , P ρx , P 0 } of the index set {1, . . . , n} so that x i = x j if and only if i, j ∈ P l , and x i > x j for any i ∈ P q and j ∈ P r with q > r. We assume that P 0 contains the indices of the zero coordinates in x, and we define p l := |P l |. It could be that p 0 = 0 for a given x. On the other hand, we have p l > 0 for all l = 1, . . . , ρ x . Recall the equality Here we used the observation For a partition P of [n], define the set ∆ P := {x ∈ R n +,≥ : P x = P}. The set of all such ∆'s defines an affine stratification of R n +,≥ . Let P * correspond to a stratum ∆ * in this stratification satisfying S ∩∆ * = ∅ and having maximal dimension among all strata that have a nonempty intersection with S. Then for any point x * ∈ S ∩∆ * , we can choose a sufficiently small is an open (in the Euclidean topology) subset of M. Taking into account that both S and M are equidimensional, we deduce Appealing to (2.1), we arrive at the formula Example 2.6 (Rank variety). Recall the rank variety R n×t r of matrices of rank at most r. In this case, S is the union of all coordinate planes in R n of dimension r and S C is the set of all r-dimensional coordinate planes in C n . Also, M C = C n×t r , the set of all matrices in C n×t of rank at most r.
Note that S is equidimensional. Then along with a point x * we have p * 0 = n − r and p * i = 1 for all i = 1, . . . , r. Applying (2.2) we get that the dimension of C n×t

Example 2.7 (Essential variety). The essential variety is
is known to be irreducible and of dimension six [9]. In this case, S ⊆ R 3 consists of the six lines defined by x 1 = ±x 2 , x 1 = ±x 3 and x 2 = ±x 3 with the remaining coordinate set to zero in each case. We can verify dim(E C ) = 6 using (2.2). Indeed, picking a generic point x * on the line x 1 = x 2 in R 3 + , we see that P x * has p * 0 = 1 and p * 1 = 2. Now applying the formula (2.2) we get dim(E C ) = 1 + 1 · 2 + 3 − 0 = 6.

Algebraic Singular Value Decompositions and GIT quotients
In this section we fix a Π ± n -invariant variety S ⊆ R n and the induced O(n)×O(t)invariant matrix variety M := σ −1 (S). The description of M as the preimage σ −1 (S) is not convenient when seeking to understand the algebraic geometric correspondences between M and S, since σ is not a polynomial map. Instead, we may equivalently write In this notation, it is clear that M is obtained from S by an algebraic group action -a description that is more amenable to analysis. Naturally then to understand geometric correspondences between the closures M C and S C , we search for a description analogous to (3.1), with M, S, O(n), and O(t) replaced by their Zariski closures M C , S C , O C (n), and O C (t). The difficulty is that an exact equality analogous to (3.1) usually fails to hold; instead, equality holds only in a certain generic sense that is sufficient for our purposes. We now make this precise.
3.1. Algebraic SVD. Our strategy revolves around an "algebraic singular value decomposition", a notion to be made precise shortly. Note that the common extension of a singular value decomposition (SVD) from real to complex matrices using unitary matrices, their conjugates, and the Hermitian metric does not fit well in the algebraic setting because unitary matrices form a real (but not a complex) variety and conjugation is not an algebraic operation. In particular, it is not suitable for studying the EDdegree of a matrix variety. Hence we will need an algebraic analog of SVD that uses complex orthogonal matrices. For a recent geometric treatment of SVD rooted in algebraic geometry see the survey [23].
Definition 3.1 (Algebraic SVD). We say that a matrix A ∈ C n×t admits an algebraic SVD if it can be factored as A = U DV ⊤ for some orthogonal matrices Not all matrices admit an algebraic SVD; indeed, this is the main obstruction to an equality analogous to (3.1)   Suppose A admits an algebraic SVD A = U Diag (d) V ⊤ for some orthogonal matrices U ∈ O C (n) and V ∈ O C (t), and a vector d ∈ C n . Then the numbers d 2 i are eigenvalues of A ⊤ A and AA ⊤ , and the columns of U are eigenvectors of AA ⊤ and the columns of V are eigenvectors of A ⊤ A, arranged in the same order as d i . We call the complex numbers d i the algebraic singular values of A. They are determined up to sign.
We record the following immediate consequence of Theorem 3.2 for ease of reference. Corollary 3.3. A matrix A ∈ C n×t has an algebraic SVD provided the eigenvalues of AA ⊤ are nonzero and distinct.
Suppose V is a variety over R or C. We say that a property holds for a generic point x ∈ V if the set of points x ∈ V for which the property holds contains an open dense subset of V (in Zariski topology). In this terminology, Theorem 3.2 implies that generic complex matrices A ∈ C n×t do admit an algebraic SVD.
We can now prove the main result of this section (cf. equation (3.1)).
2), we conclude that N S C ⊆ M C , as claimed. Moreover, clearly M is a subset of N S C , and hence the inclusion M C ⊆ N S C holds. We conclude the equality M C = N S C . Now suppose that Q contains an open dense subset of S C and consider the continuous polynomial map P : Noting the equations Q = S C and N Q = P (O C (n) × Q × O C (t)), we obtain Hence N Q is a dense subset of M C , as claimed. . , x 2 n ) ∀x ∈ S C }. We first claim that Ω is a variety. To see this, by [26, Proposition 2.6.4], the variety S C admits some Π ± n -invariant defining polynomials f 1 , . . . , f k ∈ C[x]. Since f j are invariant under coordinate sign changes, they are in fact symmetric polynomials in the squares x 2 1 , . . . , x 2 n . Then by the fundamental theorem of symmetric polynomials, we may write each f j as some polynomial q j in the quantities e i (x 2 1 , . . . , x 2 n ). We claim that Ω is precisely the zero set of {q 1 , . . . , q k }. By construction q j vanish on Ω. Conversely, suppose q j (y) = 0 for each j. Letting x 2 1 , . . . , x 2 n be the roots of the polynomial λ n − y 1 λ n−1 + · · · + (−1) n y n , we obtain a point x ∈ C n satisfying y i = e i (x 2 1 , . . . , x 2 n ) for each i. We deduce then that x lies in S C and hence y lies in Ω as claimed. We conclude that Ω is closed.
Observe the mapping π : M C → C n defined by π(X) = (e 1 (XX ⊤ ), . . . , e n (XX ⊤ )) satisfies π(N S C ) ⊆ Ω, and so we deduce π(M C ) = π(N S C ) ⊆ π(N S C ) ⊆ Ω. Hence for any y ∈ C n satisfying Diag (y) ∈ M C , there exists x ∈ S C satisfying e i (x 2 1 , . . . , x 2 n ) = e i (y 2 1 , . . . , y 2 n ) for each index i = 1 . . . , n. We deduce that x 2 1 , . . . , x 2 n and y 2 1 , . . . , y 2 n are all roots of the same characteristic polynomial of degree n. Taking into account that S C is Π ± n -invariant, we conclude that y lies in S C . The result follows. We conclude with the following two enlightening corollaries, which in particular characterize matrices in M C admitting an algebraic SVD. Proof. This follows immediately from Theorems 2.2, 3.2, and 3.6. From Theorem 3.4 we know N S C contains an open dense subset of M C . It follows from the above discussion that N S C is Euclidean dense in M C . Given X ∈ M C , we let x be the vector of the square roots of the eigenvalues of XX ⊤ , which is defined up to sign and order. We know there is a sequence X k : , and x k ∈ S C such that X k → X as k → ∞. Hence (e 1 (X k X ⊤ k ), . . . , e n (X k X ⊤ k )) → (e 1 (XX ⊤ ), . . . , e n (XX ⊤ )). Since roots of polynomials are continuous with respect to the coefficients [30, Theorem 1], we deduce that the roots of the characteristic polynomial det(λI − X k X ⊤ k ), namely ((x k 1 ) 2 , . . . , (x k n ) 2 ), converge to (x 2 1 , . . . , x 2 n ) up to a coordinate reordering of x k 's and x. Passing to a subsequence, we deduce that x k converge to x up to a signed permutation. Since S C is closed, we conclude that x lies in S C , as claimed.

ED critical points of an orthogonally invariant variety
We are now ready to prove our main results characterizing ED critical points of a data point Y ∈ C n×t with respect to an orthogonally invariant matrix variety M ⊆ R n×t . We first give the precise definition of an ED critical point; see [11, §2]. For any variety V over R or C, we let V reg be the open dense subset of regular points in V. Recall that if V is a union of irreducible varieties V i , then V reg is the union of V reg i minus the points in the intersection of any two irreducible components. In what follows, for any two vectors v, w ∈ C n , the symbol v ⊥ w means v ⊤ w = 0, and for any set Q ⊆ C n we define Q ⊥ := {v ∈ C n : v ⊤ w = 0 for all w ∈ Q} . Definition 4.1 (ED critical point, ED degree). Let V be a real variety in R n and consider a data point y ∈ C n . An ED critical point of y with respect to V is a point is the tangent space of V C at x. For any generic point y in C n , the number of ED critical points of y with respect to V is a constant; see [11] called the EDdegree of V and denoted by EDdegree(V).
Here is a basic fact that will be needed later. Proof. The proof is a dimensional argument explained in [11]. Without loss of generality assume that V C is irreducible. Consider the ED correspondence E V C , as defined in [11, §4], with its two projections π 1 on V C and π 2 on C n×t . Since π 1 is an affine vector bundle over V reg C , it follows that π 2 π −1 1 (V C \ W) has dimension smaller than nt. Remark 4.3. We mention in passing, that the ED degree of a variety V, as defined above equals the sum of the ED degrees of its irreducible components V i , which coincides with the original definition of ED degree in [11]. This follows from Lemma 4.2 by noting that the set V reg C ∩ (V i ) C is an open dense subset of (V i ) C for each i.
We say that two matrices X and Y admit a simultaneous algebraic SVD if there exist orthogonal matrices U ∈ O C (n) and V ∈ O C (t) so that both U ⊤ XV and U ⊤ Y V are diagonal matrices. Our first main result is that every ED critical point X of a generic matrix Y ∈ C n×t with respect to an orthogonally invariant variety M admits a simultaneous algebraic SVD with Y . The proof of this theorem relies on the following three lemmas.
Consider the map F : C n×n → C n×n given by W → W W ⊤ . Note that for any W, B ∈ C n×n and t ∈ R, one has  Proof. The "if" part follows because A ij − A ji = trace(A(E ij − E ji )) where E ij denotes the n × n matrix whose (i, j)-entry is one and all other entries are zero. The "only if" part follows by the same reasoning since {E ij − E ji } is a basis for the space of skew-symmetric matrices.
Lemma 4.7. Consider a matrix A ∈ C n×t and a diagonal matrix D ∈ C n×t with nonzero diagonal entries d i such that the squares d 2 i are distinct. Then if AD ⊤ and D ⊤ A are both symmetric, the matrix A must be diagonal.
Proof. The symmetry of AD ⊤ means A ij d j = A ji d i for any i, j = 1, . . . , n. In addition, the symmetry of D ⊤ A implies A ij d i = A ji d j for all i, j = 1, . . . , n and A ij d i = 0 for any i = 1, . . . , n and j > n. Therefore for any i, j, one has j for all i = j, we get A ij = 0 for all i = j, i, j = 1, . . . , n. Since the d i 's are all nonzero and A ij d i = 0 for any i = 1, . . . , n and j > n, we have A ij = 0 for any i = 1, . . . , n and j > n. Thus A is diagonal.
By Lemma 4.6, this means (D − A)A ⊤ is symmetric. Since AA ⊤ is symmetric, we have that DA ⊤ is symmetric; therefore the transpose AD ⊤ is symmetric. By considering F : O C (t) → M C given by W → U AW ⊤ , we get as above, that for any skew-symmetric matrix Z, and by Lemma 4.6, (D − A) ⊤ A is symmetric. Again, since A ⊤ A is symmetric, we get that D ⊤ A is symmetric. Since AD ⊤ and D ⊤ A are both symmetric, we conclude A is diagonal by Lemma 4.7, as claimed.
The next ingredient in our development is a version of Sard's Theorem in algebraic geometry (often called "generic smoothness" in textbooks); see [18, III, Corollary 10.7]. Lemma 4.9 (Generic smoothness on the target). Let V and W be varieties over C.
Consider a polynomial map f : V → W. Then there is an open dense subset W ′ of W reg (and hence of W) such that for any w ∈ W ′ and any point v ∈ V reg ∩ f −1 (w), the linear map ∇f (x) : We now establish a key technical result: a representation of the tangent space of M C at a generic matrix X ∈ M C in terms of the tangent space of S C at the vector of algebraic singular values of X. (a) A generic point X ∈ M C lies in M reg C , admits an algebraic SVD, and its vector of algebraic singular values lies in S reg C . Moreover, the tangent space T M C (X) admits the representation for any U ∈ O C (n), V ∈ O C (t), and x ∈ S reg C satisfying X = U Diag (x) V ⊤ . (b) A generic point x ∈ S C lies in S reg C . Moreover, for any U ∈ O C (n), V ∈ O C (t), the point X = U Diag (x) V ⊤ lies in M reg C , and satisfies (4.1).
Proof. We begin by proving claim (a). By Theorem 3.4 with Q = S reg C , a generic point X ∈ M C admits an algebraic SVD: is an open dense subset of M C , we can assume that X lies in M reg C . Consider the polynomial map P : By Lemma 4.9 we can assume that ∇P (U, x, V ) is surjective whenever we can write X = U Diag (x) V ⊤ for some U ∈ O C (n), V ∈ O C (t) and x ∈ S reg C . Therefore the description of tangent space in (4.1) follows from Leibniz rule on P and Lemma 4.5. Hence claim (a) is proved.
Next, we argue claim (b). To this end, let Θ be the dense open subset of M C guaranteed to exist by (a). We claim that we can assume that Θ is in addition orthogonally invariant. To see this, observe that all the claimed properties in (a) continue to hold on the dense, orthogonally invariant subset Γ : We are now ready to prove the main result of this paper, equation (⋆) from the introduction. As a byproduct, we will establish an explicit bijection between the ED critical points of a generic matrix Y = U Diag (y) V ⊤ ∈ C n×t on M and the ED critical points of y on S C . Theorem 4.11 (ED degree). Consider a Π ± n -invariant variety S ⊆ R n and the induced real variety M := σ −1 (S). Then a generic matrix Y ∈ C n×t admits a decomposition Y = U Diag (y) V ⊤ , for some matrices U ∈ O C (n), V ∈ O C (t), and y ∈ C n . Moreover, then the set of ED critical points of Y with respect to M is x is an ED critical point of y with respect to S}, In particular, equality EDdegree(M) = EDdegree(S) holds.
Proof. For generic Y ∈ C n×t , the eigenvalues of Y Y ⊤ are nonzero and distinct. Then by Corollary 3.3, we can be sure that Y admits an algebraic SVD. We fix such a decomposition Y = U Diag (y) V ⊤ , for some U ∈ O C (n), V ∈ O C (t), and y ∈ C n .
Let X be an ED critical point of Y with respect to M. By Theorem 4.4, we can assume that X and Y admit a simultaneous SVD, that is both U ′⊤ XV ′⊤ and U ′⊤ Y V ′⊤ are diagonal for some matrices U ′ ∈ O C (n), V ′ ∈ O C (t). Notice that the columns of U and U ′ are equal up to a sign change and a permutation. Similarly the first n columns of V and V ′ are equal up to a sign change and a permutation. Hence we may assume that X can be written as X = U Diag (x) V ⊤ for some x ∈ S C . By Lemmas 4.2 and 4.10, we can further assume that X lies in M reg C and x lies in S reg C , and moreover the tangent space T M C (X) at X = U Diag (x) V ⊤ is given in (4.1).
We will now show that x is an ED critical point of y with respect to S. To see this, observe the inclusion {U Diag (a) V ⊤ : a ∈ T S C (x)} ⊆ T M C (X). and hence 0 = trace(U Diag (y − x) V ⊤ (U Diag (a) V ⊤ ) ⊤ ) for any a ∈ T S C (x).
Simplifying, we immediately conclude (y − x) ⊤ a = 0 for any a ∈ T S C (x), and hence x is an ED critical point of y with respect to S.
Conversely, suppose x ∈ S reg C is an ED critical point of y with respect to S. Applying Theorem 3.4 with Q = C n , we deduce that if a set Q ⊆ C n contains an open dense set in C n , then contains an open dense subset of C n×t . Define now the matrix X := U Diag (x) V ⊤ . Then by Lemmas 4.2 and 4.10, we may assume that X is regular and the tangent space of M C at X is generated by all matrices of the form We will show by dividing the proof according to the three cases i),ii), iii) above. For i), observe where the last equality follows from Lemma 4.6. The computation for iii) is entirely analogous. For ii), we obtain where the last equation follows from the hypothesis that x is an ED critical point of y on S C . We conclude that X is an ED critical point of Y relative to M C , as claimed. The equality, EDdegree(M) = EDdegree(S), quickly follows.
In the first three examples, the set S is a subspace arrangement and hence its ED degree is the number of distinct maximal subspaces in the arrangement. We will elaborate on this situation in Section 5.
The matrix variety SL ± n consists of all matrices A ∈ C n×n satisfying det(A) = ±1. The ED degree of SL ± n was explicitly computed in [2]. We show below how our main theorem provides a simple alternate proof of their result.
The absolutely symmetric variety S in this case is H n := {x ∈ R n : x 1 x 2 · · · x n = ±1}. To compute the ED degree of H n , we add up the ED degrees of its two irreducible components H + n := {x ∈ R n : x 1 x 2 · · · x n = 1} and H − n := {x ∈ R n : x 1 x 2 · · · x n = −1}. To compute the ED degree of H + n , we begin with a point y ∈ C n . Then by a straightforward computation, x is an ED critical point of y with respect to H + n if and only if x solves the system By Bézout's Theorem, we know EDdegree(H + n ) ≤ n2 n−1 . We now argue that the data point y = 0 has n2 n−1 ED critical points with respect to H + n which proves that EDdegree(H + n ) = n2 n−1 . When y = 0, the system (4.3) is equivalent to which has n2 n−1 solutions in (H + n ) C . Indeed, choose x 1 such that x n 1 = ±1 (2n choices); then choose x i for i = 2, . . . , n−1 such that x 2 i = x 2 1 (2 choices for each i); finally set x n = 1 x1···xn−1 . Hence EDdegree(H + n ) = n2 n−1 . Similarly, EDdegree(H − n ) = n2 n−1 , and therefore we conclude EDdegree(H n ) = n2 n .
The variety F n,t,d = {X ∈ R n×t : X d = 1} is the unit ball of the Schatten When d is even, the corresponding absolute symmetric variety is the affine Fermat hypersurface The ED degree of a Fermat hypersurface was computed in [19].

Orthogonally invariant varieties from subspace arrangements
In this section, we augment the results of the previous section in the special (and important) case when S is a subspace arrangement. Many important matrix varieties, such as the rank varieties R n×t r and the essential variety E, fall in this category. Recall that S is a subspace arrangement if S can be written as a union of finitely many affine subspaces {S i } k i=1 of R n . Assuming that the representation of S is chosen in such a way that S i is not contained in S j for any distinct i, j, we call S i the affine components of S. The following result follows directly from Theorem 4.11.
Moreover, a general data point Y in R n×t has exactly k ED-critical points with respect to M: for any decomposition Y = U Diag (σ(Y )) V ⊤ with orthogonal matrices U ∈ O(n) and V ∈ O(t), the set of ED-critical points is precisely {U Diag (x) V ⊤ : x is the orthogonal projection of σ(Y ) onto S i }.
In particular, all ED critical points of Y with respect to M are real.
Proof. Let Θ be the dense open subset of C n×t guaranteed to exist by Theorem 4.11. Clearly we can also assume that each matrix Y ∈ Θ has EDdegree(M) many ED critical points with respect to M. A standard argument shows that the set Θ R := {Y ∈ R n×t : Y ∈ Θ} is a dense open subset of R n×t . Fix a matrix Y ∈ Θ R and consider a singular value decomposition Y = U Diag (σ(Y )) V ⊤ with orthogonal matrices U ∈ O(n) and V ∈ O(t). By Theorem 4.11, the set of ED critical points of Y with respect to M is given by {U Diag (x) V ⊤ : x is an ED critical point of σ(Y ) with respect to S}.
Since σ(Y ) is a real vector, the ED critical points of σ(Y ) with respect to S are precisely the orthogonal projections of σ(Y ) on each component S i . Therefore we deduce k = EDdegree(S) = EDdegree(M).
The first three examples in Example 4.12 illustrate Corollary 5.1. Typically, as the data point y ∈ R n varies, the number of real ED critical points of y with respect to a variety V ⊆ R n varies. Corollary 5.1 shows that when S is a subspace arrangement, all ED critical points of a real data point with respect to M = σ −1 (S) are again real and their number is constant. This unusual feature is easy to see using Theorem 4.11 that creates a bijection between the ED critical points of M and S, but is not at all obvious if S is not in the picture.
In common examples, outside of the subspace arrangement case, all ED critical points of a real data point may be purely imaginary and the number of real critical points typically varies as the data point moves around. For instance, the hyperbola H n in Example 4.12 can have complex ED critical points for a generic y ∈ R n . The same is therefore true for SL ± n . In a sense, Corollary 5.1 generalizes the fact that the pairs of singular vectors of a real matrix are real. Indeed, the pairs of singular vectors of a real matrix Y correspond to the ED critical points of Y with respect to the orthogonally invariant variety of rank one matrices; the corresponding absolutely symmetric variety is the union of all coordinate axes.
Remark 5.2. Results analogous to those in this paper hold for symmetric matrices under the action of the orthogonal group U · A = U AU ⊤ . More precisely, consider the space of real n × n symmetric matrices S n . A set M ⊆ S n is orthogonally invariant provided U MU ⊤ = M for all matrices U ∈ O(n). Such a set M can be written as λ −1 (S) where λ : S n → R n assigns to each matrix X the vector of its eigenvalues in a nonincreasing order and S is the diagonal restriction S = {x ∈ R n : Diag (x) ∈ M}. Conversely any permutation invariant set S ⊆ R n gives rise to the orthogonally invariant set λ −1 (S). Similar techniques to the ones developed here can then be used to study the correspondence between ED critical points of algebraic varieties S and λ −1 (S). This research direction deserves further investigation.