# Max filtering with reflection groups

Dustin G. Mixon111Department of Mathematics, The Ohio State University,
Columbus, OH 222Translational Data Analytics Institute, The Ohio State
University, Columbus, OH Daniel Packer11footnotemark: 1

###### Abstract

Given a finite-dimensional real inner product space $V$ and a finite subgroup
$G$ of linear isometries, max filtering affords a bilipschitz Euclidean
embedding of the orbit space $V/G$. We identify the max filtering maps of
minimum distortion in the setting where $G$ is a reflection group. Our
analysis involves an interplay between Coxeter’s classification and
semidefinite programming.

##  1 Introduction

Machine learning often requires an object to be represented as a point $x$ in
a vector space $V$. In many settings, there is a linear group $G$ of
ambiguities for which the same object can be represented as $gx$ for any $g\in
G$. For example, when the object is a point cloud or a graph, the vector
representation depends on how the points or vertices are labeled. One is
inclined to apply a $G$-invariant feature map $\Phi\colon V\to F$ to factor
out these ambiguities before training a machine learning model. Recently, [6]
introduced such a feature map that is well suited for groups of linear
isometries:

######  Definition 1.

Fix a real inner product space $V$ and a group $G\leq\operatorname{O}(V)$.

  * (a)

The max filtering map $\langle\langle\cdot,\cdot\rangle\rangle\colon V/G\times
V/G\to\mathbb{R}$ is defined by

$\langle\langle G\cdot x,G\cdot y\rangle\rangle:=\sup_{\begin{subarray}{c}p\in
G\cdot x\\\ q\in G\cdot y\end{subarray}}\langle p,q\rangle.$

  * (b)

Given $\\{t_{i}\\}_{i=1}^{n}$ in $V$, the corresponding max filter bank
$\Phi\colon V/G\to\mathbb{R}^{n}$ is defined by

$\Phi(G\cdot x):=\\{\langle\langle G\cdot t_{i},G\cdot
x\rangle\rangle\\}_{i=1}^{n}.$

The vectors $\\{t_{i}\\}_{i=1}^{n}$ that determine a max filter bank are known
as templates. Max filter banks offer a noteworthy contrast to the polynomial
invariants that are typically studied in the literature [2, 11, 5, 3, 1]. In
particular, every $G$-invariant polynomial map $V\to\mathbb{R}^{n}$ is either
affine linear or not Lipschitz. As a result, polynomial invariants are doomed
to either fail to separate orbits or fail to exhibit numerical stability.
Meanwhile, [6] establishes that for every finite $G\leq\operatorname{O}(d)$,
there exists a bilipschitz max filter bank
$\mathbb{R}^{d}/G\to\mathbb{R}^{n}$. We enunciate the quantitative details of
this result in terms of the following definition:

######  Definition 2.

Given a group $G\leq\operatorname{O}(d)$ whose action on $\mathbb{R}^{d}$ has
closed orbits, the optimal max filtering condition number $\kappa(G)$ is the
infimum of quotients $C/c$ for which there exist $n\in\mathbb{N}$ and
templates $\\{t_{i}\\}_{i=1}^{n}$ in $\mathbb{R}^{d}$ such that the
corresponding max filter bank (as a map from $\mathbb{R}^{d}/G$ with the
quotient Euclidean metric to $\mathbb{R}^{n}$ with the Euclidean metric) has
upper and lower Lipschitz bounds $C$ and $c$, respectively.

######  Proposition 3 (see Theorem 18 in [6]).

There exists a universal constant $C>0$ such that for every $d,m\in\mathbb{N}$
and every finite group $G\leq\operatorname{O}(d)$ of order $m$, it holds that

$\kappa(G)\leq Cm^{3}d^{1/2}(d\log d+d\log m+\log^{2}m)^{1/2}.$

Proposition 3 is the first of its kind, but it is not sharp and thus warrants
further investigation. In this paper, we derive the exact value of $\kappa(G)$
for every finite reflection group $G$. To compare with Proposition 3, an easy-
to-state consequence of our main results is that

$\kappa(G)\leq Cm$

whenever $G$ is a finite reflection group. While this upper bound is saturated
by the dihedral groups, $\kappa(G)$ is typically much smaller, frequently
being on the order of $d$. In addition to determining $\kappa(G)$ for each
finite reflection group $G$, we also identify $n=d$ max filtering templates
that attain this optimal condition number.

In the next section, we review some preliminaries on reflection groups. In
Section 3, we formulate our main results and describe how our problem reduces
to the study of Weyl chambers of essential and irreducible finite reflection
groups. Sections 4 and 5 contain the proofs of our main results.

##  2 Background on reflection groups

This section reviews basic information about reflection groups. We encourage
the interested reader to consult [10] for more information.

A reflection is an orthogonal transformation with exactly one negative
eigenvalue. Every nonzero vector $u\in\mathbb{R}^{d}$ determines a reflection
with matrix representation

$R(u):=I-\frac{2}{\|u\|^{2}}uu^{\top},$

where $I$ denotes the identity matrix. A reflection group is any group that is
generated by a set of reflections, implying that it is a subgroup of the
orthogonal group $\operatorname{O}(d)$. For example, the group of permutation
matrices is generated by the transposition matrices $R(e_{i}-e_{j})$, where
$e_{i}$ and $e_{j}$ denote standard basis elements of $\mathbb{R}^{d}$. Given
nonzero vectors $\\{u_{i}\\}_{i=1}^{k}$, the fixed points of the reflection
group generated by $\\{R(u_{i})\\}_{i=1}^{k}$ form the orthogonal complement
of $\operatorname{span}\\{u_{i}\\}_{i=1}^{k}$. We say a reflection group is
essential if the origin is its only fixed point. The group of permutation
matrices fixes the all-ones vector, and so this reflection group is not
essential in $\mathbb{R}^{d}$ (however, it is essential when interpreted as a
reflection group on the orthogonal complement of the all-ones vector).

Given a finite reflection group $G\leq\operatorname{O}(d)$, let $U$ denote the
union of the hyperplanes fixed by each individual reflection in $G$. The
connected components of $\mathbb{R}^{d}\setminus U$ are known as the Weyl
chambers of $G$. Fix a Weyl chamber $C\subseteq\mathbb{R}^{d}$. It turns out
that $C$ is an open set whose boundary is contained in a union of
$\ell\in\mathbb{N}$ hyperplanes corresponding to reflections in $G$ (and no
fewer). We denote these reflections by $\\{R(\alpha_{i})\\}_{i=1}^{\ell}$ for
unit vectors $\\{\alpha_{i}\\}_{i=1}^{\ell}$, which are signed so that they
reside in the dual cone of $C$. Then $\\{\alpha_{i}\\}_{i=1}^{\ell}$ is known
as the fundamental system of $G$ corresponding to $C$. Interestingly, the
reflections $\\{R(\alpha_{i})\\}_{i=1}^{\ell}$ generate the original
reflection group $G$. In the case where $G$ is essential, we have $\ell=d$,
and furthermore, the dual basis $\\{\beta_{i}\\}_{i=1}^{d}$ of the fundamental
system $\\{\alpha_{i}\\}_{i=1}^{d}$ generates the closed convex cone
$\overline{C}$, i.e., $\overline{C}$ is an example of a simplicial cone.

As an example, consider the symmetries of the square, i.e., the dihedral group
of order $8$. Figure 1 illustrates the $1$-eigenspaces (in this case, lines)
of the reflections in this group. These lines carve the plane into eight Weyl
chambers, one of which we call $C$. The corresponding fundamental system
consists of the unit vectors
$\alpha_{1}:=(\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}})$ and
$\alpha_{2}:=(0,1)$, and the resulting dual basis, given by
$\beta_{1}:=(\sqrt{2},0)$ and $\beta_{2}:=(1,1)$, generates $\overline{C}$.

$C$

$C$$\alpha_{2}$$\alpha_{1}$$\beta_{2}$$\beta_{1}$

Figure 1:  (left) Weyl chamber arising from dihedral group. (right)
Fundamental system and its dual basis.

A reflection group in $\operatorname{O}(d)$ is said to be reducible if it can
be decomposed as a direct product of nontrivial reflection groups in
$\operatorname{O}(d)$, in which case $\mathbb{R}^{d}$ can be correspondingly
decomposed into orthogonal invariant subspaces. For example, the group of
orthogonal diagonal matrices is reducible and can be decomposed along the
lines spanned by the standard basis. We note that this use of “reducible”
differs slightly from its usage in representation theory. While a reflection
group may be viewed as the image of a representation, the representation is
irreducible precisely when its image is both irreducible and essential as a
reflection group. For example, the group of permutation matrices is reducible
as a representation but irreducible as a reflection group (since it is not
essential).

For each $d\in\mathbb{N}$, there are finitely many finite essential
irreducible reflection groups in $\operatorname{O}(d)$ up to conjugation by an
orthogonal matrix. These were famously classified by Coxeter [8] in terms of
abstract group presentations. To motivate these presentations, note that for
linearly independent unit vectors $u,v\in\mathbb{R}^{d}$, the composition
$R(u)R(v)$ has a $1$-eigenspace of dimension $d-2$, and it acts as a rotation
by $2\arccos\langle u,v\rangle$ radians in the $2$-dimensional orthogonal
complement. If $R(u)$ and $R(v)$ belong to a common finite reflection group,
it must hold that $R(u)R(v)$ has finite order, and so $\arccos\langle
u,v\rangle$ is a rational multiple of $\pi$. If $u$ and $v$ belong to a
fundamental system of the reflection group, it turns out that $\langle
u,v\rangle=-\cos\frac{\pi}{m}$, where $m$ is the order of $R(u)R(v)$. As an
abstraction of this, a Coxeter system consists of generators
$\\{r_{i}\\}_{i=1}^{d}$ and orders $\\{m_{ij}\\}_{i,j=1}^{d}$ such that
$m_{ii}=1$ and $m_{ij}\geq 2$ for $i\neq j$. The resulting Coxeter group is
then given by

$\langle r_{1},\ldots,r_{d}:(r_{i}r_{j})^{m_{ij}}=1\rangle.$

Every Coxeter system has a Coxeter diagram, namely, a graph with vertex set
$\\{1,\ldots,d\\}$ and adjacency $i\leftrightarrow j$ precisely when
$m_{ij}\geq 3$, and this edge is labeled by $m_{ij}$ whenever $m_{ij}\geq 4$.
The Coxeter system is irreducible when the Coxeter diagram is connected. For
example, the connected Coxeter diagram on two vertices whose edge is labeled
by $4$ corresponds to the Coxeter group

$\langle r_{1},r_{2}:r_{1}^{2}=r_{2}^{2}=(r_{1}r_{2})^{4}=1\rangle,$

which is isomorphic to the dihedral group of order $8$; see Figure 1 for a
relevant illustration.

Given a finite irreducible Coxeter system, one may use the geometry of
fundamental systems to reconstruct the corresponding finite essential
irreducible reflection group (which again is unique up to conjugation).
Indeed, the Gram matrix of the fundamental system $\\{\alpha_{i}\\}_{i=1}^{d}$
is given by

$\langle\alpha_{i},\alpha_{j}\rangle=\left\\{\begin{array}[]{cl}1&\text{if
}i=j\\\ -\cos\frac{\pi}{m_{ij}}&\text{if }i\neq j,\end{array}\right.$

which can then be Cholesky factored to determine $\\{\alpha_{i}\\}_{i=1}^{d}$
up to orthogonal transformation. Then $\\{R(\alpha_{i})\\}_{i=1}^{d}$
generates the desired reflection group. In the above case where $d=2$ and
$m_{12}=4$, we obtain the Gram matrix

$\left[\begin{array}[]{cc}\phantom{-}1&-\frac{1}{\sqrt{2}}\\\
-\frac{1}{\sqrt{2}}&\phantom{-}1\end{array}\right],$

which can be factored to recover the fundamental system illustrated in Figure
1.

In the case where $G$ is essential and irreducible, the closed fundamental
chamber is an acute cone, i.e., a convex cone $K$ such that every nonzero
$x,y\in K$ satisfies $\langle x,y\rangle>0$. This geometric fact will prove
useful in understanding the spectral properties associated with fundamental
systems of $G$.

######  Lemma 4.

For every essential and irreducible finite reflection group $G$, each closed
chamber of $G$ is an acute cone.

###### Proof.

Since the rows of $A$ form a fundamental system, the off-diagonal entries of
the Gram matrix $AA^{\top}$ are nonpositive; see Lemma B on page 39 in [10].
Furthermore, since the reflection group is irreducible, the Gram matrix
$AA^{\top}$ is irreducible as a matrix (i.e., it is not permutation equivalent
to a block-diagonal matrix). It follows from Corollary 3.24 in [12] that
$B^{\top}B=(AA^{\top})^{-1}$ is entrywise positive, which implies the result.
∎

All of our main results rely on the following spectral phenomena:

######  Lemma 5.

Suppose $G\leq\operatorname{O}(d)$ is an essential and irreducible finite
reflection group, and select any matrix $A\in\mathbb{R}^{d\times d}$ with
unit-norm rows that form a fundamental system for $G$.

  * (a)

The top and bottom eigenvectors of $AA^{\top}$ satisfy
$(v_{1})_{i}^{2}=(v_{d})_{i}^{2}$ for all $i\in[d]$.

Next, consider the matrix $M:=AA^{\top}-I_{d}$. For each $j\in[d]$, let
$M^{(j)}$ denote the principal submatrix of $M$ obtained by discarding the
$j$th row and column, and let $\lambda_{k}(\cdot)$ denote the $k$th largest
eigenvalue of the argument, counted with multiplicity.

  * (b)

For each $k\in[d]$, it holds that $\lambda_{d-k+1}(M)=-\lambda_{k}(M)$.

  * (c)

For each $j\in[d]$ and $k\in[d-1]$, it holds that
$\lambda_{d-k}(M^{(j)})=-\lambda_{k}(M^{(j)})$.

We could not locate a proof of the above facts, and so we provide our own in
Appendix A. Our proof argues by cases over Coxeter’s classification.

##  3 Main results and key reductions

Our first main result describes minimal optimal max filter banks for every
reflection group in terms of its decomposition into irreducible constituent
representations:

######  Theorem 6.

Suppose $G\leq\operatorname{O}(d)$ is a finite reflection group.

  * (a)

If $G$ is the trivial group, then $\kappa(G)=1$, and minimal optimal templates
are given by any orthonormal basis.

  * (b)

If $G$ is essential and irreducible, then for any matrix
$A\in\mathbb{R}^{d\times d}$ with unit-norm rows that form a fundamental
system for $G$, it holds that
$\kappa(G)=\frac{\sigma_{\max}(A)}{\sigma_{\min}(A)}$, and minimal optimal
templates are given by the columns of $A^{-1}$.

  * (c)

Otherwise, $G$ can be decomposed into irreducible constituents
$G_{i}\leq\operatorname{O}(d_{i})$, one of which is trivial precisely when $G$
is not essential, and the others are essential and irreducible as reflection
groups. Then $\kappa(G)=\max_{i}\kappa(G_{i})$, and minimal optimal templates
are given by an orthogonal direct sum of the minimal optimal templates for
each irreducible constituent described in (a) and (b).

Theorem 6(a) is immediate. The proof of part (c) is straightforward after some
preliminary analysis of Weyl chambers, and we provide it later in this
section. The proof of part (b) occupies Section 4. Our second main result
(Theorem 7) leverages Theorem 6(b) to compute $\kappa(G)$ for the standard
representation $G$ of any irreducible Coxeter group, which in turn determines
$\kappa(G)$ for any finite reflection group $G$ by Theorem 6(c). The proof of
Theorem 7 appears in Section 5.

######  Theorem 7.

The optimal max filtering condition numbers of the exceptional Coxeter groups
are reported in Table 1. For the remaining Coxeter groups, we have

  * (a)

$\kappa(A_{\ell})=(\frac{2}{\pi}+o(1))\ell$,

  * (b)

$\kappa(B_{\ell})=(\frac{4}{\pi}+o(1))\ell$,

  * (c)

$\kappa(D_{\ell})=(\frac{4}{\pi}+o(1))\ell$, and

  * (d)

$\kappa(I_{m})=\sqrt{\frac{1+\cos(\frac{\pi}{m})}{1-\cos(\frac{\pi}{m})}}=(\frac{2}{\pi}+o(1))m$.

Table 1:  Optimal max filtering condition numbers of exceptional Coxeter groups  $G$ | $\kappa(G)$ | minimal polynomial
---|---|---
$E_{6}$ | $7.5957$ | $x^{4}-8x^{3}+2x^{2}+8x+1$
$E_{7}$ | $11.4301$ | $x^{6}-12x^{5}+3x^{4}+40x^{3}+3x^{2}-12x+1$
$E_{8}$ | $19.0811$ | $x^{8}-16x^{7}-60x^{6}+16x^{5}+134x^{4}+16x^{3}-60x^{2}-16x+1$
$F_{4}$ | $7.5957$ | $x^{4}-8x^{3}+2x^{2}+8x+1$
$H_{3}$ | $6.3137$ | $x^{4}-4x^{3}-14x^{2}-4x+1$
$H_{4}$ | $19.0811$ | $x^{8}-16x^{7}-60x^{6}+16x^{5}+134x^{4}+16x^{3}-60x^{2}-16x+1$

Before proving Theorem 6(c), we first motivate our approach with an example.
When $G$ is the group of $d\times d$ permutation matrices, it is
straightforward to verify that

$\langle\langle G\cdot x,G\cdot
y\rangle\rangle=\langle\operatorname{sort}(x),\operatorname{sort}(y)\rangle.$
(1)

It turns out that every reflection group has a map analogous to sorting. As
motivation, we observe that the image of the sorting map is the polyhedral
cone

$\\{(x_{1},\ldots,x_{d})\in\mathbb{R}^{d}:x_{1}\geq\cdots\geq x_{d}\\}.$

Every orbit $G\cdot x$ intersects this cone at a single point, namely, at
$\operatorname{sort}(x)$. One may show that the above cone is the closure of a
Weyl chamber of $G$, which offers a hint for how to generalize the sorting
map.

Given a finite reflection group $G\leq\operatorname{O}(d)$ and a corresponding
Weyl chamber $C\subseteq\mathbb{R}^{d}$, we define
$\operatorname{rep}\colon\mathbb{R}^{d}/G\to\overline{C}$ so that
$\operatorname{rep}(G\cdot x)$ is the unique member of $(G\cdot
x)\cap\overline{C}$; indeed, uniqueness is established on page 62 in [10],
which also demonstrates that $\operatorname{rep}$ is bijective. In addition,
$\operatorname{rep}$ preserves distances:

######  Lemma 8.

The bijection $\operatorname{rep}\colon\mathbb{R}^{d}/G\to\overline{C}$
defined above is an isometry.

This implies the following generalization of (1):

$\displaystyle\langle\langle G\cdot x,G\cdot y\rangle\rangle$
$\displaystyle=\frac{1}{2}\Big{(}\|x\|^{2}+\|y\|^{2}-d(G\cdot x,G\cdot
y)^{2}\Big{)}$ $\displaystyle=\frac{1}{2}\Big{(}\|\operatorname{rep}(G\cdot
x)\|^{2}+\|\operatorname{rep}(G\cdot y)\|^{2}-\|\operatorname{rep}(G\cdot
x)-\operatorname{rep}(G\cdot y)\|^{2}\Big{)}$
$\displaystyle=\langle\operatorname{rep}(G\cdot x),\operatorname{rep}(G\cdot
y)\rangle.$ (2)

###### Proof of Lemma 8.

A change of variables gives

$d(G\cdot x,G\cdot y)=\min_{g,h\in G}\|gx-hy\|=\min_{y^{\prime}\in G\cdot
y}\|\operatorname{rep}(G\cdot x)-y^{\prime}\|.$

We note for future use that $(x,y)\mapsto d(G\cdot x,G\cdot y)$ is continuous
since the first equality above expresses it as a minimum of finitely many
continuous functions.

Suppose $x,y\in C$. For each $y^{\prime\prime}\in G\cdot y$ with
$y^{\prime\prime}\neq y$, there is a hyperplane orthogonal to some $\alpha$ in
the fundamental system of $C$ that strictly separates $y^{\prime\prime}$ from
$y\in C$, and so

$\|x-y^{\prime\prime}\|>\|x-R(\alpha)y^{\prime\prime}\|\geq\min_{y^{\prime}\in
G\cdot y}\|x-y^{\prime}\|.$

It follows that $\|x-y^{\prime}\|$ is minimized over $y^{\prime}\in G\cdot y$
at $y^{\prime}=y$, i.e.,

$d(G\cdot x,G\cdot y)=\|x-y\|=\|\operatorname{rep}(G\cdot
x)-\operatorname{rep}(G\cdot y)\|.$

Now consider any $x,y\in\mathbb{R}^{d}$, and take sequences
$\\{x_{n}\\}_{n=1}^{\infty}$ and $\\{y_{n}\\}_{n=1}^{\infty}$ in $C$ such that
$x_{n}\to\operatorname{rep}(G\cdot x)$ and $y_{n}\to\operatorname{rep}(G\cdot
y)$. Then continuity implies

$d(G\cdot x_{n},G\cdot y_{n})\to d\Big{(}G\cdot\operatorname{rep}(G\cdot
x),G\cdot\operatorname{rep}(G\cdot y)\Big{)}=d(G\cdot x,G\cdot y).$

Meanwhile, the previous argument gives

$d(G\cdot x_{n},G\cdot y_{n})=\|x_{n}-y_{n}\|\to\|\operatorname{rep}(G\cdot
x)-\operatorname{rep}(G\cdot y)\|.$

It follows that $d(G\cdot x,G\cdot y)=\|\operatorname{rep}(G\cdot
x)-\operatorname{rep}(G\cdot y)\|$, as desired. ∎

By virtue of (2), we may represent max filtering as a linear map precomposed
with the $\operatorname{rep}$ map. While the image of $\operatorname{rep}$ is
$C$, the linear map is defined on the full space. As the following lemma
shows, extending the linear map does not alter its condition number.

######  Lemma 9.

Let $G\leq\operatorname{O}(d)$ be a finite reflection group. Given
$T:=\\{t_{i}\\}_{i=1}^{n}\in(\mathbb{R}^{d})^{n}$, define
$\Phi\colon\mathbb{R}^{d}/G\to\mathbb{R}^{n}$ and
$L\colon\mathbb{R}^{d}\to\mathbb{R}^{n}$ by

$\Phi(G\cdot x):=\\{\langle\langle G\cdot t_{i},G\cdot
x\rangle\rangle\\}_{i=1}^{n},\qquad L(x):=\\{\langle\operatorname{rep}(G\cdot
t_{i}),x\rangle\\}_{i=1}^{n}.$

Then $\Phi$ and $L$ have identical upper and lower Lipschitz bounds.

###### Proof.

By Lemma 8, $\operatorname{rep}\colon\mathbb{R}^{d}/G\to\overline{C}$ is a
bijective isometry. Letting
$L_{\overline{C}}\colon\overline{C}\to\mathbb{R}^{n}$ denote the restriction
of $L$ to $\overline{C}\subseteq\mathbb{R}^{d}$, we have
$\Phi=L_{\overline{C}}\circ\operatorname{rep}$, and so it suffices to show
that $L_{\overline{C}}$ and $L$ have identical upper and lower Lipschitz
bounds. Since $L$ is linear, its Lipschitz bounds are precisely its top and
bottom singular values, and by restriction, it holds that

$\sigma_{\min}(L)\leq\frac{\|L_{\overline{C}}(x)-L_{\overline{C}}(y)\|}{\|x-y\|}\leq\sigma_{\max}(L)$

for every $x,y\in\overline{C}$ with $x\neq y$. To show that these bounds are
optimal for $L_{\overline{C}}$, select any $y\in C$, and let $z$ be a top
(respectively, bottom) right-singular unit vector of $L$. Since $C$ is open,
it holds that $x:=y+\epsilon z\in C$ for an appropriately small $\epsilon>0$,
in which case

$\frac{\|L_{\overline{C}}(x)-L_{\overline{C}}(y)\|}{\|x-y\|}=\frac{\|L(x)-L(y)\|}{\|x-y\|}=\frac{\|L(x-y)\|}{\|x-y\|}=\frac{\|L(\epsilon
z)\|}{\|\epsilon z\|}=\|Lz\|,$

which achieves equality in the upper (respectively, lower) Lipschitz bound, as
desired. ∎

To find the best conditioned max filtering map, Lemma 9 suggests finding
templates $\\{t_{i}\\}_{i=1}^{n}$ for which the vectors
$\\{\operatorname{rep}(G\cdot t_{i})\\}_{i=1}^{n}$ form the rows of an
optimally conditioned matrix. Since these vectors are constrained to reside in
the closed Weyl chamber $\overline{C}$, this optimization problem motivates
the following definition.

######  Definition 10.

The optimal condition number $\kappa(A)$ of a set $A\subseteq\mathbb{R}^{d}$
is the infimum of quotients $C/c$ for which there exists $n\in\mathbb{N}$ and
vectors $\\{t_{i}\\}_{i=1}^{n}$ in $A$ such that

$c\|x\|\leq\bigg{(}\sum_{i=1}^{n}|\langle
t_{i},x\rangle|^{2}\bigg{)}^{1/2}\leq C\|x\|\qquad\forall x\in\mathbb{R}^{d}.$

Notably, $C/c$ is the condition number of the $d\times n$ matrix with columns
$\\{t_{i}\\}_{i=1}^{n}$.

The optimal condition number of a (possibly nonconvex) cone interacts nicely
with direct sums in the sense that the worst distortion is the distortion of
the worst behaved summand. This is made precise in the following lemma.

######  Lemma 11.

Given spanning sets $X\subseteq\mathbb{R}^{d_{X}}$ and
$Y\subseteq\mathbb{R}^{d_{Y}}$ that are closed under positive scalar
multiplication, the direct sum $X\oplus Y\subseteq\mathbb{R}^{d_{X}+d_{Y}}$
has optimal condition number

$\kappa(X\oplus Y)=\max\\{\kappa(X),\kappa(Y)\\}.$

###### Proof.

To further overload notation, given $A\in\mathbb{R}^{d\times n}$, we let
$\kappa(A)$ denote the condition number of $A$. It suffices to show two
things:

  * (a)

For all matrices $U$ and $V$ with columns from $X$ and $Y$, respectively,
there exists a matrix $W$ with columns from $X\oplus Y$ such that
$\kappa(W)\leq\max\\{\kappa(U),\kappa(V)\\}$.

  * (b)

For every matrix $W$ with columns from $X\oplus Y$, there exist matrices $U$
and $V$ with columns from $X$ and $Y$, respectively, such that
$\max\\{\kappa(U),\kappa(V)\\}\leq\kappa(W)$.

For (a), we may assume $\kappa(U),\kappa(V)<\infty$. Scale $U$ and $V$ so that
$\sigma_{\min}(U)=\sigma_{\min}(V)=1$. Taking $W$ to be block diagonal with
blocks $U$ and $V$, then $\sigma_{\min}(W)=1$ and so

$\kappa(W)=\max\\{\sigma_{\max}(U),\sigma_{\max}(V)\\}=\max\\{\kappa(U),\kappa(V)\\}.$

For (b), we may assume $\kappa(W)<\infty$. We may decompose $W$ as

$W=\left[\begin{array}[]{c}U\\\ V\end{array}\right],$

where $U$ has columns from $X$ and $V$ has columns from $Y$. We claim that

$0<\sigma_{\min}(W)\leq\sigma_{\min}(U)\leq\sigma_{\max}(U)\leq\sigma_{\max}(W)<\infty,$

and similarly for $V$; this in turn implies the desired inequality. Indeed,

$\sigma_{\max}(W)=\max_{\|x\|=1}\|W^{\top}x\|\geq\max_{\|y\|=1}\left\|\left[\begin{array}[]{cc}U^{\top}&V^{\top}\end{array}\right]\left[\begin{array}[]{c}y\\\
0\end{array}\right]\right\|=\max_{\|y\|=1}\|U^{\top}y\|=\sigma_{\max}(U),$

and a similar argument gives the desired bound for $\sigma_{\min}(U)$. ∎

We are now ready to prove Theorem 6(c).

###### Proof of Theorem 6(c).

Combining Lemmas 9 and 11 gives $\kappa(G)=\max_{i}\kappa(G_{i})$. Next, we
view $\mathbb{R}^{d}$ as a direct sum of $\mathbb{R}^{d_{i}}$ according to the
factorization of $G$, and let $B_{i}$ denote the matrix whose columns are the
minimal optimal templates for $\mathbb{R}^{d_{i}}$. Then by Lemma 5(b) and
Theorem 6(a) and (b),

$\frac{1}{\sigma_{\max}(B_{i})^{2}}+\frac{1}{\sigma_{\min}(B_{i})^{2}}=2,$

from which is follows that $\sigma_{\min}(B_{i})$ and $\sigma_{\max}(B_{i})$
are inversely related. Take $B\in\mathbb{R}^{d\times d}$ to be block diagonal
with blocks $B_{i}$. Then for all $i$, it holds that

$\sigma_{\min}(B)\leq\sigma_{\min}(B_{i})\leq\sigma_{\max}(B_{i})\leq\sigma_{\max}(B).$

Furthermore, since $\sigma_{\min}(B_{i})$ and $\sigma_{\max}(B_{i})$ are
inversely related, there exists $j$ such that both
$\sigma_{\min}(B_{j})=\sigma_{\min}(B)$ and
$\sigma_{\max}(B_{j})=\sigma_{\max}(B)$. It follows that

$\frac{\sigma_{\max}(B)}{\sigma_{\min}(B)}=\frac{\sigma_{\max}(B_{j})}{\sigma_{\min}(B_{j})}=\max_{i}\frac{\sigma_{\max}(B_{i})}{\sigma_{\min}(B_{i})}=\max_{i}\kappa(G_{i})=\kappa(G),$

i.e., the columns of $B$ are optimal templates. Finally, since a finite
condition number requires $B$ to have at least $d$ columns, $B$ is minimal. ∎

##  4 Proof of Theorem 6(b)

In this section, we leverage convex duality to establish Theorem 6(b). Our
reduction to convex programming is summarized by the following:

######  Lemma 12.

Let $G\leq\operatorname{O}(d)$ be a finite reflection group with Weyl chamber
$C\subseteq\mathbb{R}^{d}$. Denote

$\alpha:=\inf\Bigg{\\{}\bigg{\|}\sum_{i=1}^{n}t_{i}t_{i}^{\top}-I_{d}\bigg{\|}_{2\to
2}:n\in\mathbb{N},t_{1},\ldots,t_{n}\in\overline{C}\Bigg{\\}}.$

Then $\kappa(G)=\sqrt{\frac{1+\alpha}{1-\alpha}}$.

###### Proof.

By Lemma 9, every max filter bank shares upper and lower Lipschitz bounds with
a linear map $L\colon\mathbb{R}^{d}\to\mathbb{R}^{n}$ of the form
$L(x)=\\{\langle t_{i},x\rangle\\}_{i=1}^{n}$ for some
$t_{1},\ldots,t_{n}\in\overline{C}$. These bounds are the square roots of the
top and bottom eigenvalues of $LL^{*}$, whose matrix representation is
$\sum_{i=1}^{n}t_{i}t_{i}^{\top}$. The scaling of $L$ that makes the
eigenvalues of $LL^{*}$ uniformly closest to $1$ makes the top and bottom
eigenvalues exhibit a common distance $r$ from $1$. Meanwhile, this scaling
does not affect the quotient $\sqrt{\frac{1+r}{1-r}}$ of Lipschitz bounds. The
result follows. ∎

The definition of $\alpha$ in Lemma 12 was directly inspired by Cahill and
Chen’s treatment of scalable frames in [4]. Scalable frames are concerned with
best choices of vectors belonging to a particular union of $1$-dimensional
cones (i.e., rays). Our result replaces this union with a particular closed
convex cone, namely, a Weyl chamber of a finite reflection group.

For the remainder of this section, we assume that $G$ is an essential and
irreducible finite reflection group, and we use the following notation: Take
$A\in\mathbb{R}^{d\times d}$ to be the matrix whose unit-norm rows form the
fundamental system corresponding to the Weyl chamber $C$, and put $B:=A^{-1}$.
Then

$\overline{C}=\\{x\in\mathbb{R}^{d}:Ax\geq 0\\}=\\{By:y\geq 0\\}.$

Observe that for each $t\in\overline{C}$, there exists $y\geq 0$ such that
$tt^{\top}=Byy^{\top}B^{\top}$. By factoring out $B$ and $B^{\top}$, arbitrary
sums of such $tt^{\top}$ correspond to arbitrary sums of $yy^{\top}$, which in
turn make up the convex cone $\operatorname{CP}(d)$ of $d\times d$ completely
positive matrices. Thus,

$\bigg{\\{}\sum_{i=1}^{n}t_{i}t_{i}^{\top}:n\in\mathbb{N},t_{1},\ldots,t_{n}\in\overline{C}\bigg{\\}}=\Big{\\{}BMB^{\top}:M\in\operatorname{CP}(d)\Big{\\}}.$

In particular, the program in Lemma 12 can be reformulated as

$\text{minimize}\quad\|BMB^{\top}-I_{d}\|_{2\to 2}\quad\text{subject to}\quad
M\in\operatorname{CP}(d).$ (3)

Our approach is to prove a sequence of technical conditions on the optimizers
of (3).

######  Lemma 13.

There exists an optimizer of (3) that is a positive multiple of $I_{d}$.

Indeed, Lemma 13 allows us to prove our result:

###### Proof of Theorem 6(b).

By Lemmas 13, 12, and 5(c), we have

$\kappa(G)=\sqrt{\frac{1+\|cBB^{\top}-I_{d}\|_{2\to
2}}{1-\|cBB^{\top}-I_{d}\|_{2\to
2}}}=\sqrt{\frac{\lambda_{\max}(BB^{\top})}{\lambda_{\min}(BB^{\top})}}=\frac{\sigma_{\max}(B)}{\sigma_{\min}(B)}=\frac{\sigma_{\max}(A)}{\sigma_{\min}(A)},$

with optimal templates given by the columns of $B$. ∎

To prove Lemma 13, we first prove a weaker result:

######  Lemma 14.

There exists an optimizer of (3) that is diagonal.

We will prove Lemma 14 by observing an interplay between dual and restricted
programs. A restriction of the primal program (for instance to a diagonal
primal variable) corresponds to a relaxation of the dual program. To show the
restriction does not change the value of the primal program, we can show that
an optimizer of the relaxed dual program is still feasible in the original
dual program.

The dual program of (3) is naturally expressed in terms of the convex cone
$\operatorname{COP}(d)$ of copositive matrices, that is, symmetric matrices
$A\in\mathbb{R}^{d\times d}$ such that $x^{\top}Ax\geq 0$ for all $x\geq 0$:

$\text{maximize}\quad\operatorname{tr}W\quad\text{subject
to}\quad\|W\|_{*}\leq 1,\quad-B^{\top}WB\in\operatorname{COP}(d).$ (4)

Consider the restriction of (3) to diagonal $M\in\operatorname{CP}(d)$, i.e.,
$M=\operatorname{diag}(x)$ with $x\geq 0$:

$\text{minimize}\quad\|B\operatorname{diag}(x)B^{\top}-I_{d}\|_{2\to
2}\quad\text{subject to}\quad x\geq 0.$ (5)

The dual of this restriction is a relaxation of (4):

$\text{maximize}\quad\operatorname{tr}Y\quad\text{subject
to}\quad\|Y\|_{*}\leq 1,\quad
Y^{\top}=Y,\quad\operatorname{diag}(B^{\top}YB)\leq 0.$ (6)

Since the feasibility regions of (4) and (5) each have nonempty interior, they
satisfy strong duality by Slater’s condition. We will show that (6) has an
optimizer that is feasible in (4). By strong duality, this in turn implies
Lemma 14. First, we use complementary slackness to derive useful statements
about optimizers, for example:

######  Lemma 15.

  * (a)

Any optimal $x$ in (5) necessarily satisfies
$\|B\operatorname{diag}(x)B^{\top}-I_{d}\|_{2\to 2}<1$ and $x>0$.

  * (b)

Any optimal $Y$ in (6) necessarily satisfies
$\operatorname{diag}(B^{\top}YB)=0$.

###### Proof.

If $x$ has a zero entry, then $B\operatorname{diag}(x)B^{\top}$ is rank
deficient, and so the objective in (5) at $x$ is at least $1$. Meanwhile,
taking $x:=\sigma_{\max}(B)^{-2}\cdot\mathbf{1}$ gives $0\prec
B\operatorname{diag}(x)B^{\top}\preceq I_{d}$, and so the objective in (5) at
$x$ is strictly less than $1$. This implies (a), and then (b) follows from
complementary slackness. ∎

We can say even more about the optimal $x$ and $Y$ by leveraging the following
version of the von Neumann trace inequality:

######  Proposition 16 (symmetric von Neumann trace inequality).

Suppose $A,B\in\mathbb{R}^{n\times n}$ are symmetric with eigenvalues
$\lambda_{1}\leq\cdots\leq\lambda_{n}$ and $\mu_{1}\leq\cdots\leq\mu_{n}$,
respectively. Then

$\operatorname{tr}(AB)\leq\sum_{i=1}^{n}\lambda_{i}\mu_{i},$

with equality precisely when there exist orthonormal $\\{u_{i}\\}_{i=1}^{n}$
in $\mathbb{R}^{n}$ such that

$A=\sum_{i=1}^{n}\lambda_{i}u_{i}u_{i}^{\top}\qquad\text{and}\qquad
B=\sum_{i=1}^{n}\mu_{i}u_{i}u_{i}^{\top}.$

###### Proof.

First, $A$ and $B$ of the prescribed form achieve equality in the given bound.
It remains to prove the bound and then show that equality requires $A$ and $B$
to have this form.

Consider the case where $A$ and $B$ are both positive definite. Then the
eigenvalues coincide with singular values, and so Theorem 3.1 in [7] gives the
bound, with equality precisely when there exist $V,W\in\operatorname{O}(n)$
such that $A=V\operatorname{diag}(\lambda)W^{\top}$ and
$B=V\operatorname{diag}(\mu)W^{\top}$. Since $A$ is positive definite, it has
polar decomposition $A=(VW^{\top})(W\operatorname{diag}(\lambda)W^{\top})$,
whose uniqueness implies $VW^{\top}=I_{n}$, i.e., $V=W$. This resolves the
positive definite case.

Now suppose $A$ and $B$ are symmetric, but not necessarily positive definite.
Then there exist $\alpha,\beta\in\mathbb{R}$ such that $A+\alpha I_{n},B+\beta
I_{n}\succ 0$. Our analysis above then gives

$\displaystyle\operatorname{tr}(AB)$
$\displaystyle=\operatorname{tr}((A+\alpha I_{n})(B+\beta
I_{n}))-\beta\operatorname{tr}A-\alpha\operatorname{tr}(B)-\alpha\beta n$
$\displaystyle\leq\sum_{i=1}^{n}(\lambda_{i}+\alpha)(\mu_{i}+\beta)-\beta\sum_{i=1}^{n}\lambda_{i}-\alpha\sum_{i=1}^{n}\mu_{i}-\alpha\beta
n=\sum_{i=1}^{n}\lambda_{i}\mu_{i},$

with equality precisely when there exist orthonormal $\\{u_{i}\\}_{i=1}^{n}$
in $\mathbb{R}^{n}$ such that

$A+\alpha
I_{n}=\sum_{i=1}^{n}(\lambda_{i}+\alpha)u_{i}u_{i}^{\top}\qquad\text{and}\qquad
B+\beta I_{n}=\sum_{i=1}^{n}(\mu_{i}+\beta)u_{i}u_{i}^{\top}.$

The result then follows since $\sum_{i}u_{i}u_{i}^{\top}=I_{n}$. ∎

Next, we show that for every optimal $x$ in (5) and $Y$ in (6), the top
eigenvector of $B\operatorname{diag}(x)B^{\top}$ is the bottom eigenvector of
$Y$, and it resides in $C$.

######  Lemma 17.

  * (a)

For every optimal $x$ in (5), the top eigenvalue of
$B\operatorname{diag}(x)B^{\top}$ is simple, and the corresponding eigenspace
is spanned by a positive combination of the columns of $B$.

  * (b)

Every optimal $Y$ in (6) has a unique negative eigenvalue, this eigenvalue is
simple, and the corresponding eigenspace is identical to the top eigenspace in
(a).

###### Proof.

For (a), let $D$ denote the square root of $\operatorname{diag}(x)$, and put
$S:=BD$. Since $S$ is square, we have that
$B\operatorname{diag}(x)B^{\top}=SS^{\top}$ has the same spectrum as
$S^{\top}S=DB^{\top}BD$ with the same multiplicities. By Lemma 4, $B^{\top}B$
is entrywise positive. Since $x>0$ by Lemma 15(a), it holds that $S^{\top}S$
is also entrywise positive, and so Perron–Frobenius gives that the top
eigenvalue is simple with an entrywise positive eigenvector $v$. Then the top
eigenvector of $B\operatorname{diag}(x)B^{\top}=SS^{\top}$ is $Sv=BDv$, i.e.,
a positive combination of the columns of $B$.

For (b), we first give a proof of weak duality between (5) and (6): For every
feasible $x$ in (5) and $Y$ in (6), if we let $\lambda,\mu\in\mathbb{R}^{d}$
denote the vectors of sorted eigenvalues of $Y$ and
$I_{d}-B\operatorname{diag}(x)B^{\top}$, respectively, then symmetric von
Neumann and Hölder together give

$\displaystyle\operatorname{tr}Y$ $\displaystyle\leq\operatorname{tr}Y-\langle
B^{\top}YB,\operatorname{diag}(x)\rangle$ $\displaystyle=\langle
Y,I_{d}-B\operatorname{diag}(x)B^{\top}\rangle$
$\displaystyle\leq\langle\lambda,\mu\rangle\leq\|\lambda\|_{1}\|\mu\|_{\infty}=\|Y\|_{*}\|B\operatorname{diag}(x)B^{\top}-I_{d}\|_{2\to
2}\leq\|B\operatorname{diag}(x)B^{\top}-I_{d}\|_{2\to 2}.$ (7)

If $x$ is optimal, then we may combine a portion of (7) with Lemma 15(a) to
get

$\operatorname{tr}Y\leq\|Y\|_{*}\|B\operatorname{diag}(x)B^{\top}-I_{d}\|_{2\to
2}<\|Y\|_{*}.$

Thus, every feasible $Y$ has a strictly negative eigenvalue, i.e.,
$\lambda_{1}<0$. Next, any optimal $x$ and $Y$ together achieve equality in
the following portion of (7):

$\langle\lambda,\mu\rangle\leq\|\lambda\|_{1}\|\mu\|_{\infty}.$

Equality requires $\operatorname{supp}(\lambda)\subseteq\arg\max_{i}|\mu_{i}|$
and $\lambda_{i}\mu_{i}\geq 0$ for all $i$. Since $\lambda_{1}<0$, we have
$1\in\arg\max_{i}|\mu_{i}|$. As a consequence of the simplicity conclusion of
part (a), $\mu$ is nonzero, meaning $|\mu_{1}|=\max_{i}|\mu_{i}|>0$, which,
combined with $\lambda_{1}<0$ and $\lambda_{1}\mu_{1}\geq 0$, implies
$\mu_{1}<0$. Next, part (a) gives $\mu_{1}<\mu_{i}$ for all $i>1$. It follows
that any $j\in\arg\max_{i}|\mu_{i}|$ with $j\neq 1$ must have $\mu_{j}>0$, and
so $\lambda_{j}\geq 0$. As such, $\lambda_{1}$ is the only negative eigenvalue
of $Y$.

Finally, any optimal $x$ and $Y$ achieve equality in the following portion of
(7):

$\langle
Y,I_{d}-B\operatorname{diag}(x)B^{\top}\rangle\leq\langle\lambda,\mu\rangle.$

By part (a), we have $\mu_{1}<\mu_{2}$, while the above gives
$\lambda_{1}<\lambda_{2}$. As such, Proposition 16 gives that the bottom
eigenspace of $Y$ is identical to the top eigenspace of
$B\operatorname{diag}(x)B^{\top}$. ∎

###### Proof of Lemma 14.

Given an optimizer $x$ of (5), we will show that $M:=\operatorname{diag}(x)$
is an optimizer of (3). Such a choice of $M$ is feasible in (3). By strong
duality, it suffices to show that any optimal $Y$ in (6) is feasible in (4).
To this end, by Lemma 17, we may diagonalize $Y=UDU^{\top}$ so that the first
column of $U$ is a positive combination of the columns of $B$ and
$D=\operatorname{diag}(\lambda_{1},\ldots,\lambda_{d})$ with
$\lambda_{1}<0\leq\lambda_{2}\leq\cdots\leq\lambda_{d}$. Consider the
ellipsoid

$E:=\\{z\in\mathbb{R}^{d}:z^{\top}Dz\leq
0,z_{1}=1\\}=\\{z\in\mathbb{R}^{d}:\lambda_{2}z_{2}^{2}+\cdots+\lambda_{d}z_{d}^{2}\leq|\lambda_{1}|,z_{1}=1\\}.$

Notably, $E$ is convex. Fix $i\in[d]$ and let $b_{i}$ denote the $i$th column
of $B$. We claim that $v:=U^{\top}b_{i}\in\operatorname{cone}(E)$. By Lemma
15(b), we have

$-|\lambda_{1}|v_{1}^{2}+\lambda_{2}v_{2}^{2}+\cdots+\lambda_{d}v_{d}^{2}=v^{\top}Dv=b_{i}^{\top}Yb_{i}=(B^{\top}YB)_{ii}=0.$

Rearranging then gives

$\lambda_{2}v_{2}^{2}+\cdots+\lambda_{d}v_{d}^{2}=|\lambda_{1}|v_{1}^{2}.$

Lemmas 17 and 4 together give $v_{1}>0$, and so $v\in\operatorname{cone}(E)$,
as claimed. Since our choice for $i\in[d]$ was arbitrary, it follows that the
closed chamber $\overline{C}$ (which is generated by the columns of $B$)
satisfies $U^{\top}\overline{C}\subseteq\operatorname{cone}(E)$. To show that
$Y$ is feasible in (4), i.e., $-B^{\top}YB\in\operatorname{COP}(d)$, take any
vector $x\geq 0$. Then $Bx\in\overline{C}$, and so
$v:=U^{\top}Bx\in\operatorname{cone}(E)$, meaning

$x^{\top}B^{\top}YBx=x^{\top}B^{\top}UDU^{\top}Bx=v^{\top}Dv\leq 0,$

as desired. ∎

###### Proof of Lemma 13.

By Lemma 14, there exists an optimizer of (3) that is diagonal, i.e., any
optimizer $x$ of the restriction (5) corresponds to an optimizer
$\operatorname{diag}(x)$ of (3). Consider a further restriction of (5):

$\text{minimize}\quad\|cBB^{\top}-I_{d}\|_{2\to 2}\quad\text{subject to}\quad
c\geq 0.$ (8)

In what follows, we show that any optimizer $c$ of (8) is strictly positive
and corresponds to an optimizer $c\mathbf{1}$ of (5).

First, the optimal $c$ in (8) is strictly positive, since $c=0$ has value $1$,
while $c=\sigma_{\max}(B)^{-2}$ has value strictly less than $1$ since the
columns of $B$ span. Next, the dual program of (8) is

$\text{maximize}\quad\operatorname{tr}Z\quad\text{subject
to}\quad\|Z\|_{*}\leq 1,\quad
Z^{\top}=Z,\quad\operatorname{tr}(B^{\top}ZB)\leq 0.$ (9)

Since (8) satisfies Slater’s condition, we have strong duality, and so it
suffices to show that an optimizer of the dual program (9) is feasible in (6).
To this end, we first give a proof of weak duality between (8) and (9): For
every feasible $c$ in (8) and $Z$ in (9), if we let
$\lambda,\mu\in\mathbb{R}^{d}$ denote the vectors of sorted eigenvalues of $Z$
and $I_{d}-cBB^{\top}$, respectively, then symmetric von Neumann and Hölder
together give

$\displaystyle\operatorname{tr}Z$
$\displaystyle\leq\operatorname{tr}Z-c\operatorname{tr}(B^{\top}ZB)$
$\displaystyle=\langle Z,I_{d}-cBB^{\top}\rangle$
$\displaystyle\leq\langle\lambda,\mu\rangle\leq\|\lambda\|_{1}\|\mu\|_{\infty}=\|Z\|_{*}\|cBB^{\top}-I_{d}\|_{2\to
2}\leq\|cBB^{\top}-I_{d}\|_{2\to 2}.$

Equality in
$\operatorname{tr}Z\leq\operatorname{tr}Z-c\operatorname{tr}(B^{\top}ZB)$
requires $\operatorname{tr}(B^{\top}ZB)=0$. Next, by Proposition 16, equality
in $\langle Z,I_{d}-cBB^{\top}\rangle\leq\langle\lambda,\mu\rangle$ implies
that $Z$ and $I_{d}-cBB^{\top}$ are simultaneously diagonalizable. Equality in
$\langle\lambda,\mu\rangle\leq\|\lambda\|_{1}\|\mu\|_{\infty}$ then gives that
$\lambda_{i}\neq 0$ only if $i\in\\{1,d\\}$.

Select any optimal $c$ in (8) and optimal $Z$ in (9). Let
$\\{u_{i}\\}_{i=1}^{d}$ denote the orthonormal basis of eigenvectors of
$I_{d}-cBB^{\top}$ afforded by Proposition 16. These eigenvectors appear in
the singular value decomposition

$B=\sum_{i=1}^{d}\sigma_{i}u_{i}v_{i}^{\top}$

as well as the eigenvalue decomposition

$Z=\lambda_{1}u_{1}u_{1}^{\top}+\lambda_{d}u_{d}u_{d}^{\top}.$

Then
$B^{\top}ZB=\sigma_{1}^{2}\lambda_{1}v_{1}v_{1}^{\top}+\sigma_{d}^{2}\lambda_{d}v_{d}v_{d}^{\top}$,
the trace of which is $\sigma_{1}^{2}\lambda_{1}+\sigma_{d}^{2}\lambda_{d}=0$
by the above complementary slackness argument. Thus,
$\operatorname{diag}(B^{\top}ZB)=0$ precisely when
$(v_{1})_{i}^{2}=(v_{d})_{i}^{2}$ for all $i\in[d]$, which in turn holds by
Lemma 5(a). As such, an optimizer of the dual program (9) is feasible in (6),
as desired. ∎

##  5 Proof of Theorem 7

Theorem 6 reports the best choice of max filtering templates in terms of the
matrix whose unit-norm rows form a fundamental system of $G$. Furthermore, the
singular values of this matrix determine the optimal condition number.
Recalling Coxeter’s classification, we compute these optimal condition numbers
in Mathematica333https://github.com/Daniel-Packer/reflection-
groups/blob/main/ExceptionalGroups.nb for finitely many reflection groups. The
optimal condition numbers for the dihedral groups are easy to compute by hand:

$AA^{\top}=\left[\begin{array}[]{cc}1&-\cos(\frac{\pi}{m})\\\
-\cos(\frac{\pi}{m})&1\end{array}\right]$

has eigenvalues $1\pm\cos(\frac{\pi}{m})$, and so
$\kappa(I_{m})=\sqrt{\frac{1+\cos(\frac{\pi}{m})}{1-\cos(\frac{\pi}{m})}}$,
which is $(\frac{2}{\pi}+o(1))m$ by the Taylor series expansion of cosine.

The remaining families $A_{\ell}$, $B_{\ell}$, and $D_{\ell}$ correspond to
$\ell\times\ell$ matrices whose characteristic polynomials are cumbersome to
interact with as $\ell\to\infty$. Instead, we determine the asymptotic form of
the optimal condition numbers in these cases. To do so, we embed the relevant
matrices as integral operators over a common Hilbert space, where we can
characterize spectral convergence as the matrix size grows.

######  Definition 18.

The pixel embedding of $A\in\mathbb{R}^{n\times n}$ is $A^{\sharp}\in
L^{2}([0,1]^{2})$ defined by

$A^{\sharp}(x,y)=\sum_{i=1}^{n}\sum_{j=1}^{n}A_{ij}\cdot n\cdot
1_{(\frac{i-1}{n},\frac{i}{n})}(x)\cdot 1_{(\frac{j-1}{n},\frac{j}{n})}(y),$

i.e., we chop the unit square into squares of width $1/n$, and then we take
$A^{\sharp}$ to be constant on each square according to appropriately scaled
entries of $A$. We interpret $A^{\sharp}$ as the kernel of an integral
operator $L^{2}([0,1])\to L^{2}([0,1])$, which we also denote $A^{\sharp}$ by
an abuse of notation:

$(A^{\sharp}f)(x):=\int_{0}^{1}A^{\sharp}(x,y)f(y)dy.$

######  Lemma 19.

Given a sequence $\\{A_{n}\\}_{n=1}^{\infty}$ of matrices of possibly
different sizes such that $A_{n}^{\sharp}\to K$ in $L^{2}([0,1]^{2})$, it
holds that $\|A_{n}\|_{2\to 2}\to\|K\|_{L^{2}\to L^{2}}$.

###### Proof.

First, we observe some relationships between $A\in\mathbb{R}^{n\times n}$ and
its pixel embedding $A^{\sharp}$:

  * •

The operator $A^{\sharp}$ acts invariantly on the subspace $P_{n}\leq
L^{2}([0,1])$ spanned by the characteristic functions of intervals
$(\frac{i-1}{n},\frac{i}{n})$.

  * •

$A$ is the matrix representation of the restriction $A^{\sharp}|_{P_{n}}$ with
respect to this basis.

  * •

The kernel of $A^{\sharp}$ contains the orthogonal complement of $P_{n}$ in
$L^{2}([0,1])$.

Thus, $\|A\|_{2\to 2}=\|A^{\sharp}\|_{L^{2}\to L^{2}}$. The result then
follows from Cauchy–Schwarz:

$\big{|}\|A_{n}^{\sharp}\|_{L^{2}\to L^{2}}-\|K\|_{L^{2}\to
L^{2}}\big{|}\leq\|A_{n}^{\sharp}-K\|_{L^{2}\to
L^{2}}=\sup_{\|f\|_{L^{2}}=1}\|(A_{n}^{\sharp}-K)f\|_{L^{2}}\leq\|A_{n}^{\sharp}-K\|_{L^{2}([0,1]^{2})}.\qed$

In the following subsections, we apply Lemma 19 to treat $A_{\ell}$,
$B_{\ell}$, and $D_{\ell}$. Unlike $B_{\ell}$ and $D_{\ell}$, the action of
$A_{\ell}$ is more naturally represented in an $(\ell+1)$-dimensional space.
For this reason, our analysis of $A_{\ell}$ is more intricate, while our
analysis of $B_{\ell}$ and $D_{\ell}$ is straightforward.

###  5.1 $A_{\ell}$

Fix $\ell\in\mathbb{N}$, put $d=\ell$, and select $A\in\mathbb{R}^{d\times d}$
with unit-norm rows that form a fundamental system for $A_{\ell}$. In this
subsection, we estimate

$\kappa(A_{\ell})=\frac{\sigma_{\max}(A)}{\sigma_{\min}(A)}=\sqrt{\frac{\lambda_{\max}(AA^{\top})}{\lambda_{\min}(AA^{\top})}}=\sqrt{\frac{2-\lambda_{\min}(AA^{\top})}{\lambda_{\min}(AA^{\top})}},$

where the last equality applies Lemma 5(b). It will be convenient to analyze

$M:=\left[\begin{array}[]{cc}AA^{\top}&0\\\ 0^{\top}&1\end{array}\right],$

which satisfies $\lambda_{\min}(M)=\lambda_{\min}(AA^{\top})$ by Lemma 5(b).
From the Coxeter diagram of $A_{\ell}$, we have that $AA^{\top}$ is
tridiagonal with $1$’s on the diagonal and $-\frac{1}{2}$’s above and below
the diagonal. Define $S\in\mathbb{R}^{(d+1)\times(d+1)}$ by

$S:=\left[\begin{array}[]{rrr|c}\frac{1}{\sqrt{2}}&&&\frac{1}{\sqrt{d+1}}\\\
-\frac{1}{\sqrt{2}}&\ddots&&\frac{1}{\sqrt{d+1}}\\\
&\ddots&\frac{1}{\sqrt{2}}&\vdots\\\
&&-\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{d+1}}\\\ \end{array}\right],$

where the blank entries are zeros. Then $S^{\top}S=M$, and furthermore, one
may verify that

$(S^{-1})_{ij}=\left\\{\begin{array}[]{cl}\sqrt{2}\cdot(1-\frac{i}{d+1})&\text{if
}j\leq i\leq d\\\ \frac{1}{\sqrt{d+1}}&\text{if }j\leq i=d+1\\\
-\sqrt{2}\cdot\frac{i}{d+1}&\text{if }j>i.\end{array}\right.$

We wish to estimate

$\sqrt{\lambda_{\min}(AA^{\top})}=\sqrt{\lambda_{\min}(M)}=\sigma_{\min}(S)=\sigma_{\max}(S^{-1})^{-1}=\tfrac{1}{d+1}\cdot\|\tfrac{1}{d+1}S^{-1}\|_{2\to
2}^{-1}.$

It is straightforward to verify that as $d\to\infty$, the pixel embedding
$(\frac{1}{d+1}S^{-1})^{\sharp}$ converges in $L^{2}([0,1]^{2})$ to the kernel
$K$ defined by

$K(x,y):=\left\\{\begin{array}[]{cl}\sqrt{2}\cdot(1-x)&\text{if }y\leq x\\\
-\sqrt{2}\cdot x&\text{if }y>x.\end{array}\right.$

Lemma 20 below gives that $\|K\|_{L^{2}\to L^{2}}=\sqrt{2}/\pi$, which
combined with Lemma 19 implies

$(d+1)\cdot\sqrt{\lambda_{\min}(AA^{\top})}=\|\tfrac{1}{d+1}S^{-1}\|_{2\to
2}^{-1}\to\|K\|_{L^{2}\to L^{2}}^{-1}=\tfrac{\pi}{\sqrt{2}},$

and so recalling $d=\ell$, we have

$\kappa(A_{\ell})=\sqrt{\frac{2-\lambda_{\min}(AA^{\top})}{\lambda_{\min}(AA^{\top})}}=(\tfrac{2}{\pi}+o(1))\ell,$

as desired.

######  Lemma 20.

For $K$ defined above, it holds that $\|K\|_{L^{2}\to L^{2}}=\sqrt{2}/\pi$.

###### Proof.

We start by identifying all eigenvalues and eigenvectors of $KK^{*}$. To this
end, a straightforward calculation gives

$(KK^{*}f)(x)=2\int_{0}^{x}\int_{y}^{1}f(z)dzdy-2x\int_{0}^{1}\int_{y}^{1}f(z)dzdy.$

Observe that $(KK^{*}f)(0)=0=(KK^{*}f)(1)$ for any $f\in L^{2}([0,1])$, and so
any eigenvector $g$ of $KK^{*}$ with nonzero eigenvalue must satisfy the
boundary conditions

$g(0)=0=g(1).$

Next, two applications of the fundamental theorem of calculus gives
$(KK^{*}f)^{\prime\prime}=-2f$, meaning $g$ is an eigenvector with eigenvalue
$\lambda$ only if $\lambda g^{\prime\prime}=-2g$. Notably, this implies that
$0$ is not an eigenvalue of $KK^{*}$. Since $KK^{*}$ is positive definite, it
follows that every eigenvalue is strictly positive. As such, $g$ is an
eigenvector with eigenvalue $\lambda>0$ only if
$g^{\prime\prime}=-\omega^{2}g$ with $\omega:=\sqrt{2/\lambda}$, i.e., there
exist $a,b\in\mathbb{R}$ such that

$g(x)=a\cos(\omega x)+b\sin(\omega x).$

The boundary condition $g(0)=0$ then implies that $a=0$, and since $g$ is an
eigenvector, it follows that $b\neq 0$. The boundary condition $g(1)=0$ then
gives $b\sin(\omega)=0$, i.e., $\omega=k\pi$ for some $k\in\mathbb{N}$. Thus,
every eigenvalue of $KK^{*}$ takes the form $2/(k\pi)^{2}$ for some
$k\in\mathbb{N}$. Furthermore, an easy calculation confirms that
$g(x):=\sin(\pi x)$ satisfies $KK^{*}g=(2/\pi^{2})g$. The $C^{*}$ identity and
the spectral theorem for compact self-adjoint operators then gives
$\|K\|_{L^{2}\to L^{2}}^{2}=\lambda_{\max}(KK^{*})=2/\pi^{2}$. ∎

###  5.2 $B_{\ell}$ and $D_{\ell}$

First, we address $B_{\ell}$. Fix $\ell\in\mathbb{N}$, put $d=\ell$, and
consider $A,B\in\mathbb{R}^{d\times d}$ defined by

$A:=\left[\begin{array}[]{cccc}\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}&\phantom{\ddots}&\\\
&\ddots&\ddots&\\\ &\phantom{\ddots}&\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}\\\
&&\phantom{\ddots}&1\end{array}\right],\qquad
B:=\left[\begin{array}[]{cccc}\sqrt{2}&\cdots&\sqrt{2}&1\\\
&\ddots&\vdots&\vdots\\\ &&\sqrt{2}&1\\\ &&&1\end{array}\right].$

The rows of $A$ form a fundamental system for $B_{\ell}$, and $B=A^{-1}$. As
$d\to\infty$, the pixel embedding $(\frac{1}{d}B)^{\sharp}$ converges in
$L^{2}([0,1]^{2})$ to $K$ defined by

$K(x,y):=\left\\{\begin{array}[]{cl}\sqrt{2}&\text{if }y\geq x\\\ 0&\text{if
}y<x.\end{array}\right.$

The operator $\frac{1}{\sqrt{2}}K$ is the adjoint of the Volterra operator,
whose operator norm is well known to be $2/\pi$ (by an argument similar to our
analysis of $A_{\ell}$). Then

$\lambda_{\min}(AA^{\top})=\lambda_{\max}(B^{\top}B)^{-1}=\tfrac{1}{d^{2}}\cdot\|\tfrac{1}{d}B\|_{2\to
2}^{-2}=\tfrac{1}{d^{2}}\Big{(}\|K\|_{2\to
2}^{-2}+o(1)\Big{)}=\tfrac{1}{d^{2}}(\tfrac{\pi^{2}}{8}+o(1)),$

and so recalling $d=\ell$, we have

$\kappa(B_{\ell})=\sqrt{\frac{2-\lambda_{\min}(AA^{\top})}{\lambda_{\min}(AA^{\top})}}=\sqrt{\frac{2-\tfrac{1}{d^{2}}(\tfrac{\pi^{2}}{8}+o(1))}{\tfrac{1}{d^{2}}(\tfrac{\pi^{2}}{8}+o(1))}}=(\tfrac{4}{\pi}+o(1))\ell.$

To analyze $D_{\ell}$, we instead take

$A:=\left[\begin{array}[]{cccr}\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}&\phantom{\ddots}&\\\
&\ddots&\ddots&\\\ &\phantom{\ddots}&\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}\\\
&\phantom{\ddots}&\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\end{array}\right],\qquad
B:=\left[\begin{array}[]{cccrc}\sqrt{2}&\cdots&\sqrt{2}&\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\\
&\ddots&\vdots&\vdots\phantom{~{}}&\vdots\\\
&&\sqrt{2}&\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\\
&&\phantom{\vdots}&-\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\end{array}\right].$

The rows of $A$ form a fundamental system for $D_{\ell}$, and $B=A^{-1}$. As
$d\to\infty$, the pixel embedding $(\frac{1}{d}B)^{\sharp}$ converges in
$L^{2}([0,1]^{2})$ to the same kernel $K$ defined above, and so the identical
argument gives $\kappa(D_{\ell})=(\tfrac{4}{\pi}+o(1))\ell$.

## Acknowledgments

The authors thank Jameson Cahill, Joey Iverson, John Jasper, and Yousef
Qaddura for enlightening discussions.

## References

  * [1] R. Balan, N. Haghani, M. Singh, Permutation Invariant Representations with Applications to Graph Deep Learning, arXiv:2203.07546
  * [2] A. S. Bandeira, B. Blum-Smith, J. Kileel, A. Perry, J. Weed, A. S. Wein, Estimation under group actions: Recovering orbits from invariants, arXiv:1712.10163
  * [3] T. Bendory, D. Edidin, W. Leeb, N. Sharon, Dihedral multi-reference alignment, IEEE Trans. Inform. Theory 68 (2022) 3489–3499.
  * [4] J. Cahill, X. Chen, A note on scalable frames, SampTA 2013, arXiv:1301.7292
  * [5] J. Cahill, A. Contreras, A. Contreras-Hip, Complete set of translation invariant measurements with Lipschitz bounds, Appl. Comput. Harmon. Anal. 49 (2020) 521–539.
  * [6] J. Cahill, J. W. Iverson, D. G. Mixon, D. Packer, Group-invariant max filtering, arXiv:2205.14039
  * [7] M. Carlsson, von Neumann’s trace inequality for Hilbert–Schmidt operators, Expo. Math. 39 (2021) 149–157.
  * [8] H. S. M. Coxeter, The complete enumeration of finite groups of the form $R_{i}^{2}=(R_{i}R_{j})^{k_{ij}}=1$, J. London Math. Soc. s1-10 (1935) 21–25.
  * [9] P. B. Denton, S. J. Parke, T. Tao, X. Zhang, Eigenvectors from eigenvalues: A survey of a basic identity in linear algebra, Bull. Am. Math. Soc. 59 (2021) 31–58.
  * [10] R. M. Kane, Reflection Groups and Invariant Theory, Springer, 2001.
  * [11] A. Perry, J. Weed, A. S. Bandeira, P. Rigollet, A. Singer, The sample complexity of multireference alignment, SIAM J. Math. Data Science 1 (2019) 497–517.
  * [12] R. S. Varga, Iterative Matrix Analysis, Springer, 1962.

##  Appendix A Proof of Lemma 5

###  A.1 Proof of Lemma 5(b) and (c)

The exceptional cases are treated in the Mathematica same notebook from
Section 5. In the case $G=I_{m}$, the eigenvalues of
$M=-\cos(\frac{\pi}{m})\cdot[\begin{smallmatrix}0&1\\\ 1&0\end{smallmatrix}]$
are $\pm\cos(\frac{\pi}{m})$, while $M^{(1)}=M^{(2)}=0$. For the remaining
cases where $G\in\\{A_{\ell},B_{\ell},D_{\ell}\\}$, we show that the
characteristic polynomials of $M$ and $M^{(j)}$ are either even or odd. Due to
the form of these matrices, it is more convenient to instead work with $2M$
and $2M^{(j)}$.

First, suppose $G=A_{\ell}$ for $\ell\in\mathbb{N}$ and denote

$M(A_{\ell}):=M,\qquad P_{\ell}(\lambda):=\operatorname{det}(\lambda
I_{\ell}-2M(A_{\ell})).$

If $\ell=1$, then $M(A_{\ell})=0$ and $P_{1}(\lambda)=\lambda$ is odd. If
$\ell=2$, then $G=I_{3}$ and $P_{2}(\lambda)=\lambda^{2}-1$ is even.
Otherwise, we have

$\lambda
I_{\ell}-2M(A_{\ell})=\left[\begin{array}[]{ccc}\lambda&1&0_{\ell-2}^{\top}\\\
1&\lambda&e_{1}^{\top}\\\ 0_{\ell-2}&e_{1}&\lambda
I_{\ell-2}-2M(A_{\ell-2})\end{array}\right],$ (10)

and so the cofactor expansion across the first row gives

$\displaystyle P_{\ell}(\lambda)$
$\displaystyle=\lambda\operatorname{det}\left[\begin{array}[]{cc}\lambda&e_{1}^{\top}\\\
e_{1}&\lambda
I_{\ell-2}-2M(A_{\ell-2})\end{array}\right]-\operatorname{det}\left[\begin{array}[]{cc}1&e_{1}^{\top}\\\
0_{\ell-2}&\lambda I_{\ell-2}-2M(A_{\ell-2})\end{array}\right]$ (15)
$\displaystyle=\lambda P_{\ell-1}(\lambda)-P_{\ell-2}(\lambda).$ (16)

By induction, it follows that $P_{\ell}(\lambda)$ is odd (even) precisely when
$\ell$ is odd (even). This proves Lemma 5(b) in this case. Meanwhile, Lemma
5(c) in this case follows from the fact that

$\lambda I_{\ell-1}-2M(A_{\ell})^{(j)}=\left[\begin{array}[]{cc}\lambda
I_{j-1}-2M(A_{j-1})&0\\\ 0&\lambda
I_{\ell-j}-2M(A_{\ell-j})\end{array}\right],$

whose determinant is a product of odd and/or even functions of $\lambda$.

Next, suppose $G=B_{\ell}$ for $\ell\in\mathbb{N}\setminus\\{1\\}$ and denote

$M(B_{\ell}):=M,\qquad Q_{\ell}(\lambda):=\operatorname{det}(\lambda
I_{\ell}-2M(B_{\ell})).$

If $\ell=2$, then $G=I_{4}$ and $Q_{2}(\lambda)=\lambda^{2}-2$ is even. If
$\ell=3$, then

$Q_{3}(\lambda)=\operatorname{det}\left[\begin{array}[]{ccc}\lambda&1&0\\\
1&\lambda&\sqrt{2}\\\
0&\sqrt{2}&\lambda\end{array}\right]=\lambda^{3}-3\lambda$

is odd. Otherwise, the same recursions (10) and (16) hold for $M(B_{\ell})$
and $Q_{\ell}$. By induction, it follows that $Q_{\ell}(\lambda)$ is odd
(even) precisely when $\ell$ is odd (even). This proves Lemma 5(b) in this
case. Meanwhile, denoting $X_{1}:=M(A_{1})$ and otherwise
$X_{\ell}:=M(B_{\ell})$, Lemma 5(c) in this case follows from the fact that

$\lambda I_{\ell-1}-2M(B_{\ell})^{(j)}=\left[\begin{array}[]{cc}\lambda
I_{j-1}-2M(A_{j-1})&0\\\ 0&\lambda I_{\ell-j}-2X_{\ell-j}\end{array}\right],$

whose determinant is a product of odd and/or even functions of $\lambda$.

Finally, suppose $G=D_{\ell}$ for $\ell\in\mathbb{N}\setminus\\{1,2\\}$ and
denote

$M(D_{\ell}):=M,\qquad R_{\ell}(\lambda):=\operatorname{det}(\lambda
I_{\ell}-2M(D_{\ell})).$

If $\ell=3$, then $G=A_{3}$ and so (16) gives that
$R_{3}(\lambda)=P_{3}(\lambda)$ is odd. If $\ell=4$, then

$R_{4}(\lambda)=\operatorname{det}\left[\begin{array}[]{cccc}\lambda&1&0&0\\\
1&\lambda&1&1\\\ 0&1&\lambda&0\\\
0&1&0&\lambda\end{array}\right]=\lambda^{4}-3\lambda^{2}$

is even. Otherwise, the same recursions (10) and (16) hold for $M(D_{\ell})$
and $R_{\ell}$. By induction, it follows that $R_{\ell}(\lambda)$ is odd
(even) precisely when $\ell$ is odd (even). This proves Lemma 5(b) in this
case. Meanwhile, denoting $Y_{1}:=M(A_{1})$, $Y_{2}:=0\in\mathbb{R}^{2\times
2}$, and otherwise $Y_{\ell}:=M(D_{\ell})$, Lemma 5(c) in this case follows
from the fact that

$\lambda I_{\ell-1}-2M(D_{\ell})^{(j)}=\left[\begin{array}[]{cc}\lambda
I_{j-1}-2M(A_{j-1})&0\\\ 0&\lambda I_{\ell-j}-2Y_{\ell-j}\end{array}\right],$

whose determinant is a product of odd and/or even functions of $\lambda$.

###  A.2 Proof of Lemma 5(a)

First, $AA^{\top}$ has the same eigenvectors as $M:=AA^{\top}-I_{d}$, and so
we can combine Lemma 5(b) and (c) with the eigenvector–eigenvalue identity
described in [9]:

$(v_{1})_{j}^{2}=\frac{\displaystyle\prod_{k=1}^{d-1}\Big{|}\lambda_{1}(M)-\lambda_{k}(M^{(j)})\Big{|}}{\displaystyle\prod_{k=2}^{d}\Big{|}\lambda_{1}(M)-\lambda_{k}(M)\Big{|}},\qquad(v_{d})_{j}^{2}=\frac{\displaystyle\prod_{k=1}^{d-1}\Big{|}\lambda_{d}(M)-\lambda_{k}(M^{(j)})\Big{|}}{\displaystyle\prod_{k=1}^{d-1}\Big{|}\lambda_{d}(M)-\lambda_{k}(M)\Big{|}}.$

The usual limiting argument allows us to assume that the denominators above
are nonzero without loss of generality. By Lemma 5(b) and (c), the numerators
are equal (as are the denominators):

$\prod_{k=1}^{d-1}\Big{|}\lambda_{1}(M)-\lambda_{k}(M^{(j)})\Big{|}=\prod_{k=1}^{d-1}\Big{|}-\lambda_{d}(M)+\lambda_{d-k}(M^{(j)})\Big{|}=\prod_{k=1}^{d-1}\Big{|}\lambda_{d}(M)-\lambda_{k}(M^{(j)})\Big{|},$
$\prod_{k=2}^{d}\Big{|}\lambda_{1}(M)-\lambda_{k}(M)\Big{|}=\prod_{k=2}^{d}\Big{|}-\lambda_{d}(M)+\lambda_{d-k+1}(M)\Big{|}=\prod_{k=1}^{d-1}\Big{|}\lambda_{d}(M)-\lambda_{k}(M)\Big{|},$

where in both cases the last step follows from reindexing.