DROPS

Document

DOI: 10.4230/LIPIcs.ISAAC.2024.35

Generating All Invertible Matrices by Row Operations

Authors: Petr Gregor, Hung P. Hoang, Arturo Merino, and Ondřej Mička

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract

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.

Cite as

Petr Gregor, Hung P. Hoang, Arturo Merino, and Ondřej Mička. Generating All Invertible Matrices by Row Operations. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.ISAAC.2024.35,
  author =	{Gregor, Petr and Hoang, Hung P. and Merino, Arturo and Mi\v{c}ka, Ond\v{r}ej},
  title =	{{Generating All Invertible Matrices by Row Operations}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{35:1--35:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.35},
  URN =		{urn:nbn:de:0030-drops-221621},
  doi =		{10.4230/LIPIcs.ISAAC.2024.35},
  annote =	{Keywords: Hamilton cycle, combinatorial Gray code, invertible matrices, finite field, general linear group, generation algorithms}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2020.60

On the Central Levels Problem

Authors: Petr Gregor, Ondřej Mička, and Torsten Mütze

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract

The central levels problem asserts that the subgraph of the (2m+1)-dimensional hypercube induced by all bitstrings with at least m+1-𝓁 many 1s and at most m+𝓁 many 1s, i.e., the vertices in the middle 2𝓁 levels, has a Hamilton cycle for any m ≥ 1 and 1 ≤ 𝓁 ≤ m+1. This problem was raised independently by Savage, by Gregor and Škrekovski, and by Shen and Williams, and it is a common generalization of the well-known middle levels problem, namely the case 𝓁 = 1, and classical binary Gray codes, namely the case 𝓁 = m+1. In this paper we present a general constructive solution of the central levels problem. Our results also imply the existence of optimal cycles through any sequence of 𝓁 consecutive levels in the n-dimensional hypercube for any n ≥ 1 and 1 ≤ 𝓁 ≤ n+1. Moreover, extending an earlier construction by Streib and Trotter, we construct a Hamilton cycle through the n-dimensional hypercube, n≥ 2, that contains the symmetric chain decomposition constructed by Greene and Kleitman in the 1970s, and we provide a loopless algorithm for computing the corresponding Gray code.

Cite as

Petr Gregor, Ondřej Mička, and Torsten Mütze. On the Central Levels Problem. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 60:1-60:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gregor_et_al:LIPIcs.ICALP.2020.60,
  author =	{Gregor, Petr and Mi\v{c}ka, Ond\v{r}ej and M\"{u}tze, Torsten},
  title =	{{On the Central Levels Problem}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{60:1--60:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.60},
  URN =		{urn:nbn:de:0030-drops-124678},
  doi =		{10.4230/LIPIcs.ICALP.2020.60},
  annote =	{Keywords: Gray code, Hamilton cycle, hypercube, middle levels, symmetric chain decomposition}
}

Search Results

Documents authored by Mička, Ondřej

Generating All Invertible Matrices by Row Operations

Abstract

Cite as

On the Central Levels Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message