# Smallest matrix with entries $0$ and $\pm 1$ and with an invariant factor divisible by a given prime.

Let $$A$$ be an $$m\times n$$ matrix over the integers whose entries $$a_{ij}$$ are $$0$$ or $$\pm 1$$. The Smith normal form of $$A$$ is a matrix of the form $$\begin{pmatrix} \alpha_1 & 0 & 0 & & \cdots & & 0 \\ 0 & \alpha_2 & 0 & & \cdots & & 0 \\ 0 & 0 & \ddots & & & & 0\\ \vdots & & & \alpha_r & & & \vdots \\ & & & & 0 & & \\ & & & & & \ddots & \\ 0 & & & \cdots & & & 0 \end{pmatrix}$$

where $$\alpha_k \mid \alpha_{k+1}$$ for $$1\leq k < r$$. The $$\alpha_k$$ are the invariant factors of $$A$$.

Let $$p$$ be a prime number. Define $$X_p = \{ A\in M_{m\times n}(\mathbb{Z}) \mid m,n\in\mathbb{Z}_+, a_{i,j}\in\{-1,0,1\}, p~\text{divides}~\alpha_k~\text{for some}~ k\},$$ that is $$X_p$$ consists of all matrices with integer entries of any size whose entries are $$0$$ or $$\pm 1$$ such that $$p$$ divides one of the invariant factors.

Define $$\operatorname{min-size}(X_p)$$ to be the minimum number of columns of any matrix in $$X_p$$, and define $$\operatorname{min-entries}(X_p)$$ to be the minimum number of nonzero entries of any matrix in $$X_p$$.

Question: Can we compute or find good lower bounds for either $$\operatorname{min-size}(X_p)$$ or $$\operatorname{min-entries}(X_p)$$?

After playing around for a while, the best I can find is the $$p\times p$$ matrix of the form

$$A = \begin{pmatrix} 1 & 1 & 1 & 1 & \cdots & 1 & 1\\ -1 & 1 & 0 & 0 & \cdots & 0& 0\\ 0 & -1 & 1 & 0 & \cdots & 0 & 0\\ 0 & 0 & -1 & 1 & \cdots & 0 & 0\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots\\ 0 & 0 & 0 & 0 & \cdots & -1 & 1 \end{pmatrix}.$$

This matrix $$A$$ has $$p-1$$ invariants factors of $$1$$ and one invariant factor of $$p$$. It has $$p$$ columns and $$3p-2$$ non-zero entries. Thus $$\operatorname{min-size}(X_p)\leq p$$ and $$\operatorname{min-entries}(X_p)\leq 3p-2$$.