Gram matrix | EPFL Graph Search

In linear algebra, the Gram matrix (or Gramian matrix, Gramian) of a set of vectors v_1,\dots, v_n in an inner product space is the Hermitian matrix of inner products, whose entries are given by the inner product G_{ij} = \left\langle v_i, v_j \right\rangle. If the vectors v_1,\dots, v_n are the columns of matrix X then the Gram matrix is X^\dagger X in the general case that the vector coordinates are complex numbers, which simplifies to X^\top X for the case that the vector coordinates are real numbers. An important application is to compute linear independence: a set of vectors are linearly independent if and only if the Gram determinant (the determinant of the Gram matrix) is non-zero. It is named after Jørgen Pedersen Gram. Examples For finite-dimensional real vectors in \mathbb{R}^n with the usual Euclidean dot product, the Gram matrix is G = V^\top V, where

Capacities, Systoles and Jacobians of Riemann Surfaces

Björn Mützel

To any compact Riemann surface of genus g one may assign a principally polarized abelian variety (PPAV) of dimension g, the Jacobian of the Riemann surface. The Jacobian is a complex torus and we call a Gram matrix of the lattice of a Jacobian a period Gram matrix. The aim of this thesis is to contribute to the Schottky problem, which is to discern the Jacobians among the PPAVs. Buser and Sarnak approached this problem by means of a geometric invariant, the first successive minimum. They showed that the square of the first successive minimum, the squared norm of the shortest non-zero vector, in the lattice of a Jacobian of a Riemann surface of genus g is bounded from above by log(4g), whereas it can be of order g for the lattice of a PPAV of dimension g. The main goal of this work was to improve this result and to get insight into the connection between the geometry of a compact Riemann surface that is given in hyperbolic geometric terms, and the geometry of its Jacobian. We show the following general findings: For a hyperelliptic surface the first successive minimum is bounded from above by a universal constant. The square of the second successive minimum of the Jacobian of a Riemann surface of genus g is equally of order log(g). We provide refined upper bounds on the consecutive successive minima if the surface contains several disjoint small simple closed geodesics and a lower bound for the norm of certain lattice vectors of the Jacobian, if the surface contains small non-separating simple closed geodesics. If the concrete geometry of the Riemann surface is known, more precise statements can be made. In this case we obtain theoretical and practical estimates on all entries of the period Gram matrix. Here we establish upper and lower bounds based on the geometry of the cut locus of simple closed geodesics and also on the geometry of Q-pieces. In addition the following two results have been obtained: First, an improved lower bound for the maximum value of the norm of the shortest non-zero lattice vector among all PPAVs in even dimensions. This follows from an averaging method from the geometry of numbers applied to a family of symmetric PPAVs. Second, a new proof for a lower bound on the number of homotopically distinct geodesic loops, whose length is smaller than a fixed constant. This lower bound applies not only to geodesic loops on Riemann surfaces, but on arbitrary manifolds of non-positive curvature.

EPFL2011

Algorithmic aspects of sums of Hermitian squares of noncommutative polynomials

Sabine Burgdorf

This paper presents an algorithm and its implementation in the software package NCSOStools for finding sums of Hermitian squares and commutators decompositions for polynomials in noncommuting variables. The algorithm is based on noncommutative analogs of the classical Gram matrix method and the Newton polytope method, which allows us to use semidefinite programming. Throughout the paper several examples are given illustrating the results.

Springer2013

Least-Squares Padé approximation of parametric and stochastic Helmholtz maps

Francesca Bonizzoni, Fabio Nobile, Davide Pradovera

The present work deals with rational model order reduction methods based on the single-point Least-Square (LS) Padé approximation techniques introduced in Bonizzoni et al. (ESAIM Math. Model. Numer. Anal., 52(4), 1261–1284 2018, Math. Comput. 89, 1229–1257 2020). Algorithmical aspects concerning the construction of rational LS-Padé approximants are described. In particular, we show that the computation of the Padé denominator can be carried out efficiently by solving an eigenvalue-eigenvector problem involving a Gramian matrix. The LS-Padé techniques are employed to approximate the frequency response map associated with two parametric time-harmonic acoustic wave problems, namely a transmission-reflection problem and a scattering problem. In both cases, we establish the meromorphy of the frequency response map. The Helmholtz equation with stochastic wavenumber is also considered. In particular, for Lipschitz functionals of the solution and their corresponding probability measures, we establish weak convergence of the measure derived from the LS-Padé approximant to the true one. 2D numerical tests are performed, which confirm the effectiveness of the approximation methods.

2020

Capacities, Systoles and Jacobians of Riemann Surfaces

Björn Mützel

EPFL2011