Group-Generated Frames from Matrix Orbits
Dihedral and Finite Heisenberg Representations on \(\mathbb{C}^n\)
-1. Prelude & Motivation: Random vs. Structured Constructions
Our goal is to learn how to build frames in finite-dimensional spaces. A frame is a
collection of vectors that spans the space (and, in tight/Parseval cases, does so with excellent
numerical behavior). We will use two friendly recipes: a simple random recipe and a structured
recipe using matrices that come from a group action.
Two friendly recipes
- Random (SIM) recipe.
Pick an \(N\times M\) matrix \(A=[\,f_1\ \cdots\ f_M\,]\) by choosing each entry at random
from a continuous distribution (e.g., normal). The only way this fails to span is if
all \(N\times N\) minors are zero. Those minors are polynomials in the entries, and
the set where a nontrivial polynomial vanishes has measure zero. Hence, for \(M\ge N\), a
random draw gives a frame with probability one.Caveat: “probability one” is not a guarantee for a specific sample, and conditioning
(the ratio of the largest to smallest eigenvalue of the frame operator) can still be poor
for some draws. - Structured (group-orbit) recipe.
Choose a representation \(\rho:G\to\mathrm{GL}_d(\mathbb{C})\) and a seed vector \(v\).
Form the orbit \(\mathcal O_\rho(v)=\{\rho(g)v: g\in G\}\) and assemble the
orbit synthesis matrix \(A(v)=[\,\rho(g_1)v\ \cdots\ \rho(g_M)v\,]\).
The algebra of \(\rho\) often lets us prove, deterministically, that the orbit spans; if
\(\rho\) is unitary (i.e., \(\rho(g)^*=\rho(g)^{-1}\)), we can frequently get exact
tight identities for the frame operator.
- Representation: \(\rho:G\to\mathrm{GL}_d(\mathbb C)\) is any homomorphism
(matrices need not preserve inner products). - Unitary representation: \(\rho:G\to U(d)\); each \(\rho(g)\) is unitary, so
\(\langle\rho(g)x,\rho(g)y\rangle=\langle x,y\rangle\). - For finite (or compact) groups, one can change the inner product by averaging
to make a representation unitary.
Concrete mini-examples
1) Random frame in \(\mathbb R^2\) with three vectors.
Let
\(A=\begin{bmatrix}a_{11}&a_{12}&a_{13}\\ a_{21}&a_{22}&a_{23}\end{bmatrix}\) with i.i.d. normal entries and columns
\(f_1,f_2,f_3\). Almost surely, at least one \(2\times2\) minor is nonzero, so
\(\{f_1,f_2,f_3\}\) spans \(\mathbb R^2\).
The frame operator is \(S=F\,\overline{F}^{\top}=\sum_{i=1}^3 f_i\,\overline{f_i}^{\top}\).
If its two eigenvalues are close, the frame is well-conditioned.
2) A tiny dihedral example (\(n=4\)).
Take
\(T=\begin{bmatrix}0&1&0&0\\0&0&1&0\\0&0&0&1\\1&0&0&0\end{bmatrix}\)
and the reflection \(F\) sending \(e_k\) to \(e_{-k}\) (indices mod 4).
They are unitary and satisfy \(FTF=T^{-1}\).
With the seed \(v=e_1+e_2\), the orbit
\(\mathcal D(v)=\{T^k v,\ FT^k v:\ 0\le k\lt 4\}\) produces up to eight vectors;
in practice, two or three already span \(\mathbb C^4\). If we choose \(v\) so its DFT
magnitudes are equal on conjugate frequency pairs and vanish at the DC index, the full orbit
becomes tight (see §3.3).
3) Always-tight Heisenberg example (\(N=3\)).
Let
\(T=\begin{bmatrix}0&1&0\\0&0&1\\1&0&0\end{bmatrix}\), \(M=\operatorname{diag}(1,\omega,\omega^2)\) with
\(\omega=e^{2\pi i/3}\). For any seed \(g\in\mathbb C^3\), the orbit
\(\{M^qT^p g: p,q\in\mathbb Z_3\}\) satisfies
\[
\sum_{p,q}(M^qT^p)\,g\,\overline{g}^{\top}(T^{-p}M^{-q})=3\,\|g\|^2 I,
\]
so the system is tight with bound \(3\|g\|^2\) regardless of \(g\).
- Vectors are columns; inner product is linear in the first slot:
\(\langle x,y\rangle=x^{\top}\overline{y}\). - For \(F=[\,f_1\ \cdots\ f_M\,]\): \(G=\overline{F}^{\top}F\) (Gram) and
\(S=F\overline{F}^{\top}=\sum_i f_i\overline{f_i}^{\top}\) (frame operator). - We distinguish representations from unitary representations throughout (see §1.3–1.4′).
0. Overview & Learning Outcomes
We construct frames in finite-dimensional complex spaces using group orbits and highlight when unitary structure
yields immediate tightness. Proofs are carried out with explicit matrices.
- Vectors are columns relative to the standard basis \(e_0,\dots,e_{d-1}\).
- Inner product is linear in the first slot: \(\langle x,y\rangle = x^{\top}\overline{y}\).
- Rank‑one map is \(P_g = g\,\overline{g}^{\top}\) so that \(P_g x=\langle x,g\rangle\,g\).
- All operators are given as concrete matrices; e.g. \(FTF=T^{-1}\) is a matrix identity.
- State and contrast representation vs unitary representation; define orbit, frame, tight/Parseval.
- Write the dihedral generators \(T,F\) and Heisenberg generators \(T,M\) as matrices and verify their relations.
- Form an orbit \(\{\rho(g)v\}\), compute \(G\) and \(S\), and test tightness spectrally.
- Explain why the Heisenberg orbit is always tight and how DFT conditions yield tight dihedral orbits.
1. Core Definitions
Definition 1.1 (Group). A set \(G\) with a binary operation \((g,h)\mapsto gh\) that is associative, has an identity element \(e\), and for each \(g\in G\) an inverse \(g^{-1}\) with \(gg^{-1}=g^{-1}g=e\).
Definition 1.2 (Unitary matrix). \(U\in\mathbb{C}^{d\times d}\) is unitary if \(U^{*}U=I\).
Definition 1.3 (Representation). A map \(\rho:G\to \mathrm{GL}(V)\cong \mathrm{GL}_d(\mathbb{C})\) satisfying \(\rho(gh)=\rho(g)\rho(h)\). No inner-product preservation is assumed; matrices \(\rho(g)\) need not be unitary.
Definition 1.4′ (Unitary representation). A representation \(\rho:G\to U(d)\subset\mathrm{GL}_d(\mathbb{C})\) for which each \(\rho(g)\) is unitary (i.e., \(\rho(g)^{*}=\rho(g)^{-1}\)). Equivalently, \(\langle \rho(g)x,\rho(g)y\rangle=\langle x,y\rangle\) for all \(x,y\).
For finite (or compact) groups over \(\mathbb{C}\), any representation is unitarizable: one can change the inner product by averaging to make all \(\rho(g)\) unitary. For noncompact groups this need not hold.
Definition 1.5 (Orbit). For \(v\in\mathbb{C}^d\), \(\operatorname{Orb}(v)=\{\rho(g)v: g\in G\}\).
Definition 1.6 (Frame). A finite family \(\{f_i\}_{i=1}^M\subset\mathbb{C}^d\) is a frame if there exist \(A,B>0\) such that
\[
A\|x\|^2 \le \sum_{i=1}^M |\langle x,f_i\rangle|^2 \le B\|x\|^2 \quad(\forall x\in\mathbb{C}^d).
\]
If \(A=B=\alpha\) it is tight with bound \(\alpha\); if \(\alpha=1\) it is Parseval.
Frame operator & Gram (matrix form).
Let \(F=[\,f_1\ \cdots\ f_M\,]\in\mathbb{C}^{d\times M}\). With \(\langle\cdot,\cdot\rangle\) linear in the first slot,
\[
S=\sum_{i=1}^M f_i\,\overline{f_i}^{\top}=F\,\overline{F}^{\top},\qquad
G=\overline{F}^{\top}F,\quad G_{ij}=\langle f_j,f_i\rangle.
\]
The nonzero spectra of \(S\) and \(G\) coincide; optimal bounds are \(A=\lambda_{\min}(S)\), \(B=\lambda_{\max}(S)\).
Definition 2.1 (Gram matrix; matrix form).
Let \(\mathcal{F}=\{f_i\}_{i=1}^M\subset\mathbb{C}^d\) and assemble the analysis matrix
\(F=[\,f_1\ \cdots\ f_M\,]\in\mathbb{C}^{d\times M}\) (column vectors, standard basis).
With the convention \(\langle x,y\rangle = x^{\top}\overline{y}\) (linear in the first slot), the Gram matrix
\(G\in\mathbb{C}^{M\times M}\) is
\[
G_{ij}=\langle f_j,f_i\rangle,\qquad\text{equivalently}\qquad
G=\overline{F}^{\top}F.
\]
The frame operator is the \(d\times d\) matrix
\[
Sx=\sum_{i=1}^M \langle x,f_i\rangle f_i
\quad\Longleftrightarrow\quad
S=\sum_{i=1}^M f_i\,\overline{f_i}^{\top} = F\,\overline{F}^{\top}.
\]
Why the Gram matrix is important in frame theory.
- Encodes all inner products. \(G\) stores pairwise correlations; it detects orthogonality and redundancy.
- Rank and span. \(\mathrm{rank}(G)=\dim\mathrm{span}\,\{f_i\}\); spanning \(\Leftrightarrow\) \(\mathrm{rank}(G)=d\).
- Frame bounds via eigenvalues. \(S=F\,\overline{F}^{\top}\), \(G=\overline{F}^{\top}F\) have the same nonzero spectrum; tightness means that spectrum is constant.
- Parseval & partial isometries. Parseval \(\Leftrightarrow S=I\) \(\Leftrightarrow\) rows of \(F\) are orthonormal on the span.
3. The Dihedral Group \(D_{2n}\) on \(\mathbb{C}^n\)
3.1 Matrices and Relations
Let \(e_0,\ldots,e_{n-1}\) be the standard basis (indices mod \(n\)). Define the shift and negation-permutation matrices
T e_k=e_{k+1},\qquad
T=\begin{bmatrix}
0&1&0&\cdots&0\\
0&0&1&\cdots&0\\
\vdots&&&\ddots&\vdots\\
1&0&0&\cdots&0
\end{bmatrix},\qquad
F e_k=e_{-k},\qquad
F=\big[\ \delta_{i,\,-j\!\!\!\pmod n}\ \big]_{i,j=0}^{n-1},
\]
so \(F\) is the permutation matrix with a \(1\) in position \((i,j)\) iff \(i\equiv -j\pmod n\). The matrices are unitary and satisfy \(T^n=I\), \(F^2=I\), and \(FTF=T^{-1}\).
These realize the presentation \(D_{2n}=\langle r,s\mid r^n=e,\ s^2=e,\ srs=r^{-1}\rangle\) via \(\rho(r)=T\), \(\rho(s)=F\). This is a unitary representation.
3.2 Orbit System
For a seed \(v\in\mathbb{C}^n\), the dihedral orbit is
\mathcal{D}(v)
= \{\, T^{k}v,\ FT^{k}v \;|\; 0 \le k < n \,\}. \]
3.3 Tightness via a DFT Criterion
Discrete Fourier Transform (matrix form).
Let \(W_n=[\,\omega_n^{k\ell}\,]_{k,\ell=0}^{n-1}\) with \(\omega_n=e^{-2\pi i/n}\) and
\(F_n = \tfrac{1}{\sqrt{n}}W_n\). Then \(\widehat v = F_n^{\top}\overline{v}\). In the frequency basis,
\([
T]_{\text{DFT}}=\operatorname{diag}(e^{2\pi i\ell/n})\), and \([F]_{\text{DFT}}\) permutes conjugate indices \(\{\ell,n-\ell\}\).
Proposition 3.1 (Tight dihedral orbit: checkable condition).
If \(\widehat v[0]=0\) (and \(\widehat v[n/2]=0\) when \(n\) is even) and \(|\widehat v[\ell]|\) is constant on each nontrivial conjugate pair, then the unique elements of \(\mathcal{D}(v)\) form a tight frame.
Sketch. In the DFT basis, the representation decomposes into one- and two-dimensional invariant blocks; the frame operator is block-diagonal with each active block equal to a scalar multiple of the identity equal to the block energy. The stated equal-modulus conditions equalize these scalars.
4. The Finite Heisenberg (Weyl) Group on \(\mathbb{C}^N\)
4.1 Matrices and Commutation
Fix \(\omega=e^{2\pi i/N}\). Define the unitary matrices
T=\begin{bmatrix}
0&1&0&\cdots&0\\
0&0&1&\cdots&0\\
\vdots&&&\ddots&\vdots\\
1&0&0&\cdots&0
\end{bmatrix},\qquad
M=\operatorname{diag}(1,\omega,\omega^2,\dots,\omega^{N-1}).
\]
They satisfy the commutation relation \(MT=\omega\,TM\). The set \(\{M^qT^p: p,q\in\mathbb{Z}_N\}\) has size \(N^2\) and furnishes a unitary representation.
4.2 Orbit and Main Theorem
For a seed \(g\in\mathbb{C}^N\), define the Heisenberg orbit
\mathcal{G}(g)=\{\,M^{q}T^{p}g:\ p,q\in\mathbb{Z}_N\,\}.
\]
Theorem 4.1 (Tightness with exact bound; matrix statement).
\[
S
= \sum_{p,q} (M^qT^p)\,g\,\overline{g}^{\top}\,(T^{-p}M^{-q})
= N\,\|g\|^2\, I.
\]
Hence \(\mathcal{G}(g)\) is tight with bound \(N\|g\|^2\).
Entrywise proof. Write \(v_{p,q}=M^qT^p g\); then \(S=\sum_{p,q} v_{p,q}\,\overline{v_{p,q}}^{\top}\). Using \(v_{p,q}[m]=\omega^{qm}\,g[m-p]\) and summing the geometric series in \(q\) kills off‑diagonals and leaves \(S=N\|g\|^2 I\).
5. Worked Examples & Computation Patterns
5.1 Dihedral, \(n=6\)
Let \(\widehat v[0]=\widehat v[3]=0\) and \(|\widehat v[1]|=|\widehat v[2]|=1\). Choose phases to make \(v\in\mathbb{R}^6\); compute \(v=\overline{F_6}\,\widehat v\). Build \(\mathcal{D}(v)\) and select six columns to form a \(6\times 6\) matrix. Row‑reduce to confirm independence and estimate tightness via the spectrum of \(S\).
5.2 Heisenberg, \(N=5\)
Take a random unit \(g\in\mathbb{C}^5\), form a \(15\)-vector subsample \(\{M^qT^p g\}\) (e.g., \(p,q\in\{0,1,2\}\)), and check the span equals \(\mathbb{C}^5\). Then compute the full frame matrix to observe \(S=5I\).
6. Exercises (with brief solutions)
-
Gram structure (Dihedral). For \(n=5\) and \(v=e_0\), compute \(\langle T^{k’}v, T^{k}v\rangle\) and \(\langle FT^{k’}v, T^{k}v\rangle\) explicitly as functions of \(k-k’\).
Solution sketch. \(\langle T^{k’}e_0, T^{k}e_0\rangle=\delta_{k,k’}\). For the mixed term, use \(F_{i,j}=\delta_{i,-j\!\!\!\pmod 5}\) and shift indices. -
Unitary checks (Heisenberg). Verify \(T^{*}T=I\) and \(M^{*}M=I\); compute \(T^{*}\) and \(M^{*}\) explicitly.
Solution. \(T\) is a permutation matrix, hence unitary with \(T^{*}=T^{-1}=T^{N-1}\). \(M\) is diagonal with unimodular entries, so \(M^{*}=M^{-1}=\operatorname{diag}(1,\omega^{-1},\dots,\omega^{-(N-1)})\). - Heisenberg tightness (entrywise proof). Reproduce the proof of Theorem 4.1 by computing \(S_{m’,m}\) and summing over \(q\) first to kill off‑diagonals via \(\sum_q \omega^{q(m’-m)}\).
- DFT design (Dihedral, real seed). For \(n=8\), prescribe \(|\widehat v[1]|=|\widehat v[2]|=|\widehat v[3]|=1\), set \(\widehat v[0]=\widehat v[4]=0\), enforce conjugate symmetry, and compute \(v=\overline{F_8}\,\widehat v\). Explain tightness from the block‑diagonal picture.
7. Summary & Checklist
- Definitions: group, unitary, representation vs unitary representation, orbit, frame, tight/Parseval, frame operator, Gram.
- Dihedral: \(T\) (shift), \(F\) (negation permutation), relation \(FTF=T^{-1}\), DFT-based tightness criterion.
- Heisenberg: \(T\) (shift), \(M\) (diagonal modulation), relation \(MT=\omega TM\), tightness with bound \(N\|g\|^2\).