The kernel of the adjacency matrix of a rectangular mesh

DOI10.1007/S00454-002-2819-ZMaRDI QIDQ1849448zbMATH OpenOpenAlexFDO

Authors Tania Vieira, Carlos Tomei

Publication date 1 December 2002

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0201211

zbMATH Keywords

adjacency matrixkernelrectangular meshrectangular tilings

Mathematics Subject Classification ID

Tilings in (2) dimensions (aspects of discrete geometry) (52C20)

Abstract: Given an m x n rectangular mesh, its adjacency matrix A, having only integer entries, may be interpreted as a map between vector spaces over an arbitrary field K. We describe the kernel of A: it is a direct sum of two natural subspaces whose dimensions are equal to $lceilc/2ceil$ and $lfloorc/2floor$, where c = gcd (m+1,n+1) - 1. We show that there are bases to both vector spaces, with entries equal to 0, 1 and -1. When K = Z/(2), the kernel elements of these subspaces are described by rectangular tilings of a special kind. As a corollary, we count the number of tilings of a rectangle of integer sides with a specified set of tiles.

Review text

Given an \(m \times n\) rectangular mesh, its adjacency matrix \(A,\) having only integer entries, may be interpreted as a map between vector spaces over an arbitrary field \(K.\) The authors prove that the kernel of \(A\) is a direct sum of two natural subspaces whose dimensions are equal to \(\lceil c/2 \rceil\) and \(\lfloor c/2 \rfloor\) where \(c = \text{gcd} (m + 1, n + 1 - 1).\) They show that there are bases to both vector spaces, with entries equal to \(0, 1\) or \(-1.\) When \(K = \mathbb{Z}/(2),\) the kernel elements of these subspaces are described by rectangular tilings of a special kind. As a corollary, the authors count the number of tilings of a rectangle of integer sides with a specified set of tiles.

Recommendations

• Domino tilings and determinants
• Singular polynomials of generalized Kasteleyn matrices
• A \((0,1)\)-matrix existence theorem and equivalent tiling problems with dimers and monomers
• Adjacency preserving mappings of rectangular matrices
• Cut-and-paste of quadriculated disks and arithmetic properties of the adjacency matrix

Cited in

(2)

• Channels, billiards, and perfect matching 2-divisibility
• Cut-and-paste of quadriculated disks and arithmetic properties of the adjacency matrix

This page was built for publication: The kernel of the adjacency matrix of a rectangular mesh

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1849448)