11
$\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$
  • 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$ – Alex Nelson Dec 10 '12 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 '12 at 3:33
  • 1
    $\begingroup$ What does "Each row is well-ordered up to a multiple of five" mean? $\endgroup$ – Gerry Myerson Dec 10 '12 at 3:59
  • $\begingroup$ @GerryMyerson, post has been updated. $\endgroup$ – Fred Kline Dec 10 '12 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$ – Gerry Myerson Dec 10 '12 at 6:23
13
$\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$
11
$\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$
  • $\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$ – jobe Feb 11 '18 at 15:50
  • $\begingroup$ @jobe, you have four slots to fill, each of which can be filled in $q$ ways, hence, $q^4$. $\endgroup$ – Gerry Myerson Feb 11 '18 at 20:23
  • $\begingroup$ Sorry, I've mistakenly forgotten the word non-singular. I am interested in the number of non-singular matrices. $\endgroup$ – jobe Feb 12 '18 at 0:54
  • $\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$ – Gerry Myerson Feb 12 '18 at 1:34
  • $\begingroup$ Forgot to include @jobe in previous comment. $\endgroup$ – Gerry Myerson Feb 12 '18 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$
  • $\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$ – Fred Kline Dec 10 '12 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$

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.