Alternating sign matrices and polynomiography

Research output: Contribution to journalArticle

4 Scopus citations

Abstract

To each permutation matrix we associate a complex permutation polynomial with roots at lattice points corresponding to the position of the ones. More generally, to an alternating sign matrix (ASM) we associate a complex alternating sign polynomial. On the one hand visualization of these polynomials through polynomiography, in a combinatorial fashion, provides for a rich source of algorithmic art-making, interdisciplinary teaching, and even leads to games. On the other hand, this combines a variety of concepts such as symmetry, counting and combinatorics, iteration functions and dynamical systems, giving rise to a source of research topics. More generally, we assign classes of polynomials to matrices in the Birkhoff and ASM polytopes. From the characterization of vertices of these polytopes, and by proving a symmetry-preserving property, we argue that polynomiography of ASMs form building blocks for approximate polynomiography for polynomials corresponding to any given member of these polytopes. To this end we offer an algorithm to express any member of the ASM polytope as a convex of combination of ASMs. In particular, we can give exact or approximate polynomiography for any Latin Square or Sudoku solution. We exhibit some images.

Original languageEnglish (US)
Pages (from-to)1-22
Number of pages22
JournalElectronic Journal of Combinatorics
Volume18
Issue number2
DOIs
StatePublished - 2011

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Keywords

  • Alternating sign matrices
  • Doubly stochastic matrices
  • Latin squares
  • Linear programming
  • Newton's method
  • Polynomial roots
  • Polynomiography
  • Voronoi diagram

Fingerprint Dive into the research topics of 'Alternating sign matrices and polynomiography'. Together they form a unique fingerprint.

  • Cite this