Counting Vanishing Matrix-Vector Products

Abstract

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 v ∈ Qd be a rational vector, (T1, T2 . . . Tm) a list of d × d rational matrices, S ∈ Qh×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 Ti1, Ti2, Tik from the list such that STik,· Ti1 v = 0 ∈ Qh. In this paper, we show that this problem is #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 #W[2]-hard for parameter k. We also discuss a decision version of the problem and its several modifications for which we show W[1]/W[2]-hardness. This is in contrast to the parameterized k-sum problem, which is only 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 the matrix dimensions and the order of the field.