Browse Prior Art Database

Evaluation of an Integer Determinant

IP.com Disclosure Number: IPCOM000065640D
Original Publication Date: 1985-Apr-01
Included in the Prior Art Database: 2005-Feb-19

Publishing Venue

IBM

Related People

Authors:
Rutter, RS [+details]

Abstract

When operating on integer data, this method evaluates a deter- minant in polynomial time without using floating point arithmetic. It requires only integers and executes in 0 (n3) time. Each iteration produces a matrix of rank, one smaller than the previous matrix, whose determinant is not equal to that previous matrix. This matrix finally becomes a 1 x 1 matrix whose value is the determinant of the original matrix. The algorithm is described as follows: DET: PROC; / * INVENTION METHOD * / DEFINE M(N,N) MATRIX N DIMENSION OF M MI, MJ, QL VARIABLES QL = 1; DO I = 1 TO N-1; MI = M(I,I); DO J = I+1 TO N; MJ = M(J,I); DO K = I+1 TO N; M(J,K) = (M(J,K) * MI - M(I,K) * MJ) / QL; END; END; QL = M(I,I); END; ANSWER = M(I,I); END DET;