I've been working recently with vectors over finite fields, but I was hoping to work in a more general setting and consider vectors over finite commutative rings. The question I had is as follows: if I fill $n$ vectors with random entries over a given finite commutative ring (call it $\mathcal{R}$), then what is the probability that the resulting vectors are a basis for (or at least span) $\mathcal{R}^n$? I'm pretty sure I have this worked out for the case of finite fields, but I'm having trouble generalizing so any help would be great. Thanks!
2
-
4$\begingroup$ I've not thought too hard about this, but: a general finite ring is semi-local so a product of local rings, so that reduces the question to local rings. And then via a Nakayama argument my gut feeling is that you'll be able to reduce to the case of the residue field, which you've already done. $\endgroup$– Kevin BuzzardCommented Oct 10, 2010 at 8:55
-
2$\begingroup$ Kevin, this is indeed true. $v_1, \dots, v_n \in \mathcal{R}^n$ give a basis of $\mathcal{R}^n$ iff $\det (v_1, \dots, v_n) \in \mathcal{R}^\ast$, and this is the case iff $\det (v_1, \dots, v_n) \neq 0$ modulo every maximal ideal of $\mathcal{R}$. Hence, the probability that a random $n \times n$-matrix is invertible is the product of the probabilities for random $n \times n$-matrices to be invertible over all residue fields of $\mathcal{R}$. $\endgroup$– felixCommented Oct 10, 2010 at 21:56
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
This question was more-or-less answered in the comments already; here is a summary posted as an actual answer:
If $R$ is any commutative ring, then a square matrix $A$ over $R$ is invertible if and only if $\det A$ is a unit. It is a polynomial identity that $(\text{adj}\;A)A = \det A$, where $\text{adj}\;A$ is the adjugate matrix. So, if $\det A$ is a unit, you can divide and make $A^{-1}$. On the other hand, if $A^{-1}$ exists, then $\det A^{-1}$ is the reciprocal of $\det A $, by the polynomial identity $\det AB = (\det A)(\det B)$.
If $R$ is any commutative ring and $x \in R$, then $x$ is a unit if and only if its image $x_I$ is non-zero in $R/I$ for every maximal ideal of $R$. If $x$ is a unit, then $x^{-1}$ is the reciprocal in every $R/I$. On the other hand, if $x$ is not a unit, then the ideal $(x)$ is proper and is contained in a maximal ideal $I$, and then $x_I = 0$ for that choice of $I$.
If $R$ is a finite commutative ring, then it is the direct sum of local rings. (Where by definition a local ring is one with only one maximal ideal.) This implies that if $x \in R$ is uniformly random, then the variables $x_I$ are independent and uniformly random for the different maximal ideals. (When $R$ is infinite, the same thing can be approximately true for various natural distributions. For instance if $R = \mathbb{Z}$ and $x$ is chosen randomly in $\{1,\ldots,N\}$, then for small primes $p$, $x$ is approximately random mod $p$.)
If $I$ is maximal and $R/I$ is finite, then $R/I \cong \mathbb{F}_{q_I}$ for some prime power $q_I$. So, if $R$ is finite and $A$ is a random matrix over $R$, then the matrices $A_I$ over $R/I$ are independent random matrices over the finite fields $\mathbb{F}_{q_I}$. The probability that $A$ is invertible is thus the product of these probabilities, which for a random $n \times n$ matrix over $\mathbb{F}_q$ is: $$p = (1-\frac1{q})(1-\frac1{q^2})\cdots(1-\frac1{q^n}).$$
answered Oct 24, 2010 at 16:13
$\begingroup$
$\endgroup$
1
Is this $n$ vectors of length $n$? Whatever it is, for the case of integers mod $m$ where $m$ is square free it is just the product of the probabilities over the prime factors.
In the case that $n=1$ and the ring is the integers mod $m$ then it could be very small if $m$ was the product of the first many primes (it goes under 0.1 for the product of the primes up to 257).
answered Oct 10, 2010 at 6:29
-
$\begingroup$ @Aaron: if you want a smaller ring where the probability is tiny then just consider a product of lots of $\mathbf{Z}/2\mathbf{Z}$s. $\endgroup$ Commented Oct 10, 2010 at 8:56