A damped structure does not produce Ax = λx. It produces (λ²M + λC + K)x = 0, where the matrix whose null vector is wanted is a function of the number being solved for — so there is nothing to factorise, an n × n problem has 2n answers, and the eigenvectors cannot be a basis.
Every eigenvalue problem this collection has met so far is a question about a matrix that is
sitting still. Ax = λx gives one matrix
and asks which directions it does not turn. Ax = λBx
gives two and asks the same question about their pencil. In both cases the data is fixed
before the question is asked, and everything that follows — a Hessenberg reduction, a shift, a
Schur form — is arithmetic performed on numbers that do not move.
A damped structure does not produce either of them.
Write down a chain of masses joined by springs, add damping proportional to velocity, and the
equation of motion is Mü + Cu̇ + Ku = 0. Look for solutions that decay or oscillate at a single
rate, u(t) = e^λtx, and what comes back is
Q(λ)x = (λ²M + λC + K)x = 0.
The matrix whose null vector is wanted is a function of the number being solved for. There is
no matrix to factorise, because Q is not a matrix: it is a matrix-valued polynomial, and the
object with a spectrum is the polynomial rather than any one of its values.
Fig. 1 The eigenvalues of an eight-by-eight quadratic. There are sixteen of them, the crosses are a
closed form and the discs are what a real Schur factorisation of a sixteen-by-sixteen matrix
returns, and the two routes agree to 10⁻¹⁴ without sharing a line of code.
There are 2n eigenvalues. det Q(λ) is a determinant of a matrix whose entries are quadratics
in λ, so it is a polynomial of degree 2n when M is nonsingular. An eight-by-eight problem has
sixteen solutions. Nothing about that is subtle and everything downstream of it is: a matrix with
eight rows has produced sixteen eigenvalues, and there are only eight dimensions for their
eigenvectors to live in.
So the eigenvectors are not a basis. Nine vectors in eight dimensions are dependent, as a
matter of counting rather than of arithmetic. Measured at n = 6: take the seven eigenvectors
belonging to the seven smallest real eigenvalues, stack them into a 6 × 7 matrix, and its
smallest singular value is 10⁻¹⁵⁷ times the largest — dependent to the limit of what a double
can express. Every one of those seven is a perfectly good eigenvector: each satisfies its own
equation with a relative residual of 4.5·10⁻¹⁶. The pairs are right and the set is not a basis,
and the two facts are unrelated.
That is worth pausing on, because a great deal of what this site has said about eigenvalue
problems rests on the eigenvectors spanning something. The plane that survives what its vectors
do not is about an invariant subspace being
better conditioned than any vector in it; the gap decides the
eigenvector is about how far apart two eigenvalues have
to be for their directions to be separable. Neither statement has a quadratic analogue that can be
had by translation. What replaces them is a longer story and it is not this essay’s.
And the count is not 2n when M is singular. A degree of freedom with no inertia — a massless
node, a rigid link, an algebraic constraint in a model that otherwise has dynamics — makes M
singular, and det Q loses degree. The missing eigenvalues are at infinity, which is the object
an eigenvalue with no value is about, arriving here by a
different route and for a physical reason rather than a structural one.
Fig. 2 Where the missing eigenvalues went. The degree is computed exactly, in BigInt rationals, by
interpolating det Q at 2n + 1 nodes; the rank of M is a decision about a gap. Two routes to one
integer, and only the second of them is a judgement.
The count is measured twice and the difference between the routes is the whole of why it is drawn.
det Q is interpolated exactly, in rationals, at 2n + 1 integer nodes, and its degree is read
off: at n = 6 with one mass removed the degree is 11 rather than 12, with three removed it is 9.
The other route asks how many singular values of M are zero, which is a rank decision, and
rank is a decision rather than a property. Here the two agree at
every setting, because the gap the decision rests on is between something exactly zero and
something of order one. A mass that is small rather than absent is where they part company, and
that is the case every model built from measurements is actually in.
Nothing above would be worth much if the “true” spectrum were itself a computation. So the family
every measurement in this field is made on is one whose eigenvalues are known in closed form.
Take M = I, K the tridiagonal model stiffness whose eigenvalues are 4sin²(jπ/2(n+1)) — the closed
form this site has used since the rate the condition number
predicts — and let the damping be
proportional: C = αM + βK. In the basis of K’s eigenvectors, all three coefficients are
diagonal at once, and the quadratic falls apart into n scalar quadratics
λ² + (α + βκⱼ)λ + κⱼ = 0.
Two roots each, 2n in total, available exactly, at every n and every α and β. That is the same
standing the Hilbert inverse has on this site, and it is worth
as much: proportional damping is a modelling convenience nobody believes physically, and it is the
assumption that makes the answer exactly available.
The important half is that the computation being checked never sees the decoupling. It forms a
2n × 2n matrix, inverts a coefficient, and runs the same real Schur factorisation
the form a real matrix can reach describes, on a
matrix with no visible structure at all. Two routes that share nothing but the three coefficients,
agreeing to 2.8·10⁻¹⁵ at n = 6 and 3.0·10⁻¹⁴ at n = 12.
Which brings up the sentence this whole field turns on: nothing anybody runs is an algorithm for
Q. There is no quadratic analogue of the QR algorithm, no sequence of similarity transformations
that drives a matrix polynomial towards triangular. What every library does instead is
linearise: build a 2n × 2n pencil with exactly the eigenvalues of Q and hand it to the
machinery that already exists.
The one every textbook writes is the first companion form,
C₁(λ) = λ [ M 0 ] + [ C K ]
[ 0 I ] [ −I 0 ],
whose eigenvector is [λx; x], so the quadratic’s eigenvector is the bottom half of the
linearisation’s. Check it by multiplying out: the first block row is λ²Mx + λCx + Kx, which is
zero exactly when λ is an eigenvalue of Q, and the second is λx − λx.
That is an identity, exact, with nothing approximated. Three of them are used here — the first
companion form, a second one that weights the coefficients differently, and a symmetric member of
the DL(Q) family that keeps M, C and K symmetric if they were. All three have exactly the
eigenvalues of Q, and all three reach the closed form to about 2·10⁻¹⁵ on a well-scaled problem.
Fig. 3 Six routes to one spectrum — three linearisations, each reduced to a standard eigenvalue problem
two ways — on a problem whose units are sensible. They differ by a factor of seventeen at the
fourteenth digit, which is noise. The essay two doors along puts the same six on a problem whose
units are not.
So a reader could be forgiven for concluding that the substitution is free. It is not, and the
measurement that says so is the next essay: a backward-stable answer to a problem nobody
asked puts one problem through
eight decades of a change of variable that is exact in both directions, and watches the
linearisation stay backward stable while the quadratic loses every digit it had.
What the picture shows, and what the slider does #
The hero draws the spectrum in the complex plane. Two things about it are worth reading slowly.
The eigenvalues come in conjugate pairs wherever they are complex, which is the same fact
the form a real matrix can reach is about: the
coefficients are real, so det Q has real coefficients, so its complex roots pair off. Each pair is
one oscillating mode of the physical chain — the imaginary part is how fast it oscillates and the
real part is how fast it dies away.
And the slider is the damping. At β = 0 the eigenvalues sit on an arc; raising β walks them
towards the real axis, and they arrive there two at a time, stiffest mode first. Each arrival
is a collision of two eigenvalues at one point, which is a double root, and a double root is a
place where the accuracy of a computed eigenvalue halves — a fact with a closed-form boundary and
a measurement, in every eigenvalue real, and a test that says so in
advance.
At the last stop of the slider every eigenvalue is real. That family — overdamped, and the
subject of its own essay — is where this field does most of its measuring, for a reason worth
stating plainly: an eigenvector belonging to a complex eigenvalue is complex, and everything the
libraries here hold is an array of doubles. The restriction is a real one and it is written down
rather than hidden.
Why the polynomial is the object and not the trick #
There is a tempting way to file all of this: the quadratic is a notation, the linearisation is
what it really is, and the field is a chapter about a change of variables.
That reading survives exactly as long as nobody measures anything. The three counts above are
already about Q rather than about any linearisation of it — 2n eigenvalues is a statement about
the degree of det Q, the dependence of the eigenvectors is a statement about n dimensions, and the
eigenvalues at infinity are a statement about M. And the conditioning is about Q too: the next
essay measures an eigenvalue’s condition number as an eigenvalue of the quadratic, finds it
sits at 4.98 and does not move under a substitution that raises the linearised matrix’s by eleven
orders of magnitude.
That is the shape of the whole field, and it is the site’s oldest distinction in a new place. The
problem has a difficulty of its own; the method adds one; and the two are separately measurable.
The exact answer to a nearby problem said it about
a linear solve, and everything from here says it about a polynomial.
One more piece of bookkeeping, because it is the thing that makes the field’s later measurements
comparable. A 2n × 2n pencil with the right eigenvalues is not automatically a linearisation of Q.
The definition asks for more: there must be unimodular matrices — polynomial matrices whose
determinants are nonzero constants — taking L(λ) to the block-diagonal form with Q in one corner
and an identity in the other. That is what guarantees the elementary divisors match, so a
repeated eigenvalue of Q is repeated in L the same number of times and in the same way.
It matters here for a practical reason rather than an algebraic one. If the correspondence were
only between the eigenvalue sets, then a linearisation could split a double eigenvalue into two
simple ones and a reader would have no way of knowing whether a pair of nearby computed numbers
was a genuine pair or an artefact. All three linearisations used here are linearisations in the
strict sense, which is why the collision the slider walks into stays a collision in every one of
them — measured, and drawn, in the essay on overdamping.
Why this is the tenth kind of matrix and not the first kind of notation #
Every field on this site so far has opened with a matrix that is difficult for a reason. A
Hilbert matrix is ill conditioned by construction; a kernel matrix is dense and compressible; a
Kronecker sum is enormous and described by almost nothing; the matrix a constraint
makes has a zero block that is a theorem. In each
case there is an object, it has entries, and something about those entries is the subject.
Here there is no object. Q(λ) is a rule for producing a matrix once the answer is known, and
the three coefficient matrices are the data. That changes what the standard questions even mean:
What is its condition number? Not the condition number of any Q(λ), which would be a
property of a value rather than of the problem. The right quantity measures the three
coefficients separately, and it is what the next essay measures.
What is its backward error? The smallest perturbation of (M, C, K) as three matrices
for which a computed pair is exact. A perturbation of the linearised matrix is not one of
these, and the gap between the two is the largest finding in this field.
What is its residual? ‖Q(λ)x‖, which needs a scale to be relative to, and the scale is
|λ|²‖M‖ + |λ|‖C‖ + ‖K‖ rather than ‖Q(λ)‖ — because ‖Q(λ)‖ can be small precisely where the
three coefficients cancel, which is exactly at an eigenvalue.
None of those three is a translation of a matrix quantity. Each is a new definition that reduces
to the familiar one when the polynomial has degree one, and each of them is the reason the field
takes essays rather than a footnote.
Fig. 4 No stiffness damping at all: every eigenvalue has the same real part, and the closed form and the
computation still agree to 10⁻¹⁴. Sorting two spectra of this shape is what taught the comparison
to match rather than sort.Fig. 5 And at the other end of the slider, where the last pair has arrived on the real axis.Fig. 6 Sixteen masses, thirty-two eigenvalues, and the arc drawn more densely rather than further.Fig. 7 Three masses removed, three eigenvalues at infinity, and a characteristic polynomial three degrees
short.Fig. 8 Four removed, on a chain of six, which is as far as the family goes before there is nothing left
to be dynamic.Fig. 9 What the substitution costs, from the next essay, over four decades instead of eight.Fig. 10 And the condition number that belongs to the polynomial rather than to the method.Fig. 11 The same six routes at a change of units of 10⁶, where the noise becomes a factor of forty.Fig. 12 The eigenvalue at infinity in the linear pencil that met it first, as a point of the projective
line rather than an overflow.Fig. 13 The real Schur form the linearisation is handed to, with one two-by-two block per conjugate pair.Fig. 14 The rank decision the second route to the count depends on.Fig. 15 Why a computed eigenvalue moves at all, from the spectra field.Fig. 16 Where the last pair of eigenvalues arrives on the real axis, located two ways.Fig. 17 And what the spectrum looks like once every one of them has arrived.Fig. 18 The collision itself, and the half of the digits it costs.Fig. 19 Conjugate pairs in the plane, from the essay that first drew them.Fig. 20 What a gap between two eigenvalues is worth to a method that computes values.Fig. 21 Two eigenvalues close enough that no direction belongs to either.Fig. 22 The model problem’s spectrum, which is the closed form this whole family is built out of.Fig. 23 And where the field ends: a problem whose spectrum is countably infinite.Fig. 24 A quadratic whose eigenvalues arrive in pairs of a different kind.Fig. 25 And the Krylov space a problem with no matrix still has.Fig. 26 A little damping: the arc has barely moved off the imaginary axis, and all sixteen eigenvalues are still complex.Fig. 27 Two masses removed, and a characteristic polynomial two degrees short of 2n.Fig. 28 The six routes at two decades of badly chosen units, where an ordering starts to be visible.Fig. 29 The stiffness matrix’s own eigenvalues, which are the closed form each scalar quadratic is built from.Fig. 30 Eigenvalues at infinity in a linear pencil, counted by a rank rather than by a degree.Fig. 31 The symmetric eigenvalue problem this one is a departure from.Fig. 32 And the iteration that solves the unsymmetric one, which the linearisation is handed to.Fig. 33 A conjugate pair close to the real axis, which is what the slider’s last stops produce.Fig. 34 What a perturbation does to a computed spectrum, in the field that measured it first.Fig. 35 A basis whose conditioning degrades with degree, which is the scalar case of this field’s subject.Fig. 36 And two lines of scaling, which is what the field’s third essay does about all of it.Fig. 37 The same closed-form spectrum at the size the drag stops use.Fig. 38 Twelve masses and twenty-four eigenvalues.