An official website of the United States government
Abstract Assume that a ground‐based vehicle moves in a room with walls or other planar surfaces. Can the vehicle reconstruct the positions of the walls from the echoes of a single sound event? We assume that the vehicle carries some microphones and that a loudspeaker is either also mounted on the vehicle or placed at a fixed location in the room. We prove that the reconstruction is almost always possible if (1) no echoes are received from floors, ceilings, or sloping walls and the vehicle carries at least three noncollinear microphones, or if (2) walls of any inclination may occur, the loudspeaker is fixed in the room and there are four noncoplanar microphones. The difficulty lies in the echo‐matching problem: How to determine which echoes come from the same wall. We solve this by using a Cayley–Menger determinant. Our proofs use methods from computational commutative algebra.
more »
« less
Heronian Friezes
Abstract Motivated by computational geometry of point configurations on the Euclidean plane, and by the theory of cluster algebras of type $$A$$, we introduce and study Heronian friezes, the Euclidean analogues of Coxeter’s frieze patterns. We prove that a generic Heronian frieze possesses the glide symmetry (hence is periodic) and establish the appropriate version of the Laurent phenomenon. For a closely related family of Cayley–Menger friezes, we identify an algebraic condition of coherence, which all friezes of geometric origin satisfy. This yields an unambiguous propagation rule for coherent Cayley–Menger friezes, as well as the corresponding periodicity results.
more »
« less
- Award ID(s):
- 1664722
- PAR ID:
- 10274151
- Date Published:
- Journal Name:
- International Mathematics Research Notices
- Volume:
- 2021
- Issue:
- 1
- ISSN:
- 1073-7928
- Page Range / eLocation ID:
- 648 to 694
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Frieze groups are discrete subgroups of the full group of isometries of a flat strip. We investigate here the dynamics of specific architected materials generated by acting with a frieze group on a collection of self-coupling seed resonators. We demonstrate that, under unrestricted reconfigurations of the internal structures of the seed resonators, the dynamical matrices of the materials generate the full self-adjoint sector of the stabilized group C*-algebra of the frieze group. As a consequence, in applications where the positions, orientations and internal structures of the seed resonators are adiabatically modified, the spectral bands of the dynamical matrices carry a complete set of topological invariants that are fully accounted by the K-theory of the mentioned algebra. By resolving the generators of the K-theory, we produce the model dynamical matrices that carry the elementary topological charges, which we implement with systems of plate resonators to showcase several applications in spectral engineering. The paper is written in an expository style.more » « less
-
Abstract Does every $$n$$-vertex Cayley graph have an orthonormal eigenbasis all of whose coordinates are $$O(1/\sqrt{n})$$? While the answer is yes for abelian groups, we show that it is no in general. On the other hand, we show that every $$n$$-vertex Cayley graph (and more generally, vertex-transitive graph) has an orthonormal basis whose coordinates are all $$O(\sqrt{\log n / n})$$, and that this bound is nearly best possible. Our investigation is motivated by a question of Assaf Naor, who proved that random abelian Cayley graphs are small-set expanders, extending a classic result of Alon–Roichman. His proof relies on the existence of a bounded eigenbasis for abelian Cayley graphs, which we now know cannot hold for general groups. On the other hand, we navigate around this obstruction and extend Naor’s result to nonabelian groups.more » « less
-
The spectral decomposition of graph adjacency matrices is an essential ingredient in the design of graph signal processing (GSP) techniques. When the adjacency matrix has multi-dimensional eigenspaces, it is desirable to base GSP constructions on a particular eigenbasis that better reflects the graph’s symmetries. In this paper, we provide an explicit and detailed representation-theoretic account for the spectral decomposition of the adjacency matrix of a weighted Cayley graph. Our method applies to all weighted Cayley graphs, regardless of whether they are quasi-Abelian, and offers detailed descrip- tions of eigenvalues and eigenvectors derived from the coefficient functions of the representations of the underlying group. Next, we turn our attention to constructing frames on Cayley graphs. Frames are overcomplete spanning sets that ensure stable and potentially redundant systems for signal re- construction. We use our proposed eigenbases to build frames that are suitable for developing signal processing on Cayley graphs. These are the Frobenius–Schur frames and Cayley frames, for which we provide a characterization and a practical recipe for their construction.more » « less
-
Let $$G$$ be a finite group acting transitively on $$[n]=\{1,2,\ldots,n\}$$, and let $$\Gamma=\mathrm{Cay}(G,T)$$ be a Cayley graph of $$G$$. The graph $$\Gamma$$ is called normal if $$T$$ is closed under conjugation. In this paper, we obtain an upper bound for the second (largest) eigenvalue of the adjacency matrix of the graph $$\Gamma$$ in terms of the second eigenvalues of certain subgraphs of $$\Gamma$$. Using this result, we develop a recursive method to determine the second eigenvalues of certain Cayley graphs of $$S_n$$, and we determine the second eigenvalues of a majority of the connected normal Cayley graphs (and some of their subgraphs) of $$S_n$$ with $$\max_{\tau\in T}|\mathrm{supp}(\tau)|\leqslant 5$$, where $$\mathrm{supp}(\tau)$$ is the set of points in $[n]$ non-fixed by $$\tau$$.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1093/imrn/rnaa057
