Method
Linear systems and the matrix exponential
Adapted
Gives the solution of the first-order linear system x' = A(t)x in terms of a fundamental matrix, shows that for constant A the fundamental matrix is exp(tA) and the unique solution of the initial-value problem is exp(tA)x_0, and turns this into a recipe that reads the solution off the eigenvalues and eigenvectors of A, including the two real solutions carried by each complex conjugate pair.
Prerequisites: Functions of matrices and the matrix exponential, Structure of linear equations and the Wronskian, Eigenvalues and eigenvectors, Jordan normal form, Existence and uniqueness of solutions, Determinants, Linear systems and rank, Generalized eigenproblems and normal modes
Fix an interval together with an matrix whose entries are continuous complex-valued functions of . The homogeneous linear system is
where a solution is a differentiable function satisfying this identity at every ; derivatives and integrals of vector- and matrix-valued functions are taken entry by entry. When does not depend on the system is said to have constant coefficients, and we write it .
An matrix-valued function on whose columns are linearly independent solutions of the system is called a fundamental matrix of it. Equivalently — reading the defining equation column by column — satisfies the matrix differential equation
and its columns are linearly independent as functions on . If moreover for a chosen , we call the principal fundamental matrix at . (Throughout the unit denotes the identity matrix, the letter without a subscript being reserved for the interval.) The two-variable matrix
built from any fundamental matrix is called the propagator (or state-transition matrix) of the system: the statements below show that it does not depend on which was used, and that it carries the state at time to the state at time .
Let and have entries continuous on an interval containing . For every the initial-value problem
has one and only one solution on the whole of ((Coddington (1989), Ch. 6, §7, Theorem 6, p. 256)). Three consequences, for the homogeneous system :
- The solution space. The set of solutions of on is a vector space of dimension exactly over , and for each fixed the evaluation map is a linear isomorphism of it onto .
- Fundamental matrices are nonsingular everywhere or nowhere. If solves on , then either for every , in which case is a fundamental matrix, or for every . In particular it is enough to test one point.
- The general solution and the propagator. If is a fundamental matrix then every solution is for exactly one constant vector , the solution with being . Consequently the propagator is the same for every fundamental matrix , and is again a fundamental matrix for every nonsingular constant matrix ((Dummit & Foote (2004), §12.3, Exercise 54, p. 506)).
The interval is not shrunk anywhere: linear systems have non-local existence, and the solution lives as long as the coefficients are continuous. Coddington reaches it by observing that the successive-approximation proof of his local existence theorem, which is stated for an interval , goes through unchanged on an arbitrary interval containing ((Coddington (1989), Ch. 6, §7, p. 256)); may even be infinitely long.
Everything here is the single sentence "the solution is determined by its value at one instant", which is what existence and uniqueness say, read in three directions. Read as a statement about a linear map it says that evaluation at is injective (uniqueness) and surjective (existence) from the solution space onto , which forces the dimension to be . Read as a statement about a matrix of solutions it says that a nontrivial linear relation between the columns at one instant propagates to every instant, because the solution that the relation builds vanishes at that instant and therefore vanishes identically. Read as a formula it says that the only freedom in a solution is the constant vector of coefficients, and matching to fixes .
We take the existence-and-uniqueness theorem as given and derive parts 1-3 from it.
-
The solution space. The set of solutions on is a complex vector space: if and solve the system and , then , because differentiation is linear and acts linearly. Fix and let be , which is linear. is surjective: given , the theorem applied with , produces a solution on all of with that value. is injective: if and , then and the zero function are both solutions of the initial-value problem with data — the zero function solves it because — so uniqueness gives . A linear isomorphism onto forces .
-
Nonsingular everywhere or nowhere. Suppose for some . Then the columns of are linearly dependent, so there is with . The function is a solution of , since — here being constant is what lets it pass through the derivative — and . By the injectivity just proved, , that is for every with the same . Hence for every . Contrapositively, if is nonzero at one point it is nonzero at all of them; and then at each the columns of are independent vectors, so the columns of are independent as functions and is a fundamental matrix. (Conversely, if the columns are independent as functions, they cannot be dependent at any single point, by the argument just given, so the determinant never vanishes. The two descriptions of a fundamental matrix in the definition therefore agree.)
-
The general solution. Let be a fundamental matrix and any solution. Put for some fixed , legitimate by part 2. Then and are solutions agreeing at , so they agree on by injectivity again; and is unique because with invertible gives . Choosing and gives the stated formula. If is another fundamental matrix, each of its columns is for some , so with the constant matrix of columns , and is invertible; therefore
so the propagator is independent of the choice. Running this backwards, for any nonsingular constant the matrix satisfies and has determinant , so it is a fundamental matrix.
Let be a constant complex matrix. Then is a fundamental matrix of on all of ; it is the principal one at . The unique solution of
is ((Hirsch, Smale & Devaney (2013), §6.4, Theorem, p. 129)), and the propagator depends only on the elapsed time:
Three readings of the same fact are worth separating. (i) Algebraically, is invertible with inverse , so the state can be propagated backwards as well as forwards. (ii) Dynamically, : the system is autonomous, and only elapsed time matters. (iii) Structurally, , so is a one-parameter group of matrices whose generator is ; this is the finite-dimensional case of the semigroup picture of evolution equations.
All of it comes from the one differentiation rule established in the unit on the matrix exponential: that rule is literally the statement for , and is nonsingular, so the previous statement does the rest with no new work. The time-translation form of the propagator then follows from the product rule for exponentials of commuting matrices, since and always commute.
-
is a fundamental matrix. By the properties of the exponential (matrix exponential) the matrix-valued function is differentiable with , so each of its columns solves . At the series collapses to its first term, , which is nonsingular, so by part 2 of the previous statement is a fundamental matrix, and by construction it is principal at .
-
The initial-value problem. By part 3 of the previous statement with , the unique solution with is . This is the theorem of (Hirsch, Smale & Devaney (2013), §6.4, p. 129), whose own proof is self-contained: it differentiates to verify that it is a solution, and for uniqueness sets for a second solution and computes , so that is the constant . That route needs only the differentiation rule and the invertibility of the exponential, not the dimension count of the previous statement.
-
The propagator. The matrices and commute, so the product rule for exponentials of commuting matrices gives
using also . Replacing by changes neither nor therefore ; and the same identity with replaced by reads .
Let be a constant matrix.
- Eigensolutions. If with , then solves . Conversely every solution of the form with arises this way.
- Diagonalizable . If has eigenvectors forming a basis of , with , then
is the general solution, and where is the matrix with columns . This covers in particular the case of distinct eigenvalues, in which Hirsch, Smale and Devaney obtain exactly this formula by diagonalizing and solving the decoupled system ((Hirsch, Smale & Devaney (2013), §6.1, p. 108)). 3. Real form for a complex pair. Let be real, let with be an eigenvalue and (with ) a corresponding eigenvector. Then
are real solutions of , they are linearly independent over — and hence, both being real-valued, over as well — and their complex span is the same as the complex span of the two complex eigensolutions belonging to and . They are the real and imaginary parts of , and this is the device by which real solutions are extracted from a complex one in (Hirsch, Smale & Devaney (2013), §3.2, pp. 44-47). 4. Defective . If is not diagonalizable, parts 1-3 do not supply enough solutions, and the missing ones are obtained from by the splitting with diagonalizable, nilpotent and (matrix exponential). Every entry of is then a sum of terms over the eigenvalues , the degree of the polynomial attached to being at most one less than the size of the largest Jordan block for .
Hirsch, Smale and Devaney state part 2 together with part 3 in a single theorem for the case of distinct eigenvalues, of them real and conjugate pairs: the change of coordinates built from the eigenvectors (and from the real and imaginary parts of the complex ones) puts into a block form with the real eigenvalues on the diagonal and blocks , and the general solution is applied to the explicit column of exponentials, sines and cosines displayed there ((Hirsch, Smale & Devaney (2013), §6.1, Theorem, p. 111)). The version above separates the two hypotheses, because a diagonalizable matrix with repeated eigenvalues — a real symmetric matrix, for instance — is covered by part 2 but not by a theorem that assumes the eigenvalues distinct.
A single eigendirection reduces the system to one scalar equation, because along the matrix only multiplies by ; so the whole of parts 1 and 2 is the scalar fact , applied once per eigendirection and reassembled. Part 3 is bookkeeping with conjugation: a real matrix maps real vectors to real vectors, so it commutes with taking real and imaginary parts, and therefore the real and imaginary parts of any complex solution are separately solutions. The two real solutions so obtained are not new information — they span the same thing as the conjugate pair of complex eigensolutions — but they are the form in which an answer to a real physical problem has to be delivered.
-
Eigensolutions. If , then has , using the linearity of to move the scalar across it. Conversely if with solves the system, then differentiating and cancelling the nonzero scalar gives , so is an eigenvalue with eigenvector .
-
Diagonalizable . Each is a solution by part 1, so by linearity every is one. These exhaust the solutions by a dimension count: let be the matrix with columns . Then , which is nonsingular because the form a basis, so is a fundamental matrix by part 2 of the existence statement, and by part 3 of it every solution is — which is the displayed sum. Setting gives , hence .
-
Real form for a complex pair. Expanding with Euler's formula and ,
with exactly as displayed, and both are real because , , and are. Write , a solution by part 1. Since has real entries, for every — this is where the hypothesis that is real is used, and it is the only place — so taking complex conjugates in gives : the conjugate is a solution too. Hence so are the combinations
and these are the real and imaginary parts. The same two formulas, read backwards as and , show that the complex span of equals that of ; and is the eigensolution for , since conjugating gives .
For linear independence over , suppose on an interval with real. At this reads . Differentiating and evaluating at , using and , gives ; subtracting times the first relation leaves , and gives . Combining,
Now and cannot both be zero, since ; so and hence .
Independence over follows from the real case because both functions take values in : if with , splitting that relation into its real and imaginary parts gives the two real relations and , whose coefficients all vanish by the paragraph above; hence . This is what makes the comparison of complex spans in the previous paragraph a comparison of two-dimensional spaces.
- Defective . This is the content of the method for computing in the matrix exponential, combined with the statement above that is a fundamental matrix; nothing further is proved here.
- Continuity of on the whole interval is what makes existence non-local. For the scalar system on the solution through is , which blows up as : the interval on which the coefficient is continuous is exactly the interval of existence, and no larger one is claimed.
- Linearity is what rules out blow-up inside and what makes the solution set a vector space. The nonlinear scalar equation with has solution although its right-hand side is continuous everywhere; so the non-local conclusion of the existence-and-uniqueness theorem — that the solution lives on the whole interval on which the coefficients are continuous — is not a consequence of continuity alone, and linearity in is what buys it.
- real is used only in part 3 of the spectral statement, to conjugate the equation. For complex an eigenvalue need not come with its conjugate, and there is no real form to extract.
- in part 3 is needed for the independence of and : at they become and , which are dependent whenever and are parallel — as they may be for a real eigenvalue, where can be scaled to be real and .
- A basis of eigenvectors is what part 2 needs, not distinct eigenvalues. Conversely, distinctness is sufficient but is also strictly stronger: has a repeated eigenvalue and is diagonalizable, while has a repeated eigenvalue and is not, and for it carries a solution that is not of the form at all. That is why part 4 cannot be dispensed with.
- nonsingular at one point is all that part 2 of the existence statement requires, and the conclusion genuinely uses that solves the differential equation: an arbitrary matrix-valued function can of course be singular at some points and not others. For this is the familiar fact that a nontrivial solution of a linear scalar equation has no zeros.
- Compute the characteristic polynomial and its roots. ; its roots are the eigenvalues, with algebraic multiplicities (eigenvalues and eigenvectors). For matrices use .
- For each eigenvalue , solve and record the dimension of the kernel (the geometric multiplicity). If the geometric multiplicities add up to , is diagonalizable and steps 3-4 finish the job; otherwise go to step 5.
- Real eigenvalue : each basis vector of its eigenspace contributes the solution .
- Complex pair , , with real: take an eigenvector for only — the conjugate eigenvalue contributes nothing new — and write down the two real solutions
Do not also use : that would double-count. 5. Defective eigenvalue: either compute by the splitting of the matrix exponential and take its columns, or build a chain of generalized eigenvectors with and , which contributes the solutions
— that is, , then , then , and so on. 6. Assemble the fundamental matrix from the solutions as columns, and check at the single convenient point . 7. Fit the initial condition by solving the linear system (linear systems); the answer is . Equivalently , and if the exponential itself is wanted. 8. Two cheap checks. must equal , and must equal ; and , so (determinants).
Reading the answer without computing it. The real parts of the eigenvalues decide the fate of every solution: for all means every solution decays to ; one eigenvalue with means almost every solution grows; contributes oscillation at angular frequency , that is period . Eigenvalues of very different magnitude make the system stiff and its numerical solution delicate (stiffness); the planar case is classified completely in the classification of planar linear systems.
A scalar equation of order ,
becomes a first-order system in the vector of derivatives: setting , the first components of restate the definitions , and the last restates the equation. Coddington uses exactly this substitution to transfer existence and uniqueness from systems to -th order equations ((Coddington (1989), Ch. 6, §8, Theorems 7 and 8, pp. 259-260)); Dummit and Foote note that the resulting coefficient matrix is the transpose of the companion matrix of the characteristic polynomial, and that the first row of a fundamental matrix of the system is a basis of solutions of the scalar equation ((Dummit & Foote (2004), §12.3, Exercise 57 and the preceding discussion, p. 507)).
Two consequences are worth keeping. The characteristic polynomial of the companion matrix is the characteristic polynomial of the scalar equation, so "eigenvalues of " and "roots of the indicial polynomial" of the constant-coefficient equation are the same list, and a root of multiplicity gives a single Jordan block of size . (That last point is ours, not the sources': for the matrix above, deleting the first column and the last row of leaves a triangular matrix with 's on the diagonal, so and every eigenspace is one-dimensional — a companion matrix is maximally defective, and step 5 of the method is unavoidable for a scalar equation with a repeated root.) And the Wronskian of the theory of linear equations is the determinant of the corresponding fundamental matrix, which is why the two nonvanishing criteria match. In the other direction, a system can always be reduced to a single scalar equation of order by elimination, but the matrix route is the one that generalizes and the one that numerical software uses.
Take the real system with
Written out, this is a damped oscillator driven by a variable that decays on its own: with .
1. Eigenvalues (step 1). The last row of has only the entry on the diagonal, so expanding along its last row gives
using with for the block. The eigenvalues are and : three distinct values, so is diagonalizable and step 5 is not needed. All three have real part , so every solution decays like , with oscillation of period .
2. The real eigenvalue (steps 2-3). Solve :
the first equation giving and the second then giving . Taking ,
3. The complex pair (step 4). Take and solve . The third row reads with , so ; the first row then reads , so . (The second row is then automatically satisfied, as it must be, since is an eigenvalue.) With ,
so , and step 4 gives the two real solutions
4. Fundamental matrix and the initial condition (steps 6-7). Collecting the three solutions as columns,
Expanding along its last row gives , so is a fundamental matrix. Solving : the third equation gives , so ; the first gives , so ; the second gives , so . Hence
5. Checks (step 8). At the bracket is , as required. The middle component must be the derivative of the first, since in this system:
which it is. And the second equation of the system — row 2 of — namely , holds: differentiating gives , while
the same thing. Finally , and indeed , because each of the three columns carries one factor and the remaining determinant is the constant (its entries involve and , but expanding along the last row leaves by ).
6. A number. At we have and , so
The displacement and the velocity happen to coincide a quarter of the way into the first oscillation.
7. The exponential, if it is wanted. , and , as one checks by multiplying out. Note that the solution above was obtained without ever forming this product: eigenvectors answer the initial-value problem directly, and the exponential is needed only when the propagator itself is the object of interest — as it is in the forced problem of nonhomogeneous systems.
- Small oscillations of a mechanical or electrical network. A conservative system linearized about equilibrium obeys with positive definite and symmetric; written as a first-order system in it is with . Its eigenvalues satisfy , where runs over the eigenvalues of (all real, since is self-adjoint for the inner product ). At a stable equilibrium is positive definite as well as symmetric; then every , each is a conjugate pair on the imaginary axis, and step 4 of the method produces exactly the normal modes of normal modes, one mode per pair, oscillating at its own frequency . The two degenerate possibilities a merely symmetric allows are worth naming: gives a double eigenvalue with a defective block, hence a solution drifting linearly in (a zero mode, such as a rigid translation), and gives the real pair , an unstable direction growing exponentially rather than a mode. Adding linear damping moves an imaginary pair off the axis to the left, and its real part is the decay rate of that mode.
- Stability of a steady state of a nonlinear system. Near an equilibrium of the deviation obeys to first order. The eigenvalues of the Jacobian therefore decide local stability, by the reading given at the end of the method, and this is the content of linearization: a sink when all real parts are negative, a saddle when they have both signs, oscillatory approach when there are complex pairs. The borderline cases — a purely imaginary pair, a zero eigenvalue — are precisely the ones the linear system cannot settle, and are where bifurcations occur.
- Relaxation in coupled compartments. First-order chemical kinetics, radioactive decay chains, heat exchange between lumped bodies and linear pharmacokinetic models all have the form with a matrix of rate constants whose columns sum to zero when the total amount is conserved. That column sum makes a left null vector, so is an eigenvalue and the corresponding eigenvector is the equilibrium distribution; the remaining eigenvalues, necessarily with negative real parts for a stable network, are the relaxation rates measured in a kinetics experiment. The same matrix structure, transposed, is the generator of a continuous-time Markov chain: with , which has zero row sums, is the matrix of transition probabilities over time .
- Why software solves systems, not high-order equations. Every numerical integrator in use — Runge-Kutta, multistep, implicit — is written for first-order systems, so the reduction of the remark above is the first thing done to an -th order equation before it is handed to an ODE integrator. The eigenvalues of also set the step size an explicit method can take: the product of the step with the largest must stay inside the method's stability region, which is why a system with widely separated eigenvalues is expensive to integrate explicitly.