The rank of sparse symmetric matrices over arbitrary fields

Remco van der Hofstad; Noela Müller; Haodong Zhu

doi:10.1002/rsa.21258

The rank of sparse symmetric matrices over arbitrary fields

Remco van der Hofstad, Noela Müller, Haodong Zhu (Corresponding author)

Research output: Contribution to journal › Article › Academic › peer-review

16 Downloads (Pure)

Abstract

Let (Formula presented.) be an arbitrary field and (Formula presented.) be a sequence of sparse weighted Erdős–Rényi random graphs on (Formula presented.) vertices with edge probability (Formula presented.), where weights from (Formula presented.) are assigned to the edges according to a matrix (Formula presented.). We show that the normalized rank of the adjacency matrix of (Formula presented.) converges to a constant, and derive the limiting expression. Our result shows that for the general class of sparse symmetric matrices under consideration, the asymptotics of the normalized rank are independent of the edge weights and even the field, in the sense that the limiting constant for the general case coincides with the one previously established for adjacency matrices of sparse nonweighted Erdős–Rényi matrices over (Formula presented.). Our proof, which is purely combinatorial in its nature, is based on an intricate extension of a novel perturbation approach to the symmetric setting.

Original language	English
Article number	e21258
Number of pages	66
Journal	Random Structures and Algorithms
Volume	66
Issue number	1
Early online date	3 Oct 2024
DOIs	https://doi.org/10.1002/rsa.21258
Publication status	Published - Jan 2025

Bibliographical note

Publisher Copyright:
© 2024 The Author(s). Random Structures & Algorithms published by Wiley Periodicals LLC.

Funding

The authors are supported by Netherlands Organisation for Scientific Research (NWO) through the Gravitation NETWORKS grant 024.002.003. The work of Haodong Zhu is further supported by the European Union's Horizon 2020 research and innovation programme under the Marie Sk\u0142odowska-Curie grant agreement no. 945045. The authors are supported by Netherlands Organisation for Scientific Research (NWO) through the Gravitation NETWORKS grant 024.002.003. The work of Haodong Zhu is further supported by the European Union's Horizon 2020 research and innovation programme under the Marie Sk\u0142odowska\u2010Curie grant agreement no. 945045.

Funders	Funder number
Marie Skłodowska‐Curie
European Union's Horizon 2020 - Research and Innovation Framework Programme
European Union's Horizon 2020 - Research and Innovation Framework Programme	945045
Nederlandse Organisatie voor Wetenschappelijk Onderzoek	024.002.003

Keywords

Erdős–Rényi graph
random matrix
rank

Access to Document

10.1002/rsa.21258

pdfFinal published version, 2.45 MBLicence: CC BY

Cite this

@article{f143fbb88da9473cbcb4469d58b99228,

title = "The rank of sparse symmetric matrices over arbitrary fields",

abstract = "Let (Formula presented.) be an arbitrary field and (Formula presented.) be a sequence of sparse weighted Erd{\H o}s–R{\'e}nyi random graphs on (Formula presented.) vertices with edge probability (Formula presented.), where weights from (Formula presented.) are assigned to the edges according to a matrix (Formula presented.). We show that the normalized rank of the adjacency matrix of (Formula presented.) converges to a constant, and derive the limiting expression. Our result shows that for the general class of sparse symmetric matrices under consideration, the asymptotics of the normalized rank are independent of the edge weights and even the field, in the sense that the limiting constant for the general case coincides with the one previously established for adjacency matrices of sparse nonweighted Erd{\H o}s–R{\'e}nyi matrices over (Formula presented.). Our proof, which is purely combinatorial in its nature, is based on an intricate extension of a novel perturbation approach to the symmetric setting.",

keywords = "Erd{\H o}s–R{\'e}nyi graph, random matrix, rank",

author = "{van der Hofstad}, Remco and Noela M{\"u}ller and Haodong Zhu",

note = "Publisher Copyright: {\textcopyright} 2024 The Author(s). Random Structures & Algorithms published by Wiley Periodicals LLC.",

year = "2025",

month = jan,

doi = "10.1002/rsa.21258",

language = "English",

volume = "66",

journal = "Random Structures and Algorithms",

issn = "1042-9832",

publisher = "Wiley",

number = "1",

}

TY - JOUR

T1 - The rank of sparse symmetric matrices over arbitrary fields

AU - van der Hofstad, Remco

AU - Müller, Noela

AU - Zhu, Haodong

PY - 2025/1

Y1 - 2025/1

N2 - Let (Formula presented.) be an arbitrary field and (Formula presented.) be a sequence of sparse weighted Erdős–Rényi random graphs on (Formula presented.) vertices with edge probability (Formula presented.), where weights from (Formula presented.) are assigned to the edges according to a matrix (Formula presented.). We show that the normalized rank of the adjacency matrix of (Formula presented.) converges to a constant, and derive the limiting expression. Our result shows that for the general class of sparse symmetric matrices under consideration, the asymptotics of the normalized rank are independent of the edge weights and even the field, in the sense that the limiting constant for the general case coincides with the one previously established for adjacency matrices of sparse nonweighted Erdős–Rényi matrices over (Formula presented.). Our proof, which is purely combinatorial in its nature, is based on an intricate extension of a novel perturbation approach to the symmetric setting.

AB - Let (Formula presented.) be an arbitrary field and (Formula presented.) be a sequence of sparse weighted Erdős–Rényi random graphs on (Formula presented.) vertices with edge probability (Formula presented.), where weights from (Formula presented.) are assigned to the edges according to a matrix (Formula presented.). We show that the normalized rank of the adjacency matrix of (Formula presented.) converges to a constant, and derive the limiting expression. Our result shows that for the general class of sparse symmetric matrices under consideration, the asymptotics of the normalized rank are independent of the edge weights and even the field, in the sense that the limiting constant for the general case coincides with the one previously established for adjacency matrices of sparse nonweighted Erdős–Rényi matrices over (Formula presented.). Our proof, which is purely combinatorial in its nature, is based on an intricate extension of a novel perturbation approach to the symmetric setting.

KW - Erdős–Rényi graph

KW - random matrix

KW - rank

UR - http://www.scopus.com/inward/record.url?scp=85205566121&partnerID=8YFLogxK

U2 - 10.1002/rsa.21258

DO - 10.1002/rsa.21258

M3 - Article

AN - SCOPUS:85205566121

SN - 1042-9832

VL - 66

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

IS - 1

M1 - e21258

ER -

The rank of sparse symmetric matrices over arbitrary fields

Abstract

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this