# proportions of invertible matrices

Let $GL(d,R)$ denote the invertible $d\times d$-matrices over a ring $R$, and $M_{d}(R)$ the set of all $d\times d$-matrices over $R$. When $R$ is a finite field of order $q$, commonly denoted $GF(q)$ or $\mathbb{F}_{q}$, we prefer to write simply $q$. In particular, $q$ is a power of a prime.

###### Proposition 1.
 $\frac{|GL(d,q)|}{|M_{d}(q)|}=\prod_{i=1}^{d}\left(1-\frac{1}{q^{i}}\right).$
###### Proof.

The number of $d\times d$-matrices over a $GF(q)$ is $q^{d^{2}}$. When a matrix is invertible, its rows form a basis of the vector space $GF(q)^{d}$ and this leads to the following formula

 $|GL(d,q)|=q^{\binom{d}{2}}\prod_{i=1}^{d}(q^{i}-1).$

(Refer to order of the general linear group. (http://planetmath.org/OrdersAndStructureOfClassicalGroups))

Now we prove the ratio holds:

 $\prod_{i=1}^{d}\left(1-\frac{1}{q^{i}}\right)=\prod_{i=1}^{d}\frac{q^{i}-1}{q^% {i}}=\frac{1}{q^{\binom{d+1}{2}}}\prod_{i=1}^{d}(q^{i}-1)=\frac{1}{q^{d^{2}}}q% ^{\binom{d}{2}}\prod_{i=1}^{d}(q^{i}-1)=\frac{|GL(d,q)|}{|M_{d}(q)|}.$

###### Corollary 2.

As $q\rightarrow\infty$ with $d$ fixed, the proportion of invertible matrices to all matrices converges to 1. That is:

 $\lim_{q\rightarrow\infty}\frac{|GL(d,q)|}{|M_{d}(q)|}=1.$
###### Corollary 3.

As $d\rightarrow\infty$ and $q$ is fixed, the proportion of invertible matrices decreases monotonically and converges towards a positive limit. Furthermore,

 $\frac{1}{4}\leq 1-\frac{q^{2}-q+1}{q^{2}(q-1)}\leq\prod_{i=1}^{d}\left(1-\frac% {1}{q^{i}}\right)\leq 1-\frac{1}{q}.$
###### Proof.

By direct expansion we find

 $\prod_{i=1}^{\infty}(1-a_{i})=1-\sum_{1\leq i}a_{i}+\sum_{1\leq i

So setting $a_{0}=1$ and

 $a_{i+1}=a_{i}\sum_{j=i+1}^{\infty}\frac{1}{q^{j}}=a_{i}\frac{1}{q^{i}(q-1)}$

for all $i\in\mathbb{N}$, we have

 $\prod_{i=1}^{\infty}\left(1-\frac{1}{q^{i}}\right)=\sum_{i=0}^{\infty}(-1)^{i}% a_{i}.$

As $a_{i}\geq 0$, $a_{i}\geq a_{i+1}$ for all $i\in\mathbb{N}$ and $a_{i}\rightarrow 0$ as $i\rightarrow\infty$, we may use Leibniz’s theorem to conclude the alternating series converges. Furthermore, we may estimate the error to the $N$-th term with error within $\pm a_{N+1}$. Using $N=2$ we have an estimate of $1-1/q$ with error $\pm\frac{1}{q^{2}(q-1)}$. Since $q\geq 2$ this gives $1/2$ with error $\pm 1/4$. Thus we have at least $1/4$ chance of choosing an invertible matrix at random. ∎

###### Remark 4.

$q=2$ is the only field size where the proportion of invertible matrices to all matrices is less than $1/2$.

Acknowledgements: due to discussions with Wei Zhou, silverfish and mathcam.

Title proportions of invertible matrices ProportionsOfInvertibleMatrices 2013-03-22 15:57:35 2013-03-22 15:57:35 Algeboy (12884) Algeboy (12884) 16 Algeboy (12884) Theorem msc 15A33 proportions invertible linear transformations