SATN-42
Determinant-Like Functions
Produced by the Dot Operator

K.E. Iverson
 

Abstract

The operator denoted by the dot has been extended to provide a monadic function (as in -.×m ) as well as the established dyadic inner product function (as in n+.×m ). The case -.×m (on a square matrix m ) is the familiar determinant function, and the general case f.g m is defined analogously as reduction by f over a set of !n←1↑⍴m “products” produced by reduction by g over !n distinct sets of n elements chosen one from each row and column of the argument. The extension to non-square arguments allows the use of -.× on an n+1 by n argument to compute the signed volume of the simplex it represents in n-space.

Introduction

The determinant is an important function defined on square matrices — applied to a matrix of coefficients of a set of linear equations it determines the character of the solutions, applied to the matrix of partial derivatives of a vector function on vector arguments it yields the volume transformation effected by the function, and applied to the matrix s,1 it yields !1↓⍴s times the signed value of the simplex of n←1↑⍴s vertices in (n-1)-space.

The determinant of a square matrix m is defined as the alternating sum (i.e. reduction by - ) of the !n←1↑⍴m products over n elements chosen (in each of the !n possible ways) one from each row and column. Analogous calculations in which other function pairs are substituted for - and × lead to other useful functions; examples include the pairs ⌈⌊ , ∧∨ , and +× , the last (called the permanent) being useful in combinatorics [1].

Because of the utility of cases other than the pair -× , we introduce a dyadic operator instead of a specific determinant function; because the result of the dot operator is defined only for the dyadic case of the resulting function (as in a+.×b and a^.=b), we adopt its monadic case for the “determinant” operator. Thus -.×b is the determinant of b , and +.×b is the permanent.
 

Formal Definition of f.g b

The function dop in workspace 1 satn42 models the determinant operator. For example, if m is a magic square of order 3, then:

      m
6 7 2
1 5 9
8 3 4

      -.×m                       '-×'dop m
360                        360

      +.×m                       '+×'dop m
900                        900

      ∨.^m                       '∨^'dop m
2                          2

dop and its supporting functions are displayed below; the subsequent comments may be helpful in grasping their details. Origin 1 is assumed throughout:

dop⋄(1↑⍺)cr⍎(¯1↑⍺),'/x',0⍴x←all ⍵

all⋄((⍳k),k←⍴⍴y)⍉⍵[y←perm⍴⍵;]

perm⋄(s,⍴s)⍴⍉mf 1+s⊤¯1+⍳×/s←(⌊/⍵)↑⌽⍳1↑⍵

mf⋄0≠1↑⍴⍵⋄⍵⋄⍵[,1;],[1]x+⍵[(1↑⍴x)⍴1;]≤x←mf 1 0↓⍵

cr⋄0≠⍴⍴x←⍵⋄⍵⋄⍺cr⍎⍺,'/x'

The diagonal section 1 1⍉m contains one element from each row and column, and is therefore one of the sets of elements over which the reduction g/ is to be applied in evaluating f.g m . All such sets can be obtained from the expression 1 1⍉m[p;] , where p is one of the !n permutations of order n←1↑⍴m . Consequently, if ap is an array of all permutations of order n , then a suitable section of m[ap;] provides all the required sets of elements, and g/ over this section produces an array of all “products” to which reduction by f is to be applied. For example:

      ⎕←ap←perm ⍴m               ⎕←r←all m
1 2 3                      6 5 4
     
1 3 2                      6 3 9
     
     
2 1 3                      1 7 4
     
2 3 1                      1 3 2
     
     
3 1 2                      8 7 9
     
3 2 1                      8 5 2

      ⍴ap
3 2 1 3

      ⎕←pr←×/r                   -/pr
120                        120 162
162                         28   6
                           504  80
 28                              -/-/pr
  6                        ¯42 22 424
                                 -/-/-/pr
504                        360
 80

The permutations ap are in lexical order, but the outer shape of the array is ⌽⍳n rather than !n , and the shape of the array of products is therefore ⌽⍳n as well. Reduction by f is therefore carried out over a succession of axes (beginning with the last) as provided by the recursively-defined function cr . The reader may wish to verify that the pattern of reduction provided by this argument of rank n ensures that the function f applies over the products in an order such that the permutations which produced them alternate in parity. This ordering is significant for any non-associative function f ; for the case -.× it ensures agreement with the established definition of the determinant.
 

Non-Square Arguments

Except for one important case, the extension of the determinant functions to non-square arguments may not greatly increase their utility. However, the extension is straightforward; if >/⍴m , then ×/s←(1↓⍴m)↑⌽⍳1↑⍴m distinct sets of 1↓⍴m elements can be selected without repetition of either column or row, and these are arranged in lexical order in an array of shape s . For example:

      ⎕←m←?4 2⍴9
6 4
5 5
4 3
1 4

      ⎕←ap←perm ⍴m               ⎕←r←all m
1 2                        6 5
1 3                        6 3
1 4                        6 4

2 1                        5 4
2 3                        5 3
2 4                        5 4

3 1                        4 4
3 2                        4 5
3 4                        4 4

4 1                        1 4
4 2                        1 5
4 3                        1 3

      ⎕←pr←×/r
30 18 24
20 15 20
16 20 16
 4  5  3
      -/-/r
0 0 1 ¯1
      -/-/pr
21
      -.×m
21

For a wide matrix m , the result of f.g m is equivalent to f.g (⌊\⍴m)↑m .

The case of -.× applied to an n+1 by n matrix is of special interest because it is equivalent to -.×m,1 , and can therefore be used to compute the volume of the simplex defined by m without explicit catenation of a final column of ones.
 

Evaluation Methods

Because of the special properties of the ordinary determinant, the function -.× on a square matrix is treated specially and is evaluated by the process used in matrix inversion; the time taken therefore varies as the cube of the order of the matrix.

All other cases are treated by explicit evaluation of each of the ÷/!|-\⍴m sets of ¯1↑⍴m elements; the time therefore varies as the product of the foregoing quantities.

Although the model shows the computation of an aray a of “products” of the form g/v followed by repeated reductions f/…f/a , the processes are merged so that the reductions are effected as early as possible. Consequently the number of intermediate results recorded in the reductions does not exceed ⍴⍴a . The scheme can be illustrated by evaluating -/-/a for a matrix a , beginning at the right of the last row, keeping the result of its reduction while reducing the penultimate row, and then applying reduction (the one applied to the reduction of -/a ) to these two results before proceeding with the reduction of another row.
 

Comments on Uses of f.g m

Applications of the ordinary determinant ( -.× ) on square matrices will not be discussed except to remark that it may be used as a test for invertibility before applying the function ⌹ .

If a , b , and c are two-element vectors, then -.×m←3 2⍴a,b,c yields twice the signed area of the triangle with vertices a , b , and c , signed because the sign of the result depends on the order of the vertices, positive if they are in counterclockwise order, and negative if in clockwise order. For example, if a←1 1 and b←1 0 and c←0 1 then:

      -.×3 2⍴a,b,c
¯1
      -.×3 2⍴b,a,c
1

Questions concerning the position of point a in relation to the line bc are more easily posed and answered in terms of the ordering of the points (i.e. in terms of the signed area) than in terms such as “above bc” (or should it be “left of bc” if bc is nearly vertical), or “a lies on the line bc” (for example, does it lie on the line if b and c are coincident?).

The signed result of -.× is significant in higher dimensions as well; if a , b , c , and d are points in three-space (in a dextral coordinate system), then -.× 4 3⍴a,b,c,d gives (!3 times) the signed volume of the tetrahedron, the results being zero if the points are coplanar, and positive if the points b , c , and d are in counterclockwise order when viewed from a . For example:

      a←1 1 1
      b←1 0 0
      c←0 1 0
      d←0 0 1
   
      -.×4 3⍴a,b,c,d
2
      -.×4 3⍴a,c,b,d
¯2

We will illustrate the use of functions other than - and × in the context of the so-called assignment problem: one of n persons (or machines) is to be assigned to each one of n tasks in some optimal way, the cost associated with assigning person i to task j being given by element m[i;j] of the square matrix m .

If we wish to minimize the sum of the costs in the assignment, then the optimal value is given by ⌊.+m , since the summation (+/) is applied to each of the !1↑⍴m possible assignments, and the minimum (⌊) is applied over them. Other useful function pairs in assignment type problems include ⌈+ , ⌊× , ⌈× , ⌊⌈ , and ⌈⌊ .

A square boolean matrix b is said to be a Latin square if it contains exactly 1↑⍴b ones, with one in each row and one in each column; one boolean matrix c is said to cover another, d , if ∧/,c≥d . The expression ∨.∧c yields 1 if c covers a Latin square, and the expression +.∧c tells how many distinct Latin squares are covered by c .
 

Acknowledgements

The system programming for this extension to the APL system was done by D.B. Allen. I am grateful to Mr. Allen and to Mr. E.E. McDonnell for comments on a draft of this paper.
 

References

Errata