Gauss-Jordan Elimination for Matrices Represented as Functions.
Tobias Nipkow · 2011
This theory provides a compact formulation of Gauss-Jordan elimination for matrices represented as functions. Its distinctive feature is succinctness. It is not meant for large computations. 1 Gauss-Jordan elimination algorithm theory Gauss-Jordan-Elim-Fun imports Main begin Matrices are functions: type-synonym ′a matrix = nat ⇒ nat ⇒ ′a In order to restrict to finite matrices, a matrix is usually combined with one or two natural numbers indicating the maximal row and column of the matrix. Gauss-Jordan elimination is parameterized with a natural number n. It indicates that the matrix A has n rows and columns. In fact, A is the augmented matrix with n+1 columns. Column n is the “right-hand side”, i.e. the constant vector b. The result is the unit matrix augmented with the solution in column n; see the correctness theorem below. fun gauss-jordan :: ( ′a::field)matrix ⇒ nat ⇒ ( ′a)matrix option where gauss-jordan A 0 = Some(A) | gauss-jordan A (Suc m) = (case dropWhile (λi . A i m = 0 ) [0 ..<Suc m] of [] ⇒ None | p # ⇒ (let Ap ′ = (λj . A p j / A p m); A ′ = (λi . if i=p then Ap ′ else (λj . A i j − A i m ∗ Ap ′ j )) in gauss-jordan (Fun.swap p m A ′) m)) Some auxiliary functions: definition solution :: ( ′a::field)matrix ⇒ nat ⇒ (nat ⇒ ′a) ⇒ bool where