Combining Two Representations of Matrices for a Formalization of the Perron-Frobenius Theorem

Add to your list(s) Download to your calendar using vCal

• René Thiemann (University of Innsbruck)
• Thursday 27 November 2025, 17:00-18:00
• MR14 Centre for Mathematical Sciences.

If you have a question about this talk, please contact Angeliki Koutsoukou-Argyraki.

Matrix interpretations are useful for automated complexity analysis of term rewrite systems. For checking the correct application of these interpretations in automatically generated proofs, one needs a verified algorithm to determine the asymptotic growth rate of A^n for a given non-negative real matrix A.

Since the direct approach to compute the growth rate of A via algebraic numbers is quite slow, in our certifier CeTA we utilize a simple algorithm that does not require algebraic numbers. Despite the simplicity of the algorithm, its verification in Isabelle/HOL is technically interesting. For proving soundness of the algorithm, we need to formalize the Perron-Frobenius theorem. And to achieve the latter task, we establish a connection between two different Isabelle/HOL libraries on matrices, that facilitates an easy exchange of theorems between both libraries.

=== Hybrid talk ===

Join Zoom Meeting https://cam-ac-uk.zoom.us/j/89856091954?pwd=Bba77QB2KuTideTlH6PjAmbXLO8HbY.1

Meeting ID: 898 5609 1954 Passcode: ITPtalk

This talk is part of the Formalisation of mathematics with interactive theorem provers series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge talks
• DPMMS Lists
• DPMMS Pure Maths study groups
• DPMMS info aggregator
• DPMMS lists
• Department of Computer Science and Technology talks and seminars
• Formalisation of mathematics with interactive theorem provers
• Hanchen DaDaDash
• Interested Talks
• MR14 Centre for Mathematical Sciences
• Martin's interesting talks
• School of Physical Sciences
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31
• yk449

Note that ex-directory lists are not shown.