Echelon Form

Jose Divasón 🌐 and Jesús Aransay 🌐

February 12, 2015

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

Abstract

We formalize an algorithm to compute the Echelon Form of a matrix. We have proved its existence over Bézout domains and made it executable over Euclidean domains, such as the integer ring and the univariate polynomials over a field. This allows us to compute determinants, inverses and characteristic polynomials of matrices. The work is based on the HOL-Multivariate Analysis library, and on both the Gauss-Jordan and Cayley-Hamilton AFP entries. As a by-product, some algebraic structures have been implemented (principal ideal domains, Bézout domains...). The algorithm has been refined to immutable arrays and code can be generated to functional languages as well.

License

BSD License

Topics

Session Echelon_Form