2
$\begingroup$

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!

$\endgroup$
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$ 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$
    – felix
    Oct 10, 2010 at 21:56

2 Answers 2

1
$\begingroup$

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}).$$

$\endgroup$
0
$\begingroup$

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).

$\endgroup$
1
  • $\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$ Oct 10, 2010 at 8:56

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.