Browse Prior Art Database

Exact Evaluation of Determinants Via Permutation Arrays

IP.com Disclosure Number: IPCOM000085004D
Original Publication Date: 1976-Feb-01
Included in the Prior Art Database: 2005-Mar-02
Document File: 7 page(s) / 96K

Publishing Venue

IBM

Related People

Stacy, EW: AUTHOR

Abstract

The algorithm which is described enables exact evaluation of mathematical determinants in a highly efficient manner. It is considerably faster than most previously known methods for exact evaluations. A significant feature of the method is an algorithm for obtaining the complete set of N! permutations, by generating only (N!)/2 permutations in an array whose structure facilitates determinant evaluation.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 23% of the total text.

Page 1 of 7

Exact Evaluation of Determinants Via Permutation Arrays

The algorithm which is described enables exact evaluation of mathematical determinants in a highly efficient manner. It is considerably faster than most previously known methods for exact evaluations. A significant feature of the method is an algorithm for obtaining the complete set of N! permutations, by generating only (N!)/2 permutations in an array whose structure facilitates determinant evaluation.

A variety of techniques are known for calculating the determinant for any square matrix of numbers. Whenever the matrix is large, it is usual to employ techniques which achieve approximate results, while effecting significant reductions in the total number of arithmetic operations which yield the final result. The shorter methods entail numerous divisions as well as multiplications and additions. Thereby. the likelihood of encountering repeating decimals and corresponding rounding errors is great. Such errors are not always tolerable.

Some problems involve determinants in such a way as to make knowledge of exact values essential. For example, the inverse of a matrix does not exist if the determinant for the matrix is exactly zero valued; and no degree of approximation can be useful in that situation. In such cases where exact answers are required, the algorithm described herein provides a substantial improvement in speed and efficiency.

Convenience of exposition is served by simple notation. Toward that end, a general matrix will be written herein in the following manner: A(1)A(2)A(3)

B(1)B(2)B(3)

C(1)C(2)C(3), without the customary parentheses.

Alphabetic characters in their normal order are used to denote rows. Integers are used as subscripts for denoting columns. This later convention provides an easy way to write various products which occur in the expansion of a determinant, and to count the number of left to right inversions in the order of the subscripts which define the products. Thus, A(4)B(1)C(2)D(3) presents three inversions of subscript order and the product should be associated with (-1)/3/ as its sign. In other words, this particular product should be given a negative sign.

For other products, the sign is determined by (-1)/n/, where "n" is the number of subscript inversions reading from left to right.

That number will be called the inversion number. For any k by k matrix, the maximum inversion number which can be presented by subscripts for a product is k(k-1)/2.

In the following discussion, it will be necessary to display matrices whose elements are chosen from the first nine positive integers. Spaces between columns in such displays may be deleted without confusion. For example, the following are two expressions for the same matrix: 1 2 3 123

1

Page 2 of 7

3 1 2 and 312

2 3 1 231.

Also, notation from the APL computer language will be used herein. A matrix P, for example, may be defined by: 123

P <-- 312

231.

Similarly, the expressions 1,P and P+1, respectively...