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, unexpecte…
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...
Mathematicians prove Pólya's conjecture for the eigenvalues of a disk
41–50 of 64 posts
Re: Mathematicians prove Pólya's conjecture for the eigenvalues of a disk
#42The 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, unexpecte…
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ᵀ.
Huh?
Math 101, simple is better.
Re: Mathematicians prove Pólya's conjecture for the eigenvalues of a disk
#43Earlier quoted context omitted.
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ᵀ.
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.
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 eigenvalues of a disk
#44The 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, unexpecte…
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ᵀ.
removed
Re: Mathematicians prove Pólya's conjecture for the eigenvalues of a disk
#45Earlier quoted context omitted.
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ᵀ.
removed
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 eigenvalues of a disk
#46Earlier quoted context omitted.
What was the noise cancelling project? How did you use this fact to cancel noise?
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 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 eigenvalues of a disk
#47The 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, unexpecte…
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 eigenvalues of a disk
#48The 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, unexpecte…
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?
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 eigenvalues of a disk
#49The 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, unexpecte…
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...
You may enjoy this:
Re: Mathematicians prove Pólya's conjecture for the eigenvalues of a disk
#50The 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, unexpecte…
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...
Matrix Analysis by Horn and Johnson is another great book, though it is a bit pricier than a Dover book.