Abstract
We continue developing the theory around the twinwidth of totally ordered binary structures (or equivalently, matrices over a finite alphabet), initiated in the previous paper of the series. We first introduce the notion of parity and linear minors of a matrix, which consists of iteratively replacing consecutive rows or consecutive columns with a linear combination of them. We show that a matrix class (i.e., a set of matrices closed under taking submatrices) has bounded twinwidth if and only if its linearminor closure does not contain all matrices. We observe that the fixedparameter tractable (FPT) algorithm for firstorder model checking on structures given with an O(1)sequence (certificate of bounded twinwidth) and the fact that firstorder transductions of bounded twinwidth classes have bounded twinwidth, both established in Twinwidth I, extend to firstorder logic with modular counting quantifiers. We make explicit a winwin argument obtained as a byproduct of Twinwidth IV, and somewhat similar to bidimensionality, that we call rankbidimensionality. This generalizes the seminal work of Guillemot and Marx [SODA '14], which builds on the MarcusTardos theorem [JCTA '04]. It works on general matrices (not only on classes of bounded twinwidth) and, for example, yields FPT algorithms deciding if a small matrix is a parity or a linear minor of another matrix given in input, or exactly computing the grid or mixed number of a given matrix (i.e., the maximum integer k such that the row set and the column set of the matrix can be partitioned into k intervals, with each of the k² defined cells containing a nonzero entry, or two distinct rows and two distinct columns, respectively).
Armed with the abovementioned extension to modular counting, we show that the twinwidth of the product of two conformal matrices A, B (i.e., whose dimensions are such that AB is defined) over a finite field is bounded by a function of the twinwidth of A, of B, and of the size of the field. Furthermore, if A and B are n × n matrices of twinwidth d over F_q, we show that AB can be computed in time O_{d,q}(n² log n).
We finally present an ad hoc algorithm to efficiently multiply two matrices of bounded twinwidth, with a singleexponential dependence in the twinwidth bound. More precisely, pipelined to observations and results of Pilipczuk et al. [STACS '22], we obtain the following. If the inputs are given in a compact treelike form (witnessing twinwidth at most d), called twindecomposition of width d, then two n × n matrices A, B over F₂ can be multiplied in time 4^{d+o(d)}n, in the sense that a twindecomposition of their product AB, with width 2^{d+o(d)}, is output within that time, and each entry of AB can be queried in time O_d(log log n). Furthermore, for every ε > 0, the query time can be brought to constant time O(1/ε) if the running time is increased to nearlinear 4^{d+o(d)}n^{1+ε}. Notably, the running time is sublinear (essentially square root) in the number of (nonzero) entries.
BibTeX  Entry
@InProceedings{bonnet_et_al:LIPIcs.STACS.2023.15,
author = {Bonnet, \'{E}douard and Giocanti, Ugo and Ossona de Mendez, Patrice and Thomass\'{e}, St\'{e}phan},
title = {{TwinWidth V: Linear Minors, Modular Counting, and Matrix Multiplication}},
booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)},
pages = {15:115:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772662},
ISSN = {18688969},
year = {2023},
volume = {254},
editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17667},
URN = {urn:nbn:de:0030drops176675},
doi = {10.4230/LIPIcs.STACS.2023.15},
annote = {Keywords: Twinwidth, matrices, parity and linear minors, model theory, linear algebra, matrix multiplication, algorithms, computational complexity}
}
Keywords: 

Twinwidth, matrices, parity and linear minors, model theory, linear algebra, matrix multiplication, algorithms, computational complexity 
Collection: 

40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023) 
Issue Date: 

2023 
Date of publication: 

03.03.2023 