News for hackers. Stuff that matters.
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by mikhailfranco on Saturday March 02, 2024 @10:51AM (#39573335)
The title words remind of an unrelated fact, Gershgorin Disks:

  The eigenvalues of any N x N matrix, A, 
  are contained in the union of N discs in the complex plane. 
  The center of the i_th disc is the i_th diagonal element of A. 
  The radius of the i_th disc is the absolute values 
  of the off-diagonal elements in the i_th row. 
https://blogs.sas.com/content/iml/2019/05/22/gershgorin-disc...

It's rather remarkable, unexpected, and perhaps shocking, when you first hear it. There does not seem to be enough information to make it true. But it is.

I used it in a real project to cancel noise.

Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by stabbles on Saturday March 02, 2024 @12:01PM (#39573839)
It's not that remarkable at all? The proof requires the definition and triangle inequality, that's all?

Given Ax=λx, take i for which |xᵢ| is largest. Look at the i'th equation: sum aᵢⱼxⱼ = λxᵢ, move the aᵢᵢxᵢ term to the rhs, take absolute values, divide by |xᵢ|, apply triangle inequality, and you have |aᵢᵢ - λ| ≤ sum |aᵢⱼ| over j≠i. So for every eigenvalue you can find such a disc.

That's by column, for row use Aᵀ.

Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by kmm on Saturday March 02, 2024 @01:02PM (#39574364)
Being easy to prove doesn't make it unremarkable. Lots of theorems, including this one, have straightforward proofs once you are given the exact formulation. The tricky part is coming up with the idea for the theorem itself. I remember being (mildly) shocked when I was taught this in undergrad, it just seemed too good to be true.
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by stabbles on Saturday March 02, 2024 @01:41PM (#39574748)
I think that's just how textbooks present it. A fact is stated but you're lacking intuition.

If you had played around a bit with Laplacian matrices, like tri-diagonal matrices with stencil [-1, 2, -1], and found that its eigenvalues are within 2 ± 2, and if you also realized that A + τI has the same eigenvalues shifted by τ, then it's a small step to consider that the magnitude of the off-diagonal may have something to do with the spread of eigenvalues.

It's likely that Gerschgorin stumbled upon it like this.

Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by xelxebar on Sunday March 03, 2024 @08:05AM (#39580570)
> tri-diagonal matrices with stencil [-1, 2, -1],

Just trying to understand these terms. So is a 5x5 tridiagonal matrix with your stencil look like this?

     2 -1  0  0  0
    -1  2 -1  0  0
     0 -1  2 -1  0
     0  0 -1  2 -1
     0  0  0 -1  2
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by stabbles on Sunday March 03, 2024 @09:26AM (#39581000)
Yeah, exactly. Your matrix shows up when you do a 3-point discretization of -u''(x) = λu(x) with u(0) = u(1) = 0, at 5 equidistant (interior) grid points. That's the discrete, 1D version of the problem they're looking at in the paper.

See https://en.wikipedia.org/wiki/Compact_stencil#Three_Point_St...

Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by llmzero on Saturday March 02, 2024 @02:36PM (#39575156)
Just thinking about some intuition for the result of the theorem: If the off diagonal elements are zero then the diagonal element is an eigenvalue, by continuity of the determinant, if the off diagonal element are small then $det(A-a_{ii}\lambda)$ is almost zero, that is the new eigenvalue is near aii. So it suggests that the off diagonal elements measure how far is aii from being an eigenvalue.
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by nine_k on Saturday March 02, 2024 @01:02PM (#39574367)
The Euler's identity is also trivial to deduce, but this doesn't diminish its beauty.
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by xanderlewis on Saturday March 02, 2024 @01:25PM (#39574576)
The Yoneda lemma is another great example of (once you've got the right setup) trivial but beautiful
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by moralestapia on Saturday March 02, 2024 @02:34PM (#39575144)
Huh?

Math 101, simple is better.

Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by jonahx on Saturday March 02, 2024 @03:09PM (#39575375)
removed
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by tsimionescu on Saturday March 02, 2024 @04:29PM (#39575944)
They are saying that the Greshgorin theorem that the OP is talking about is simple to prove, not the Polya conjecture that took 70 years from the article.
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by jonathan_landy on Saturday March 02, 2024 @11:24AM (#39573564)
Matrix theory by Franklin is a great, affordable book containing many interesting results such as this — can highly recommend for those interested in linear algebra.

https://www.amazon.com/Matrix-Theory-Dover-Books-Mathematics...

Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by packetlost on Saturday March 02, 2024 @11:56AM (#39573809)
If I have an atrophied high school level understanding of linear algebra, will I get anything out of that book?
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by jonathan_landy on Saturday March 02, 2024 @12:48PM (#39574232)
Certainly a useful reference, if you might deal with the topic for some project … but not the best refresher out there for the basics.
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by amelius on Sunday March 03, 2024 @05:27AM (#39579915)
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by doubloon on Saturday March 02, 2024 @02:09PM (#39574991)
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by homerowilson on Saturday March 02, 2024 @05:23PM (#39576302)
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by Ziggy_Zaggy on Sunday March 03, 2024 @05:16PM (#39585061)
Any more details on this one? What might one use-case be for this application?
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by kwkelly on Saturday March 02, 2024 @05:28PM (#39576334)
Matrix Analysis by Horn and Johnson is another great book, though it is a bit pricier than a Dover book.
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by abetusk on Saturday March 02, 2024 @11:02AM (#39573391)
What was the noise cancelling project? How did you use this fact to cancel noise?
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by sdenton4 on Saturday March 02, 2024 @12:36PM (#39574134)
Just guessing, but....

A common noise cancellation technique is to throw away small eigenvalues, as in PCA. This result relates eigenvalues to the structure of the matrix, so might be helpful for reducing ev's without bothering with diagonalization?

[Edit] This would presumably involve just zeroing out the rows with small diagonal elements and small-ish off-diagonal norm... Center the eigenvalue estimate disk at zero, and then zero out the rest of the row to make the estimate exact.

Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by sdenton4 on Saturday March 02, 2024 @04:55PM (#39576114)
(and after one more thought about it, one would zero out the row /and column/ to preserve the symmetry of the matrix, if applicable, and thus keep the eigenvalues real. and one would probably want to think a bit about whether this kind of deletion actually makes sense for the problem... doing real PCA isn't /that/ hard in most cases - I think I would do something this janky only for extremely large matrices or for realtime operation on a microcontroller or something, and then only after thinking hard about it.)
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by frutiger on Saturday March 02, 2024 @11:00AM (#39573387)
Sounds very cool. One thing I didn’t understand though:

> The radius of the i_th disc is the absolute values

How can a radius of a single disc (i.e. a single value) correspond to multiple values?

Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by ximeng on Saturday March 02, 2024 @11:09AM (#39573442)
If you look at the link there’s a formula showing it’s the sum.
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by abetusk on Saturday March 02, 2024 @11:18AM (#39573521)
Specifically:

    r_i = \sum_{i \ne j} |A_{i j}|
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by reactordev on Saturday March 02, 2024 @11:05AM (#39573423)
I’m assuming, but could be wrong as my matrix math ended with GameDev, that the radius of the disk = the absolute values of the other things. +\- depending on which side of the disk they fall?

That line got me as well.

Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by Sharlin on Saturday March 02, 2024 @11:23AM (#39573556)
It's missing the word "sum". Which apparently my brain auto-deduced for me because I didn't notice anything off in the sentence on the first reading.
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by _zoltan_ on Saturday March 02, 2024 @12:17PM (#39573981)
My brain also automatically added sum and also haven't noticed anything, but I have a math degree, maybe it's just assuming things :-)
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by frutiger on Saturday March 02, 2024 @12:25PM (#39574053)
I have a physics degree and did not assume it, that might explain the difference :)
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by tomrod on Saturday March 02, 2024 @11:52AM (#39573788)
Sum the absolute values of a row for all the off diagonal elements
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by Infinity315 on Saturday March 02, 2024 @05:07PM (#39576197)
An intuitive explaination is imagine a nearly diagonal matrix where the values along the diagonal are much larger than values on the off diagonal. We know the eigenvalues of a diagonal matrix is simply the values on the diagonal, so for nearly diagonal matrices you can be pretty sure that the true eigenvalues are going to be pretty close to those diagonal entries, but a natural question to ask is how far we'd deviate from those diagonal entries.

The answer to the above question is Gerschgorin disks and it's closely related cousin Brauer's Oval of Cassini.

For matrices with real eigenvalues it's moreso along the real number line, only for cases where the eigenvalues are imaginary do we imagine disks.

Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by bee_rider on Saturday March 02, 2024 @01:19PM (#39574525)
It has an intuitive element to it; we’re looking for the eigenvalue, the vector/scalar pair where the scalar has the same effect on the vector as multiplying by the matrix. And we’re comparing against something that looks vaguely like the magnitude of the matrix (shifted by the diagonal, and of course if you had a diagonal matrix, the eigenvalues would just be the diagonal).

Not a proof or anything, of course the proof is on Wikipedia and nice and elegant. Just a thought on the gut feeling.

I agree that it is a very nice result.

Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by Infinity315 on Saturday March 02, 2024 @05:03PM (#39576162)
See also Brauer's oval of Cassini which give an equivalent or even better approximation of the eigenvalues of a matrix.
Re:Mathematicians prove Pólya's conjecture for the eigenvalu... by Tommah on Saturday March 02, 2024 @07:05PM (#39577024)
bee_rider already touched on this in another comment, but the theorem makes sense if you consider a matrix with large diagonal values and small off-diagonal values (in magnitude). If I have a matrix with 1,000,000 on the diagonal and 1 everywhere else, I'd expect the eigenvalues to be 1,000,000 plus or minus some small error. The Gershgorin disk theorem proves this and puts an upper bound on the error.

The diagonal elements of matrices have a lot of rather "magical" properties if you think about it. Their sum is also the sum of the eigenvalues of the matrix. And if you have a matrix A that is singular, you can choose any value x that is not an eigenvalue, and then A - xI is invertible but still mostly behaves like A.