The paper deals with the following four types of sparsity problems: -- Weighted sparsity problem (WSP): Given \(A\in \mathbb{R}^{m\times n}\), \(b \in \mathbb{R}^ m\) and \(w \in \mathbb{R}^ n\), which define constraints \(Ax = b\) with weight \(w_ j\) on column \(j\), find a nonsingular \(T \in \mathbb{R}^{m \times m}\) such that \(\hat A = TA\) minimizes \(\sum^ n_{j=1}w_ j\cdot\) (number of nonzeros in column \(j\) of \(\hat A\)); -- Sparsity problem (SP): Solve WSP with all \(w_ j = 1\); -- One-row weighted sparsity problem (ORWSP): For a fixed row \(i\), find multipliers \(t_{ik}\), \(k \neq i\), such that \(\hat A_{i\cdot} = A_{i\cdot} + \sum_{k\neq i}t_{ik}A_{k\cdot}\) has a minimum weight of nonzeros. -- One-row sparsity problem (ORSP): Solve ORWSP with all \(w_ j = 1\). The main results concern the complexity of the weighted problems. It is shown that all four problems are NP-hard without a nondegeneracy assumption, called the matching property (MP), on the numerical values of nonzero entries of \(A\). Polynomial algorithms exist for SP that have been applied to real linear programming problems that violate MP, with good results. Assuming MP, WSP is polynomial when restricted to at most two nonzeros per row or per column. Finally, some ideas on a heuristic algorithm for WSP are presented.