Abstract

In automated complexity analysis of term rewriting, estimating the growth rate of the values in the k-th power of a matrix A – for fixed A and increasing k – is of fundamental interest. This growth rate can be exactly characterized via A’s Jordan normal form (JNF). We formalize this result in our library IsaFoR and our certifier CeTA, and thereby improve the support for certifying polynomial bounds derived by (untrusted) complexity analysis tools. To this end, we develop a new library for matrices that allows us to conveniently work with block matrices. Besides the mentioned complexity result, we formalize Gram-Schmidt’s orthogonalization algorithm and the Schur decomposition in order to prove existence of JNFs. We also provide a uniqueness result for JNFs which allows us to compute Jordan blocks for individual eigenvalues. In order to determine eigenvalues automatically, we moreover formalize Yun’s square-free factorization algorithm.

BibTeX

@inproceedings{RTAY-CPP2016,
  author    = "Ren{\'e} Thiemann and Akihisa Yamada",
  title     = "Formalizing {J}ordan Normal Forms in {I}sabelle/{HOL}",
  booktitle = "Proceedings of the 5th {ACM} {SIGPLAN} Conference on Certified Programs
               and Proofs ({CPP} 2016)",
  pages     = "88--99",
  year      = 2016,
  doi       = "10.1145/2854065.2854073"
}