Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question

1 Answer 1

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

share|improve this answer
    
Thank you Ilya! This was very helpful! –  user30076 Dec 19 '12 at 7:40

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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