---
author:
- 'Madeline Brandt, DJ Bruce, Taylor Brysiewicz, Robert Krone, Elina Robeva'
bibliography:
- 'ref.bib'
title: 'The degree of $\operatorname{SO}(n)$'
---

Introduction {#introsect}
============

The *special orthogonal group* $\operatorname{SO}(n,\mathbb{R})$ is the group of automorphisms of $\mathbb{R}^n$ which preserve the standard inner product and have determinant equal to one. The complex special orthogonal group is the complexification of the special orthogonal group and can be thought of more explicitly as the group of matrices $$\operatorname{SO}(n):=\operatorname{SO}(n,{\mathbb{C}})=\left\{M\in \text{Mat}_{n,n}({\mathbb{C}}) \; | \; \det M =1, \quad M^{t}M=\text{Id}\right\}.$$ As these conditions are polynomials in the entries of such a matrix, we view $\operatorname{SO}(n)$ as a complex variety.

Recall that the degree of a complex variety $X$ is the generic number of intersection points of $X$ with a linear space of complementary dimension. Problem $4$ on Grassmannians in [@fitness] asks for a formula for the degree of the of $\operatorname{SO}(n)$. Our primary result is the following theorem, which answers this question completely.

[theorem]{}[maintheorem]{} \[degson\] The degree of $\operatorname{SO}(n)$ is given by $$\deg \operatorname{SO}(n)=2^{n-1}\det \left( {2n-2i-2j}\choose{n-2i} \right)_{1\leq i , j \leq \lfloor{\frac n 2}\rfloor}.$$

Our proof of Theorem \[degson\] uses a formula of Kazarnovskij [@kazarnovskii] (see also Theorem \[Kazarnovskij\]) for the degree of the image of a representation of a connected, reductive, algebraic group over an algebraically closed field. By applying this formula to the case of the standard representation of $\operatorname{SO}(n)$ we are able to express the degree of $\operatorname{SO}(n)$ in terms of its root data and other invariants.

In addition to this result, Theorem \[non-intersecting\] provides a combinatorial interpretation of this degree in terms of non-intersecting lattice paths. In contrast to Theorem \[degson\], the combinatorial statement has the immediate benefit of being obviously non-negative.

Let ${\Bbbk}$ be a field of characteristic zero. We can define $\operatorname{SO}(n,{\Bbbk})$ using the same system of equations since they are defined over the prime field ${\mathbb{Q}}$. For ${\Bbbk}$ that is not algebraically closed, the degree of a variety can be defined in terms of the Hilbert series of its coordinate ring. Since the Hilbert series does not depend on the choice of ${\Bbbk}$, the degree does not either. We choose to work over ${\mathbb{C}}$ not only for simplicity, but also so that we may use the above definition of degree.

Our methods are not specific to $\operatorname{SO}(n)$. The same approach can be used to compute the degree of other algebraic groups. For example, toward the end of Section \[sec:degson\] we provide a similar closed formula for the degree of the symplectic group. This formula is also interpreted combinatorially in Section \[NILP\].

In order to verify Theorem \[degson\], as well as explore the structure of $\operatorname{SO}(n)$ in further depth, it is useful to compute this degree explicitly. We were able to do this for small $n$ using symbolic and numerical computations. A comparison of the success of these two approaches, together with our formula from Theorem \[degson\], is illustrated by the following table.

\[fig:SO\]

   $\mathbf{n}$   **Symbolic**   **Numerical**   **Formula**
  -------------- -------------- --------------- -------------
        2              2               2              2
        3              8               8              8
        4              40             40             40
        5             384             384            384
        6              -             4768           4768
        7              -            111616         111616
        8              -               -           3433600
        9              -               -          196968448

  : Degree of $\operatorname{SO}(n)$ computed in various ways

This project started in the spring of 2014, when Benjamin Recht asked the fifth author to describe the geometry of low-rank semidefinite programming (see Section \[SDP\]). In particular, he asked why the augmented Lagrangian algorithm for solving this problem [@BM] almost always recovers the correct optimum despite the existence of multiple local minima. It quickly became clear that to even compute the number of local extrema, one needs to know the degree of the orthogonal group. In Section \[SDP\] we find a formula for the number of critical points of low-rank semidefinite programming (see Theorem \[thm:LRSDP\]).

The rest of this article is organized as follows. In Section \[backgroundsect\] we give the reader a brief introduction to algebraic groups and state Kazarnovskij’s Theorem. Section \[sec:degson\] proves Theorem \[degson\] by applying Kazarnovskij’s Theorem and simplifying the resulting expressions. After simplification, we are left with a determinant of binomial coefficients which can be interpreted combinatorially using the celebrated Gessel-Viennot lemma which we describe in Section \[NILP\]. The relationship between the degree of $\operatorname{SO}(n)$ and the degree of low-rank semidefinite programming is elaborated upon in Section \[SDP\]. Section \[Computational\] contains descriptions of the symbolic and numerical techniques involved in the explicit computation of $\deg \operatorname{SO}(n)$. Finally, in Section \[reality\] we explore questions involving the real points on $\operatorname{SO}(n)$.

Background {#backgroundsect}
==========

In this section we provide the reader with the necessary language to understand the statement of Kazarnovskij’s Theorem (see Theorem \[Kazarnovskij\]), our main tool for determining the degree of $\operatorname{SO}(n)$. We invite those who already are familiar with Lie theory to skip to the statement of Theorem \[Kazarnovskij\] and continue to Section \[sec:degson\] for our main result. We note, that aside from applying Theorem \[Kazarnovskij\], no understanding of the material in this section is necessary for understanding the remainder of the proof of Theorem \[degson\]. A more thorough treatment of the theory of algebraic groups can be found in [@derksen; @fulton; @humphreys].

An *algebraic group* $G$ is a variety equipped with a group structure such that multiplication and inversion are both regular maps on $G$. When the unipotent radical of $G$ is trivial and $G$ is over an algebraically closed field, we say that $G$ is a *reductive group*. Throughout this section, we let $G$ denote a connected reductive algebraic group over an algebraically closed field ${\Bbbk}$. Let ${{\mathbb{G}}_{\mathrm{m}}}$ denote the multiplicative group of ${\Bbbk}$, so as a set, ${{\mathbb{G}}_{\mathrm{m}}}= {\Bbbk}\setminus \{0\}$. Let $T$ denote a fixed maximal torus of $G$. By *maximal torus*, we mean a subgroup of $G$ isomorphic to ${{\mathbb{G}}_{\mathrm{m}}}^r$ and which is maximal with respect to inclusion. The number $r$ is well-defined and is called the *rank* of $G$. After fixing $T$, we define the *Weyl group* of $G$, denoted $W(G)$, to be the quotient of the normalizer of $T$ by its centralizer, $W(G) = N_G(T)/Z_G(T)$. Like $r$, $W(G)$ does not depend on the choice of $T$ up to isomorphism.

\[maxTori\] We can parametrize $\operatorname{SO}(2,{\mathbb{C}})$ by ${{\mathbb{G}}_{\mathrm{m}}}$ via the map $$\mathbf{R}(t) := \frac{1}{2}\begin{pmatrix}
    t+t^{-1}    & -i(t-t^{-1}) \\
    i(t-t^{-1}) &  t+t^{-1}
   \end{pmatrix},$$ which is in fact a group isomorphism. (Note that $\mathbf{R}(e^{i\theta})$ is the rotation matrix by angle $\theta$.) Therefore $\operatorname{SO}(2)$ has rank 1.

Fix $r \in \mathbb{N}$. Then $$\begin{aligned}
T_{2r}&:=\left\{
\begin{pmatrix}
\mathbf{R}(t_1) & 0 & 0 & \cdots & 0\\
0 & \mathbf{R}(t_2) & 0 & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \cdots & \mathbf{R}(t_r)
\end{pmatrix} \Bigg|  t_i \in {{\mathbb{G}}_{\mathrm{m}}}\right\}\cong \operatorname{SO}(2)^{r}\subset \operatorname{SO}(2r)\\
 T_{2r+1}&:=\left\{
\begin{pmatrix}
\mathbf{R}(t_1) & 0 & 0 & \cdots & 0 & 0\\
0 & \mathbf{R}(t_2) & 0 & \cdots & 0 & 0\\
\vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\
0 & 0 & 0 & \cdots & \mathbf{R}(t_r) & 0\\
0 & 0 & 0 & \cdots & 0 & 1
\end{pmatrix}\; \Bigg| \; t_i \in {{\mathbb{G}}_{\mathrm{m}}}\right\}\cong \operatorname{SO}(2)^{r}\subset \operatorname{SO}(2r+1)\end{aligned}$$ are maximal tori of rank $r$ of their respective groups. Therefore, $\text{rank}(\operatorname{SO}(2r))=\text{rank}(\operatorname{SO}(2r+1))=r$ and we see that the rank of $\operatorname{SO}(n)$ depends fundamentally on the parity of $n$.

The *character group* $M(T)$ is the set of algebraic group homomorphisms from $T$ to ${{\mathbb{G}}_{\mathrm{m}}}$, i.e. group homomorphisms defined by polynomial maps, $$M(T):=\operatorname{Hom}_{{\mathbf{AlgGrp}}}(T,{{\mathbb{G}}_{\mathrm{m}}}).$$ Since $T$ is isomorphic to ${{\mathbb{G}}_{\mathrm{m}}}^r$, all such homomorphisms must be of the form $$(t_1,\ldots,t_r) \mapsto t_1^{a_1}\cdots t_r^{a_r}$$ with $a_1,\ldots,a_r$ integers. This character group is isomorphic to ${\mathbb{Z}}^r$ and for this reason it is often called the character lattice. Dual to this is the *group of 1-parameter subgroups* $$N(T):=\operatorname{Hom}_{{\mathbf{AlgGrp}}}({{\mathbb{G}}_{\mathrm{m}}},T),$$ which is also isomorphic to ${\mathbb{Z}}^r$. Indeed, each 1-parameter subgroup is of the form $t \mapsto (t^{b_1},\ldots,t^{b_r})$ for integers $b_1,\ldots,b_r$. There exists a natural bilinear pairing between $N(T)$ and $M(T)$, given by $$\begin{aligned}
M(T)\times N(T)&\rightarrow \operatorname{Hom}_{{\mathbf{AlgGrp}}}({{\mathbb{G}}_{\mathrm{m}}},{{\mathbb{G}}_{\mathrm{m}}})\cong{\mathbb{Z}}\\
\langle \chi, \sigma \rangle &\mapsto \chi \circ \sigma.\end{aligned}$$

Now if $\rho:G\rightarrow{}\operatorname{GL}(V)$ is a representation of $G$ we attach to it special characters called weights. A *weight* of the representation $\rho$ is a character $\chi\in M(T)$ such that the set $$V_\chi:=\bigcap_{s\in T}\ker(\rho(s)-\chi(s)\operatorname{Id}_V)$$ is non-trivial. This condition is equivalent to saying that all of the matrices in $\{\rho(s) \; | \; s\in T\}$ have a simultaneous eigenvector $v\in V$ such that the associated eigenvalue for $\rho(s)$ is $\chi(s)$. We will use $C_V$ to denote the convex hull of the weights of the representation $\rho$.

\[ex:weight\] An example that will be important for us later will be the standard representation coming from the natural embedding $\rho:\operatorname{SO}(n) \to \operatorname{GL}({\mathbb{C}}^n)$. For any $t \in {{\mathbb{G}}_{\mathrm{m}}}$, the matrix $\mathbf{R}(t) \in \operatorname{SO}(2)$ has eigenvectors $e_1 + ie_2$ and $e_1 - ie_2$ with eigenvalues $t$ and $t^{-1}$ respectively. From the explicit description of $T$ in Example \[maxTori\] we see that the eigenvectors of $\rho(t_1,\ldots,t_r)$ are all vectors of the form $e_{2j-1} \pm ie_{2j}$ with $1\leq j \leq r$ and the eigenvalues are $t_1^{\pm 1},\ldots,t_r^{\pm 1}$. These eigenvalues, viewed as characters, are the weights of $\rho$. Additionally when $n = 2r+1$, we have that $e_{2r+1}$ is an eigenvector with eigenvalue 1, corresponding to the trivial character.

Another representation of a matrix group $G \subseteq \operatorname{End}(V)$ is the *adjoint representation*, $\operatorname{Ad}:G \to \operatorname{GL}(\operatorname{End}(V))$, with $\operatorname{Ad}(g)$ the linear map defined by $A \mapsto gAg^{-1}$. The *roots* of $G$ are the weights of the adjoint representation. Given a linear functional $\ell$ on $M(T)$, we define the *positive roots* of $G$ with respect to $\ell$ to be the roots $\chi$ such that $\ell(\chi)>0$. We denote the positive roots of $G$ by $\alpha_1,\ldots,\alpha_l$. For the algebraic groups in this paper, we can choose $\ell$ to be the inner product with the vector $(r,r-1,\ldots,1)$ so that a root of the form $e_j-e_k$ is positive if and only if $j<k$. To each root $\alpha$, we associate a *coroot* $\check \alpha$, defined to be the linear function $\check \alpha (\vec{x}):= \frac{2\langle\vec{x},\alpha\rangle}{\langle\alpha,\alpha\rangle}$ where $\langle , \rangle$ must be $W(G)$-invariant. Throughout this paper, we fix this to be the standard inner product.

We now compute the roots of $\operatorname{SO}(n)$, starting with $n$ even. It can be shown that the simultaneous eigenvectors of $\operatorname{Ad}(s)$ over all $s \in T$ are matrices $A$ with the following structure. These matrices are zero outside a $2\times 2$ block $B$ in rows $2j-1,2j$ and columns $2k-1,2k$ for some $1\leq j,k \leq r$. Furthermore, $B = v_1v_2^T$ with each $v_k$ equal to one of the eigenvectors of $\mathbf{R}(t)$, $e_1 \pm ie_2$. Indeed, suppose $s \in T$ has blocks along the diagonal $\mathbf{R}(t_j)$ with $t_1,\ldots,t_r \in {{\mathbb{G}}_{\mathrm{m}}}$. Then $\operatorname{Ad}(s)(A)$ will also be zero except in the same $2\times 2$ block, and that block will be $$\mathbf{R}(t_j)B\mathbf{R}(t_k)^T = t_j^{\pm 1}t_k^{\pm 1}B,$$ where the signs in the exponents depend on the choices of $v_1$ and $v_2$. Thus the roots of $\operatorname{SO}(2r)$ are the characters of the form $t_j^{\pm 1}t_k^{\pm 1}$ for $1\leq j,k \leq r$.

In the case that $n$ is odd, $A$ has an extra row and column. Consider $A$ with support only in the last column. Then for $s \in T$, $\operatorname{Ad}(s)(A) = sAs^{-1}$ but $s^{-1}$ acts trivially on the left, while $s$ acts on the last column as an element of $\operatorname{GL}({\mathbb{C}}^n)$ as in the standard representation. As in Example \[ex:weight\] we get weights $t_1^{\pm 1},\ldots,t_r^{\pm 1},1$. The same weights appear for $A$ with support in the last row.

Associated to $G$ is a Lie algebra $\mathfrak{g}$, which comes equipped with a Lie bracket $[\ ,\ ]$. A *Cartan subalgebra* $\mathfrak{h}$ is a nilpotent subalgebra of $\mathfrak{g}$ that is self-normalizing, meaning if $[x,y] \in \mathfrak{h}$ for all $x \in \mathfrak{h}$, then $y \in \mathfrak{h}$. Let $S(\mathfrak{h}^*)$ be the ring of polynomial functions on $\mathfrak{h}$. The Weyl group $W(G)$ acts on $\mathfrak{h}$, and this extends to an action of $W(G)$ on $S(\mathfrak{h}^*)$. The space $S(\mathfrak{h}^*)^{W(G)}$ of polynomials which are invariant up to the action of $W(G)$ is generated by $r$ homogeneous polynomials whose degrees, $c_1+1,\ldots,c_r+1$, are uniquely determined. The values $c_1, \ldots, c_r$ are called *Coxeter exponents*.

We are now prepared to state Kazarnovskij’s theorem.

\[Kazarnovskij\] Let $G$ be a connected reductive group of dimension $m$ and rank $r$ over an algebraically closed field. If $\rho:G\rightarrow{}\operatorname{GL}(V)$ is a representation with finite kernel then, $$\deg\overline{\rho\left(G\right)}=\frac{m!}{|W(G)|(c_1!c_2!\cdots c_r!)^2|\ker(\rho)|}\int_{C_V}(\check{\alpha}_{1}\check{\alpha}_2\cdots\check{\alpha}_l)^2dv.$$ where $W(G)$ is the Weyl group, $c_i$ are Coxeter exponents, $C_V$ is the convex hull of the weights, and $\check  \alpha_i$ are the coroots.

If $\rho$ is the standard representation for an algebraic group $G$, then it follows that $\deg \overline{\rho(G)}=\deg G$. Therefore, in order to compute $\deg \operatorname{SO}(n)$, all we must do is apply this theorem for the standard representation of $\operatorname{SO}(n)$. The relevant data for this theorem is given in Table \[data\] below for $\operatorname{SO}(n)$ and $\operatorname{Sp}(n)$.

\[data\]

[ l c c c c c c]{} Group& Dimension& Rank & Positive Roots & Weights & $|W(G)|$ & Coxeter Exponents\
\
$\operatorname{SO}(2r)$& ${2r}\choose{2}$ & $r$ &$\{e_i \pm e_j\}_{ i<j }$ & $\{\pm e_i\}$ & $r!2^{r-1}$ & $1,3,\ldots,2r-3,r-1$\
\
$\operatorname{SO}(2r+1)$ & ${2r+1}\choose{2}$& $r$ & $\{e_i \pm e_{j}\}_{i<j} \cup \{e_i\}$ & $\{\pm e_i\}$ & $r! 2^r$ & $1,3, 5, \ldots, 2r-1$\
\
$\operatorname{Sp}(r)$ & ${2r}\choose{2}$ & $r$ &$\{e_i \pm e_j\}_{i<j }\cup\{2e_i\}$ & $\{\pm e_i\}$ & $r! 2^r$ & $1,3, 5, \ldots, 2r-1$\
\

Main Result: The Degree of $\operatorname{SO}(n)$ {#sec:degson}
=================================================

We now prove our main result, Theorem \[degson\]. At the end of this section we use the same method to obtain a formula for the degree of the symplectic group.

We begin by directly applying Theorem \[Kazarnovskij\] to $\operatorname{SO}(2r)$ and $\operatorname{SO}(2r+1)$ to obtain

$$\begin{aligned}
\label{eqn:even-int}
\deg\operatorname{SO}(2r)&=\frac{\displaystyle \binom{2r}{2}!}{\displaystyle r!2^{r-1}(r-1)!^2\prod_{k=1}^{r-1}(2k-1)!^2} \int_{C_V} \left(\prod_{1\leq i<j\leq r}(x_i^2-x_j^2)^2\right)dv,\\
\label{eqn:odd-int}
\deg\operatorname{SO}(2r +1) &= \frac{\displaystyle \binom{2r +1}{2}!}{r!2^r \displaystyle \prod_{k=1}^r(2k-1)!^2} \int_{C_V} \left(\prod_{1\leq i<j\leq r}(x_i^2-x_j^2)^2\prod_{i=1}^r(2x_i)^2\right)dv.\end{aligned}$$

Thus, to compute the degree of $\operatorname{SO}(n)$ it suffices to find formulas for the integrals above. We do this by first expanding the integrand into monomials, and then integrating the result. We use the well-known expression for the determinant of the Vandermonde matrix, $$\prod_{1\leq i < j\leq r}(y_j-y_i)=\sum_{\sigma\in S_r}\left(\operatorname{sgn}(\sigma)\prod_{i=1}^r y_i^{\sigma(i)-1}\right).$$ Substituting $y_i = x_i^2$ and squaring the entire expression yields $$\label{rewrite-integrand}
 \prod_{1\leq i<j\leq r}(x_i^2-x_j^2)^2 = \sum_{\sigma,\tau \in S_r}\left(\operatorname{sgn}(\sigma\tau) \prod_{i=1}^r x_i^{2\sigma(i)+2\tau(i)-4}\right).$$ Additionally, we point out that every variable in the integrand is being raised to an even power and $C_V$ is the convex hull of weights, $\{\pm e_i\}$. Because of this symmetry, the integrals over $C_V$ are $2^r$ times the same integrals over $\Delta_r$, the standard $r$-simplex. We have now reduced the computation of this integral to understanding the integral of any monomial over the standard simplex. The following proposition provides a formula for this.

\[integral-monomial\] Let $\Delta_{r}\subset \mathbb{R}^{r}$ be the standard $r$-simplex. If $\mathbf{a}=(a_1,\ldots,a_r)\in \mathbb{Z}_{>0}^r$ then $$\int_{\Delta_r}\mathbf{x}^\mathbf{a}d\mathbf{x}=\int_{\Delta_r}x_1^{a_1}x_{2}^{a_2}\cdots x_{r}^{a_r}dx_1dx_2\cdots dx_r=
\frac{1}{(r+\sum a_i)!}\prod_{i=1}^r a_i!.$$

We can now get expressions for the integrals in (\[eqn:even-int\]) and (\[eqn:odd-int\]) directly by applying (\[rewrite-integrand\]) and Proposition \[integral-monomial\].

\[two-integrals\] Let $I_{even}(r)$ and $I_{odd}(r)$ denote the integrals in (\[eqn:even-int\]) and (\[eqn:odd-int\]) respectively. Then, $$I_{even}(r) =\frac{r!2^r}{\binom{2r}{2}!}\det\left((2i+2j-4)!\right)_{1\leq i,j\leq r}.$$ $$I_{odd}(r) =\frac{r!2^{3r}}{\binom{2r+1}{2}!}\det\left((2i+2j-2)!\right)_{1\leq i,j\leq r}.$$

As mentioned above, we can compute $I_{odd}$ by considering the integrand only over the simplex. This, along with equation gives us that $$\begin{aligned}
I_{odd}(r) &= 2^r \int_{\Delta_r} \prod_{1\leq i<j\leq r} (x_i^2-x_j^2)^2 \prod_{i=1}^r (2x_i)^2 dv\\
&= 2^r \int_{\Delta_r} \left(\sum_{\sigma,\tau \in S_r}\operatorname{sgn}(\sigma\tau) \prod_{i=1}^r x_i^{2\sigma(i)+2\tau(i)-4}\right) \prod_{i=1}^r(2x_i)^2 dv\\
&= 2^{3r} \sum_{\sigma,\tau \in S_r}\operatorname{sgn}(\sigma\tau)\int_{\Delta_r}\prod_{i=1}^r x_i^{2\sigma(i)+2\tau(i)-2} dv.\end{aligned}$$ As the integrand is homogeneous of degree $4\binom{r}{2}+2r$, applying Proposition \[integral-monomial\] and simplifying yields $$\begin{aligned}
I_{odd}(r)
&= \frac{2^{3r}}{\left(4\binom{r}{2}+3r\right)!} \sum_{\sigma,\tau\in S_r} \operatorname{sgn}(\sigma\tau) \prod_{i=1}^r (2\sigma(i)+2\tau(i)-2)!,\end{aligned}$$ which after replacing $i$ with $\sigma^{-1}(i)$ gives us $$\prod_{i=1}^r(2\sigma(i)+2\tau(i)-2)! = \prod_{i=1}^r(2i+2\tau\sigma^{-1}(i)-2)!.$$ Let $\rho = \tau\sigma^{-1}$. Over all pairs $\sigma,\tau \in S_r$, the permutation $\rho$ appears as each permutation in $S_r$ exactly $r!$ times, and $\operatorname{sgn}(\sigma\tau) = \operatorname{sgn}(\rho)$. Therefore, we have that $$\begin{aligned}
I_{odd}(r)
&= \frac{r!2^{3r}}{\left(4\binom{r}{2}+3r\right)!} \sum_{\rho\in S_r} \operatorname{sgn}(\rho) \prod_{i=1}^r (2i+2\rho(i)-2)!\\
&= \frac{r!2^{3r}}{\binom{2r+1}{2}!} \det\left((2i+2j-2)!\right)_{1\leq i,j\leq r}.\end{aligned}$$ The derivation of $I_{even}$ follows precisely the same steps.

Theorem \[degson\] now follows directly from the subsequent simplification.

$$\begin{aligned}
\deg \operatorname{SO}(2r+1) &= \frac{2^{2r}}{(1!3!\cdots(2r-1)!)^2} \det ((2i+2j-2)!)\\
&=\frac{2^{2r}}{(1!2!\cdots (2r-1)!)} \det\left(\frac{(2i+2j-2)!}{(2i-1)!}\right)\\
&=2^{2r}\det\left(\frac{(2i+2j-2)!}{(2i-1)!(2j-1)!}\right)\\
&=2^{2r}\det\left(\binom{2i+2j-2}{2i-1}\right)_{1\leq i,j\leq r}.\end{aligned}$$

Reversing the order of the rows and columns of the final matrix and reindexing produces the formula given in Theorem \[degson\]. Similarly, for the even case, we have

$$\begin{aligned}
\deg \operatorname{SO}(2r) &= \frac{2}{(1!3!\cdots(2r-3)!(r-1)!)^2} \det ((2i+2j-4)!)\\
&= \frac{2 \cdot (2^{r-1})^2}{(1!3!\cdots(2r-3)!2\cdot 4 \cdots (2r-2))^2} \det ((2i+2j-4)!)\\
&= 2^{2r-1} \det \left(\frac{(2i+2j-4)!}{(2i-2)!(2j-2)!}\right)\\
&=2^{2r-1}\det\left(\binom{4r-2i-2j}{2r-2i}\right)_{1\leq i,j\leq r}.\end{aligned}$$

This finishes the proof of Theorem \[degson\].

Since the orthogonal group $\operatorname{O}(n)$ has two components that are isomorphic to $\operatorname{SO}(n)$, we immediately get a formula for the degree of $\operatorname{O}(n)$.

\[degOn\]

The degree of $\operatorname{O}(n)$ is given by $$\deg \operatorname{O}(n)=2^{n}\det \left( {2n-2i-2j}\choose{n-2i} \right)_{1\leq i , j \leq \lfloor{\frac n 2}\rfloor}.$$

Furthermore, as mentioned in the introduction, there is no reason, [*a priori*]{}, that the steps taken in this section are particular to $\operatorname{SO}(n)$. We now apply these methods to find the degree of $\operatorname{Sp}(r)$, the group of (complex) symplectic matrices.

Recall the *symplectic group* over ${\mathbb{C}}$ is defined to be $$\operatorname{Sp}(r):=\operatorname{Sp}(r,{\mathbb{C}}) = \{ M \in \text{Mat}_{2r,2r}({\mathbb{C}}) \ |\ M^T \Omega M = \Omega\},$$ where $$\Omega =
\begin{pmatrix}
0 & I_r \\
-I_r & 0
\end{pmatrix}.$$

\[thm:symplectic\] The degree of $\operatorname{Sp}(r)$ is given by $$\deg \operatorname{Sp}(r) =\det\left({2i + 2j - 2 \choose 2i-1}\right)_{1\leq i,j\leq r}.$$

For $1 \leq r \leq 5$ the values of $\deg \operatorname{Sp}(r)$ are $2,24,1744,769408,2063048448,\ldots$. This was verified using both numerical and symbolic techniques up to $r=3$.

This is an application of Kazarnovskij’s result which is completely analogous to the computation for the special orthogonal group. The integral is the same as the one for $\operatorname{SO}(2r+1)$ up to factors of 2, so it is evaluated in the same way, and then the expression can be simplified $$\begin{aligned}
\deg \left(\text{Sp}(r)\right) &=\frac{(r(2r+1))!}{r! 2^r (1!3!\cdots(2r-1)!)^2}\int_{C_V} \left(\prod_{1\leq i<j\leq r}(x_i-x_j)^2(x_i+x_j)^2\prod_{i=1}^r x_i^2\right)dv \\
&=\frac{1}{(1!3!\cdots(2r-1)!)^2} \det\left((2i+2j-2)!\right)_{1\leq i,j\leq r}\\
&=\det\left({2i + 2j - 2 \choose 2i-1}\right)_{1\leq i,j\leq r}.\end{aligned}$$

We remark that our formula for $\deg \text{Sp}(r)$ is particularly interesting because the determinant in Theorem \[thm:symplectic\] is the same as the determinant in Theorem \[degson\] when $n=2r+1$.

\[cor:sp\] $$\deg \operatorname{SO}(2r+1)=2^{2r}\deg \text{Sp}(r)$$

Sending the $(i,j)$ entry of the matrix in Theorem \[thm:symplectic\] to the ${(r-i+1,r-j+1)}$ entry does not change the determinant and gives us that $$\deg \text{Sp}(r)=\det\left({4r+2-2i-2j \choose 2r+1-2i}\right)_{1\leq i,j\leq r}.$$ When $n=2r+1$, this is the matrix appearing in Theorem \[degson\] and all that is different is the coefficient in front. Accounting for this coefficient finishes the proof.

Non-Intersecting Lattice Paths {#NILP}
==============================

The formulas given in the previous section for the degrees of $\operatorname{SO}(n),\operatorname{O}(n),$ and $\text{Sp}(r)$ can be interpreted as a count of non-intersecting lattice paths via the Gessel-Viennot Lemma [@GV].

\[GV\] Let $A=\{a_1, \ldots,a_r\}$, $B=\{b_1, \ldots,b_r\}$ be collections of lattice points in $\mathbb{Z}^2$. Let $M_{i,j}$ be the number of lattice paths from $a_i$ to $b_j$ using only unit steps in either the North or East direction. If the only way that a system of these lattice paths from $A \to B$ do not cross each other is by sending $a_i\mapsto b_i$, then the determinant of $M$ equals the number of such non-intersecting lattice paths.

The number of lattice paths from $(0,0)$ to $(i,j)$ is the binomial coefficient ${i+j} \choose i$. Since the matrix involved in the formulas for the degrees of $\operatorname{SO}(n),$ $\operatorname{O}(n),$ and $\text{Sp}(r)$ has binomial coefficients as entries, it is natural to search for a interpretation of its determinant via Gessel-Viennot.

\[non-intersecting\] Let $N(n)$ count the number of non-intersecting lattice paths from $A(n):=\{a_i\}_{i=1}^{\lfloor \frac n 2 \rfloor}$ to $B(n):=\{b_j\}_{j=1}^{\lfloor \frac n 2 \rfloor}$ where $a_i=(2i-n,0)$ and $b_j=(0,n-2j)$. Then $$\begin{aligned}
\deg\operatorname{SO}(n) &= 2^{n-1}N(n), \\
\deg\operatorname{O}(n) &= 2^{n}N(n), \\
\deg\text{Sp}(r) &= N(2r+1).\end{aligned}$$

It is enough to prove this theorem for $\operatorname{SO}(n)$ and apply Corollaries \[degOn\] and \[cor:sp\]. Noticing that the matrix appearing in Theorem \[degson\] is the minor of Pascal’s matrix which skips every other row and every other column up to $\lfloor \frac n 2 \rfloor$ shows that we have a correct point configuration for Gessel-Viennot.

Figure \[fig:GVExample\] computes that $N(5)=24$ by explicitly listing all $24$ non-intersecting lattice paths from $A(5)$ to $B(5)$. Then, according to Theorem \[non-intersecting\], we see that $\deg \operatorname{SO}(5)=2^4 \cdot 24=384$, $\deg \operatorname{O}(5)=2^5 \cdot 24=768$, and $\deg \text{Sp}(2)=24$.

Theorem \[non-intersecting\] suggests a relationship between these non-intersecting lattice paths and the degrees of $\operatorname{SO}(n),\operatorname{O}(n),$ and $\text{Sp}(r)$. Such a direct interpretation could be interesting, and so we pose the question:

\[ourQuestion\] Does Theorem \[non-intersecting\] have a deeper combinatorial interpretation?

Because the formula for the degree of the symplectic group has no coefficient in front of the lattice path count in Theorem \[non-intersecting\], studying the combinatorial meaning of the degree of $\text{Sp}(r)$ may be an ideal starting point to tackle Question \[ourQuestion\].

An Application - The Degree of Low Rank Semidefinite Programming {#SDP}
================================================================

In this section we show how knowing the degree of $\operatorname{SO}(n)$ can be used to compute the number of critical points for a certain optimization problem (cf. Theorem \[thm:LRSDP\]).

Consider the standard formulation of *semidefinite programming* $$\begin{aligned}
\label{primalProblem}
&\text{minimize}_{X\in\mathcal S^n} \quad C\bullet X\notag\\
&\text{such that }\quad A_i\bullet X = b_i, i=1,..., m, \quad X\succeq 0.\end{aligned}$$ Here $\mathcal S^n$ is the set of $n\times n$ real symmetric matrices, $b\in\mathbb Q^m$ is a vector, $C, A_1, ..., A_m\in\mathbb Q\mathcal S^n$ are matrices, and $\bullet$ denotes the trace inner product for matrices: $U\bullet V = \text{trace}(UV)$.

Semidefinite programming can be solved in polynomial time in the size $n$ of the unknown matrix $X$ and in the number of constraints $m$. It is a widely used method in practice, and many NP-hard problems possess semidefinite relaxations [@BV2; @GW2]. However, it is often the case that the size $n$ is very large, and solving exactly can be computationally prohibitive. On the other hand, the rank $r$ of the optimal solution $X^*$ is often much smaller than $n$, and in those cases we can solve  more rapidly by replacing $X$ by the low rank positive semidefinite matrix $RR^T$, where $R\in\mathbb R^{n\times r}$. This idea and an algorithm to solve the new problem are due to Burer and Monteiro [@BM]. The problem becomes $$\begin{aligned}
\label{newProblem}
&\text{minimize}_{R\in\mathbb R^{n\times r}} \quad C\bullet (RR^T)\notag\\
&\text{such that }\hspace{0.33cm} A_i\bullet (RR^T) = b_i, ~~i=1, ..., m.\end{aligned}$$ The constraint $X\succeq 0$ is now implicit and the number of variables has decreased from $n^2$ to $nr$. However, the objective function and the constraints are no longer linear; instead, they are quadratic and the feasible set is non-convex. In [@BM]  Burer and Monteiro propose a fast algorithm for solving . Despite the existence of multiple local minima, in practice this algorithm quickly finds the global minimum. It starts by choosing the rank $r=1$, and increments it until $C - \sum_{i=1}^my_i A_i\succeq 0$, which ensures that we have arrived at the smallest optimal $r$. For each fixed rank $r$, the optimization problem is non-convex, and its appealing behavior still remains to be examined. In Theorem \[thm:LRSDP\] we give a formula for the number of critical points of this optimization problem. We call a [*critical point*]{} of the optimization problem any point $(R, y)$ which satisfies the Lagrange multipliers equations arising from this problem. Here $y$ is a vector of size $m$, and its entries $y_1,\dots, y_m$ are the new dual variables introduced for the $m$ constraints in (see equation ). Before we state our theorem, we need the following definition.

Let $$\psi_i = 2^{i-1}, \quad \psi_{i,j} = \sum_{k=i}^{j-1}\binom{i+j-2}k \text{ when } i < j,$$ and $$\psi_{i_1,\dots, i_r}= \operatorname{Pf}(\psi_{i_k, i_l})_{1\leq k < l\leq r} \text{ if } r \text{ is even},$$ $$\psi_{i_1,\dots, i_r}= \operatorname{Pf}(\psi_{i_k, i_l})_{0\leq k < l\leq r} \text{ if } r \text{ is odd}$$ where $r>2$, $\psi_{0, k } = \psi_{k}$, and $\operatorname{Pf}$ denotes the Pfaffian. Then, define $\delta(m, n, r)$ as $$\delta(m, n, r) = \sum_{I} \psi_I\psi_{I^c},$$ where the sum runs over all strictly increasing subsequences $I = \{i_1, ..., i_{n-r}\}$ of $\{1, ..., n\}$ of length $n - r$ and such that $i_1 + ... + i_{n-r} = m$.

\[thm:LRSDP\] The number of critical points of the low-rank semidefinite programming algorithm is $$2 (\deg\operatorname{SO}(r)) \delta(m, n, r).$$

The number $\delta(m, n, r)$ is called the [*algebraic degree of semidefinite programming*]{} and was originally defined in [@NRS] as the number of critical points of the original semidefinite programming problem for which the matrix $X$ has rank $r$. The final formula for it was computed in [@VR].

*Proof of Theorem \[thm:LRSDP\]:* In order to analyze the optimality conditions for the program (\[newProblem\]) for a fixed $r$, consider the Lagrangian function $$\begin{aligned}
\label{Lagrangian}
L(R, y) = C\bullet (RR^T) - \sum_{i=1}^my_i(A_i\bullet(RR^T) - b_i).\end{aligned}$$ Taking derivatives, we find out that the critical points $(R, y)$ of this optimization problem are given by the Lagrange multipliers equations: $$\begin{aligned}
\label{equations}
\left(C - \sum_{i=1}^my_iA_i\right)RR^T&= 0\\
A_i\bullet(RR^T) &= b_i, i=1,2,...,m.\notag\end{aligned}$$ In addition, those critical points relevant for applications have to be real and have to satisfy $$\begin{aligned}
\label{addEquation}
\left(C - \sum_{i=1}^my_iA_i\right)\succeq 0,\end{aligned}$$ since this is the constraint in the dual to the optimization problem . However, in this article we are primarily concerned with counting all of the critical points. Analogously, in [@NRS] Nie, Ranestad, and Sturmfels show that the critical points of the original semidefinite programming problem satisfy $$\begin{aligned}
\left(C - \sum_{i=1}^my_iA_i\right)X &= 0,\label{optimalSolutions1}\\
A_i\bullet X &= b_i, i=1,...,m.\label{optimalSolutions2}\end{aligned}$$ In addition, the critical points relevant for applications have to satisfy $$\begin{aligned}
\left(C - \sum_{i=1}^my_iA_i\right)\succeq 0 \text{ and } X&\succeq 0,\label{optimalSolutions3}\end{aligned}$$ but these conditions are disregarded and the total number of critical points is counted. Nie, Ranestad, and Sturmfels show that the number of solutions $(X, y)$ to -, for which the rank of $X$ is $r$, equals $\delta(m, n, r)$ (c.f. Definition 1). Comparing our system of equations to the equations -, we see that the fiber of the map $(R, y) \mapsto (RR^T, y)$ above each point $(X, y)$, satisfying -, consists of all points $(R, y')$, satisfying , and such that $y' = y$ and $X = RR^T$. Given $X$ and one matrix $R$ such that $X = RR^T$, all other matrices $S$ such that $(S, y)$ is in the fiber above $(X, y)$ have the form $S = RU$ where $U$ runs over all orthogonal $r\times r$ matrices. In other words, this fiber is isomorphic to a copy of the orthogonal group $O(r)$. Therefore, the number of solutions to is equal to $2(\deg\operatorname{SO}(r))\delta(m, n, r)$.

The number of critical points of low-rank semidefinite programming grows rapidly with the rank $r$, and the appealing behavior of the augmented Lagrangian algorithm [@BM] still needs to be explained. It would be quite interesting and relevant for applications to examine how many of the critical points computed in Theorem 5 and in [@NRS] are real, and moreover, how many of them satisfy the additional linear matrix inequality constraints and respectively. This is a real algebraic problem and would involve counting polynomial system solutions over semialgebraic sets. This question is addressed more in Section \[reality\].

Computational Methods {#Computational}
=====================

Although we have already derived a formula for the degree of $\operatorname{SO}(n)$, it is natural to want to compute this degree explicitly for particular values of $n$. Aside from merely verifying the formula in Theorem \[degson\], the computation of this degree gives us access to other useful data along the way. In our case, this manifests itself as either a Gröbner basis or a witness set for $\operatorname{SO}(n)$. Once computed, either may be used in further computations (such as those done in Section \[reality\] using witness sets). Additionally, $\operatorname{SO}(n)$ serves as a prime example of when numerical algorithms are better suited for computation than other techniques. Even though our computations focus on $\operatorname{SO}(n)$, these methods are useful for studying many other varieties.

In this section, we describe three techniques which can compute the degree of a variety: a Gröbner basis algorithm, polynomial homotopy continuation, and a numerical monodromy algorithm. The first is symbolic and the last two use numerical algebraic geometry. The results of our symbolic and numerical computations for $\deg \operatorname{SO}(n)$ appear in the first two columns of Table \[fig:SO\]. Code for each method is given in the appendix.

Using Gröbner bases, we were able to compute the degree of $\operatorname{SO}(n)$ for $n \leq 5$. The standard algorithm computes a Gröbner basis for the ideal of $\operatorname{SO}(n)$ over $\mathbb{Q}$ and uses this to produce the Hilbert polynomial. However, since the dimension of $\operatorname{SO}(n)$ grows quadratically in $n$, this method quickly becomes computationally infeasible. Computing a Gröbner basis over a finite field can speed up the computation, but this method is still quite slow.

A common numerical algorithm for computing the degree of $\operatorname{SO}(n)$ over $\mathbb{C}$ randomly chooses an affine linear space $\mathcal L$ of complementary dimension and counts the number of complex solutions $S$ to the zero-dimensional system corresponding to $\operatorname{SO}(n) \cap \mathcal L$. This data is contained in the triple $(\operatorname{SO}(n),\mathcal L, S)$ which is called a *witness set* for $\operatorname{SO}(n)$. This is the fundamental data type in numerical algebraic geometry in the sense that the computation of a witness set is often a necessary step for other numerical algorithms. Such techniques include sampling points on the variety at a rapid rate, studying its asymptotic behaviour, computing its monodromy group, or even studying its real locus, as we do in Section \[reality\]. Both numerical algorithms presented below produce a witness set for $\operatorname{SO}(n)$.

*Polynomial homotopy continuation* computes a witness set by solving a system of polynomials describing these points. Briefly, this method begins with a “start” polynomial system that has similar structure to the “target” system we want to solve, but for which the solutions are obvious. The solutions of the start system are quickly tracked through a homotopy towards those of the target system [@SW]. The most basic start system one uses for this technique has a solution count equal to the product of the degrees of the polynomials in the target system. This number is called the *Bézout bound* and for our case is equal to $2^{n(n+1)/2}$ (for $n=6$, this is already $2097152$). The *polyhedral start system*, however, has a solution count equal to the mixed volume of the Newton polytopes of these polynomials. In our case, this count provides no savings as it is equal to the Bézout bound. Because of how many paths need to be tracked with this method, we were only able to compute the degree of $\operatorname{SO}(n)$ up to $n=5$ with this method, just like with Gröbner bases.

The method that proved to be the most efficient takes advantage of the monodromy group of $\operatorname{SO}(n)$. The basic idea is that if we know some point on a linear cut $W=\mathcal{L} \cap \operatorname{SO}(n)$, we can track this solution from the slice $W$ along some path $\gamma$ to another slice $W'$ using homotopy methods. Tracking this solution along a different path $\gamma'$ back to $W$ then induces a permutation $\sigma_{\gamma,\gamma'}$ on the points in $W$. Therefore, applying this action to a point $x_0 \in W$ will likely produce a new point $\sigma_{\gamma,\gamma'}(x_0) \in W$. One iterates this process hoping to populate the witness set associated to $W$. Other than knowing the degree [*a priori*]{}, stopping criteria for this method tend to be heuristic in nature: one can wait until the algorithm fails to produce new points (suggesting there are no new points to be found) or one can compute a *trace test* [@tracetest] which numerically decides whether or not a witness set is complete. This monodromy method has been implemented in the package *monodromySolver* for *Macaulay2* [@M2] and is explained in much more detail in [@duff2016solving].

A major computational result arising from this project was the computation of witness sets for $\operatorname{SO}(6)$ and $\operatorname{SO}(7)$. This was done in $630$ and $42790$ seconds respectively using *monodromySolver*. The algorithm stopped when no new points were found on ten consecutive iterations.

Real Points on $\operatorname{SO}(n)$ {#reality}
=====================================

An interesting question pertaining to $\operatorname{SO}(n)$ is whether or not this variety always admits some witness set consisting of only real points. Since tracking points of one witness set to those of another is computationally inexpensive via homotopy continuation, we use this method to generate experimental data regarding real points on witness sets of $\operatorname{SO}(3),$ $\operatorname{SO}(4),$ and $\operatorname{SO}(5)$.

The number of coefficients needed to produce a linear cut of $\operatorname{SO}(n)$ is $(n^2+1) {{n}\choose 2}$. We randomly choose these coefficients using the *random* function in *Macaulay2* in order to sample linear cuts of $\operatorname{SO}(n)$. We then use homotopy continuation to track solutions of a precomputed witness set to those lying on the randomly chosen linear cut. Finally, we determine how many solutions in the new cut are real by checking whether each solution is within a $0.001$ numerical tolerance of a real point coordinate-wise. One can certify the results using the software *alphaCertify* which implements Smale’s $\alpha$ theory [@alphaCertified]. For the sake of speed, we chose not to certify all of the results, but instead certify at least one witness set achieving the observed maximum of real points (cf. Table \[fig:SO3Real\], Table \[fig:SO4Real\], and Table \[fig:SO5Real\]).

After computing $1398000$, $1004100$, and $48200$ witness sets for $\operatorname{SO}(3),\operatorname{SO}(4),$ and $\operatorname{SO}(5)$ respectively, we have summarized the number of real solutions found in each witness set in the frequency tables and histograms below. Explicit data and code used can be found in [@dataSite]. Note that very rarely, numerical failures occur because the path that homotopy continuation is being performed over is ill-conditioned (for example, almost singular). These occurrences are also tallied below under “fail”.

  -------------------- ------------------------------------------------------------------------ -- -- -- -- -- --
   \#(Real Solutions)   **[Fail]{}&**[0]{} & **[2]{} & **[4]{} & **[6]{}& **[8]{}&**[Total]{}\                 
                           Frequency &2& 285676 & 420049 & 549875 & 127699 & 14699&1398000\                    
                                                    **************                                             
  -------------------- ------------------------------------------------------------------------ -- -- -- -- -- --

  : Number of real points on witness sets of $\operatorname{SO}(3)$[]{data-label="fig:SO3Real"}

  -------------------- -------------- ---------------------------------------------------------------- -- -- -- -- --
   \#(Real Solutions)   [**Fail**]{}              **0 & **2& **4& **6& **[8]{}& **[10]{}\                          
                                       Frequency &51 &183427 &108273 &132143 &156010 &159630 &124843\              
                                                                ************                                       
  -------------------- -------------- ---------------------------------------------------------------- -- -- -- -- --

  : Number of real points on witness sets of $\operatorname{SO}(4)$[]{data-label="fig:SO4Real"}

[ |c|c|c|c|c| c | c | c | c | c | c | c | c ||c]{} **[12]{}& **[14]{}& **[16]{}& **[18]{}& **[20]{} &**[22]{} &**[24]{}&**[26]{}&**[28]{}&**[30]{}&**[32]{}&$\cdots$&**[40]{}&**[Total]{}\
**************************

76965 &38243 &16150 &5780 &1897 &510 &145 &23 &9 &1 &0 &$\cdots$ &0 &1004100\

  -------------------- -------------- ----------------------------------------------------------------------- -- -- -- -- -- -- -- --
   \#(Real Solutions)   [**Fail**]{}   **0 & **2& **4& **6& **[8]{}& **[10]{}& **[12]{}& **[14]{}& **[16]{}\                       
                                       Frequency &81 &6162 &2628 &2377 &2306 &2275 &2272 &2275 &2383 &2473\                        
                                                                ******************                                                 
  -------------------- -------------- ----------------------------------------------------------------------- -- -- -- -- -- -- -- --

  : Number of real points on witness sets of $\operatorname{SO}(5)$[]{data-label="fig:SO5Real"}

[|c|c|c|c|c|c|c|c|c|c|c|c|c|c]{} **[18]{}& **[20]{}& **[22]{}& **[24]{}& **[26]{}& **[28]{}& **[30]{}& **[32]{}& **[34]{}& **[36]{}& **[38]{}& **[40]{}& **[42]{}& **[44]{}\
****************************

2497 &2527 &2504 &2485 &2280 &2009 &1755 &1644 &1331 &1051 &802 &591 &468 &362\

  ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --
   **[46]{}& **[48]{}& **[50]{}& **[52]{}& **[54]{}& **[56]{}& **[58]{}& **[60]{}& **[62]{} &**[64]{} &**[66]{}&**[68]{}&**[70]{}&**[72]{}&**[74]{}&**[76]{}&**[78]{}&$\cdots$&**[384]{}&**[Total]{}\                                                        
                                                            235 &150 &118 &60 &44 &21 &16 &8 &4 &3 &1 &0 &0 &0 &0 &2 &0 &$\cdots$ &0 &48200\                                                                                                                 
                                                                                 **************************************                                                                                                                                      
  ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- --

  : Number of real points on witness sets of $\operatorname{SO}(5)$[]{data-label="fig:SO5Real"}

\[fig:so4histogram\]

\[fig:so5histogram\]

In each case, we were able to find a witness set which failed to have any real solutions on it. This is unsurprising as $\operatorname{SO}(n)$ is compact over the real numbers. Despite the fact that all witness sets computed for $\operatorname{SO}(4)$ had fewer than $40$ solutions, and for $\operatorname{SO}(5)$, fewer than $384$, there is little evidence suggesting that a non-trivial upper bound for the number of real solutions on a witness set of $\operatorname{SO}(n)$ exists. We end with a conjecture.

For any $n$, $\operatorname{SO}(n)$ admits some real witness set.

Appendix: Macaulay2 Code {#appendix-macaulay2-code .unnumbered}
========================

This section contains code which computes the degree of $\operatorname{SO}(n)$ for various $n$ using Gröbner bases, polynomial homotopy continuation, *MonodromySolver*, and Theorem \[degson\] respectively. They are all done in *Macaulay2*.

First, we compute the degree of $\operatorname{SO}(5)$ using Gröbner bases. The computation is done over the finite field $\mathbb{Z}_{101}$ for $\operatorname{O}(5)$ and the result is halved to give the degree of $\operatorname{SO}(5)$.

    n=5
    R = ZZ/101[x_(1,1)..x_(n,n)]
    M = genericMatrix(R,n,n)
    J = minors(1,M*transpose(M)-id_(R^n))
    degOn = degree J
    degSOn = degOn//2

Computing the degree of $\operatorname{O}(n)$, rather than $\operatorname{SO}(n)$ directly, is useful because it throws out the polynomial of highest degree in the system. This is especially useful in numerical methods since they perform best with polynomials of low degree.

The code below uses the package *NumericalAlgebraicGeometry* to solve the zero dimensional system given by a linear slice of $\operatorname{O}(3)$. The method *solveSystem* employs the standard method of polynomial homotopy continuation. Again, the answer is halved to give $\deg \operatorname{SO}(3)$.

    loadPackage "NumericalAlgebraicGeometry"
    n = 3
    L = toList apply(
          (0,0)..(n-1,n-1), (i,j)->"x"|toString i|toString j
          )
    R = CC[L]
    M = genericMatrix(R,n,n)
    B = M*(transpose M) - id_(R^n)
    polys = flatten for i from 0 to n-1 list(
              for j from i to n-1 list B_(i,j)
            )
    linearSlice = apply(
                    binomial(n,2), i->random(1,R)-random(CC)
                  )
    S = solveSystem(polys|linearSlice);
    degOn = #S
    degSOn = degOn//2

Next, we provide code that computes the degree of $\operatorname{SO}(7)$ using the package *MonodromySolver*. We again do not include the determinant condition, but this time we do *not* need to halve the result. This is because our starting point, the identity matrix, lies on $\operatorname{SO}(7)$ and this method only discovers points on the irreducible component corresponding to our starting point. The linear slices are parametrized by the $t$ and $c$ variables which are varied within the function *monodromySolve* to create monodromy loops. The method stops when ten consecutive loops provide no new points. Although it is possible that this stopping criterion is satisfied prematurely, in our case the program stopped at the correct number, serving as a testament to the practicality of the software and also this stopping criterion.

    loadPackage "MonodromySolver"
    N=7
    d=binomial(N,2)
    R=CC[c_1..c_d,t_(1,1,1)..t_(d,N,N)][x_(1,1)..x_(N,N)]
    M=genericMatrix(R,N,N)
    B=M*transpose(M)-id_(R^N)
    polys=flatten for j from 0 to N-1 list(
           for k from j to N-1 list B_(j,k)
          );
    linearSlice=for i from 1 to d list(
                  c_i+sum(
                    flatten for j from 1 to N list(
                      for k from 1 to N list t_(i,j,k)*x_(j,k)
                    )
                  )
                );
    G = polySystem join (polys,linearSlice)
    x0coords = flatten entries id_(CC^N)
    setRandomSeed 0
    (p0, x0) := createSeedPair(G,x0coords)
    elapsedTime (V,npaths) = 
        monodromySolve(G,p0,{x0},NumberOfNodes=>2,NumberOfEdges=>4);
    --node1: 111616                                                                                                                
    --node2: 111616                                                                                                                
    -- 42790.9 seconds elapsed    

Finally, for the mathematician wanting to compute the degree of $\operatorname{SO}(n)$ quickest, we give code that evaluates the formula in Theorem \[degson\].

    degSO = method()
    degSO(ZZ) := N ->(
        n := N//2;
        M := matrix for i from 1 to n list (
            for j from 1 to n list (
                binomial(2*N-2*i-2*j,N-2*i)
                )
            );
        2^(N-1)*(det M)
        )

This article was initiated during the Apprenticeship Weeks (22 August-2 September 2016), led by Bernd Sturmfels, as part of the Combinatorial Algebraic Geometry Semester at the Fields Institute.

The authors are very grateful to Jan Draisma for his tremendous help with understanding Kazarnovskij’s formula, and to Kristian Ranestad for many helpful discussions. The authors thank Anton Leykin for performing the computation of $\operatorname{SO}(7)$. The first three authors would also like to thank the Max Planck Institute for Mathematics in the Sciences in Leipzig, Germany for their hospitality where some of this article was completed. The motivation for computing the degree of the orthogonal group came from project that started by the fifth author at the suggestion of Benjamin Recht.

The first author was supported by the National Science Foundation Graduate Research Fellowship under Grant No. DGE 1106400. The second author was partially supported by the NSF GRFP under Grant No. DGE-1256259 and the Graduate School and the Office of the Vice Chancellor for Research and Graduate Education at the University of Wisconsin-Madison with funding from the Wisconsin Alumni Research Foundation.
