<p>The double-array is an implementation of a trie, which is a data structure that has been well conceived in practice for indexing a set of strings for prefix search or membership queries — a fundamental task with many applications such as information retrieval or database systems. Due to the fundamental nature of this problem, it has sparked much interest, leading to a variety of trie implementations with different characteristics. While a traversal takes constant time per node visit, the needed space consumption in computer words can be as large as the product of the number of nodes and the alphabet size. Despite that several heuristics have been proposed on lowering the space requirements, we are unaware of any theoretical guarantees. In this article, we study the decision problem whether there exists a double-array of a given size. To this end, we first draw a connection to the sparse matrix compression problem, which makes our problem NP-complete for alphabet sizes linear to the number of nodes. The sparse matrix compression problem is to linearize all matrix columns to a single string and use offsets to identify the placement of the columns. Introduced by Ziegler in an unpublished note in 1977, this problem has been discovered in many applications. While it is well-known that the problem is NP-hard even for offsets of lengths at most two, much is left unknown about which parameters make this problem hard. Here, we show that the sparse matrix compression problem is NP-hard even for matrices with at least logarithmic widths by a reduction from the restricted directed Hamiltonian path problem. This translates to NP-completeness of the addressed space problem of the double-array even for alphabets with at least logarithmic sizes. Our final contribution is a MAX-SAT encoding of the problem to find the smallest layout of a double-array, for which we practically could observe a gain of up to 10% when indexing a few hundred words common in English texts.</p>