1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.