4
$\begingroup$

Let $A$ be an $n\times n$ matrix with integer entries and let $d_1,...,d_n|q$ all be given natural numbers (I am happy to assume that $q$ is a prime power).

How many solutions $x_1,...,x_n$ modulo $q$ does

\[ A\mathbf x\equiv \mathbf 0\hspace {5mm}\text {mod}\hspace {1mm}(\mathbf d)\]

have?

(Motivation/context: This comes up in the local factors in a circle method application.)

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

You can assume WLOG that all $d_i$ are equal to $q$, by multiplying the $i$-th row of your matrix $A$ by $q/d_i$. So you are trying to find the size of the kernel of $A$ as an endomorphism of $\mathbf{Z} / q\mathbf{Z}$.

By the Smith normal form theorem, we can write $A$ as a product $U D V$ where $U, V$ are invertible over the integers and $D$ is diagonal. So you can WLOG assume that $D$ is itself diagonal, say with diagonal entries $c_1, \dots, c_n$ (some of which may be 0), and the kernel has size $\prod_i gcd(c_i, q)$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ The only problem is that the $c_i$s are the fundamental divisors of the matrix formed by taking each row of $A$ and multiplying by $q/d_i$, from which I'm not sure how to disentangle the $d_i$ dependency :/ perhaps it's not possible and indeed that's what I'm assuming now :( $\endgroup$
    – tomos
    Commented Mar 26, 2017 at 18:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .