Spectra of product graphs and permanents of matrices over finite rings

Le Anh Vinh

Vol. 267 (2014), No. 2, 479–487

DOI: 10.2140/pjm.2014.267.479

Abstract

We study the spectra of product graphs over the finite cyclic ring ${\mathbb{Z}}_m$. Using this spectra, we show that if $@\mathcal{ℰ}$ is a sufficiently large subset of ${\mathbb{Z}}_m^k$ then the set of permanents of $k\times k$ matrices with rows in $@‘\mathcal{ℰ}$ contains all nonunits of ${\mathbb{Z}}_m$.

Keywords

permanent, finite ring, expander graph

Mathematical Subject Classification 2010

Primary: 05C50

Milestones

Received: 18 December 2011

Revised: 9 September 2013

Accepted: 16 September 2013

Published: 11 May 2014