2
$\begingroup$

Let $A_1$ and $A_2$ be two arbitrary $n\times n$ matrices with entries in $Z_p$. How many $n\times n$ matrices $B$ are there so that both $A_1-B$ and $A_2-B$ are of rank $n-1$ or less? What is the formula if the rank is $n-k$ (for both $A_1-B$ and $A_2-B$)?

It is okay if I know a loose bound (but not trivial, of course). It looks like they are certainly less than $n^2.p^{n^2-k}$. Anything better would be really helpful.

Thanks!

$\endgroup$

1 Answer 1

1
$\begingroup$

$\def\rk{\mathop{\rm rank}}\def\ZZ{{\mathbb Z}}$ We need to estimate the number of expansions of the form $A:=A_1-A_2=C_1-C_2$ with $\rk C_i\leq n-k$ (then $B=A_1-C_1=A_2-C_2$). Since the multiplication by a non-degenerate matrix does not change anything, this depends only on $\rk A$.

Assume, for instance, that $A$ is non-degenerate. Fix two $(n-k)$-dimensional subspaces $V_1,V_2$ of the space of rows $V=\ZZ_p^n$ with $\dim V_i=n-k$; counting the bases, we obtain that there are there are $$ N=\displaystyle \frac{\prod_{i=0}^{n-1}(p^n-p^i)} {\prod_{i=0}^{n-2k-1}(p^{n-2k}-p^i)\cdot \bigl(\prod_{i=n-2k}^{n-k-1}(p^{n-k}-p^i)\bigr)^2} $$ such pairs of subspaces.

Denote by $C_i^j$ the $j$th row of $C_i$. Now let us count all the pairs $(C_1,C_2)$ such that $\mathop{\rm span} (C_i^1,\dots,C_i^n)\subseteq V_i$. Let $V'=V_1\cap V_2$. Then $C_i^j\mod V'$ is determined uniquely, hence we have $p^{n-2k}$ variants for each $C_1^j$, and $C_2$ is reconstructed from $C_1$. Thus we have $p^{n(n-2k)}$ pairs.

In total, we get $N\cdot p^{n(n-2k)}$ pairs. In fact, this is an upper bound, since the rank of $C_i$ may be less than $p-k$, and in this case one pair will correspond to several pairs $(V_1,V_2)$.

You may easily obtain a bound for $N$, but it would be better to know the relation between $p$ and $n$...

If $A$ is degenerate, then this bound should increase, since we just need $V_1+V_2$ to contain the space generated by the rows of $A$. On the other hand, we may restrict ourselves to the case when $(V_1+V_2)\mod V'=\mathop{\rm span}(A^1,\dots,A^n)\mod V'$.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.