Source author record

Jan Draisma

Jan Draisma appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Catalog footprint

What is connected

31works
10topics
4close collaborators

Actions

Connect this record

Log in to claim

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

31 published item(s)

preprint2024arXiv

Two improvements in Brauer's theorem on forms

Let $k$ be a Brauer field, that is, a field over which every diagonal form in sufficiently many variables has a nonzero solution; for instance, $k$ could be an imaginary quadratic number field. Brauer proved that if $f_1, \ldots, f_r$ are homogeneous polynomials on a $k$-vector space $V$ of degrees $d_1, \ldots, d_r$, then the variety $Z$ defined by the $f_i$'s has a non-trivial $k$-point, provided that $\dim{V}$ is sufficiently large compared to the $d_i$'s and $k$. We offer two improvements to this theorem, assuming $k$ is infinite. First, we show that the Zariski closure of the set $Z(k)$ of $k$-points has codimension $<C$, where $C$ is a constant depending only on the $d_i$'s and $k$. And second, we show that if the strength of the $f_i$'s is sufficiently large in terms of the $d_i$'s and $k$, then $Z(k)$ is actually Zariski dense in $Z$. The proofs rely on recent work of Ananyan and Hochster on high strength polynomials.

preprint2022arXiv

Components of symmetric wide-matrix varieties

We show that if X_n is a variety of cxn-matrices that is stable under the group Sym([n]) of column permutations and if forgetting the last column maps X_n into X_{n-1}, then the number of Sym([n])-orbits on irreducible components of X_n is a quasipolynomial in n for all sufficiently large n. To this end, we introduce the category of affine FI^op-schemes of width one, review existing literature on such schemes, and establish several new structural results about them. In particular, we show that under a shift and a localisation, any width-one FI^op-scheme becomes of product form, where X_n=Y^n for some scheme Y in affine c-space. Furthermore, to any FI^op-scheme of width one we associate a component functor from the category FI of finite sets with injections to the category PF of finite sets with partially defined maps. We present a combinatorial model for these functors and use this model to prove that Sym([n])-orbits of components of X_n, for all n, correspond bijectively to orbits of a groupoid acting on the integral points in certain rational polyhedral cones. Using the orbit-counting lemma for groupoids and theorems on quasipolynomiality of lattice point counts, this yields our Main Theorem.

preprint2022arXiv

Implicitisation and Parameterisation in Polynomial Functors

In earlier work, the second author showed that a closed subset of a polynomial functor can always be defined by finitely many polynomial equations. In follow-up work on $\operatorname{GL}\nolimits_{\infty}$-varieties, Bik-Draisma-Eggermont-Snowden showed, among other things, that in characteristic zero every such closed subset is the image of a morphism whose domain is the product of a finite-dimensional affine variety and a polynomial functor. In this paper, we show that both results can be made algorithmic: there exists an algorithm $\mathbf{implicitise}$ that takes as input a morphism into a polynomial functor and outputs finitely many equations defining the closure of the image; and an algorithm $\mathbf{parameterise}$ that takes as input a finite set of equations defining a closed subset of a polynomial functor and outputs a morphism whose image is that closed subset.

preprint2022arXiv

On the quadratic equations for odeco tensors

Elina Robeva discovered quadratic equations satisfied by orthogonally decomposable ("odeco") tensors. Boralevi-Draisma-Horobeţ-Robeva then proved that, over the real numbers, these equations characterise odeco tensors. This raises the question to what extent they also characterise the Zariski-closure of the set of odeco tensors over the complex numbers. In the current paper we restrict ourselves to symmetric tensors of order three, i.e., of format $n \times n \times n$. By providing an explicit counterexample to one of Robeva's conjectures, we show that for $n \geq 12$, these equations do not suffice. Furthermore, in the open subset where the linear span of the slices of the tensor contains an invertible matrix, we show that Robeva's equations cut out the limits of odeco tensors for dimension $n \leq 13$, and not for $n \geq 14$ on. To this end, we show that Robeva's equations essentially capture the Gorenstein locus in the Hilbert scheme of $n$ points and we use work by Casnati-Jelisiejew-Notari on the (ir)reducibility of this locus.

preprint2022arXiv

Quasihomomorphisms from the integers into Hamming metrics

A function $f: \mathbb{Z} \to \mathbb{Q}^n$ is a $c$-quasihomomorphism if the Hamming distance between $f(x+y)$ and $f(x)+f(y)$ is at most $c$ for all $x,y \in \mathbb{Z}$. We show that any $c$-quasihomomorphism has distance at most some constant $C(c)$ to an actual group homomorphism; here $C(c)$ depends only on $c$ and not on $n$ or $f$. This gives a positive answer to a special case of a question posed by Kazhdan and Ziegler.

preprint2022arXiv

The geometry of polynomial representations

We define a GL-variety to be a (typically infinite dimensional) algebraic variety equipped with an action of the infinite general linear group under which the coordinate ring forms a polynomial representation. Such varieties have been used to study asymptotic properties of invariants like strength and tensor rank, and played a key role in two recent proofs of Stillman's conjecture. We initiate a systematic study of GL-varieties, and establish a number of foundational results about them. For example, we prove a version of Chevalley's theorem on constructible sets in this setting.

preprint2022arXiv

Topological Noetherianity of polynomial functors II: base rings with Noetherian spectrum

In a previous paper, the third author proved that finite-degree polynomial functors over infinite fields are topologically Noetherian. In this paper, we prove that the same holds for polynomial functors from free $R$-modules to finitely generated $R$-modules, for any commutative ring $R$ whose spectrum is Noetherian. As Erman-Sam-Snowden pointed out, when applying this with $R = \mathbb{Z}$ to direct sums of symmetric powers, one of their proofs of a conjecture by Stillman becomes characteristic-independent. Our paper advertises and further develops the beautiful but not so well-known machinery of polynomial laws. In particular, to any finitely generated R-module M we associate a topological space, which we show is Noetherian when $\operatorname{Spec}(R)$ is; this is the degree-zero case of our result on polynomial functors.

preprint2020arXiv

Catalan-many tropical morphisms to trees; Part I: Constructions

We investigate the tree gonality of a genus-$g$ metric graph, defined as the minimum degree of a tropical morphism from any tropical modification of the metric graph to a metric tree. We give a combinatorial constructive proof that this number is at most $\lceil g/2 \rceil + 1$, a fact whose proofs so far required an algebro-geometric detour via special divisors on curves. For even genus, the tropical morphism which realizes the bound belongs to a family of tropical morphisms that is pure of dimension $3g-3$ and that has a generically finite-to-one map onto the moduli space of genus-$g$ metric graphs. Our methods focus on the study of such families. This is part I in a series of two papers: in part I we fix the combinatorial type of the metric graph, while in part II we vary the combinatorial type and show that the number of tropical morphisms, counted with suitable multiplicities, is the same Catalan number that counts morphisms from a genus-$g$ curve to the projective line.

preprint2020arXiv

The irreducible control property in matrix groups

This paper concerns matrix decompositions in which the factors are restricted to lie in a closed subvariety of a matrix group. Such decompositions are of relevance in control theory: given a target matrix in the group, can it be decomposed as a product of elements in the subvarieties, in a given order? And if so, what can be said about the solution set to this problem? Can an irreducible curve of target matrices be lifted to an irreducible curve of factorisations? We show that under certain conditions, for a sufficiently long and complicated such sequence, the solution set is always irreducible, and we show that every connected matrix group has a sequence of one-parameter subgroups that satisfies these conditions, where the sequence has length less than 1.5 times the dimension of the group.

preprint2019arXiv

The monic rank

We introduce the monic rank of a vector relative to an affine-hyperplane section of an irreducible Zariski-closed affine cone $X$. We show that the monic rank is finite and greater than or equal to the usual $X$-rank. We describe an algorithmic technique based on classical invariant theory to determine, in concrete situations, the maximal monic rank. Using this technique, we establish three new instances of a conjecture due to B. Shapiro which states that a binary form of degree $d\cdot e$ is the sum of $d$ $d$-th powers of forms of degree $e$. Furthermore, in the case where $X$ is the cone of highest weight vectors in an irreducible representation---this includes the well-known cases of tensor rank and symmetric rank---we raise the question whether the maximal rank equals the maximal monic rank. We answer this question affirmatively in several instances.

preprint2016arXiv

On the existence of identifiable reparametrizations for linear compartment models

The parameters of a linear compartment model are usually estimated from experimental input-output data. A problem arises when infinitely many parameter values can yield the same result; such a model is called unidentifiable. In this case, one can search for an identifiable reparametrization of the model: a map which reduces the number of parameters, such that the reduced model is identifiable. We study a specific class of models which are known to be unidentifiable. Using algebraic geometry and graph theory, we translate a criterion given by Meshkat and Sullivant for the existence of an identifiable scaling reparametrization to a new criterion based on the rank of a weighted adjacency matrix of a certain bipartite graph. This allows us to derive several new constructions to obtain graphs with an identifiable scaling reparametrization. Using these constructions, a large subclass of such graphs is obtained. Finally, we present a procedure of subdividing or deleting edges to ensure that a model has an identifiable scaling reparametrization.

preprint2015arXiv

Automorphism groups of Gaussian chain graph models

In this paper we extend earlier work on groups acting on Gaussian graphical models to Gaussian Bayesian networks and more general Gaussian models defined by chain graphs. We discuss the maximal group which leaves a given model invariant and provide basic statistical applications of this result. This includes equivariant estimation, maximal invariants and robustness. The computation of the group requires finding the essential graph. However, by applying Studeny's theory of imsets we show that computations for DAGs can be performed efficiently without building the essential graph. In our proof we derive simple necessary and sufficient conditions on vanishing sub-minors of the concentration matrix in the model.

preprint2015arXiv

Finiteness results for Abelian tree models

Equivariant tree models are statistical models used in the reconstruction of phylogenetic trees from genetic data. Here equivariant refers to a symmetry group imposed on the root distribution and on the transition matrices in the model. We prove that if that symmetry group is Abelian, then the Zariski closures of these models are defined by polynomial equations of bounded degree, independent of the tree. Moreover, we show that there exists a polynomial-time membership test for that Zariski closure. This generalises earlier results on tensors of bounded rank, which correspond to the case where the group is trivial, and implies a qualitative variant of a quantitative conjecture by Sturmfels and Sullivant in the case where the group and the alphabet coincide. Our proofs exploit the symmetries of an infinite-dimensional projective limit of Abelian star models.

preprint2015arXiv

Noetherianity for infinite-dimensional toric varieties

We consider a large class of monomial maps respecting an action of the infinite symmetric group, and prove that the toric ideals arising as their kernels are finitely generated up to symmetry. Our class includes many important examples where Noetherianity was recently proved or conjectured. In particular, our results imply Hillar-Sullivant's Independent Set Theorem and settle several finiteness conjectures due to Aschenbrenner, Martin del Campo, Hillar, and Sullivant. We introduce a matching monoid and show that its monoid ring is Noetherian up to symmetry. Our approach is then to factorize a more general equivariant monomial map into two parts going through this monoid. The kernels of both parts are finitely generated up to symmetry: recent work by Yamaguchi-Ogawa-Takemura on the (generalized) Birkhoff model provides an explicit degree bound for the kernel of the first part, while for the second part the finiteness follows from the Noetherianity of the matching monoid ring.

preprint2015arXiv

Orthogonal and unitary tensor decomposition from an algebraic perspective

While every matrix admits a singular value decomposition, in which the terms are pairwise orthogonal in a strong sense, higher-order tensors typically do not admit such an orthogonal decomposition. Those that do have attracted attention from theoretical computer science and scientific computing. We complement this existing body of literature with an algebro-geometric analysis of the set of orthogonally decomposable tensors. More specifically, we prove that they form a real-algebraic variety defined by polynomials of degree at most four. The exact degrees, and the corresponding polynomials, are different in each of three times two scenarios: ordinary, symmetric, or alternating tensors; and real-orthogonal versus complex-unitary. A key feature of our approach is a surprising connection between orthogonally decomposable tensors and semisimple algebras---associative in the ordinary and symmetric settings and of compact Lie type in the alternating setting.

preprint2015arXiv

Plücker varieties and higher secants of Sato's Grassmannian

Every Grassmannian, in its Plücker embedding, is defined by quadratic polynomials. We prove a vast, qualitative, generalisation of this fact to what we call Plücker varieties. A Plücker variety is in fact a family of varieties in exterior powers of vector spaces that, like the Grassmannian, is functorial in the vector space and behaves well under duals. A special case of our result says that for each fixed natural number k, the k-th secant variety of any Plücker-embedded Grassmannian is defined in bounded degree independent of the Grassmannian. Our approach is to take the limit of a Plücker variety in the dual of a highly symmetric space known as the infinite wedge, and to prove that up to symmetry the limit is defined by finitely many polynomial equations. For this we prove the auxilliary result that for every natural number p the space of p-tuples of infinite-by-infinite matrices is Noetherian modulo row and column operations. Our results have algorithmic counterparts: every bounded Plücker variety has a polynomial-time membership test, and the same holds for Zariski-closed, basis-independent properties of p-tuples of matrices.

preprint2014arXiv

The Euclidean distance degree of an algebraic variety

The nearest point map of a real algebraic variety with respect to Euclidean distance is an algebraic function. For instance, for varieties of low rank matrices, the Eckart-Young Theorem states that this map is given by the singular value decomposition. This article develops a theory of such nearest point maps from the perspective of computational algebraic geometry. The Euclidean distance degree of a variety is the number of critical points of the squared distance to a generic point outside the variety. Focusing on varieties seen in applications, we present numerous tools for exact computations.

preprint2013arXiv

Groups acting on Gaussian graphical models

Gaussian graphical models have become a well-recognized tool for the analysis of conditional independencies within a set of continuous random variables. From an inferential point of view, it is important to realize that they are composite exponential transformation families. We reveal this structure by explicitly describing, for any undirected graph, the (maximal) matrix group acting on the space of concentration matrices in the model. The continuous part of this group is captured by a poset naturally associated to the graph, while automorphisms of the graph account for the discrete part of the group. We compute the dimension of the space of orbits of this group on concentration matrices, in terms of the combinatorics of the graph; and for dimension zero we recover the characterization by Letac and Massam of models that are transformation families. Furthermore, we describe the maximal invariant of this group on the sample space, and we give a sharp lower bound on the sample size needed for the existence of equivariant estimators of the concentration matrix. Finally, we address the issue of robustness of these estimators by computing upper bounds on finite sample breakdown points.

preprint2013arXiv

Noetherianity up to symmetry

These lecture notes for the 2013 CIME/CIRM summer school Combinatorial Algebraic Geometry deal with manifestly infinite-dimensional algebraic varieties with large symmetry groups. So large, in fact, that subvarieties stable under those symmetry groups are defined by finitely many orbits of equations---whence the title Noetherianity up to symmetry. It is not the purpose of these notes to give a systematic, exhaustive treatment of such varieties, but rather to discuss a few "personal favourites": exciting examples drawn from applications in algebraic statistics and multilinear algebra. My hope is that these notes will attract other mathematicians to this vibrant area at the crossroads of combinatorics, commutative algebra, algebraic geometry, statistics, and other applications.

preprint2012arXiv

Energy minimisation of repelling particles on a toric grid

We explore the minimum energy configurations of repelling particles distributed over n possible locations forming a toric grid. We conjecture that the most energy-efficient way to distribute n/2 particles over this space is to place them in a checkerboard pattern. Numerical experiments validate this conjecture for reasonable choices of the repelling force. In the present paper, we prove this conjecture in a large number of special cases---most notably, when the sizes of the torus are either two or multiples of four in all dimensions and the repelling force is a completely monotonic function of the Lee distance between the particles.

preprint2012arXiv

Half-trek criterion for generic identifiability of linear structural equation models

A linear structural equation model relates random variables of interest and corresponding Gaussian noise terms via a linear equation system. Each such model can be represented by a mixed graph in which directed edges encode the linear equations and bidirected edges indicate possible correlations among noise terms. We study parameter identifiability in these models, that is, we ask for conditions that ensure that the edge coefficients and correlations appearing in a linear structural equation model can be uniquely recovered from the covariance matrix of the associated distribution. We treat the case of generic identifiability, where unique recovery is possible for almost every choice of parameters. We give a new graphical condition that is sufficient for generic identifiability and can be verified in time that is polynomial in the size of the graph. It improves criteria from prior work and does not require the directed part of the graph to be acyclic. We also develop a related necessary condition and examine the "gap" between sufficient and necessary conditions through simulations on graphs with 25 or 50 nodes, as well as exhaustive algebraic computations for graphs with up to five nodes.

preprint2012arXiv

Positivity for Gaussian graphical models

Gaussian graphical models are parametric statistical models for jointly normal random variables whose dependence structure is determined by a graph. In previous work, we introduced trek separation, which gives a necessary and sufficient condition in terms of the graph for when a subdeterminant is zero for all covariance matrices that belong to the Gaussian graphical model. Here we extend this result to give explicit cancellation-free formulas for the expansions of nonzero subdeterminants.

preprint2012arXiv

Tensor invariants for certain subgroups of the orthogonal group

Let V be an n-dimensional vector space and let On be the orthogonal group. Motivated by a question of B. Szegedy (B. Szegedy, Edge coloring models and reflection positivity, Journal of the American Mathematical Society Volume 20, Number 4, 2007), about the rank of edge connection matrices of partition functions of vertex models, we give a combinatorial parameterization of tensors in V \otimes k invariant under certain subgroups of the orthogonal group. This allows us to give an answer to this question for vertex models with values in an algebraically closed field of characteristic zero.

preprint2011arXiv

Bounded-rank tensors are defined in bounded degree

Matrices of rank at most k are defined by the vanishing of polynomials of degree k + 1 in their entries (namely, their (k + 1)-times-(k + 1)-subdeterminants), regardless of the size of the matrix. We prove a qualitative analogue of this statement for tensors of arbitrary dimension, where matrices correspond to two-dimensional tensors. More specifically, we prove that for each k there exists an upper bound d = d(k) such that tensors of border rank at most k are defined by the vanishing of polynomials of degree at most d, regardless of the dimension of the tensor and regardless of its sizes in each dimension. Our proof involves passing to an infinite-dimensional limit of tensor powers of a vector space, whose elements we dub infinite-dimensional tensors, and exploiting the symmetries of this limit in crucial way.

preprint2010arXiv

Trek separation for Gaussian graphical models

Gaussian graphical models are semi-algebraic subsets of the cone of positive definite covariance matrices. Submatrices with low rank correspond to generalizations of conditional independence constraints on collections of random variables. We give a precise graph-theoretic characterization of when submatrices of the covariance matrix have small rank for a general class of mixed graphs that includes directed acyclic and undirected graphs as special cases. Our new trek separation criterion generalizes the familiar $d$-separation criterion. Proofs are based on the trek rule, the resulting matrix factorizations and classical theorems of algebraic combinatorics on the expansions of determinants of path polynomials.

preprint2007arXiv

Secant dimensions of low-dimensional homogeneous varieties

We completely describe the higher secant dimensions of all connected homogeneous projective varieties of dimension at most 3, in all possible equivariant embeddings. In particular, we calculate these dimensions for all Segre-Veronese embeddings of P^1 * P^1, P^1 * P^1 * P^1, and P^2 * P^1, as well as for the variety F of incident point-line pairs in P^2. For P^2 * P^1 and F the results are new, while the proofs for the other two varieties are more compact than existing proofs. Our main tool is the second author's tropical approach to secant dimensions.

preprint2003arXiv

Higher secant varieties of the minimal adjoint orbit

We try to write (generic) elements of classical simple Lie algebras as sums of as few elements of the orbit C of long root vectors as possible. If the Lie algebra in question is sl_n or sp_n, then C consists of all rank 1 matrices in the Lie algebra, and an element of rank k is the sum of k elements of C. If, on the other hand, the Lie algebra is o_n, then C consists of all rank 2 matrices with square zero, and the situation is much more complicated. We explicitly describe, in this case as well, the closure of the set of all sums of k elements of C, also known as the (k-1)st secant variety of C.