Skip to main content
MathOverflow

Return to Answer

added 134 characters in body
Source Link
Krishanu Sankar
Krishanu Sankar
  • 131
  • 4

All I have to add to what's been said isEDIT: There's an ad-hoc argument for whyerror in this number is divisible by $p$. If you let $f(n, k)$ be the number of $n \times n$ matrices with nonzero entries having rank $k$approach, then you can easily write down the recurrence (letting $m=p-1$ for simplicity of notation)

$$f(n, k)=m^{2k}f(n-1, k)+(2m^{n+k-1}-m^{2k-1}-m^{2k-2})f(n-1, k-1)+m^{2k-3}(m^{n-k+1}-1)^2f(n-1, k-2)$$

You can thenit doesn't work. Computing some examples seems to show by induction that $f(n, n)$ and $f(n, n-1)$ are both divisible by $p$ for $n \ge 3$the answer is pretty complicated. It's true for $n=3$, because $f(3, 2)=m^5(m+1)^2(m-1)$ and $f(3, 3)=m^6(m+1)(m-1)^2$ are both divisible by $m+1$. Then since $m=p-1 \equiv -1\pmod{p}$, you can just use the above equation $\pmod{p}$ to write $$f(n, n-1) \equiv f(n-1, n-1)+2f(n-1, n-2)$$ $$f(n, n) \equiv -2f(n-1, n-1)-4f(n-1, n-2)$$ which are both zero by hypothesis.

(I did also turn the above recurrence into a generating function identity, but the result seems very hard to solve. It's been a long time since I used generating functions, so I don't know if it's hard just because of that.)(All I have to add to what's been said is an ad-hoc argument for why this number is divisible by $p$. If you let $f(n, k)$ be the number of $n \times n$ matrices with nonzero entries having rank $k$, then you can easily write down the recurrence (letting $m=p-1$ for simplicity of notation) $$f(n, k)=m^{2k}f(n-1, k)+(2m^{n+k-1}-m^{2k-1}-m^{2k-2})f(n-1, k-1)+m^{2k-3}(m^{n-k+1}-1)^2f(n-1, k-2)$$ You can then show by induction that $f(n, n)$ and $f(n, n-1)$ are both divisible by $p$ for $n \ge 3$. It's true for $n=3$, because $f(3, 2)=m^5(m+1)^2(m-1)$ and $f(3, 3)=m^6(m+1)(m-1)^2$ are both divisible by $m+1$. Then since $m=p-1 \equiv -1\pmod{p}$, you can just use the above equation $\pmod{p}$ to write $$f(n, n-1) \equiv f(n-1, n-1)+2f(n-1, n-2)$$ $$f(n, n) \equiv -2f(n-1, n-1)-4f(n-1, n-2)$$ which are both zero by hypothesis. (I did also turn the above recurrence into a generating function identity, but the result seems very hard to solve. It's been a long time since I used generating functions, so I don't know if it's hard just because of that.))

All I have to add to what's been said is an ad-hoc argument for why this number is divisible by $p$. If you let $f(n, k)$ be the number of $n \times n$ matrices with nonzero entries having rank $k$, then you can easily write down the recurrence (letting $m=p-1$ for simplicity of notation)

$$f(n, k)=m^{2k}f(n-1, k)+(2m^{n+k-1}-m^{2k-1}-m^{2k-2})f(n-1, k-1)+m^{2k-3}(m^{n-k+1}-1)^2f(n-1, k-2)$$

You can then show by induction that $f(n, n)$ and $f(n, n-1)$ are both divisible by $p$ for $n \ge 3$. It's true for $n=3$, because $f(3, 2)=m^5(m+1)^2(m-1)$ and $f(3, 3)=m^6(m+1)(m-1)^2$ are both divisible by $m+1$. Then since $m=p-1 \equiv -1\pmod{p}$, you can just use the above equation $\pmod{p}$ to write $$f(n, n-1) \equiv f(n-1, n-1)+2f(n-1, n-2)$$ $$f(n, n) \equiv -2f(n-1, n-1)-4f(n-1, n-2)$$ which are both zero by hypothesis.

(I did also turn the above recurrence into a generating function identity, but the result seems very hard to solve. It's been a long time since I used generating functions, so I don't know if it's hard just because of that.)

EDIT: There's an error in this approach, it doesn't work. Computing some examples seems to show the answer is pretty complicated...

(All I have to add to what's been said is an ad-hoc argument for why this number is divisible by $p$. If you let $f(n, k)$ be the number of $n \times n$ matrices with nonzero entries having rank $k$, then you can easily write down the recurrence (letting $m=p-1$ for simplicity of notation) $$f(n, k)=m^{2k}f(n-1, k)+(2m^{n+k-1}-m^{2k-1}-m^{2k-2})f(n-1, k-1)+m^{2k-3}(m^{n-k+1}-1)^2f(n-1, k-2)$$ You can then show by induction that $f(n, n)$ and $f(n, n-1)$ are both divisible by $p$ for $n \ge 3$. It's true for $n=3$, because $f(3, 2)=m^5(m+1)^2(m-1)$ and $f(3, 3)=m^6(m+1)(m-1)^2$ are both divisible by $m+1$. Then since $m=p-1 \equiv -1\pmod{p}$, you can just use the above equation $\pmod{p}$ to write $$f(n, n-1) \equiv f(n-1, n-1)+2f(n-1, n-2)$$ $$f(n, n) \equiv -2f(n-1, n-1)-4f(n-1, n-2)$$ which are both zero by hypothesis. (I did also turn the above recurrence into a generating function identity, but the result seems very hard to solve. It's been a long time since I used generating functions, so I don't know if it's hard just because of that.))

Source Link
Krishanu Sankar
Krishanu Sankar
  • 131
  • 4

All I have to add to what's been said is an ad-hoc argument for why this number is divisible by $p$. If you let $f(n, k)$ be the number of $n \times n$ matrices with nonzero entries having rank $k$, then you can easily write down the recurrence (letting $m=p-1$ for simplicity of notation)

$$f(n, k)=m^{2k}f(n-1, k)+(2m^{n+k-1}-m^{2k-1}-m^{2k-2})f(n-1, k-1)+m^{2k-3}(m^{n-k+1}-1)^2f(n-1, k-2)$$

You can then show by induction that $f(n, n)$ and $f(n, n-1)$ are both divisible by $p$ for $n \ge 3$. It's true for $n=3$, because $f(3, 2)=m^5(m+1)^2(m-1)$ and $f(3, 3)=m^6(m+1)(m-1)^2$ are both divisible by $m+1$. Then since $m=p-1 \equiv -1\pmod{p}$, you can just use the above equation $\pmod{p}$ to write $$f(n, n-1) \equiv f(n-1, n-1)+2f(n-1, n-2)$$ $$f(n, n) \equiv -2f(n-1, n-1)-4f(n-1, n-2)$$ which are both zero by hypothesis.

(I did also turn the above recurrence into a generating function identity, but the result seems very hard to solve. It's been a long time since I used generating functions, so I don't know if it's hard just because of that.)