proportions of invertible matrices
Let denote the invertible -matrices over a ring , and the set of all -matrices over . When is a finite field of order , commonly denoted or , we prefer to write simply . In particular, is a power of a prime.
Proposition 1.
Proof.
The number of -matrices over a is . When a matrixis invertible, its rows form a basis of the vector space and thisleads to the following formula
(Refer to order of the general linear group. (http://planetmath.org/OrdersAndStructureOfClassicalGroups))
Now we prove the ratio holds:
∎
Corollary 2.
As with fixed, the proportion of invertible matricesto all matrices converges to 1. That is:
Corollary 3.
As and is fixed, the proportion of invertible matrices decreases monotonically and converges towards a positive limit. Furthermore,
Proof.
By direct expansion we find
So setting and
for all , we have
As , for all and as , we may use Leibniz’s theorem to conclude the alternatingseries converges. Furthermore, we may estimate the error to the -th term witherror within . Using we have an estimate of with error. Since this gives with error . Thuswe have at least chance of choosing an invertible matrix at random.∎
Remark 4.
is the only field size where the proportion of invertible matrices to all matrices is less than .
Acknowledgements: due to discussions with Wei Zhou, silverfish and mathcam.