Expansion of Integer Matrices over Various Rings

Jakub Szymański · 2025

Read Expansion of Integer Matrices over Various Rings by Jakub Szymański (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-17823.txt.

Introduction

Jakub Szymanski links how fast integer matrices spread vectors over three number systems. His 2025 paper works with real numbers, whole numbers, and whole numbers modulo a prime. Such spread, or expansion, helps build high-dim expanders, graphs that stay well linked.

Szymanski sets a new kernel test, called integral spanning, on the matrix. When the test holds, real and whole-number spread match. He also bounds spread over finite fields by the whole-number case for a class of matrices. One use bounds the spread of a key map over the mod-two field in low degrees.

Catalog record

CREATORJakub Szymański
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-17823

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Expansion of Integer Matrices over Various Rings Thanks: The author was supported by the National Science Center Grant Maestro-13 UMO- 2021/42/A/ST1/00306. Jakub Szymański Abstract . In this article, we explore the problem of constructing high-dimensional expanders through the study of relations between expansion constants over different rings. We investigate expansion constants of integer matrices regarded as morphisms between free modules over ℝ \mathbb{R} , ℤ \mathbb{Z} , and ℤ / p ​ ℤ \mathbb{Z}/p\mathbb{Z} . We introduce a new condition which we call integral spanning regarding kernels of integer matrices, and prove that it ensures equality of real and integral expansions. In addition, we prove a bound on expansion constants over finite fields for a certain class of matrices in terms of the corresponding integral expansions. As an application, one may use this theorem to bound the expansion of codifferentials over ℤ / 2 ​ ℤ \mathbb{Z}/2\mathbb{Z} in degrees 0 0 and 1 1 . 2020 Mathematics Subject Classification 20F65 1. Introduction Expander graphs are characterised by being sparse yet highly connected. Due to these two desirable traits, they have found applications in many areas of theoretical computer science. For example, see [ SS96 ] for their use in error-correcting codes, and [ AKS83 ] for their use in sorting networks. Given the central role of expanders in many constructions, it is natural to ask what higher-dimensional analogues might look like. It turns out that this generalisation can be introduced in many non-equivalent ways. There are definitions of spectral, coboundary, and cosystolic expanders. Nevertheless, all of them are in a similar vein and involve the augmented cellular cochain complexes of CW complexes \left\{X_{n}\right\}_{n\in\mathbb{N}} , with coefficients in an integral domain R R\xrightarrow{}C^{0}_{\text{cell}}(X_{n},R)\xrightarrow{}C^{1}_{\text{cell}}(X_{n},R)\xrightarrow{}C^{2}_{\text{cell}}(X_{n},R)\to\ldots The definition of high dimensional expansion then requires a uniform upper bound on expansion constants, as defined below, for all codifferential maps associated with the family \left\{X_{n}\right\}_{n\in\mathbb{N}} , where, in the case of spectral expanders, we have R=\mathbb{R} and for coboundary and cosystolic expansions R=\mathbb{Z}/2\mathbb{Z} . Definition 1.1 . For a given morphism A:R^{n}\longrightarrow R^{m} , we define the expansion constant at a nonzero element v\in\operatorname{Im}(A) as \displaystyle\Xi_{R}(A,v) \displaystyle=\inf\left\{\frac{\|u\|}{\|v\|}\mid u\in A^{-1}(\{v\})\right\}, and a general expansion constant as \displaystyle\Xi_{R}(A) \displaystyle=\sup\left\{\Xi_{R}(A,v)\mid v\neq 0\in\operatorname{Im}(A)\right\}. It turns out that the construction of spectral expanders is much simpler, and can be done by taking a family of finite covers of the presentation complex corresponding to a group with Property (T) (see Theorem 4.1 [ BS24 , Theorem 1.8] ). This work is the result of considerations on cosystolic expansion constants, i.e., after change of field, in the case of the above sequence of finite covers. Namely, the principal question is about the relation of the expansion constants of integer matrices, considered as morphisms between free modules over \mathbb{R},\mathbb{Z} and \mathbb{Z}/p\mathbb{Z} for a prime number p . In [ BS24 ] the authors prove that the equality between expansion over \mathbb{Z} and \mathbb{R} holds for totally unimodular matrices, i.e. such that all minors are either -1,0 or 1 . The authors also show that expansion behaves well with respect to exact sequences, provided the matrices are totally unimodular. Theorem 1.2 . [ BS24 , Theorem 2.8] Let A and B be integer matrices of size m\times n and k\times m , such that the sequence \mathbb{R}^{n}\xrightarrow{A}\mathbb{R}^{m}\xrightarrow{B}\mathbb{R}^{k} is exact. If A is totally unimodular, then \Xi_{\mathbb{Z}}(A)=\Xi_{\mathbb{R}}(A) and \Xi_{\mathbb{Z}}(B)=\Xi_{\mathbb{R}}(B) . In the context of codifferentials, the zeroth map is always totally unimodular, and the equality \Xi_{\mathbb{R}}(\text{d}^{0})=\Xi_{\mathbb{Z}}(\text{d}^{0}) holds for every CW complex. Moreover, if we add the condition about the trivial first cohomology group, based on the above theorem, we get the same equality for the first codifferential. In the subsequent chapter we present a new condition which ensures the equality of real and integer expansions. Rather than insisting on the total unimodularity of the matrix, we establish it by formulating a condition on the kernel of the morphism defined by the matrix. We introduce this property for a free \mathbb{Z} -module in Definition 2.3 and refer to the module as integrally spanned. Using more elementary methods, we prove an analogous statement of equal expansions over \mathbb{R} and \mathbb{Z} for the zeroth and first codifferentials, based on this condition. Furthermore, we present a method for bounding the expansion over a finite field by the expansion constant over the integers. Theorem 3.1 can be applied, for example, for the expansion of zeroth and first codifferentials over \mathbb{Z}/2\mathbb{Z} . Whether this result can be extended to a larger class of matrices remains an open problem. Addressing this question would make a significant step towards providing new examples of coboundary and cosystolic higher-dimensional expanders. 2. New condition on equality of real and integer expansion In this chapter, we consider coefficient rings R equal to \mathbb{R},\mathbb{Q} , or \mathbb{Z} . For each of them, the norms on the free modules are defined as the sum of the absolute values of the coordinates of a vector. Our new condition is based on comparing finitely generated modules over integers with the corresponding modules over rationals generated by the same basis. The equalities we consider are required to hold for the generating sets after restriction to subsets of coordinates. The following definition introduces restriction maps p_{I} , which can be viewed as projections onto the selected coordinates, preserving their order. Definition 2.1 . Let I=\{i_{1}<i_{2}<\cdots<i_{m}\} be a subset of \{1,\cdots,n\} and let R be a ring with unity. Then the morphism of R -modules p_{I}:R^{n}\rightarrow R^{m} is defined by the formula p_{I}(x_{1},\cdots,x_{n})=(x_{i_{1}},\cdots,x_{i_{m}}). Definition 2.2 . Let R be a ring with unity and let M be an R -module together with elements m_{1},\cdots,m_{k}\in M . A module generated by them will be denoted by \langle m_{1},\cdots,m_{k}\rangle_{R}\subseteq M. In the following, we shall not distinguish between p_{I} as morphisms of free modules over different rings R , and we will use the same symbol p_{I} in all contexts. Definition 2.3 . Let v_{1},\cdots,v_{k}\in\mathbb{Q}^{n} be vectors with integer coefficients and let V be a \mathbb{Z} -module generated by them, V=\langle v_{1},\cdots,v_{k}\rangle_{\mathbb{Z}}\subseteq\mathbb{Q}^{n} . We say that V is integrally spanned if for each I\subseteq\{1,\cdots,n\} the following equality of \mathbb{Z} -modules is satisfied \langle p_{I}(v_{1}),\cdots,p_{I}(v_{k})\rangle_{\mathbb{Z}}=\mathbb{Z}^{|I|}\cap\langle p_{I}(v_{1}),\cdots,p_{I}(v_{k})\rangle_{\mathbb{Q}}. Lemma 2.4 . The above property of a \mathbb{Z} -module does not depend on the choice of the generating set. Proof. Let us choose two generating sets V=\{v_{1},\cdots,v_{k}\}\subseteq\mathbb{Z}^{n}\cap\mathbb{Q}^{n} and W=\{w_{1},\cdots,w_{m}\}\subseteq\mathbb{Z}^{n}\cap\mathbb{Q}^{n} such that the equalities from Definition 2.3 are satisfied for V . We will show that they hold for W as well. Since V and W are generating sets, we can introduce integers \{a^{i}_{j}\},\{b^{i}_{j}\} such that v_{i}=\sum_{j=1,\cdots,m}a^{i}_{j}w_{j},\quad w_{i}=\sum_{j=1,\cdots,k}b^{i}_{j}v_{j}. Therefore, for rational numbers \gamma_{1},\cdots,\gamma_{m}\in\mathbb{Q} and a subset I\in\{1,\cdots,n\} such that w\coloneq\gamma_{1}p_{I}(w_{1})+\cdots+\gamma_{m}p_{I}(w_{m})\in\mathbb{Z}^{|I|}, the following holds w=\left(\sum_{i=1,\cdots,m}\gamma_{i}b_{1}^{i}\right)p_{I}(v_{1})+\cdots+\left(\sum_{i=1,\cdots,m}\gamma_{i}b_{k}^{i}\right)p_{I}(v_{k}), and thus w=c_{1}p_{I}(v_{1})+\cdots+c_{k}p_{I}(v_{k}) for some c_{1},\cdots,c_{k}\in\mathbb{Z} . Then we get w=\left(\sum_{i=1,\cdots,k}c_{i}a^{i}_{1}\right)p_{I}(w_{1})+\cdots+\left(\sum_{i=1,\cdots,k}c_{i}a^{i}_{m}\right)p_{I}(w_{m})\in\langle p_{I}(w_{1}),\cdots,p_{I}(w_{m})\rangle_{\mathbb{Z}}, which proves that the equality \langle p_{I}(w_{1}),\cdots,p_{I}(w_{m})\rangle_{\mathbb{Z}}=\mathbb{Z}^{|I|}\cap\langle p_{I}(w_{1}),\cdots,p_{I}(w_{m})\rangle_{\mathbb{Q}} holds for each I\in\{1,\cdots,n\} , which is exactly the condition from Definition 2.3 . ∎ Example 2.5 . (1) For a single vector v\in\mathbb{Z}^{n}\cap\mathbb{Q}^{n} a module \langle v\rangle_{\mathbb{Z}} is integrally spanned if and only if all entries of v are in \{-1,0,1\} . Otherwise, after restricting to an entry with a value k\notin\{-1,0,1\} , the equality from Definition 2.3 does not hold \langle k\rangle_{\mathbb{Z}}\neq\mathbb{Z}=\mathbb{Z}\cap\langle k\rangle_{\mathbb{Q}}. (2) For more than one vector, the set of possible entries is not

Read the complete text