The hardware implementations of decimal arithmetic operations, which are commonly used in financial, scientific, and internet-based applications requiring accuracy and speed, become prominent. In this paper we first analyze the column sum boundaries of n-digit parallel decimal array multipliers (PDAM). A general form of the problem is formed and a heuristic solution is found with Genetic Algorithm (GA) for 16-digit multiplication. Then, for small n-digit multipliers the GA results are proved with exhaustive search. Finally, new tight boundaries on the column sums are used in a hardware implementation of a 16-digit PDAM. Inclusion of the proposed boundaries provides an 8% speedup or 20% less area.