4

I came across this line "It is often easier to determine that a matrix is singular than it is to determine that a matrix is nonsingular. The facts below illustrate this.

Fact 1.10. Let $A\in\mathbb C^{n\times n}$ and $x,b\in\mathbb C^n$.

  • If $x\ne0$ and $Ax=0$, then $A$ is singular.
  • If $x\ne0$ and $A$ is nonsingular, then $Ax\ne0$.
  • If $Ax=b$, where $A$ is nonsingular and $b\ne0$, then $x\ne0$.

I am not sure how that it is illustrated. I understand the facts and agree with them. But how they make one to determine if a matrix is singular in a EASIER way, I do not understand. Any suggestions?

kennytm
  • 7,495
Seetha Rama Raju Sanapala
  • 339

4 Answers4

8

To show that a matrix $A$ is singular, you need JUST ONE non-zero vector $v$ that $Av=0$. On the flip side, to show that a matrix is non-singular in a similar way, you have to show that for EVERY non-zero $v$, $Av$ is non-zero. The latter seems like a lot of work compared to the former is all they are saying.

It's like this: To show that a person is a law abiding citizen, you have to go through every law in the constitution and show that the person has abided by them. Whereas to show that they are not, you just find ONE law they've broken.

This is a general theme in mathematics. When a question asked is of the form "For every blah blah.. we have blah' blah' ", to disprove it, it is just easier to show one instance where it fails.

Arkady
  • 9,315
  • 1
    :I think you peeped into the author's mind correctly. But to determine zero solutions (if you do not know it already) of the matrix, you need to work. If you have non-zero solutions, the matrix is singular, otherwise non-singular. So singularity and non-singularity are the sides of the same coin. So they, require the same amount of work of determine. -- I got your point. It is factual but I think effort-wise, it is the same to determine singular or non-singular. – Seetha Rama Raju Sanapala May 01 '16 at 00:50
  • 2
    @SeethaRamaRajuSanapala You're right that in the worst case, they require the same amount of work to determine. But in the best case, singular is easier because you might stumble upon the necessary $v$ right away, and then you don't have to do any more work. – Chris Culter May 01 '16 at 01:06
  • @Chris Cutler:I am looking at the general case. Neither the best nor the worst. In general, you have to go the whole hog - solve for zero solution and determine. – Seetha Rama Raju Sanapala May 01 '16 at 02:03
  • 1
    @SeethaRamaRajuSanapala The quotation says "often". If it had said "typically" then you would be justified in restricting to the general case, but "often" need only refer to special cases that arise frequently enough to be worth mentioning. – Erick Wong May 01 '16 at 16:49
5

Here's another way to see the same lesson. Forget about vectors for a minute and focus on the data that defines the matrix, its entries.

An $n\times n$ matrix has $n^2$ entries. Imagine that you read these entries one at a time, in any order you choose. How many entries will you have to read before you can decide whether the matrix is singular?

The answer depends on the matrix, so let's focus on the best case.

If the first row of the matrix is all zeroes, then the matrix is guaranteed to be singular regardless of the remaining rows. So if you choose to read the $n$ entries in the first row, and you get lucky, and they are indeed all zeroes, then you're done. In this best-case scenario, you proved that the matrix was singular by reading only $n$ entries.

On the other hand, if the matrix is nonsingular, you will have to read most of the entries before you can prove it. For example, you might learn that the matrix is nonsingular by reading all entries above (and including) the main diagonal. That's $(n^2+n)/2$ entries, which is more than half of the whole matrix. And off the top of my head, I don't think you can do any better than that.

If $n$ is one billion, then the difference between $n$ and $(n^2+n)/2$ is staggering. So this is a quantitative sense in which proving that a matrix is singular can be much, much easier than proving that a matrix is nonsingular.

Chris Culter
  • 26,806
  • Thanks for the new perspective. The book says based on those "facts" listed. Those facts do not imply what the authors say they imply. I agree with your reasoning but I think to determine the matrix singularity, you have to find the determinant and that needs all the elements not just the diagonal and above it. – Seetha Rama Raju Sanapala May 01 '16 at 01:51
  • @SeethaRamaRajuSanapala In the same case where one row is all zeroes, you don't need any other elements to see that the determinant is zero (expansion by minors). – Erick Wong May 01 '16 at 08:12
  • @Erick Wong:In the same case of one row being full of zeros, you can immediately say it is NOT non-singular. We are actually talking of the general case. Not when the zero solution is known, row is zero etc. – Seetha Rama Raju Sanapala May 01 '16 at 08:46
  • 2
    @SeethaRamaRajuSanapala You seem to have already decided what the quotation means so that you can disagree with it. If you don't believe there is room for interpretation, then I'm honestly not sure what you hope to learn from asking this question. I believe you need to add more detail to the question to clarify your expectations. – Erick Wong May 01 '16 at 16:36
2

The idea is that singularity is an existence statement, while nonsingularity is a for-all statement. Nonsingularity is like showing that every word in the English language has at least one of the letters A, E, I, O, U, or Y. To prove it, you'd need to find a way to show this property holds for every English word.

But singularity is like showing there is a word in the English language that does not contain A, E, I, O, or U. Here all we need to prove the statement is that there is some word that contains none of these letters, and often the simplest way to do this is just to point to a witness, in our example the word "why". Now it might not always be as easy as finding such a common word, just as not all singularity proofs are easier than all non-singularity proofs, but such is the underlying idea.

AJY
  • 8,729
2

I agree with all the other answers that this must be what the book means; however, I rather disagree with the general philosophy of this quotation.

Indeed, it is the opposite of what is the case in the applied setting: if nature throws a square matrix with real-valued entries at you, you can conclude with sufficiently precise equipment that it's non-singular but you can never conclude (by measurement alone) that it is singular (the point is that a vanishing determinant is a closed condition, so no error can be tolerated in measurements, whereas a non-vanishing determinant is an open condition).

hunter
  • 29,847
  • 2
    Here's another contrarian view along these lines: working modulo a small prime $p$, you can often decide that an integer matrix is non-singular just by computing the determinant modulo $p$, which only requires looking at the "last digit" of each entry in base $p$ rather than all the digits. If the determinant is non-zero mod $p$ then the matrix is definitely non-singular; but if the determinant is zero mod $p$ you need to look at more digits in order to decide. – Erick Wong May 02 '16 at 23:50