12
$\begingroup$

I am exploring patterns of integers in $n\times n$ matrices. I have two matrices that have a determinant of $0$ and a circulant matrix that has positive determinants that differ depending on $n$.

I snipped this from Wikipedia and bolded the important part:


A square matrix that is not invertible is called singular or degenerate. A square matrix is singular if and only if its determinant is 0. Singular matrices are rare in the sense that if you pick a random square matrix over a continuous uniform distribution on its entries, it will almost surely not be singular.


The Good: $$\left( \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \\ 1 & 2 & 3 & 4 & 5 \\ \end{array} \right)$$ The Bad: $$\left( \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 5 & 1 & 2 & 3 & 4 \\ 4 & 5 & 1 & 2 & 3 \\ 3 & 4 & 5 & 1 & 2 \\ 2 & 3 & 4 & 5 & 1 \\ \end{array} \right)$$ And the Ugly: $$\left( \begin{array}{ccccc} 11 & 12 & 13 & 14 & 15 \\ 16 & 17 & 18 & 19 & 20 \\ 21 & 22 & 23 & 24 & 25 \\ 26 & 27 & 28 & 29 & 30 \\ 31 & 32 & 33 & 34 & 35 \\ \end{array} \right)$$

The Good is same as Ugly mod n and both are singular. The Bad is the circulant Good and has determinant $>0$.

Two questions:

  1. What makes a singular matrix rare?
  2. Has anyone documented the differences? (preferably, using $n$ or $n^2$)
$\endgroup$
9
  • 6
    $\begingroup$ Hint: construct equivalence classes of matrices determined by their determinant. You'll see that singular matrices are comparatively small (i.e., represented by a single class) out of uncountably many equivalence classes (assuming you are working over $\mathbb{R}$ or $\mathbb{C}$)... $\endgroup$ Dec 10, 2012 at 3:32
  • $\begingroup$ I don't know what you mean by "the $n^{\rm th}$ column elements[...] are always multiples of $n.$" E.g., $(a,b;a,b)\in\operatorname{Mat}_{2\times 2}$ is singular for any choice of $a,b.$ $\endgroup$
    – Andrew
    Dec 10, 2012 at 3:33
  • 1
    $\begingroup$ What does "Each row is well-ordered up to a multiple of five" mean? $\endgroup$ Dec 10, 2012 at 3:59
  • $\begingroup$ @GerryMyerson, post has been updated. $\endgroup$ Dec 10, 2012 at 4:21
  • 2
    $\begingroup$ Nope, no closer to understanding what you mean by "well-ordered up to a multiple of $n$," but very close to concluding that you don't understand what you mean by that phrase, either. $\endgroup$ Dec 10, 2012 at 6:23

5 Answers 5

14
$\begingroup$

Thinking in terms of probability helps. If you have a continuous probability distribution defined on some space of matrices, then typically the singular matrices will have probability zero. Thinking in terms of the determinant: The determinant is a polynomial in the entries of the matrix. Setting it to zero gives a polynomial equation, which are defining (implicitely) some surface in the matrix space. This surface will have a reduced dimension , so its (Lebesgue) measure will be zero.

$\endgroup$
12
$\begingroup$

The number of $2\times2$ matrices over a field of $q$ elements is $q^4$.

The number of non-singular $2\times2$ matrices over a field of $q$ elements is $$(q^2-1)(q^2-q)=q^4-q^3-q^2+q$$ which means only $q^3+q^2-q$ out of $q^4$ are singular.

$\endgroup$
5
  • $\begingroup$ I've failed to figure out how the number of $2\times 2$ matrices over a field of $q$ elements is computed. Could you give or indicate a proof? $\endgroup$ Feb 11, 2018 at 15:50
  • $\begingroup$ @jobe, you have four slots to fill, each of which can be filled in $q$ ways, hence, $q^4$. $\endgroup$ Feb 11, 2018 at 20:23
  • $\begingroup$ Sorry, I've mistakenly forgotten the word non-singular. I am interested in the number of non-singular matrices. $\endgroup$ Feb 12, 2018 at 0:54
  • 1
    $\begingroup$ The top row can be anything but $(0,0)$, so $q^2-1$ choices. The other row can be anything but a scalar multiple of the top row, so $q^2-q$ choices. $\endgroup$ Feb 12, 2018 at 1:34
  • $\begingroup$ Forgot to include @jobe in previous comment. $\endgroup$ Feb 12, 2018 at 11:19
4
$\begingroup$

Here is an extension of Gerry's argument. There are $q^{n^2}$ matrices in $M_{n\times n}(\mathbb{F}_q)$ and $\prod_{k=0}^{n-1}(q^n-q^k)$ elements in $GL_n(\mathbb{F}_q)$.

$$\lim_{q\to\infty}\frac{\prod_{k=0}^{n-1}(q^n-q^k)}{q^{n^2}}=\lim_{q\to\infty}(q^{-n};q)_n=\lim_{q\to\infty}\prod_{k=0}^{n-1}\left(1-q^{-n+k}\right)=1$$ where $(q^{-n};q)_n$ is the $q$-Pochammer symbol.

Note that the fact that $\mathbb{F}_q$ has nonzero characteristic doesn't affect this argument, since the formula $\prod_{k=0}^{n-1}(q^n-q^k)$ is based on picking $n$ linearly independent vectors combinatorially from $(\mathbb{F}_q)^n$, a process which extends to the infinite case independently of characteristic.

$\endgroup$
1
  • $\begingroup$ Good has rank 1 and Ugly has rank 2. Bad has no rank. I'm new at this stuff, so I hope I've read it right. $\endgroup$ Dec 10, 2012 at 4:34
3
$\begingroup$

If you think about the interpretation of a matrix as a system of equations, and take the 2-variable case as an easy to visualize example, most pairs of equations are not parallel lines. If the 2nd column is a multiple of the first, then they are parallel. Inb this case, the 2nd column will be a multiple of the first.

Of course, for the 3 dimensional case, there are linear combinations, so this no longer holds in the same sense, but you still have the nth column as a "multiple" of one or both of the other columns.

Does that clarify, or is there something more complex you are noticing?

$\endgroup$
3
$\begingroup$

There's at least one very easy way to think about this. Imagine the $n$ column vectors as just points in $\mathbf{R}^n$. Now the matrix is singular if and only if these points all lie in a single $(n-1)$-dimensional subspace i.e hyperplane that goes through the origin. Typically if I just pick $n$ random points, there is basically no chance they will accidentally lie on a single hyperplane.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .