1
$\begingroup$

(practising for combinatorics exam) question starts with Euler's pentagonal numbers theorem. then goes onto asking - how many invertible nxn matrices over a field of q elements are there? what is the probability p(n,q) that a random nxn matrix is invertible?

$\endgroup$
  • $\begingroup$ This is a nice question that I also usually give when teaching linear algebra. You can observe that the matrix is invertible if and only if all columns are linearly independent, and then imagine choosing columns one-by-one. There are $q^n-1$ choices of the first column (it only needs to be nonzero). Given this, there are...choices of the second column, and so on. Can you finish the problem? [I do not know what Euler's pentagonal number theorem is, but you can solve without it.] $\endgroup$ – Michael May 6 '17 at 20:26
  • 1
    $\begingroup$ so for the second row it's q^(n)-q because we don't want a scalar multiple of row 1, etc until the last row where it's q^(n) - q^(n-1). then we multiply all these together ? $\endgroup$ – ananas May 6 '17 at 20:35
  • $\begingroup$ Looks good. The probability question uses essentially the same reasoning. One aspect is you might want to formally prove that all $k$-dimensional subspaces of this vector space (with this $q$-field) have size $q^k$. If you like, you can answer your own question and mark it as "best answer" (this is standard practice on stackexchange when solving a question based on suggestions in the comments). $\endgroup$ – Michael May 6 '17 at 20:36
  • $\begingroup$ A part of this question has been asked before : math.stackexchange.com/questions/1399406/… $\endgroup$ – Arnaud D. May 6 '17 at 21:44
0
$\begingroup$

This is the same as choosing a basis of the vector space $F^n$ where $F$ has q elements. So for the first basis element we have $q^n-1$ choices. For the next we have $q^n-q$. In general for the ith basis element we have $q^n-q^{i-1}$ choices. So the number of invertible matrices is the product of all these expressions from i= 1 to n

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.