2026-07-23T03:28:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22162 2024-12-04T06:53:44Z ddc:004 open_access

Generating All Invertible Matrices by Row Operations Gregor, Petr Hoang, Hung P. Merino, Arturo Mička, Ondřej Hamilton cycle combinatorial Gray code invertible matrices finite field general linear group generation algorithms We show that all invertible n × n matrices over any finite field 𝔽_q can be generated in a Gray code fashion. More specifically, there exists a listing such that (1) each matrix appears exactly once, and (2) two consecutive matrices differ by adding or subtracting one row from a previous or subsequent row, or by multiplying or dividing a row by the generator of the multiplicative group of 𝔽_q. This even holds in the more general setting where the pairs of rows that can be added or subtracted are specified by an arbitrary transition tree that has to satisfy some mild constraints. Moreover, we can prescribe the first and the last matrix if n ≥ 3, or n = 2 and q > 2. In other words, the corresponding flip graph on all invertible n × n matrices over 𝔽_q is Hamilton connected if it is not a cycle. This solves yet another special case of Lovász conjecture on Hamiltonicity of vertex-transitive graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Petr Gregor and Hung P. Hoang and Arturo Merino and Ondřej Mička 2024 Is Part Of LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2024.35 urn:nbn:de:0030-drops-221621 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.35 eng https://creativecommons.org/licenses/by/4.0/legalcode