A glimpse of the algebraic theory of linear systems

I’ve been in Berkeley for the last two weeks, having lots of mathematical fun at Topos in the context of a workshop on Poly.

I focused on its links with categorical systems theory, chatting with lots of people about it. With Sophie Libkind and Toby Smithe we found a bridge between the theory of dynamic operads of David Spivak and Brandon Shapiro, the animated categories of Toby, and the cybernetic systems theories of mine. I also managed to make Sophie not scared but actually delighted by categorical systems theory, the way it handles behaviour, and the beauty of it all. Yu-uh!


But here I’d like to report about some of the amazing things I’ve learned from Mohamed Barakat. He’s a computational algebraist, i.e. someone who makes computers do algebra for us (yay!), who’s recently been applying the methods of his discipline to the theory of linear systems. It turns out Kalman’s dream of reducing linear systems theory to homological algebra is alive and well, and it’s now broadly developed in algebraic systems theory.

In algebraic systems theory, one starts from an algebra of operators D. These can be differential operators (partial or not!), difference operators, time-shift operators and more (this theory is very general!). One then uses operators from D to write down the equations of a system. For instance we might take D to be the Weyl algebra of differential operators on \R^3 and write equations

\begin{cases} 3\partial_t x - u = 0\\ (\partial_t)^2 x = \partial_x^2 x\\ y = x\\ z = u\\ \end{cases}

This is a linear system of 2 equations in the 4 variables x,y,z,u with coefficients in D, which in this (and most) case(s) is a kind of polynomial algebra. Notice that the variables are all treated equally, but display some attitude: x looks a like a state variable, u like a control one, and y,z like observables.

We now hit this with lots of interesting homological algebra, i.e. linear algebra on steroids. The starting point is to present our equations as a matrix multiplication:

\begin{pmatrix} 3\partial_t & 0 & 0 & -1\\ \partial_t^2 - \partial_x^2 & 0 & 0 & 0\\ -1 & 1 &0 & 0\\ 0 &0 & 1 & -1 \end{pmatrix} \begin{pmatrix} x\\y\\z\\u \end{pmatrix} = 0

Denote by E for the big matrix of operators. We can see it as a morphism of D-modules E : D^4 \to D^4, whose cokernel represents the equations themselves as a further D-module:

D^4 \xrightarrow{E} D^2 \twoheadrightarrow \operatorname{coker} E

In this way, morphisms from \operatorname{coker} E to any other D-module M, such as {\cal C}^\infty(\R^n) corresponds to solutions of E in M.

In fact now one can ‘kick the ladder’ and think of any finitely-presented D-module S as a linear system. Now we can formulate properties of the system S as homological properties of the module S translate to properties of the system described by S.

As an example, Mohamed showed me the following application, which I hope I’m not going to butcher. One can compute a spectral sequence related to the derived functor \operatorname{Hom}(\operatorname{Hom}(-, D), D) (take the double dual of a resolution of S) and find a presentation of S as a matrix algebra (he called it an equidimensional decomposition):

\begin{pmatrix} S_0 & \ast & \ast & \ast & \ast\\ 0 & S_1 & \ast & \ast & \ast\\ \vdots & &\ddots && \vdots\\ 0 && \cdots && S_n \end{pmatrix}

where each block S_i represents the ‘autonomy of degree i’ of S, where the latter roughly means individuation a subsystem of S which is governed by i-many ‘conservation laws’ which prevent control. Algebraically, these are degrees of torsion, since a conservation law is nothing but an operator d \in D such that ds=0 for some element s \in S.
S_0 is the part that doesn’t respect any conservation law, but still might not be controllable: there might be other kinds of constraints, or simply couplings, expressed by equations such as ds + d's' = 0, which even though don’t give rise to an autonomous subsystem of S, constrain its controllability. One can in fact compute a further decomposition of S_0 into more and more controllable parts.
A dual theory concerns observability instead, and allows one to decompose S into various degree of observability!

Moreover, Mohamed didn’t just tell me about this. He is a computational algebraist after all, so he has the means to actually compute the above homological construction, and indeed he showed me a live demo on Maple on how to solve exactly a complicated PDE in mere seconds by purely homological methods. I’m still astounded!

If you are as avid of reading more as me, Mohamed suggested to consult his webpage (linked above). Also, this paper of his student Sebastian Posur paints a better picture than I did above of this wonderful theory.

Meeting Mohamed what such a great pleasure. He blew my mind with incredible math, and he refreshed me with an uncommon balanced attitude for someone working at the interface of theory and applications, never disowning either side. And he taught me why spectral sequences work!

I look forward working with him in the future, perhaps extending the algebraic theory of linear systems with compositionality results.


I think that there’s going to be a lot of interesting algebraic geometry in systems theory very soon… See my earlier post Symbolic presentations of dynamical systems.

1 Like