Résumé : Jacobi's bound is a sharp bound on the order of quasi-regular solutions of a differential system, always conjectural in the general case. It is expressed as the tropical determinant of the order matrix of the system. This result appears in posthumous manuscripts of Jacobi, which seem to come from a large abandoned project, Phoronomia. These texts reduce complexity problems related to the computation of normal forms to combinatorial problems, solved by original methods that make Jacobi a precursor of graph theory and shortest path problems.
Knowing the matrix $(a_{i,j})$ which expresses the productivity of worker $i$ assigned to task $j$, the tropical determinant $\sum_{\sigma\in S_{n}}\sum_{i=1}^{n}a_{i,\sigma(i)}$ is the maximum total productivity. Since the polynomial time method given by Jacobi was forgotten, it took ten years to discover an equivalent solution: the Hungarian method of Kuhn (1955), which uses earlier results of Kőnig and Egerváry. We will show the connection between Jacobi's algorithm, based on the notion of canon, and Kuhn's method, based on minimal covers. Hopcroft and Karp's algorithm for the marriage problem will also be described in the context of canons.
It will be shown how shortest path problems related to the canon computation allow to bound the orders of derivation needed to go from one normal form to another, as well as generalizations to underdetermined systems. This allows to easily characterize a subclass of flat systems, systems whose control is particularly easy. Among these is a simplified model of an aircraft.

 [Slides.pdf] [article] [article] [vidéo]

Dernière modification : Thursday 21 November 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr