Numerical Linear Algebra
where the algebra stops being the arithmetic
Concept

Characteristic polynomial — where it appears

The determinant of xI - A, whose roots are the eigenvalues. Computed in exact arithmetic on an integer matrix it is a vector of integers, which makes a claim that two matrices are cospectral checkable rather than merely observed.

Named by 2 essays across 2 fields — each of them below, with the objects they name alongside it.

57911131517192110⁻¹⁷10⁻¹⁴10⁻¹¹10⁻⁸10⁻⁵10⁻²degreerelative error of the worst rootmeasuredκ × ua polynomial is its coefficientsworst root, measured0.0076predicted, κ × u0.0023root condition number10¹³largest coefficient1.4·10¹⁹the roots are integersand the coefficients are not the roots

The roots are not the coefficients

A polynomial whose roots are the integers one to twenty, expanded exactly, handed to the routine every library uses. The computed roots are wrong in the third digit, the computation is backward stable for the matrix it factorised, and above degree eighteen the coefficients are not double-precision numbers at all.

error · conditioning a triangle and a square, joinedK₂,₃ with a pendant edge1234560123456indexeigenvaluethe same, and not the samevertices each6edges each7spanning trees12spectra differ by5.3·10⁻¹⁵highest degree, left4highest degree, right3one has a trianglethe other is bipartite

The spectrum is not the graph

Two graphs on six vertices with the same Laplacian characteristic polynomial — as integer polynomials, not to fourteen digits. One contains a triangle; the other is bipartite. Every method in this field that reads only the spectrum is answering about the class.

graph · graph invariant

Named alongside it

The objects these essays reach for when they reach for this one.

Exact ground truthBackward errorBipartiteChebyshev basisCompanion formCondition numberCospectral graphsGraph invariantGraph laplacianMatrix polynomialNormalised laplacianRepresentable numbers

All concepts