A matrix that depends on its own eigenvalue

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^{\lambda t}x$, 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.

Three counts that stop being true #

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.

The count itself is structural, and it is worth seeing that it does not care what the physics does.

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.

What the physics does change is which of the sixteen are real, and that is a separate count.

Across β = 0, 0.05, 0.3, 1 the eigenvalue count is 16, 16, 16, 16 and the complex count is 16, 16, 16, 12, with the closed form agreeing to between 1.7·10⁻¹⁵ and 9.2·10⁻¹⁵ throughout. The first sequence is a theorem about the degree of a determinant and cannot move; the second is a fact about one damped chain and moves as soon as the damping is enough to overdamp four of its modes. A count that follows from the algebra and a count that follows from the coefficients are different kinds of number, and only the first is safe to build a method on — which is the distinction the rest of this section is about.

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.

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. What a mass that is small rather than absent does to them is the subject of the next section, and it is not what it looks like.

The family with an answer written down #

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.

A small mass, which is worse than a disagreement #

The natural expectation is that the two counts part company somewhere: as a mass shrinks the rank decision must eventually call it zero while the exact degree still says otherwise, and the crossing is where a model with a light node gets an ambiguous answer. Measuring it says something else twice over.

With exact input they barely part at all. Make one node light by an integer ratio — M = diag(N, N, 1, N, N, N), every entry still an integer, so the exact route still applies. The exact degree is 12 at a ratio of 1, at 10⁻⁴, at 10⁻⁸, at 10⁻¹², at 10⁻¹⁴ and at 10⁻¹⁷, because M is nonsingular for any nonzero mass and no theorem cares how small it is. The rank route agrees at every one of those down to 10⁻¹⁴ and disagrees from 10⁻¹⁵. The crossing is at machine precision, not at any mass ratio a structure would contain — a node a hundred million times lighter than its neighbours still gets the same count from both routes.

And with measured input there is no second route. The exact degree is computed by interpolating det Q at integer nodes in exact rationals, which requires the entries to be integers, and it says so: handed a mass of 0.01 it refuses, by its own assertion, before computing anything.

So on the case every model built from measurements is actually in, the two routes do not disagree. One of them is not available, and the other returns a number with nothing to check it against.

Which is the worse outcome, and why it is easy to miss #

That is a sharper finding than a disagreement and it is worse news, because of what this collection’s method rests on.

A disagreement between two routes is a diagnosis: it says a decision is being made, points at the tolerance making it, and can be printed. Two routes agreeing is evidence. What a measured model gets here is neither — it gets the silent absence of the second route, and an absence is the shape of defect this fleet keeps being caught by, because every check that runs, runs correctly.

It is worth being precise about what is and is not lost. The rank decision is not wrong on a measured model; it is a decision on a spectrum with a real gap in it, and on a structure whose light node is a thousand times lighter it is a comfortable decision. What is lost is the thing that made this essay’s version of it trustworthy — a route that shares no arithmetic and rounds nowhere — and what replaces it is the same route with a threshold in it, which is exactly the situation the rank essay describes and this one had escaped.

The escape was never from the decision. It was from the inputs: an integer model has an exact answer because integers are exact, and a measured one does not because measurements are not. That generalises past the quadratic problem to every exact-arithmetic result on this site, and it is worth stating once here because this is the field where the temptation is strongest — an exact degree is a much more satisfying object than a rank decision, and it is available on precisely the models nobody measured.

There is no algorithm for the polynomial #

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.

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.

What a linearisation is not allowed to be #

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.