I am curious about the upper bound of $\|\mathbf{A}x\|_1$ where $\mathbf{A}\in\mathbb{Z}^{m\times p}$ and $x \in \{0,1\}^p$, for a specific $\mathbf{A}$ as defined below.
I know this is an NP-hard problem in the general case, but the particular $\mathbf{A}$ I am interested in has a very symmetrical structure.
Let $\mathbf{B}$ be the matrix of all possible unique rows of length $n$. Mathematically, let each cell $\mathbf{B}_{i,j} = (i \gg j) \mod 2$. The dimensions of $\mathbf{B}$ must be $2^n \times n$ (as there are $2^n$ rows of length $n$). Let $\varphi : \mathbb{Z} \to \mathbb{Z}$ where $\varphi(z) = 2z-1$, be an entrywise mapping over matrices of any size. Finally, let $\mathbf{A} = \varphi(\mathbf{B} \mathbf{B}^\mathsf{T})$. For later, I also define $\mathbf{A}' \in \mathbb{Z}^{2^n \times {2^n}-1}$ to be $\mathbf{A}$ with the first column (the only column of all $-1$'s) removed.
Examples (optional illustration for extra clarity)
When $n=4$, $\mathbf{A} = \begin{bmatrix} -1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1&-1\\ -1& 1&-1& 1&-1& 1&-1& 1&-1& 1&-1& 1&-1& 1&-1& 1\\ -1&-1& 1& 1&-1&-1& 1& 1&-1&-1& 1& 1&-1&-1& 1& 1\\ -1& 1& 1&-1&-1& 1& 1&-1&-1& 1& 1&-1&-1& 1& 1&-1\\ -1&-1&-1&-1& 1& 1& 1& 1&-1&-1&-1&-1& 1& 1& 1& 1\\ -1& 1&-1& 1& 1&-1& 1&-1&-1& 1&-1& 1& 1&-1& 1&-1\\ -1&-1& 1& 1& 1& 1&-1&-1&-1&-1& 1& 1& 1& 1&-1&-1\\ -1& 1& 1&-1& 1&-1&-1& 1&-1& 1& 1&-1& 1&-1&-1& 1\\ -1&-1&-1&-1&-1&-1&-1&-1& 1& 1& 1& 1& 1& 1& 1& 1\\ -1& 1&-1& 1&-1& 1&-1& 1& 1&-1& 1&-1& 1&-1& 1&-1\\ -1&-1& 1& 1&-1&-1& 1& 1& 1& 1&-1&-1& 1& 1&-1&-1\\ -1& 1& 1&-1&-1& 1& 1&-1& 1&-1&-1& 1& 1&-1&-1& 1\\ -1&-1&-1&-1& 1& 1& 1& 1& 1& 1& 1& 1&-1&-1&-1&-1\\ -1& 1&-1& 1& 1&-1& 1&-1& 1&-1& 1&-1&-1& 1&-1& 1\\ -1&-1& 1& 1& 1& 1&-1&-1& 1& 1&-1&-1&-1&-1& 1& 1\\ -1& 1& 1&-1& 1&-1&-1& 1& 1&-1&-1& 1&-1& 1& 1&-1\\ \end{bmatrix} \in \mathbb{Z}^{16 \times 16}$.
For small values of $n$, I have computed the below maximums. \begin{array} {|r|rr|} \hline n & \max \|\mathbf{A}x\|_1 & \max \|\mathbf{A}'x\|_1 \\ \hline 1 & 1 & 2 \\ \hline 2 & 3 & 6 \\ \hline 3 & 9 & 14 \\ \hline 4 & 30 & 40 \\ \hline 5 & 80 & 96 \\ \hline 6 & 236 & 272 \\ \hline \end{array} Unhelpfully, the results are not a known sequence in the OEIS. Even the number of distinct solutions $x$ can take to produce the maximum $\big(\#_\mathbf{A} = \{2,8,112,896,\ldots\}; \#_{\mathbf{A}'} = \{3,6,64,488,\ldots\}\big)$ is not part of any sequence in the OEIS.
Both the matrices $\mathbf{A}$ and $\mathbf{A}'$ is also invertible and $\mathbf{A}\mathbf{A}^\mathsf{T} = 2^n \mathbf{I} \in \mathbb{Z}^{2^n \times 2^n}$ and $\mathbf{A}'\mathbf{A}'^\mathsf{T} = 2^n \mathbf{I} \in \mathbb{Z}^{({2^n}-1) \times ({2^n}-1)}$.
Weak upper bound
By definition of the $\ell_1$-norm, it's trivially noticed that $\|\mathbf{A}x\|_1 = \left\|\left(\sum_{j=1}^m a_{1j}x_j, \ldots \sum_{j=1}^m a_{pj}x_j\right)\right\|_1 \le \sum_{j=1}^m \left(\sum_{i=1}^p|a_{i,j}|\right)|x_j| \le \sum_{j=1}^m \left(\sum_{i=1}^p 1\right)1 = \sum_{j=1}^{2^n} \left(\sum_{i=1}^{2^n} 1\right)1 = 2^n * 2^n = 2^{2n}$.
By realizing that half of the cells in each row are $-1$s and the other half are $1$s, and thus $|\sum_{i=1}^{2^n} a_{i,j}| \le \frac{2^n}{2}$, we can improve this upper bound slightly to $\|\mathbf{A}x\|_1 \le 2^n * \frac{2^n}{2} = 2^{2n-1}$.
Based on the experimental data in the table above, it seems we can do much better, perhaps as low as something like ${2^n}n \le \max\|\mathbf{A}'x\|_1 \le \max\|\mathbf{A}x\|_1 \le {2^n}n\log{n}$.
