Counting Vanishing Matrix-Vector Products

Consider the following parameterized counting variation of the classic subset sum problem, which arises notably in the context of higher homotopy groups of topological spaces: Let \(\textbf{v} \in \mathbb {Q}^d\) be a rational vector, \((T_{1}, T_{2} \ldots T_{m})\) a list of \(d \times d\) rational matrices, \(S \in \mathbb {Q}^{h \times d}\) a rational matrix not necessarily square and k a parameter. The goal is to compute the number of ways one can choose k matrices \(T_{i_1}, T_{i_2}, \ldots , T_{i_k}\) from the list such that \(ST_{i_k} \cdots T_{i_1}\textbf{v} = \textbf{0} \in \mathbb {Q}^h\) . In this paper, we show that this problem is \(\# \textsf{W}[2]\) -hard for parameter k. As a consequence, computing the k-th homotopy group of a d-dimensional 1-connected topological space for \(d > 3\) is \(\# \textsf{W}[2]\) -hard for parameter k. We also discuss a decision version of the problem and its several modifications for which we show \(\textsf{W}[1]/\textsf{W}[2]\) -hardness. This is in contrast to the parameterized k-sum problem, which is only \(\textsf{W}[1]\) -hard (Abboud-Lewi-Williams, ESA’14). In addition, we show that the decision version of the problem without parameter is an undecidable problem, and we give a fixed-parameter tractable algorithm for matrices of bounded size over finite fields, parameterized by the matrix dimensions and the order of the field.