We study the sparsity of the solutions to systems of linear Diophantine equations with and without non-negativity constraints. The sparsity of a solution vector is the number of its nonzero entries, which is referred to as the
Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to non-federal websites. Their policies may differ from this site.
-
Abstract -norm of the vector. Our main results are new improved bounds on the minimal$$\ell _0$$ -norm of solutions to systems$$\ell _0$$ , where$$A\varvec{x}=\varvec{b}$$ ,$$A\in \mathbb {Z}^{m\times n}$$ and$${\varvec{b}}\in \mathbb {Z}^m$$ is either a general integer vector (lattice case) or a non-negative integer vector (semigroup case). In certain cases, we give polynomial time algorithms for computing solutions with$$\varvec{x}$$ -norm satisfying the obtained bounds. We show that our bounds are tight. Our bounds can be seen as functions naturally generalizing the rank of a matrix over$$\ell _0$$ , to other subdomains such as$$\mathbb {R}$$ . We show that these new rank-like functions are all NP-hard to compute in general, but polynomial-time computable for fixed number of variables.$$\mathbb {Z}$$