
Matrices,
Jordan
Normal
Forms,
and
Spectral
Radius
Theory
Title: 
Matrices, Jordan Normal Forms, and Spectral Radius Theory 
Authors:

RenĂ© Thiemann (rene /dot/ thiemann /at/ uibk /dot/ ac /dot/ at) and
Akihisa Yamada (akihisa /dot/ yamada /at/ uibk /dot/ ac /dot/ at)

Submission date: 
20150821 
Abstract: 
Matrix interpretations are useful as measure functions in termination proving. In order to use these interpretations also for complexity analysis, the growth rate of matrix powers has to examined. Here, we formalized a central result of spectral radius theory, namely that the growth rate is polynomially bounded if and only if the spectral radius of a matrix is at most one.
To formally prove this result we first studied the growth rates of matrices in Jordan normal form, and partially prove the result that every complex matrix has a Jordan normal form: we are restricted to uppertriangular matrices since we did not yet formalize the Schur decomposition.
The whole development is based on a new abstract type for matrices, which is also executable by a suitable setup of the code generator. It completely subsumes our former AFPentry on executable matrices, and its main advantage is its close connection to the HMArepresentation which allowed us to easily adapt existing proofs on determinants.
All the results have been applied to improve CeTA, our certifier to validate termination and complexity proof certificates.

Change history: 
[20160107]: Added Schurdecomposition, GramSchmidt orthogonalization, uniqueness of Jordan normal forms 
BibTeX: 
@article{Jordan_Normal_FormAFP,
author = {RenĂ© Thiemann and Akihisa Yamada},
title = {Matrices, Jordan Normal Forms, and Spectral Radius Theory},
journal = {Archive of Formal Proofs},
month = aug,
year = 2015,
note = {\url{http://isaafp.org/entries/Jordan_Normal_Form.shtml},
Formal proof development},
ISSN = {2150914x},
}

License: 
BSD License 
Depends on: 
AbstractRewriting, Containers, Gauss_Jordan, Matrix, Polynomial_Factorization, Polynomial_Interpolation, Show, VectorSpace 
Used by: 
Algebraic_Numbers, Berlekamp_Zassenhaus, Deep_Learning, Perron_Frobenius 
